• Process:
  • An instance of a program execution
• Interprocess Communication:
  • Processes can exchange data in a variety of different ways
  • Processes often need to coordinate their activities

• Signals:
  • Can be used to notify a process that an event has occurred
• Files:
  • File locks can be used for limited kinds of coordination
• Pipes and FIFOs:
  • Are generally used to exchange information but their blocking and signaling behavior can be used for limited kinds of coordination

• Definition:
  • A semaphore is a kernel-maintained non-negative integer that can be operated on by processes using system calls
• Operations:
  • Setting the value
  • Increasing the value by 1
  • Blocking until the value can be decreased by 1

• In And Of Itself:
  • It has no specific meaning
• In Context:
  • Meaning is given to the semaphore based on the by the coordination protocol that uses it

• Flexibility:
  • Many synchronization protocols can be implemented using semaphores
• Simplicity:
  • It is relatively easy to prove the correctness of a synchronization protocol implemented using semaphores
• Portability:
  • Though the syntax may vary from system to system, the mechanism has been implemented on many systems (though we will only consider the POSIX implementation)

• Unnamed:
  • Reside in a region of shared memory
• Named:
  • Have an associated name and hence can easily be used by unrelated processes

#include <semaphore.h>

O_CREAT is used to create a semaphore. O_CREAT & O_EXCL is used to create a semaphore but fail if it already exists.

• Convention:
  • An initial slash followed by one or more non-slash characters
• Length:
  • Limited to NAME_MAX - 4 characters

• Type:
  • A pointer to a sem_t value
• An Important Restruction:
  • Operations should not be performed on a copy of the pointer (but a child can use the "inherited" references)

#include <semaphore.h>

Note that sem_close() does not delete the semaphore.

• Remember:
  • Named semaphores have kernel persistence
• Implications:
  • You MUST remember to unlink named semaphores
• Getting a List of Semaphores:
  • ls -l /dev/shm/sem.*

• Normal Flow:
  • Decrements the semaphore by 1 and returns immediately if the semaphore has a value greater than 0
  • Otherwise blocks until the value rises above 0 (at which point the semaphore is decremented and the function returns)
• If Interrupted by a Signal Handler:
  • The function fails with the error EINTR (regardless of whther the SA_RESTART flag was used when the signal handler was installed/established)

• sem_trywait()
  • If the value of the semaphore is 0 it fails immediately with the error EAGAIN
• sem_timedwait()
  • Allows for a limit on the amount of time the call will block

• Compiling:
  • As before
• Linking:
  • -pthread

unixexamples/semaphores/sequence.c

#include <fcntl.h>       // For O_CREAT
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int
main(void)
{
  pid_t  pid;
  sem_t *done;

  // Call open() in the original process so that we don't have to
  // worry about coordinating the call to open() 
  done = sem_open("/done", O_CREAT, O_RDWR, 0);
  
  pid = fork();
  switch(pid)
    {
    case -1:
      exit(1);

    case 0:  // Child
      write(STDOUT_FILENO, "Task 1\n", 7);
      sem_post(done);    // Increment the semaphore

      sem_close(done);
      exit(0);

    default: // Parent
      sem_wait(done);    // Try to decrement the semaphore
      write(STDOUT_FILENO, "Task 2\n", 7);

      sem_close(done);
      sem_unlink("/done");
      write(STDOUT_FILENO, "\nCheck: ls -l /dev/shm/sem.* \n", 30);
      exit(0);
    }
}
        

unixexamples/semaphores/taxs1.c

#include <fcntl.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include "../signals/tax_lib.h"

