Five of this site's other ten Concurrency entries all use busy-waiting: a process spins on an ordinary shared variable, checking it over and over, until some condition changes (Peterson's algorithm, Dekker's algorithm, Lamport's bakery algorithm), or reason about which of a fixed set of resources a stuck process already holds (the Dining Philosophers Problem, the Readers-Writers Problem). The other five, the Treiber Stack, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List, never spin on an unmet condition at all — each only retries a compare-and-swap after losing an actual race, over one shared pointer for the stack, two coordinating pointers for the queue, the stack's own pointer again guarded by a published hazard or a pinned epoch, or a predecessor's own next pointer for the linked list. The Producer-Consumer (bounded buffer) problem introduces a genuinely different mechanism — the one Dijkstra built semaphores to support in the first place: a process that can't proceed blocks and yields the processor entirely, woken only once another process signals the specific resource it was waiting on. A fixed-capacity buffer sits between any number of producers and consumers. A producer blocks when the buffer is full; a consumer blocks when it's empty; a third, binary semaphore (the mutex) protects the buffer's own bookkeeping from the two sides touching it at once. Every textbook insists a process must acquire its counting semaphore before the mutex, never after. This page proves why, with the same exhaustive-interleaving-search discipline as every other Concurrency entry — and finds the two orderings aren't equally dangerous to get backwards.
Pick an ordering, how many producers and consumers there are, the buffer's capacity, and how many times each process tries to act, then either step through by hand — each Step Pi/Step Ci button runs that process's next pending action, or reports it's blocked — or press Explore all schedules to search every reachable interleaving at once. Try Buggy producer at a buffer capacity of 1 and 2 attempts: step the producer twice in a row (it fills the one slot, then blocks holding the mutex on its second attempt) — now step the consumer. It's blocked too, forever: it needs the mutex the producer is holding, and the producer needs the consumer's own next move (consuming, which signals the buffer isn't full) before it can let go. Switch to Buggy consumer, reset, and step the consumer first, before the producer does anything — same wedge, reached from the opposite, emptier starting condition.
Three pieces of shared state: emptySem (starts at the buffer's capacity K,
counts free slots), fullSem (starts at 0, counts filled slots), and mutex (free or
held by one process). A producer's attempt needs emptySem (to know a slot exists at all) and
mutex (to safely claim it); a consumer's needs fullSem and mutex the
same way. Acquiring a counting semaphore means waiting until it's positive, then decrementing it;
acquiring the mutex means waiting until it's free, then marking it held. Releasing either just reverses
that. The order the textbook insists on — counting semaphore first, mutex second — means a process can only
ever be holding the mutex for the single instant it needs it: grab the counting semaphore (which
may block, but blocks alone, holding nothing else), then grab the mutex, do the buffer update, and release
both right away.
Swap the order — mutex first, counting semaphore second — and a process can now get stuck holding the
mutex while it waits. That's the entire bug. A producer that grabs the mutex and then finds the buffer full
blocks on emptySem while still holding the mutex. The only way emptySem
ever increases is a consumer finishing an attempt — but a consumer's own attempt needs the mutex too, which
the stuck producer will never release. Circular wait between exactly two processes, over exactly two
resources, with the mutex as the one each needs that the other is holding. Nothing here needs a cycle of
three or more processes the way Dining Philosophers
does — two roles and one swapped acquire order are enough.
The textbook-correct pair:
function produce(s) {
waitEmpty(s); // counting semaphore first — may block, but holds nothing while it does
waitMutex(s);
s.fullSem++; // (buffer write happens here)
signalMutex(s);
signalFull(s);
}
function consume(s) {
waitFull(s); // counting semaphore first
waitMutex(s);
s.fullSem--; // (buffer read happens here)
signalMutex(s);
signalEmpty(s);
}
The buggy variant this page measures just swaps each role's own first two lines —
waitMutex(s) before waitEmpty(s) for a buggy producer, waitMutex(s)
before waitFull(s) for a buggy consumer — with every other line, including both releases,
completely unchanged. The demo above runs this exact state machine as independently clickable steps (request
→ acquire first resource → acquire second resource, finish, and release both), not a simplified stand-in for
it; full source in this page's own script.
Correct order never wedges — true by construction, confirmed empirically across every configuration tried. A process using the correct order only ever touches the mutex inside the single atomic step where it already holds the counting semaphore and is about to finish — it is structurally impossible for the mutex to be held in any state where that process is also blocked on something else. Confirmed across five different population/capacity combinations below (every one of the "exhausted" states below is a consumer correctly waiting for data that will never arrive because every producer already used up its attempt budget — not a bug, just the run legitimately ending with unmet demand):
| producers | consumers | capacity | attempts each | reachable states | exhausted (no more data coming) | wedged (real deadlock) |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 22 | 0 | 0 |
| 1 | 1 | 2 | 2 | 28 | 0 | 0 |
| 2 | 1 | 2 | 2 | 202 | 0 | 0 |
| 1 | 2 | 2 | 2 | 93 | 3 | 0 |
| 2 | 2 | 3 | 1 | 124 | 0 | 0 |
Buggy producer wedges only once demand exceeds capacity — and only from that point on. One producer, one consumer, counting states where the producer holds the mutex and the whole system has no further move. "Attempts" below is how many times the producer tries to produce (and the consumer to consume); a wedge needs the producer to attempt at least one more push than the buffer has room for:
| capacity | attempts 1 | attempts 2 | attempts 3 | attempts 4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 0 | 1 | 2 |
| 3 | 0 | 0 | 0 | 1 |
Reading down any column, the wedge count is exactly attempts − capacity once that's
positive, 0 otherwise — a producer only gets stuck holding the mutex on the attempt that actually finds the
buffer already full.
Buggy consumer is a sharper bug than buggy producer — reachable on attempt 1, independent of
capacity. Same setup, mutex acquired before fullSem instead. A buffer starts empty, so
a consumer that grabs the mutex before any producer has run blocks on fullSem immediately,
mutex in hand — no capacity has to fill first:
| capacity | attempts 1 | attempts 2 | attempts 3 | attempts 4 |
|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 |
| 2 | 1 | 2 | 3 | 4 |
| 3 | 1 | 2 | 3 | 4 |
Every column is identical: wedge count equals the attempt budget exactly, regardless of buffer size. The producer-side bug needs the buffer to actually fill up — a real amount of work — before it bites. The consumer-side bug needs nothing but an unlucky schedule on the very first move, because an empty buffer (every buffer's starting condition) is already the trigger. Both are reachable-deadlock counts, not guaranteed-every-run counts — the exhaustive search finds at least one schedule leading there among many that don't; Dining Philosophers' naive pickup rule is the rarer case on this site where a single fixed strategy deadlocks on every run. Scaling up the population makes both bugs worse, not better: two producers and one buggy consumer (capacity 2, 2 attempts each) reaches 10 wedged states out of 134 total; two of each, both roles buggy (capacity 1, 3 attempts each), reaches 124 wedged states out of 2,367.
Time: O(1) per wait/signal call — each is a
fixed comparison and increment/decrement, no scan over other processes (contrast Lamport's bakery algorithm's own
O(n) ticket scan). Space: O(n) for the per-process sub-state
this page's demo tracks, plus the buffer itself and three fixed semaphore values that don't grow with
n.
This page's failure mode is a fourth distinct one for the category, next to mutual-exclusion violation, circular-resource deadlock, and starvation: a two-resource acquisition-order bug, where holding one lock while blocked on another — one that only the other role's own progress can ever free — wedges the system with just two processes and no cycle of three or more. See Safety vs. Liveness for how deadlock and starvation split apart on this site's other Concurrency pages; this page's wedge is a deadlock in that same sense (the system stops moving entirely, not just one process), reached by a structurally different route.