Skip to main content

Producer-Consumer / Bounded Buffer

What This Concept Is​

The producer-consumer problem coordinates two groups of threads around a finite shared queue:

  • Producers add items. They must block when the queue is full.
  • Consumers remove items. They must block when the queue is empty.

Correctness requires three invariants:

  • Safety. The number of items in the buffer is always in [0, N], and items are never duplicated or lost.
  • Liveness (no deadlock). If some thread can make progress, some thread does.
  • Starvation freedom. A waiting producer eventually gets a slot when one becomes available; a waiting consumer eventually gets an item.

A bounded buffer is the canonical small example of the whole mutex + condvar pattern, and it is the structural basis for job queues, pipelines, logging subsystems, and network send/receive queues.

Why It Matters Here​

Almost every concurrent system contains at least one bounded buffer. Thread pools have one, Go channels are one, Java's ArrayBlockingQueue is one, Kafka producers have one per partition. Getting it right once gives you the template for all of them.

The common broken variants are equally important to study:

  • single condition variable with signal instead of broadcast: a producer can wake another producer that cannot proceed, while a consumer stays asleep.
  • checking the predicate with if: a woken thread can find the buffer in a different state than it expected.
  • signaling outside the mutex: the predicate check and the signal race.

You will see all three in real codebases. Recognizing them is half of the skill.

Concrete Example​

The reference implementation (full, tested):

#include <pthread.h>

#define N 16
static int buf[N];
static int count, head, tail;
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  not_full  = PTHREAD_COND_INITIALIZER;
static pthread_cond_t  not_empty = PTHREAD_COND_INITIALIZER;

void bb_put(int x) {
    pthread_mutex_lock(&m);
    while (count == N) pthread_cond_wait(&not_full, &m);
    buf[tail] = x; tail = (tail + 1) % N; count++;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&m);
}

int bb_get(void) {
    pthread_mutex_lock(&m);
    while (count == 0) pthread_cond_wait(&not_empty, &m);
    int x = buf[head]; head = (head + 1) % N; count--;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&m);
    return x;
}

Two condvars, one for each predicate (count < N, count > 0). signal suffices because only one thread can consume each state change.

A broken variant to study:

// BROKEN: one condvar, signal instead of broadcast
static pthread_cond_t any = PTHREAD_COND_INITIALIZER;
void bb_put_bad(int x) {
    pthread_mutex_lock(&m);
    while (count == N) pthread_cond_wait(&any, &m);
    buf[tail] = x; tail = (tail + 1) % N; count++;
    pthread_cond_signal(&any);  // might wake another producer!
    pthread_mutex_unlock(&m);
}

Under a full-buffer scenario with several blocked producers and one blocked consumer, the consumer posts an item and signals any; the wakeup can land on a producer who finds the buffer full and goes back to sleep. The consumer does not wake. Livelock in the worst case, arbitrary latency in the average case.

Common Confusion / Misconception​

"A bounded buffer with two semaphores (empty, full) is equivalent to the condvar version." Structurally yes, but the semaphore version is harder to extend. Compound predicates ("buffer not full AND not shutting down") do not compose with simple counting semaphores; you would need additional flags and an extra mutex anyway.

"Spinning on the buffer is fine because producing and consuming are fast." Spinning in user space through thousands of schedules is still worse than blocking whenever buffers ever stay empty or full for more than a few microseconds.

How To Use It​

When building any bounded queue:

  1. Name the predicates (not_full, not_empty) explicitly.
  2. One condition variable per predicate. Never fewer unless you can prove only one predicate exists.
  3. while loops around every cond_wait.
  4. Update state, then signal, all inside the mutex.
  5. Free-running index arithmetic inside the mutex, never across.

Check Yourself​

  1. Why do you need two condition variables, one per predicate, in the idiomatic solution?
  2. What goes wrong if you replace while with if in the wait loops?
  3. Why does signaling after state updates matter?

Mini Drill or Application​

Implement a bounded buffer of capacity 4 in C + pthreads. Run 3 producers and 2 consumers. Inject a 50 ms sleep inside each producer and a 200 ms sleep inside each consumer. Observe the back-pressure: producers should block when the buffer is full. Log entry/exit of each bb_put/bb_get and confirm count never exceeds 4 and never goes below 0.

Read This Only If Stuck​