Cairn
algorithms · concurrency · O(1) time per semaphore operation, O(n) space, deadlock-free only if both roles acquire their counting semaphore before the mutex

↩ back to Concurrency

Producer-Consumer Problem

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.

Try it

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.

Pick an ordering and process counts, then step each process by hand.

Why it works

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.

Reference implementation

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.

Pitfalls

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):

producersconsumerscapacityattempts eachreachable statesexhausted (no more data coming)wedged (real deadlock)
11122200
11222800
212220200
12229330
223112400

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:

capacityattempts 1attempts 2attempts 3attempts 4
10123
20012
30001

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:

capacityattempts 1attempts 2attempts 3attempts 4
11234
21234
31234

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.

Complexity

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.