§31.4The Producer/Consumer (Bounded Buffer) Problem

The producer/consumer (bounded-buffer) problem is the same one from the condition variables chapter — now rebuilt on semaphores, which turns out to be remarkably clean.

31.4 The Producer/Consumer (Bounded Buffer) Problem

The buffer and its put/get (a ring, indices mod MAX):

int buffer[MAX];
int fill = 0, use = 0;

void put(int value) {
    buffer[fill] = value;    // Line F1
    fill = (fill + 1) % MAX; // Line F2
}
int get() {
    int tmp = buffer[use];   // Line G1
    use = (use + 1) % MAX;   // Line G2
    return tmp;
}

First attempt: two semaphores, empty and full

Use two counting semaphores: empty counts free slots (init to MAX), full counts ready items (init to 0). A producer waits for a free slot then signals a full one; a consumer does the mirror image:

sem_t empty, full;

void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&empty);   // P1: is there a free slot?
        put(i);             // P2
        sem_post(&full);    // P3: announce a new item
    }
}
void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&full);    // C1: is there an item?
        int tmp = get();    // C2
        sem_post(&empty);   // C3: announce a free slot
    }
}
// main: sem_init(&empty, 0, MAX);  sem_init(&full, 0, 0);

The two semaphores are perfect counters: empty starts at MAX (all slots free), full at 0 (nothing to eat). Watch a full cycle with MAX = 1:

With MAX=1 (and even with multiple producers/consumers on the ordering alone) this works beautifully. But…

The bug at MAX > 1: a missing mutex

With MAX > 1 and multiple producers, put() itself races. empty and full control how many may produce or consume — but not mutual exclusion over the shared buffer indices:

A tempting fix that deadlocks

The obvious repair: wrap everything in a binary-semaphore mutex. But put it around the whole loop body — including the empty/full waits (Fig 31.11) — and you get a deadlock deadlock A situation where a set of threads are each holding a resource and waiting for one held by another, forming a cycle in which none can proceed — e.g. every dining philosopher holding their left fork and waiting for their right, or a consumer holding a mutex while blocked on 'full' while the producer that would post 'full' is blocked on that mutex. Studied in depth in ch32. defined in ch. 31 — open in glossary :

// BROKEN — mutex scope too wide
sem_wait(&mutex);   // P0 / C0  ← acquired BEFORE the empty/full wait
sem_wait(&empty);   // P1        (consumer: sem_wait(&full))
put(i);             // P2
sem_post(&full);    // P3
sem_post(&mutex);   // P4 / C4

The consumer grabs the mutex (C0), then blocks on sem_wait(&full) (C1) with the lock still held. The producer’s very first move is sem_wait(&mutex) (P0) — already held — so it blocks too. Each waits for the other: a classic deadlock.

At last, a working solution

The fix is simply to shrink the lock’s scope: hold the mutex only around put()/get(), leaving the empty/full waits outside it (Fig 31.12):

// CORRECT — mutex only around the critical section
sem_wait(&empty);   // P1
sem_wait(&mutex);   // P1.5  ← mutex INSIDE the empty/full wait
put(i);             // P2
sem_post(&mutex);   // P2.5
sem_post(&full);    // P3
// consumer mirrors: wait(full) → wait(mutex) → get → post(mutex) → post(empty)

Now a thread can block on empty/full without holding the mutex, so no cycle can form. The result — two counting semaphores for ordering plus a binary semaphore for mutual exclusion — is the canonical bounded buffer. Understand it now; use it later.