CS444 Handout: Semaphores, Producer-Consumer Problem (AKA bounded buffer)

Semaphores were invented in 1965 by Dijkstra. A semaphore is a system object with some sort of identifier, here “sem”.  The sem object has a count associated with it.  The two important operations on sem (after its creation) are (Tanenbaum, pg. 128, but underlined part here is not there but should be):

• down(sem):  if sem’s count is positive, decrement it and return, otherwise, the count is zero, put this process to sleep (blocked) and later have it decrement the count when it wakes up.  POSIX semaphores: sem_wait(…)
• up(sem):  increment sem’s count, and wake up a waiter (if any, and who then decrements the count back to 0).  POSIX semaphores: sem_post(…). 

To make a real system, we also need to be able to create a semaphore with a certain initial count: sem = createsem(initcount).  POSIX semaphores: sem_init(…)

Tanenbaum, pg. 130: This program assumes semaphore creation somehow automatically happens, but in real life we need to do a system call to create a semaphore. Here is that program rewritten to use POSIX semaphores. It is still incomplete because of the thread creation calls, as well as the various unimplemented functions (produce_item, etc.).

Figure 2-28 pg. 130

Actual C program using POSIX semaphores, i.e., standard UNIX/Linux semaphores

/* needs various headers, including <semaphore.h> */

sem_t mutex, empty, full;  /* struct type sem_t is defined in header */

int main()

{

       if (sem_init(&mutex, /*process-local*/ 0, /*init count*/ 1) < 0) 

         perror("Failed to create semaphore 1");   

          return 1;

        }

       if (sem_init(&empty, /*process-local*/ 0, /*init count*/ N) < 0)

         perror("Failed to create semaphore 2");

          return 1;

        }

       if (sem_init(&full, /*process-local*/ 0, /*init count*/ 0) < 0)

         perror("Failed to create semaphore 3");

          return 1;

        }

       thread_create(producer, ...);    

thread_create(consumer, ...); 

       getchar();              /* block main thread */

/* here, could bring down threads and destroy semaphores, but exit will do it for us */

return 0;

}

/* producer() and consumer() are close to Tanenbaum, pg. 130 */

/* Note: each system call should have its return value tested as show above for   sem_init */

void producer()

{

       int item;

       while (TRUE) {

          item = produce_item();

          sem_wait(&empty);        /* down: block for/claim empty spot for new item */

          sem_wait(&mutex);

          insert_item(item);       /* insert item, protected by mutex */

          sem_post(&mutex);

          sem_post(&full);         /* up: signal filled-in spot */

       }

}

void consumer()

{

       int item;

       while (TRUE) {

          sem_wait(&full);         /* down: block for/claim filled spot in buffer */

          sem_wait(&mutex);

          item = remove_item();    /* remove item, protected by mutex */

          sem_post(&mutex);

          sem_post(&empty);        /* up: signal empty spot */

          consume_item(item);

       }

}