Producer Consumer problem.

Producer Consumer is the very basic problem of multithreading. If we are not familiar with the problem, let’s dive into it straightaway.

So as the wiki says (don’t read it all, I am going to explain) “Producer Consumer problem is a classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer’s job is to generate data, put it into the buffer, and start again. At the same time, the consumer is consuming the data (i.e., removing it from the buffer), one piece at a time. The problem is to make sure that the producer won’t try to add data into the buffer if it’s full and that the consumer won’t try to remove data from an empty buffer.”

Okay, I think it would be better to tell you by giving examples first.
Example. 1.
Assume you go to a party, you find plates over there, you pick up a plate and move towards the food buffet. but, what if you don’t find a plate, you will have to wait for a clean plate, maybe somebody from the hotel staff is washing the plates and cleaning those, when he completes cleaning, he will come to the plates counter and put the clean plates, and he apologies for the delay and ask you to take the plate and start enjoying the food. now notice that, when you were waiting, you could have asked (or maybe you did. :thumbs up) the waiter or the other hotel staff about the absence of plates at the plate counter. It may also happen that there were other people as well behind you, just waiting, like you were, (that is a kind of notification for the hotel utensils cleaner).

Example. 2.
You are sitting in an exam hall, you are writing your answers on a set of papers (you are not alone, others are also writing their exams obviously). There are flexible rules, like you can submit your paper as soon as you are done and there is the invigilator who will also evaluate and give marks right away. So when multiple students are done with their exams, they will put their copies in front of the evaluator in a sequence (may be a queue), he will then pickup one and evaluate one by one.

Example .3
There is a manufacturing firm which manufactures cars. so there is an assembly line. when a new car is built, the base chassis is first put on the line by a worker machine in a queue. and there are other worker machines which will pick that (or maybe in place), do their work and pass that to other worker machines till the car is built and prepared completely. in this example there is a chain of producers and consumers.

So, till now we have learnt the similarities between the real life examples and the producer consumer problem. Simply putting, there are producers (maybe one, or more) and consumers which operate on a shared work queue. In order to work appropriately, there are some conditions for both, Producers and consumers.

There are basically 2 conditions.
Condition 1.
What if the consumer comes and the queue is empty — If you have observed the first example, then the condition is right there. you entered the dinner party, you went to take a plate, plates were missing, right ?.
so, in that case, what you did was to notify the producer(hotel staff) and kept waiting, when the producer came with plates, he notified you as well saying that ‘Sir, plates are available, my apologies.’

So consumers have to wait if the queue is empty, and a notification must be sent to producers so that they should start producing items.

Condition 2.
What if the producer comes and the queue is full — If the producer was having clean plates and was ready to put those on the counter, he noticed that the counter is already full of clean plates. He will have to wait (it’s obvious, isn’t it). he will wait right there until a consumer (party guest) comes in and picks up a plate and notify that.

So a producer has to wait when the shared queue is full, and will also notify the consumers.
Bingo, you got that, those are also known as underflow and overflow respectively.

Also note that, no two producers or consumers should use the queue simultaneously, as it may lead to an inconsistent state.

Now you are probably thinking Hey buddy, we have been talking a lot about the problem, it is enough, we want solution. Okay then, we have discussed the solution already, how?. let’s see.

So we have Queue q, one producer P (for simplicity, taken one) and one consumer.

so, assume that producer P will call produce method, and Consumer C will call consume.

Queue q;
void produce(Item item){
acquireLockOnQueue(q){ // This is to block others
while(q.isFull()){
wait; // producer waiting if the queue is full.
}
q.put(item); // putting item
q.notifyAll(); // just to tell the waiting consumers that we produced
}
}

void consume(){
acquireLockOnQueue(q){
while(q.isEmpty()){
wait; // consumer waiting if the queue is empty.
}
Item item = q.get(item); // getting item
q.notifyAll(); // just to tell the waiting producers that we consumed.
}

This is a simple pseudo code illustrating the basic implementation of PC problem (Oh ho come on.. PC — — Producer consumer problem.)

For the implementation in programming languages, actually this blog is getting lengthier so, will come up with the solution shortly. stay tuned… :)