According to Wikipeida the Producer Consumer Problem is defined as:
In computing, the producer–consumer problem (also known as the bounded-buffer 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.
In essence, the producer consumer problem occurs in multithreaded processes when there is a limited amount of memory (or memory structure) and therefore there is a fixed amount of space so we must allocate it appropriately. In the following example I use a C++11 Condition Variable (#include condition_variable), which I find very useful as well as a C++11 mutex.
Example
Rather than trying to explain it further I will walk through a simple example.
Image you’re sitting in a busy restaurant waiting for some friends to arrive and you are watching the waiters/waitresses take food from the kitchen to tables. This is a classic example of the producer-consumer problem. There are limited numbers of waiters and meals constantly being produced. Meaning there is a bound on waiters (consumers) and an unlimited supply of meals produced by the chiefs (producers).
The easy way we can identify and reduce this problem to a producer-consumer problem is by identifying that we have a limited number of consumers and a potentially infinite number of items being produced. This means we have to use a semaphore in order to keep track of how many produced items are currently being handled by consumers.
If we build an outline of the algorithm it would look as follows:
- Create a semaphore to keep track of “produced” items
- Spawn producer and consumer threads
- Produce at will and keep track of how many are still in the queue
- Consumer threads continue to run until all “produced” items are “consumed”
- Join threads when complete
If we represented the above scenario in C++11 code (or view on github):
Output:
Order: 3 being taken care of with 0 meals also ready.
Order: 5 being taken care of with 0 meals also ready.
Order: 2 being taken care of with 1 meals also ready.
Order: 6 being taken care of with 0 meals also ready.
Order: 7 being taken care of with 2 meals also ready.
Order: 8 being taken care of with 2 meals also ready.
Order: 9 being taken care of with 2 meals also ready.
Order: 4 being taken care of with 2 meals also ready.
Order: 10 being taken care of with 1 meals also ready.
Order: 1 being taken care of with 0 meals also ready.
In the example above there clearly is a race, however this is not a race condition. In this case there are no errors due to the threads running out of order and thus there is no issue. All we are trying to achieve is getting the orders out as quickly as they are produced, to maximize throughput (not priority).
As an aside, it is not necessary to have as many producers as consumers (as the example above depicts), but you do have to wait to join all of the threads until everything is consumed.