Question

Below is an attempt to solve the producer-consumer problem. Is this a correct solution? If yes, what is achieved and how? If not, what is the problem? Explain your answer in either case. (Note: Assume no syntax or compilation errors. You’re asked about the concurrency logic/correctness and the use of semaphores for this.)

#define N 100                 /* number of slots in the buffer */
semaphore mutex = 1;          /* controls access to critical */
semaphore empty = N;          /* counts empty buffer slots */
semaphore full = 0;          /* counts full buffer slots */

void producer(void)
{
   int item;
   while (TRUE){
              item = produce_item();   /* generate something to put in buffer */
              wait(&mutex);            /* enter critical region */
              wait(&empty);            /* decrement empty count */
              insert_item(item);       /* put new item in buffer */
              signal(&mutex);          /* leave critical region */
              signal(&full);           /* increment count of full slots
              }
}

void consumer(void)
{
int item;
while (TRUE){
              wait(&mutex);           /* enter critical region */
              wait(&full);            /* decrement full count */
              item = remove_item();   /* take item from buffer */
              signal(&empty);         /* increment count of empty slots */
              signal(&mutex);         /* leave critical region */
              consume_item(item);     /* do something with the item */
             }
}

Answer 1

This implementation can cause a deadlock. Here is how:
At time 0, empty is N, full is 0. Lets assume consumer is able to get the mutex and enter the critical section first - this is likely since the producer has to produce the first item. The sequence of events is:
wait (&mutex) // the consumer waits on the mutex and gets in to the critical section
wait (&full) // the consumer reaches here and is blocked since full is 0, the producer has not produced anything yet
...
After a little while, the producer finishes producing and executes:
wait (&mutex) // since the consumer is in the critical section, the producer has to wait.

This will result in both waiting indefinitely, causing a deadlock. The consumer is waiting for an item to consume and the producer is waiting to get into the critical section, neither can move forward.

In order to correct this, use of only one semaphone (the mutex) is adequate; update of shared variables (such as full and empty) is inside the critical section and therefore it is guaranteed that only one process will be accessing and / or updating these.