The producer-consumer (bounded buffer) problem

Difficulty: Intermediate

Question

Explain the bounded-buffer producer-consumer problem and solve it using semaphores. Why are three semaphores needed?

Answer

The producer-consumer problem is the poster child of synchronization, and it appears in real systems everywhere: a web server's request queue, a logging pipeline, a video decoder feeding a renderer, and even a Unix pipe. So learn it as a pattern, not just as a textbook exercise. Picture a sushi conveyor belt with limited plates. The chef (producer) can only put a plate on the belt if there is an empty slot; the customer (consumer) can only take a plate if one is available. And two people should never fiddle with the same slot at the same moment.

Formally, a producer generates items and places them into a shared buffer of fixed size N. A consumer removes items from the buffer. We need to guarantee three things. First, the producer must wait when the buffer is full. Second, the consumer must wait when the buffer is empty. Third, access to the buffer's internal data (indices, counters) must be mutually exclusive, or a race would corrupt it.

That gives us exactly three semaphores. The first is empty, a counting semaphore initialized to N, counting free slots. The second is full, a counting semaphore initialized to 0, counting occupied slots. The third is mutex, a binary semaphore initialized to 1, protecting the buffer manipulation. The producer does the following in a loop: produce an item, wait(empty), wait(mutex), insert the item, signal(mutex), signal(full). The consumer does: wait(full), wait(mutex), remove the item, signal(mutex), signal(empty), consume the item.

Now the details that interviewers probe. Why is the order wait(empty) before wait(mutex) important? If the producer took the mutex first and then blocked on a full buffer, the consumer would never be able to get the mutex to remove an item, and the system would deadlock. Always acquire the counting (resource) semaphore first, and the mutex second, and release in the reverse order. Why do we need both empty and full rather than a single counter? Because two different conditions need blocking, one for each side, and each side is woken by the other side's signal. Why do we need the mutex if the semaphores already synchronize? Because empty and full only control how many items exist, not who is touching the buffer. With multiple producers or consumers, two of them could pass the semaphores and write to the same slot simultaneously. With exactly one producer and one consumer using a circular buffer with separate in and out indices, the mutex can be dropped.

In modern code you would rarely hand-roll this. Java provides BlockingQueue, Python has queue.Queue, and Go uses buffered channels, all implementing this pattern with locks and condition variables. The condition-variable version uses a mutex plus two conditions, notFull and notEmpty, where waiters must re-check their condition in a while loop to handle spurious wakeups.

Variations include an unbounded buffer, where only the consumer ever waits and the empty semaphore disappears, and multiple producers and consumers, which is exactly why the mutex matters. You may be asked how to shut the system down cleanly: the usual trick is a poison-pill sentinel item that tells consumers to stop.

Code examples

Bounded buffer with three synchronization primitives (Python)

import threading
from collections import deque

N = 5
buf = deque()
empty = threading.Semaphore(N)     # free slots
full = threading.Semaphore(0)      # filled slots
mutex = threading.Lock()           # protects buf

def producer(pid):
    for i in range(5):
        item = f"P{pid}-item{i}"
        empty.acquire()            # wait(empty) first
        with mutex:                # then the mutex
            buf.append(item)
            print("produced", item)
        full.release()             # signal(full)

def consumer(cid, count):
    for _ in range(count):
        full.acquire()             # wait(full)
        with mutex:
            item = buf.popleft()
            print(f"  consumer {cid} consumed", item)
        empty.release()            # signal(empty)

ts = [threading.Thread(target=producer, args=(1,)),
      threading.Thread(target=producer, args=(2,)),
      threading.Thread(target=consumer, args=(1, 5)),
      threading.Thread(target=consumer, args=(2, 5))]
for t in ts: t.start()
for t in ts: t.join()

Interleaving changes between runs, but the invariants hold: never more than N items, and no consumer removes from an empty buffer.

Key points

• Three semaphores: empty (N), full (0), mutex (1).
• Acquire the resource semaphore before the mutex, or you can deadlock.
• Single producer and consumer with a circular buffer needs no mutex.
• Condition variables need a while loop, not an if, to recheck the predicate.
• BlockingQueue in Java and queue.Queue in Python implement this pattern.

Concepts covered

producer-consumer, bounded buffer, semaphores, synchronization, condition variable