Producer-Consumer Problem

Introduction

The Producer-Consumer Problem is a classic bounded-buffer problem. A producer creates items, and a consumer removes those items from a shared buffer or queue.

The buffer has limited capacity, so it cannot hold infinite work. This creates two needs: safe access to the shared buffer and proper waiting when the buffer is full or empty.

Core Idea

The producer and consumer both use the same bounded buffer. The producer adds items such as tasks, messages, packets, or work units, while the consumer removes and processes them.

The basic rules are:

Buffer full: The producer must wait because no empty slot is available.
Buffer empty: The consumer must wait because no item is available.
Buffer update: Only one thread should modify the buffer structure at a time.

So the problem needs both coordination and mutual exclusion. Coordination handles full and empty states, while mutual exclusion protects the actual buffer update.

Producer-Consumer Core Idea

Real-System Examples

The producer-consumer pattern appears in many practical systems, not only in textbook examples.

Thread pool: Submitters add tasks, and worker threads remove tasks.
Web server: A request acceptor produces work, and worker threads consume it.
Logging system: Application threads produce log messages, and a writer thread consumes them.
Network system: A receiver produces packets, and processing threads consume them.

In each case, the queue separates the part that creates work from the part that processes work.

Semaphore Setup

A standard semaphore solution uses three synchronization values: empty, full, and mutex.

Semaphore	Initial Value	Purpose
`empty`	`N`	Counts empty slots in a buffer of capacity `N`
`full`	`0`	Counts filled slots available for consumers
`mutex`	`1`	Protects the actual buffer update

empty and full are counting semaphores. mutex is used as a binary semaphore here to protect the shared buffer structure.

The division is important: empty and full count slots, while mutex protects the queue operation.

Producer Flow

The producer must first reserve an empty slot. Then it can safely enter the protected buffer update.

wait(empty)
wait(mutex)

add item to buffer

signal(mutex)
signal(full)

The meaning is:

wait(empty): Reserve one empty slot.
wait(mutex): Enter the protected buffer update.
Add item: Put the produced item into the buffer.
signal(mutex): Release the buffer.
signal(full): Announce that one more filled slot exists.

If the buffer is full, empty is 0, so the producer waits before touching the buffer.

Consumer Flow

The consumer must first reserve a filled slot. Then it can safely remove an item from the buffer.

wait(full)
wait(mutex)

remove item from buffer

signal(mutex)
signal(empty)

The meaning is:

wait(full): Reserve one available item.
wait(mutex): Enter the protected buffer update.
Remove item: Take one item from the buffer.
signal(mutex): Release the buffer.
signal(empty): Announce that one more empty slot exists.

If the buffer is empty, full is 0, so the consumer waits until a producer adds an item.

Producer and Consumer Flow

Why Ordering Matters

The order is part of the solution. A producer waits for an empty slot before locking the buffer. A consumer waits for a filled slot before locking the buffer.

If a thread locks the buffer first and then waits for a slot, it may sleep while holding mutex. That can block the other side from updating the buffer and may cause a deadlock.

The rule is simple: wait on empty or full first, and hold mutex only during the actual buffer modification.

Condition Variable Version

The Producer-Consumer Problem can also be solved using condition variables. This version uses a mutex plus conditions that describe buffer state.

mutex: Protects the shared buffer state
not_full: Producers wait here when the buffer is full
not_empty: Consumers wait here when the buffer is empty

A producer waits while the buffer is full. A consumer waits while the buffer is empty. The checks should usually be inside while loops, because a waiting thread must recheck the condition after waking.

Semaphores are natural when the problem is slot counting. Condition variables are often clearer when the waiting condition is based on shared state.

Common Mistakes

Using only mutex: This protects the buffer but does not naturally handle full and empty waiting.
Waiting after locking mutex: A thread may sleep while blocking the other side from changing the buffer.
Holding mutex too long: The buffer should be locked only during the actual update.
Using if instead of while with condition variables: A woken thread should recheck the buffer condition.

A correct solution separates counting from protection. Slot semaphores coordinate progress, and mutex protects the shared queue.

Summary

The Producer-Consumer Problem is a bounded-buffer problem where producers add items and consumers remove them from a shared queue of capacity N.

The semaphore solution uses empty = N, full = 0, and mutex = 1. Producers follow wait(empty), wait(mutex), add, signal(mutex), signal(full), while consumers follow wait(full), wait(mutex), remove, signal(mutex), signal(empty).