§30.2–30.4The Producer/Consumer (Bounded Buffer) Problem … Summary

Locks and CVs are enough to solve real synchronization problems — but getting the signaling right is subtle. The canonical proving ground is the producer/consumer problem producer/consumer problem Dijkstra's canonical synchronization problem (a.k.a. the bounded-buffer problem): one or more producer threads place items into a shared bounded buffer while one or more consumers remove them. Correct solutions need mutual exclusion on the buffer plus making producers wait when it is full and consumers wait when it is empty — a lock plus two condition variables (empty and fill). defined in ch. 30 — open in glossary (a.k.a. the bounded-buffer problem, first posed by Dijkstra).

30.2 The Producer/Consumer (Bounded Buffer) Problem

One or more producers generate items and place them in a shared buffer; one or more consumers take items out. It’s everywhere: a multithreaded web server (producers enqueue HTTP requests, consumer threads process them); a UNIX pipe grep foo file.txt | wc -l (grep is the producer, wc the consumer, an in-kernel bounded buffer between them).

Start with a single-slot buffer and its put/get (Version 1):

int buffer;
int count = 0; // initially empty

void put(int value) {
    assert(count == 0);
    count = 1;
    buffer = value;
}
int get() {
    assert(count == 1);
    count = 0;
    return buffer;
}

void *producer(void *arg) {
    int loops = (int) arg;
    for (int i = 0; i < loops; i++)
        put(i);
}
void *consumer(void *arg) {
    while (1) {
        int tmp = get();
        printf("%d\n", tmp);
    }
}

Put only into an empty buffer, get only from a full one. A plain lock around put/get gives mutual exclusion but can’t make a thread wait for the right condition — so we need condition variables.

Broken attempt #1: one CV, and an if

cond_t cond; mutex_t mutex;

void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);            // p1
        if (count == 1)                        // p2
            Pthread_cond_wait(&cond, &mutex);  // p3
        put(i);                                // p4
        Pthread_cond_signal(&cond);            // p5
        Pthread_mutex_unlock(&mutex);          // p6
    }
}
void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);            // c1
        if (count == 0)                        // c2
            Pthread_cond_wait(&cond, &mutex);  // c3
        int tmp = get();                       // c4
        Pthread_cond_signal(&cond);            // c5
        Pthread_mutex_unlock(&mutex);          // c6
        printf("%d\n", tmp);
    }
}

With one producer and one consumer this works. Add a second consumer and it shatters. Step through the disaster:

The root cause: after the producer woke Tc1 but before Tc1 ran, another thread changed the buffer. A signal only makes a thread runnable — it’s a hint that the state changed, not a guarantee it still holds. This is Mesa semantics mesa semantics The interpretation (Lampson & Redell, from the Mesa system) where a condition-variable signal is only a HINT that the waited-on state may have changed — not a guarantee it still holds when the woken thread finally runs. The woken thread must re-check the condition, hence 'while, not if'. Virtually every real system uses Mesa semantics. defined in ch. 30 — open in glossary , the contrast being Hoare semantics hoare semantics The stronger alternative to Mesa semantics (Hoare) in which signaling immediately hands the lock and CPU to a woken waiter, guaranteeing the signaled state still holds when it runs. A stronger guarantee, but harder to build — so it is rarely used in practice. defined in ch. 30 — open in glossary :

Fix #1: while, not if

Because a woken thread must re-verify reality, change every if before a wait into a while (p2 and c2). Now when Tc1 wakes it re-checks count; if the buffer is empty again, it just goes back to sleep.

while (count == 1)                     // p2 — was: if
    Pthread_cond_wait(&cond, &mutex);  // p3
// ... and in the consumer:
while (count == 0)                     // c2 — was: if
    Pthread_cond_wait(&cond, &mutex);  // c3

That kills the first bug — but a second one remains, and it’s about having only one condition variable:

Fix #2: two condition variables

The trace shows a consumer waking another consumer while the producer sleeps. Signaling must be directed: a consumer should only wake producers, and vice-versa. Use two CVs — empty and fill:

while (count == 1)
    Pthread_cond_wait(&empty, &mutex);
put(i);
Pthread_cond_signal(&fill);

while (count == 0)
    Pthread_cond_wait(&fill, &mutex);
int tmp = get();
Pthread_cond_signal(&empty);

The correct, general solution

Finally, generalize the single slot to a ring buffer of MAX entries — more concurrency, fewer context switches. Producers sleep only when all slots are full (count == MAX); consumers only when all are empty (count == 0):

int buffer[MAX];
int fill_ptr = 0, use_ptr = 0, count = 0;

void put(int value) {
    buffer[fill_ptr] = value;
    fill_ptr = (fill_ptr + 1) % MAX;
    count++;
}
int get() {
    int tmp = buffer[use_ptr];
    use_ptr = (use_ptr + 1) % MAX;
    count--;
    return tmp;
}

// producer:
while (count == MAX)
    Pthread_cond_wait(&empty, &mutex);
put(i);
Pthread_cond_signal(&fill);

// consumer:
while (count == 0)
    Pthread_cond_wait(&fill, &mutex);
int tmp = get();
Pthread_cond_signal(&empty);

And there we have it: a correct, concurrent producer/consumer. Time to sit back and drink a cold one.

30.3 Covering Conditions

One more wrinkle, from Lampson and Redell’s Mesa work. Consider a multithreaded memory allocator:

int bytesLeft = MAX_HEAP_SIZE;
cond_t c; mutex_t m;

void *allocate(int size) {
    Pthread_mutex_lock(&m);
    while (bytesLeft < size)
        Pthread_cond_wait(&c, &m);
    void *ptr = ...; // carve out size bytes
    bytesLeft -= size;
    Pthread_mutex_unlock(&m);
    return ptr;
}
void free(void *ptr, int size) {
    Pthread_mutex_lock(&m);
    bytesLeft += size;
    Pthread_cond_signal(&c); // but WHOM to wake??
    Pthread_mutex_unlock(&m);
}

The signaler can’t know which waiter its freed bytes can satisfy. Walk the failure — and the fix:

Lampson and Redell’s fix is to replace signal with broadcast broadcast pthread_cond_broadcast — wake ALL threads waiting on a condition variable, versus signal, which wakes only one. Needed when the signaler cannot identify the single correct waiter to wake (see covering condition). defined in ch. 30 — open in glossary (pthread_cond_broadcast), which wakes all waiters; each re-checks its own condition, and the ones that still can’t proceed simply sleep again. They call this a covering condition covering condition A condition on which the signaler wakes ALL waiting threads (via broadcast) rather than one (via signal), because it cannot tell which specific waiter should proceed — e.g. a memory allocator freeing bytes that could satisfy any of several differently-sized requests. Correct but potentially wasteful: needlessly woken threads simply re-check and go back to sleep. (Lampson & Redell.) defined in ch. 30 — open in glossary — it conservatively covers every thread that might need waking. The cost is performance: threads woken needlessly. As a rule, if your program only works when you turn a signal into a broadcast (and you don’t think it should need to), you probably have a bug — but for cases like this allocator, broadcast is the cleanest tool.

30.4 Summary

Condition variables — a second synchronization primitive beyond locks — let threads sleep until program state is as desired, cleanly solving the producer/consumer problem and covering conditions. The load-bearing rules: hold the lock, use a state variable, always re-check with while, and signal in a directed way (or broadcast when you can’t).