Producer Consumer Problem

The producer-consumer problem which is also known by the term bounded buffer problem is a process synchronization problem. Process synchronization coordinates the execution of processes sharing common resources in such a way that there is no concurrent access to the shared resources to avoid race conditions.

In this context, we are going to discuss the producer-consumer problem which is one of the possible problems that occurs during process synchronization.

What is the Producer-Consumer Problem?

The producer-consumer problem is popularly termed as the bounded buffer problem. This synchronization problem talks about the two processes involved in process synchronization. Consider the first process as the producer process and the second process as the consumer process.

The producer-consumer process shares a buffer with a finite size. That is the reason why it is called the bounded buffer problem. The scenario is that the producer process produces an item and place this item into the shared buffer. The consumer process removes the produced item present in the buffer and consumes it.

The problem that occurs in the synchronization of these two processes are:

1. What if the producer process has produced a new item but the buffer is already full?
2. What if the consumer wants to consume an item from the buffer and the buffer is empty?

Well, the solution to the first problem where the buffer is full, could be that the producer process must go to sleep and should not be awakened until the consumer process consumes/removes one item from the buffer.

The solution to the second problem is that seeing buffer empty the consumer process must go to sleep and should not be awakened until the producer process put a new item into the buffer. For this, we need a shared count variable and the size of the buffer would be N i.e. the buffer can hold at max N number of items.

The producer process must execute the producer code below before placing the newly produced item into the buffer.

#define N 100 /* number of slots in the buffer */

int count = 0; /* number of items in the buffer */

void producer(void)

{

int item;

while (TRUE) { /* repeat forever */

item = produce item( ); /* generate next item */

if (count == N) sleep( ); /* if buffer is full, go to sleep */

insert item(item); /* put item in buffer */

count = count + 1; /* increment count of items in buffer */

if (count == 1) wakeup(consumer); /* was buffer empty? */

}

}

void consumer(void)

{

int item;

while (TRUE) { /* repeat forever */

if (count == 0) sleep( ); /* if buffer is empty, got to sleep */

item = remove item( ); /* take item out of buffer */

count = count -1; /* decrement count of items in buffer */

if (count == N - 1) wakeup(producer); /* was buffer full? */

consume item(item); /* print item */

}

}

So once the producer produces a new item it checks whether the count is equal to N & if it is, that means the buffer is full and the producer must go to sleep.

And if the count is not equal to N then add the newly produced item to the buffer and increment the count. Further check if the value of count is equal to 1 after increment it means earlier the buffer was empty and consumer process might have gone to sleep seeing buffer empty so it must be awakened.

Now let us discuss the consumer code. First, the consumer process must check whether the count value is equal to 0 if so it means the buffer is empty and has nothing to consume so the consumer process must go to sleep. If the count is not equal to 0 then it means the buffer has something to retrieve. So the consumer process would remove an item from the buffer and decrements the value of count as an item has been removed.

Further, it would check whether the count is equal to N-1 after retrieval of one item which means the buffer was full before the removal of the item and seeing this producer process must have gone to sleep. So the consumer process will awaken the producer process and thereby consume the removed item.

Race Condition

Case 1 Buffer is Empty

Though it seems to be so simple the race condition can still occur here. Consider a scenario that the buffer is empty and the consumer process has started execution. The consumer process has only read count is zero as the buffer is empty and suddenly the scheduler has stopped the execution of the consumer process and started executing the producer process.

Now producer process will produce an item and place it into the buffer and increment the count to 1. Further verifying that count is 1 now means that the buffer was just empty thereby awaken the consumer process.

But the consumer process has not gone to sleep so the awakening signal will be lost. Now when the consumer process starts to resume its execution it will test its count which it has read as 0 before and as the count is 0 it will go to sleep.

Further sooner or later the producer process will fill up the buffer and go to sleep. Thus both the process will sleep forever thereby rendering the race condition.

Case 2 Buffer is Full

Consider that the buffer is full and the producer process has just read out the count value i.e. N as the buffer is full. Now, suddenly the scheduler has stopped the execution of the producer process and start executing the consumer process.

Now as the buffer is full the consumer will remove an item from the buffer and decrement the count to N-1. Further verifying that count is N-1 i.e. the buffer was just full and the producer process must have gone to sleep.

So the consumer process would send a wakeup call to the producer process. But as the producer process is not logically sleeping the wakeup call will be lost. Now sooner or later the consumer process will remove all the items from the buffer and emptying the buffer it will go to sleep.

When the producer process will resume its execution will test its read value of count i.e. N and seeing buffer full the producer process will also go to sleep. Both the process will sleep forever thereby rendering the race condition.

Solution to Race Condition

Now if you observe carefully the entire mess got created as the signal to wake up the consumer process was lost otherwise it would have work fine. So, let us append a wakeup waiting bit. Now how does it works? Whenever the wakeup signal is sent to the process that is not in sleep the wakeup bit will set to 1. For example, consider case 1 where the buffer is empty.

1. The consumer process has read count as 0 and suddenly the scheduler has stopped the execution of the consumer process and start the execution of the producer process.
2. The producer process produced an item and increment the count to 1. Verifying count as 1 means the buffer was just empty thereby it send a wakeup call to the consumer process.
3. But as the consumer process is not logically in sleep this wakeup call would set the wakeup bit to 1.
4. Sooner or later the producer will fill the buffer and will go to sleep.
5. When the consumer process will resume its execution and as it has already read count as 0. It will verify the count to be 0 according to which it should go to sleep. But verifying count to be 0, it will also verify the wakeup bit to be 1 and won’t go to sleep thereby set wakeup bit 0 again.

This is how the wakeup act as a piggybank for wakeup calls. The processes must clear this wakeup bit in each iteration.

So, this was the producer-consumer problem or what we call the bounded buffer problem that might occur while the process synchronization. So whenever a new synchronization scheme is proposed it should be tested for this producer and consumer problem.