We have already discussed about critical section problem and various ways to solve the critical section problem like Semaphores and Peterson Solution. Now, today we will discuss about Producer- Consumer Problem which is a very famous classical problem in process synchronisation. Then we will try to solve the Producer-Consumer Problem Using Semaphores. So, let's start, shall we?
Problem
The Producer produces certain an items and Consumer consumes an items.
We have a buffer storage present between producer and consumer with some definite size.
The Producer produces an item and places it in the buffer storage and consumer consumes by taking that item from buffer.
Now the problem is :-
- The producer shall produce an item when the buffer is not full. If the buffer is full then producer shall not place an item in it. There shall not be overflow of items in buffer.
- Same goes for consumer too that a consumer shall consume an item when buffer is not empty. The consumer shall not be allowed to consume when the buffer is empty. There shall not be underflow of items in buffer.
- The producer and consumer shall not access the buffer at the same time.
To solve this problem we use 3 semaphores S, E and F.
Semaphore S=1
Semaphore E=n
Semaphore F=0
Semaphore S is initialised to 1 because this semaphore makes sure that at a time either producer shall produce an item or consumer shall consume an item.
Semaphore E indicates number of empty slots in buffer storage. Initially, the buffer is empty so it is initialised to n.
Semaphore F indicates number of slots filled in buffer storage. Initially, the buffer has no full slots so it is 0.
Here 'n' indicates the size of buffer.
Now let's look at the code and dry run it:
void producer( ) void consumer( )
{ {
while(T) while(T)
{ {
produce( ) wait(F)
wait(E) wait(S)
wait(S) --1 take() --1
append( ) --2 signal(S) --2
signal(S) --3 signal(E) --3
signal(F) use()
} }
} }
Suppose size of buffer is 5.
1. Producer produces item by calling produce( ) and then call wait(E) because 1 slot is filled in buffer and remaining slots are 4. Next we have called wait(S) so value of S is decremented by 1 so S becomes 0 and now it won't append item. Next, we called signal(S) which increments S by1 so S becomes 1. At last we have called signal(F) so it increments F by 1 because one slot is filled and F becomes 1. So now we have 1 item in buffer now.
2. Suppose Producer produces another item by calling produce( ) and then call wait(E) because 1 more slot is filled in buffer and remaining slots are 3. Next we have called wait(S) so value of S is decremented by 1 so S becomes 0 and now it won't append item. Next, we called signal(S) which increments S by1 so S becomes 1. At last we have called signal(F) so it increments F by 1 because one slot is filled and F becomes 2 now. So now we have 2 item in buffer now.
3. Now let's consume an item. First wait(F) is called because when consumer consumes one Full slot is emptied so F will be decremented by 1 and now F has value 1. Next, we called wait(S) so S is decremented by 1 and S becomes 0 and append( ) will not be executed. Then signal(S) is called and S is incremented by 1 so S becomes 1 and an item is consumed from buffer. Next signal(E) and E is incremented by 1 because number of empty slots have been increased by 1.
4. So, basically we are decreasing E and increasing F whenever an item is produces and we increment E and decrement F whenever an item is consumed.
5. The lines 1,2,3 in the above code are there to ensure security so that at a time only either producer or consumer access the buffer.
6. Now, let's check for Underflow. We initialise S to 1, E to n and F to 0 again and buffer is also emptied.
7. So, when consumer is called the first condition is checked which is wait(F) so you have to decrement F but you cannot decrement F because it is already 0. So, that's how we check underflow.
8. Now, let's check for Overflow. The buffer is completely filled. Now , since buffer is full so value of E will be 0 and value of F will be 5.
9. So, when producer is called the first condition is checked which is wait(E) so you have to decrement E but you cannot decrement E because it is already 0. So, that's how we check overflow.