Editing Semaphore (programming) (section)

===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: <code>emptyCount</code>, the number of empty places in the queue, and <code>fullCount</code>, the number of elements in the queue. To maintain integrity, <code>emptyCount</code> may be lower (but never higher) than the actual number of empty places in the queue, and <code>fullCount</code> 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 <code>emptyCount</code> and <code>fullCount</code> maintain control over these resources.

The binary semaphore <code>useQueue</code> 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 <code>emptyCount</code> is initially ''N'', <code>fullCount</code> is initially 0, and <code>useQueue</code> 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)

Below is a substantive example:
# A single consumer enters its critical section. Since <code>fullCount</code> is 0, the consumer blocks.
# Several producers enter the producer critical section. No more than ''N'' producers may enter their critical section due to <code>emptyCount</code> constraining their entry.
# The producers, one at a time, gain access to the queue through <code>useQueue</code> and deposit items in the queue.
# Once the first producer exits its critical section, <code>fullCount</code> is incremented, allowing one consumer to enter its critical section.

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