int
main(void)
{
  float rate, sales, tax;
  int   should, status;
  pid_t pid;
  sem_t *alert;

  rate  = 0.05;

  alert = sem_open("/alert", O_CREAT, O_RDWR, 0);

  pid   = fork();
  switch(pid)
    {
    case -1:
      exit(1);

    case 0:
      if (should_tax()) sem_post(alert); // Increment (i.e., alert the child)
      sem_close(alert);
      exit(0);

    default:
      sales = total_sales();

      // Reap the child (waiting for it to finish)
      wait(&status);

      // See whether the child "alerted". This function will return -1
      // if the semaphore can't be decremented immediately
      should = sem_trywait(alert);

      if (should == -1) tax = 0.0;            // The child didn't "alert"
      else              tax = sales * rate;   // The child "alert"

      printf("Tax: %5.2f\n", tax);

      sem_close(alert);
      sem_unlink("/alert");
      exit(0);
    }
}
        

Note: The "sender" transmits one bit of information (as in the similar examples that used signals and pipes) by either incrementing the semaphore or not.

• Recall:
  • In the discussion of signals we made the example more complicated by giving the child another (long) task that the parent did not have to wait for
  • We were unable to create a coordination protocol for this problem
• The Advantage of Semaphores:
  • The are more flexible than wait()

unixexamples/semaphores/taxs2.c

#include <fcntl.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include "../signals/tax_lib.h"

int
main(void)
{
  float rate, sales, tax;
  int   should, status;
  pid_t pid;
  sem_t *alert, *done;

  rate  = 0.05;

  alert = sem_open("/alert", O_CREAT, O_RDWR, 0);
  done  = sem_open("/done",  O_CREAT, O_RDWR, 0);
  
  pid   = fork();
  switch(pid)
    {
    case -1:
      exit(1);

    case 0:
      // "Alert" the child if necessary
      if (should_tax()) sem_post(alert);

      // In either case, indicate that the calculation is done
      sem_post(done);

      record_status(); // This takes a long time

      // Close the semaphores
      sem_close(alert);
      sem_close(done);
      exit(0);

    default:
      sales = total_sales();

      // Try to decrement the semaphore and wait (until the child is done)
      // if it isn't possible
      sem_wait(done); 
      
      // See whether the child "alerted". This function will return -1
      // if the semaphore can't be decremented immediately
      should = sem_trywait(alert);

      if (should == -1) tax = 0.0;            // The child didn't "alert"
      else              tax = sales * rate;   // The child "alert"

      printf("Tax: %5.2f\n", tax);


      // Reap the child (waiting for it to finish)
      wait(&status);

      // Close and unlink the semaphores
      sem_close(alert);
      sem_unlink("/alert");
      sem_close(done);
      sem_unlink("/done");
      
      exit(0);
    }
}
        

Note: One semaphore is being used to satisfy the sequencing constraint and another is being used for "alerting".

unixexamples/semaphores/mutex.c

#include <fcntl.h>       // For O_CREAT
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int
main(void)
{
  pid_t  pid;
  sem_t *conch;

  // The semaphore is named conch in a reference to "Lord of the Flies"
  // by William Golding (you had to have the conch to talk)
  conch = sem_open("/conch", O_CREAT, O_RDWR, 1); // The initial value is 1
  
  pid = fork();
  switch(pid)
    {
    case -1:
      exit(1);

    case 0:  // Child
      sem_wait(conch);  // Try to decrement the semaphore
      // Start of Critical Section
      write(STDOUT_FILENO, "Ralph \n", 7);
      // End of Critical Section
      sem_post(conch);  // Increment the semaphore

      sem_close(conch);
      exit(0);

    default: // Parent
      sem_wait(conch);  // Try to decrement the semaphore
      // Start of Critical Section
      write(STDOUT_FILENO, "Piggy \n", 7);
      // End of Critical Section
      sem_post(conch);  // Increment the semaphore

      sem_close(conch);
      sem_unlink("/conch");
      write(STDOUT_FILENO, "\nCheck: ls -l /dev/shm/sem.* \n", 30);
      exit(0);
    }
}
        

Note: The semaphore is initialized to 1 so that whichever process checks first can "enter".