Producer-consumer problem

In computer science, the producer-consumer problem (also known as the bounded-buffer problem) is a classical example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer. The producer's job is to generate a piece of 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 go to sleep if the buffer is full. The next time the consumer removes an item from the buffer, it wakes up the producer who starts to fill the buffer again. In the same way the consumer goes to sleep if it finds the buffer to be 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.

Implementations

Inadequate implementation

This solution has a race condition. To solve the problem, a careless 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. itemCount is the number of items in the buffer.

int itemCount 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) } }

The problem with this solution is that it contains a race condition that can lead into a deadlock. Consider the following scenario:
# The consumer has just read the variable itemCount, noticed it's zero and is just about to move inside the if-block.
# Just before calling sleep, the consumer is interrupted and the producer is resumed.
# The producer creates an item, puts it into the buffer, and increases itemCount.
# Because the buffer was empty prior to the last addition, the producer tries to wake up the consumer.
# Unfortunately the consumer wasn't yet sleeping, and the wakeup call is lost. The next time the consumer runs, it goes to sleep and will never be awakened.
# The producer will loop until the buffer is full, after which it will also go to sleep.Since both processes will sleep forever, we have run into a deadlock. This solution therefore is unsatisfactory.

An alternative analysis is that if the programming language does not define the semantics of concurrent accesses to shared variables (in this case itemCount) without use of synchronization, then the solution is unsatisfactory for that reason, without needing to explicitly demonstrate a race condition.

Using semaphores

Semaphores solve the problem of lost wakeup calls. In the solution below we use two semaphores, fillCount and emptyCount, to solve the problem. fillCount is incremented and emptyCount decremented when a new item has been put into the buffer. If the producer tries to decrement emptyCount while its value is zero, the producer is put to sleep. The next time an item is consumed, emptyCount is incremented and the producer wakes up. The consumer works analogously.

semaphore fillCount = 0 semaphore emptyCount = BUFFER_SIZE procedure producer() { while (true) { item = produceItem() down(emptyCount) putItemIntoBuffer(item) up(fillCount) } } procedure consumer() { while (true) { down(fillCount) item = removeItemFromBuffer() up(emptyCount) consumeItem(item) } }

The solution above works fine when there is only one producer and consumer. Unfortunately, with multiple producers or consumers this solution contains a serious race condition that could result in two or more processes reading or writing into the same slot at the same time. To understand how this is possible, imagine how the procedure putItemIntoBuffer() can be implemented. It could contain two actions, one determining the next available slot and the other writing into it. If the procedure can be executed concurrently by multiple producers, then the following scenario is possible:
# Two producers decrement emptyCount
# One of the producers determines the next empty slot in the buffer
# Second producer determines the next empty slot and gets the same result as the first producer
# Both producers write into the same slot

To overcome this problem, we need a way to make sure that only one producer is executing putItemIntoBuffer() at a time. In other words we need a way to execute a critical section with mutual exclusion. To accomplish this we use a binary semaphore called mutex. Since the value of a binary semaphore can be only either one or zero, only one process can be executing between down(mutex) and up(mutex). The solution for multiple producers and consumers is shown below.

semaphore mutex = 1 semaphore fillCount = 0 semaphore emptyCount = BUFFER_SIZE procedure producer() { while (true) { item = produceItem() down(emptyCount) down(mutex) putItemIntoBuffer(item) up(mutex) up(fillCount) } } procedure consumer() { while (true) { down(fillCount) down(mutex) item = removeItemFromBuffer() up(mutex) up(emptyCount) consumeItem(item) } }

Notice that the order in which different semaphores are incremented or decremented is essential: changing the order might result in a deadlock.

Using monitors

The following pseudo code shows a solution to the producer-consumer problem using monitors. Since mutual exclusion is implicit with monitors, no extra effort is necessary to protect critical section. In other words, the solution shown below works with any number of producers and consumers without any modifications. It is also noteworthy that using monitors makes race conditions much less likely than when using semaphores.

monitor ProducerConsumer { int itemCount condition full condition empty procedure add(item) { while (itemCount = BUFFER_SIZE) { wait(full) } putItemIntoBuffer(item) itemCount = itemCount + 1 if (itemCount = 1) { notify(empty) } } procedure remove() { while (itemCount = 0) { wait(empty) } item = removeItemFromBuffer() itemCount = itemCount - 1 if (itemCount = BUFFER_SIZE - 1) { notify(full) } return item; } } procedure producer() { while (true) { item = produceItem() ProducerConsumer.add(item) } } procedure consumer() { while (true) { item = ProducerConsumer.remove() consumeItem(item) } }

Using Composable Memory Transactions

Composable Memory Transactions is a special form of Software Transactional Memory as proposed in 2005 by Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Duilio Protti implemented the library libCMT in C, the following link is a source code example.

[http://sourceforge.krugle.com/kse/files/svn/svn.sourceforge.net/libcmt/libcmt/tests/classic/prod-cons.c#2 Producers-Consumers example with libCMT]

References

* "Modern Operating Systems (2nd Edition)" by Andrew S. Tanenbaum (ISBN 0-13-092641-8)
* "Foundations of Multithreaded, Parallel, and Distributed Programming" by Gregory R. Andrews (ISBN 0-201-35752-6)

See also

* Sleeping barber problem
* Dining philosophers problem
* Cigarette smokers problem
* Readers-writers problem