Show how a fixed-capacity buffer can be built from two counting semaphores plus a mutex, and explain what goes wrong if a producer acquires the mutex before the semaphore that counts free slots.

## What each primitive contributes A **counting semaphore** holds a non-negative integer of permits with two operations: `acquire` (decrement; block while the count is zero) and `release` (increment; wake a waiter if any). Unlike a condition variable, a semaphore *remembers* — releasing when nobody is waiting bumps the count, so the permit is available to the next acquirer. That memory is what makes semaphores a good fit for counting resources. In a bounded buffer there are exactly two resources to count: - **free slots** — how many items may still be inserted. Starts at `CAPACITY`. - **stored items** — how many items may still be removed. Starts at `0`. A **mutex** is a different thing: it enforces that only one thread mutates the head/tail indices and the storage at a time. Semaphores gate *how many* threads may proceed; the mutex protects *the data structure*. You need both in the multi-producer / multi-consumer case. ## The canonical structure ``` sem emptySlots = CAPACITY sem fullSlots = 0 mutex m put(item): emptySlots.acquire() # may block: no room m.lock() ring[tail] = item; tail = (tail+1) % CAPACITY m.unlock() fullSlots.release() # publish: one more item available take(): fullSlots.acquire() # may block: nothing to take m.lock() item = ring[head]; head = (head+1) % CAPACITY m.unlock() emptySlots.release() # publish: one more slot available return item ``` Read it as a symmetric trade: a producer converts a *free slot* permit into an *item* permit; a consumer does the reverse. The two semaphores are never both waited on by the same thread, which is why no cycle exists in the correct ordering. **Invariants**: `emptySlots + fullSlots ≤ CAPACITY` (permits in flight account for threads currently inside the critical section), and the number of successful inserts minus removes always equals the item count. No thread ever observes a full buffer inside `put`, because the permit was already taken. ## The deadlock from inverted acquisition order Swap the first two lines of `put`: ``` put(item): m.lock() # WRONG: lock first emptySlots.acquire() # blocks here while holding m ... ``` Run it with a full buffer: ``` buffer FULL (emptySlots = 0, fullSlots = CAPACITY) P1: m.lock() -> succeeds, P1 owns the mutex P1: emptySlots.acquire() -> count is 0, P1 BLOCKS, still holding m C1: fullSlots.acquire() -> succeeds (items exist) C1: m.lock() -> BLOCKS, m is held by the sleeping P1 --- no thread can make progress, forever --- ``` This is a textbook circular wait: P1 holds the mutex and waits for a permit that only a consumer can produce; the consumer waits for the mutex that only P1 can release. All four Coffman conditions hold — mutual exclusion, hold-and-wait, no preemption, circular wait — and the two "lock-like" resources are of different kinds, which is exactly why it slips past reviewers who only look for two mutexes taken in different orders. The general rule this teaches: **acquire the blocking resource permit outside the critical section; never sleep on a condition while holding a lock whose release you depend on.** Note that condition variables do not have this problem precisely because `wait` releases the mutex atomically — that is their entire reason for existing. Semaphores do not, so ordering is your responsibility. ## Why the mutex is still needed A common follow-up trap: "the semaphores already limit how many threads are inside, so drop the mutex." `emptySlots` permits up to CAPACITY *producers* into the insert region simultaneously — they would race on `tail` and on the storage. The mutex is what makes the index update atomic. Two legitimate refinements: - **Single producer, single consumer**: there is only ever one thread on each side, and producer and consumer touch different indices, so the mutex can be dropped entirely (with proper memory ordering on the shared cells). This is the classic lock-free-ish SPSC ring buffer. - **Separate producer and consumer mutexes** (lock splitting): `putLock` guards `tail`, `takeLock` guards `head`. One producer and one consumer can then run concurrently, which roughly doubles throughput on a contended queue. The semaphores are unchanged. ## Semaphores versus condition variables here Both solutions are correct; they differ in ergonomics. - Semaphores are **counted and remembered**, so there is no lost-wakeup class of bug and no predicate loop. But they carry no association with the data, so nothing stops you from acquiring in the wrong order or forgetting a release — and a missing `release` is an unrecoverable slow leak of permits. - Condition variables keep the predicate next to the data it describes (`while count == CAPACITY`), which is far easier to audit and extends naturally to compound conditions ("wait until at least 3 slots free"). The cost is the loop, the Mesa-semantics reasoning, and the lost-wakeup pitfalls. For anything beyond "one resource, one count", condition variables generally read better. For plain bounded capacity, the semaphore pair is compact and hard to get subtly wrong — provided the acquire order is right.