Semaphores

Solving the producer-consumer problem

We can model the state of the buffer with semaphores as follows:

const int BUFFER_CAPACITY = 100; // Say, for example.
Semaphore emptySlots = new Semaphore(BUFFER_CAPACITY);
Semaphore fullSlots = new Semaphore(0);
Semaphore mutualExclusion = new Semaphore(1);
Essentially the first semaphore counts the number of slots in the buffer which are empty. This will allow the producer to WAIT for an empty slot, and allow the consumer to SIGNAL the producer to produce more items. Initially the buffer is empty (we assume), so the emptySlots semaphore has its counter initially set to BUFFER_CAPACITY.

The second semaphore counts the number of slots in the buffer which contain an item. The producer can use it to SIGNAL the consumer, in case the consumer is WAITing on an item.

The third semaphore is simply to ensure that both processes do not attempt to update the buffer simultaneously. It is ensuring mutual exclusion while in the critical section of updating the shared buffer. As before.

the code for the producer looks like this

void producer(){
    for(/*ever*/;;){
        Object item = produceItem();
        wait(emptySlots); // Wait for buffer space.
        wait(mutualExclusion); // Enter critical section.
        buffer.insertItem(item);
         signal(mutualExclusion); // Leave critical section.
        signal(fullSlots); // Signal the consumer.
    }
}
and for the consumer:
void consumer(){
    for(/*ever*/;;){
        wait(fullSlots); // Wait for item in buffer.
        wait(mutualExclusion); // Enter critical section.
        Object item = buffer.removeItem();
        signal(mutualExclusion); // Leave critical section.
        signal(emptySlots); // Signal the producer.
        consumeItem(item);
    }
}
Note: order of 'wait's is important, otherwise we're asking for deadlock.

So some examples:

if the consumer is slow (or busy with other things), and the producer just keeps producing items, eventually it does so many WAITs on 'emptySlots' that the 'emptySlots' semaphore goes to 0, and the next time the producer does a WAIT, it is forced to wait til the consumer consumes an item, and does a SIGNAL.

Conversely, is the producer is too slow, and the consumer tries to consume too many items, eventually the 'fullSlots' semaphore goes to 0 and the consumer is forced to wait til the producer sticks something in the buffer and does a SIGNAL on the 'fullSlots' semaphore.

If the buffer is neither full nor empty, the producer should be allowed to enter items in the buffer, and the consumer should be allowed to remove them. Indeed this is the case, since both semaphores would be non-zero, the producer is able to WAIT on the 'emptySlots' semaphore without blocking, and the consumer is allowed to WAIT on the 'fullSlots' semaphore without blocking.

What about the other semaphore, 'mutualExclusion'? That's just there to enable both processes access to the shared data structure which is the buffer.  (Otherwise, one process might be attempting to, for example,  increment some 'numberOfItemsInBuffer' variable, while the other is attempting to decrement it, leading to race condition hell.)

So semaphores have two roles in this example:

last updated 1998