the 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.
The
solution for the producer is to either go to sleep or discard data if the
buffer is full. The next time the consumer removes an item from the buffer, it
notifies the producer, who starts to fill the buffer again. In the same way,
the consumer can go to sleep if it finds the buffer empty. The next time the
producer puts data into the buffer, it wakes up the sleeping consumer. The
solution can be reached by means of inter-process communication, typically
using semaphores. An inadequate solution could result in a deadlock where
both processes are waiting to be awakened. The problem can also be generalized
to have multiple producers and consumers.
Inadequate implementation
To solve the problem, some
programmer might come up with a solution shown below. In the solution two
library routines are used, sleep and wakeup. When
sleep is called, the caller is blocked until another process wakes it up by
using the wakeup routine. The global variable itemCount holds
the number of items in the buffer.
int itemCount = 0;
procedure producer()
{
while (true)
{
item = produceItem();
if (itemCount == BUFFER_SIZE)
{
sleep();
}
putItemIntoBuffer(item);
itemCount = itemCount + 1;
if (itemCount == 1)
{
wakeup(consumer);
}
}
}
procedure consumer()
{
while (true)
{
if (itemCount == 0)
{
sleep();
}
item = removeItemFromBuffer();
itemCount = itemCount - 1;
if (itemCount == BUFFER_SIZE - 1)
{
wakeup(producer);
}
consumeItem(item);
}
}