Producer-Consumer Problem

The producer–consumer problem (also called the bounded-buffer problem) is the classic exercise that combines a mutex and semaphores. Producers put items into a fixed-size buffer, consumers take them out, and you must make them wait at the right times without corrupting the buffer. The same pattern sits behind job queues, logging pipelines and message brokers.

The setup#

One or more producers fill a buffer with five slots, and one or more consumers drain it.

A producer feeds a five-slot buffer holding three items while a consumer drains it; an empty semaphore counts free slots, a full semaphore counts filled slots, and a mutex guards the buffer

Three things can go wrong:

Buffer full: the producer must wait.
Buffer empty: the consumer must wait.
Simultaneous access: producer and consumer editing the buffer at once corrupts it.

Each problem gets its own primitive:

Problem	Tool	Initial value
Buffer full → track free slots	`empty` semaphore	buffer size (5)
Buffer empty → track filled slots	`full` semaphore	0
Race on the buffer → one editor at a time	`mutex`	unlocked

The solution#

Each side waits on one semaphore, edits the buffer under the mutex, then signals the other semaphore:

Step	Producer	Consumer
1	`empty.acquire()`: is there space?	`full.acquire()`: is there data?
2	`mutex.lock()`	`mutex.lock()`
3	Add item	Remove item
4	`mutex.unlock()`	`mutex.unlock()`
5	`full.release()`: data available	`empty.release()`: space available

As runnable Python:

import threading
from collections import deque

SIZE = 5
buffer = deque()
mutex = threading.Lock()
empty = threading.Semaphore(SIZE)   # free slots
full = threading.Semaphore(0)       # filled slots

def produce(item):
    empty.acquire()                 # wait for space BEFORE taking the lock
    with mutex:
        buffer.append(item)
    full.release()                  # wake a consumer

def consume():
    full.acquire()                  # wait for data BEFORE taking the lock
    with mutex:
        item = buffer.popleft()
    empty.release()                 # wake a producer
    return item

In real code you would usually reach for a ready-made thread-safe bounded queue (queue.Queue(maxsize=5) in Python), which implements exactly this.

Tracing it#

Follow the counters through three situations. Each row is one step.

Normal flow#

Start with buffer = [], empty = 5, full = 0.

Step	Action	Buffer	empty	full
1. Producer	`empty.acquire()`, lock, add item1, unlock, `full.release()`	[item1]	4	1
2. Consumer	`full.acquire()`, lock, take item1, unlock, `empty.release()`	[]	5	0

Buffer full#

Start with buffer = [A, B, C, D, E], empty = 0, full = 5.

Step	Action	Buffer	empty	full
1. Producer	`empty.acquire()`: count is 0, blocked	[A, B, C, D, E]	0	5
2. Consumer	`full.acquire()`, lock, take A, unlock, `empty.release()`; the producer wakes	[B, C, D, E]	1	4
3. Producer	Proceeds (empty back to 0), lock, add F, unlock, `full.release()`	[B, C, D, E, F]	0	5

Buffer empty#

Start with buffer = [], empty = 5, full = 0.

Step	Action	Buffer	empty	full
1. Consumer	`full.acquire()`: count is 0, blocked	[]	5	0
2. Producer	`empty.acquire()`, lock, add item1, unlock, `full.release()`; the consumer wakes	[item1]	4	1
3. Consumer	Proceeds (full back to 0), lock, take item1, unlock, `empty.release()`	[]	5	0

Why the semaphore must come before the mutex#

The order of the first two calls matters.

Correct: call empty.acquire() first. It waits for space and may block, but while holding nothing. Then call mutex.lock() to protect the buffer.
Wrong: call mutex.lock() first, then empty.acquire(). If the buffer is full, the producer blocks while holding the mutex.

In the wrong order, the failure unfolds like this:

The producer holds the mutex and blocks on empty.acquire() because the buffer is full.
The consumer needs the mutex to remove an item.
It can't get it, so it can never call empty.release().
Neither thread can move: deadlock.

Locking the mutex and then blocking on the semaphore is hold and wait, one of the four deadlock conditions. Always wait on the counting semaphore first, while holding nothing.

Three jobs, three primitives#

Each primitive answers one question:

Question	Primitive	Effect
Can I add?	`empty` semaphore	Blocks the producer when full
Can I take?	`full` semaphore	Blocks the consumer when empty
Is it safe?	mutex	One thread edits the buffer at a time

The two semaphores coordinate (when to wait, when to go); the mutex protects the data.

In practice#

The same pattern scales up to distributed systems. A producer service writes messages to a queue (such as Amazon SQS, RabbitMQ or Kafka), and a fleet of consumers pulls and processes them. The queue service handles the synchronization, and a bounded queue or consumer concurrency limit plays the role of the empty and full counters.

Key takeaways#

Use empty (starts at buffer size), full (starts at 0) and a mutex around the buffer.
Producers wait on empty and signal full; consumers wait on full and signal empty.
Acquire the semaphore before the mutex; the reverse order deadlocks when the buffer is full or empty.
Semaphores coordinate, the mutex protects; in real code, prefer a built-in blocking queue.