Semaphore (programming) - Example: Producer/consumer Problem

Example: Producer/consumer Problem

In the Producer-consumer problem, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size N and are subject to the following conditions:

• The consumer must wait for the producer to produce something if the queue is empty.
• The producer must wait for the consumer to consume something if the queue is full.

The semaphore solution to the Producer-consumer problem tracks the state of the queue with two semaphores: emptyCount, the number of empty places in the queue, and fullCount, the number of elements in the queue. To maintain integrity, emptyCount may be lower (but never higher) than the actual number of empty places in the queue, and fullCount may be lower (but never higher) than the actual number of items in the queue. Empty places and items represent two kinds of resources, empty boxes and full boxes, and the semaphores emptyCount and fullCount maintain control over these resources.

The binary semaphore useQueue ensures that the integrity of the state of the queue itself is not compromised, for example by two producers attempting to add items to an empty queue simultaneously, thereby corrupting its internal state. Alternatively a Mutex could be used in place of the binary semaphore.

The emptyCount is initially N, fullCount is initially 0, and useQueue is initially 1. The producer does the following repeatedly:

produce: P(emptyCount) P(useQueue) putItemIntoQueue(item) V(useQueue) V(fullCount)

The consumer does the following repeatedly:

consume: P(fullCount) P(useQueue) item ← getItemFromQueue V(useQueue) V(emptyCount)

Example.

1. A single consumer enters its critical section. Since fullCount is 0, the consumer blocks.
2. Several producers enter the producer critical section. No more than N producers may enter their critical section due to emptyCount constraining their entry.
3. The producers, one at a time, gain access to the queue through useQueue and deposit items in the queue.
4. Once the first producer exits its critical section, fullCount is incremented, allowing one consumer to enter its critical section.

Note that emptyCount may be much lower than the actual number of empty places in the queue, for example in the case where many producers have decremented it but are waiting their turn on useQueue before filling empty places. Note that emptyCount + fullCount ≤ N always holds, with equality if and only if no producers or consumers are executing their critical sections.