Producer Consumer Problem

Producer Consumer Problem

Problem Statement

Producer-Consumer Problem is also known as bounded buffer problem. The Producer-Consumer Problem is one of the classic problems of synchronization.

There is a buffer of N slots and each slot is capable of storing one unit of data.
There are two processes running, i.e. Producer and Consumer, which are currently operated in the buffer.

There are certain restrictions/conditions for both the producer and consumer process, so that data synchronization can be done without interruption. These are as follows:

  • The producer tries to insert data into an empty slot of the buffer.
  • The consumer tries to remove data from a filled slot in the buffer.
  • The producer must not insert data when the buffer is full.
  • The consumer must not remove data when the buffer is empty.
  • The producer and consumer should not insert and remove data simultaneously.

For solving the producer-consumer problem, three semaphores are used:

  • m(mutex) : A binary semaphore which is used to acquire and release the lock.
  • empty(), a counting semaphore whose initial value is the number of slots in the buffer, since initially, all slots are empty.
  • full, a counting semaphore, whose initial value is 0.

Implementation of producer code

void Producer(){
    do{
        //wait until empty > 0
        wait(Empty);
        wait(mutex);
        add()
        signal(mutex);
        signal(Full);
   }while(TRUE);
}

In the above code:

  • wait(empty): If the producer has to produce/insert something into the buffer, it needs to first check whether there are empty slots in the buffer. If true, the producer inserts data into the buffer and then decrements one empty slot.
  • wait(mutex): It is a binary semaphore, hence acquires the lock. This is shared among the producer and consumer. Hence, if the producer is acquiring the lock, the consumer cannot make any change in the buffer, until the lock is released.
  • add(): It adds the data to the buffer.
  • signal(mutex): It simply releases the lock acquired by the producer since the addition of data has been done in the buffer.
  • signal(full): This increments the full semaphore since one of the empty slots has now been filled.

Implementation of consumer code

void Producer(){
    do{
        //wait until empty > 0
        wait(full);
        wait(mutex);
        consume()
        signal(mutex);
        signal(empty);
   }while(TRUE);
}

In the above code:

  • wait(full): If the consumer has to remove data from the buffer, it needs to first check whether the buffer contains some item or not. If true, the consumer removes the data from the buffer and then decrements one full slot.
  • wait(mutex): It is a binary semaphore, hence acquires the lock. This is shared among the producer and consumer. Hence, if the consumer is acquiring the lock, the producer cannot make any change in the buffer, until the lock is released.
  • consumer(): It removes the data from the buffer.
  • signal(mutex): It simply releases the lock acquired by the producer since the addition of data has been done in the buffer.
  • signal(empty): This increments the empty semaphore since one of the empty slots have now been emptied.

FAQs

Can the consumer remove an item from the buffer if full() = 0?
No, if there are no items in the buffer, i.e. full semaphore  = 0, the consumer cannot remove any item.

Can the producer and consumer acquire the lock simultaneously?
No, either the producer or consumer can acquire the lock at a time. The operation wait(mutex) is used to acquire the lock.

Previous Post
XOR of Two Numbers

XOR of Two Numbers

Next Post
Lowest Common Ancestor

Lowest Common Ancestor

Total
0
Share