A worker occasionally blocks forever waiting for data that was, in fact, produced. Explain the lost-wakeup bug on a condition variable and the exact locking protocol between the producer and the waiter that prevents it.

## What "lost wakeup" means A condition variable is **edge-triggered with no memory**. `signal` wakes one thread *currently* in the wait set; if the set is empty it is a no-op. Nothing is buffered, so a signal that arrives "too early" is gone. When the waiter subsequently sleeps, nothing will ever wake it — even though the condition it wanted is already true. The result is an indefinite hang, usually intermittent and load-dependent. Contrast this with a *level-triggered* mechanism such as a semaphore, whose permit count persists: a release before any acquire is remembered, and the later acquire succeeds immediately. That difference is precisely why semaphores are hard to lose signals with, and condition variables are easy. ## Variant 1: the check-then-wait race ``` // BROKEN waiter: if not ready: // read OUTSIDE the lock (or lock released here) lock(m); cond.wait(m); unlock(m) producer: lock(m); ready = true; cond.signal(); unlock(m) ``` Interleaving: the waiter reads `ready == false`; the producer runs entirely; the waiter then enters the wait set. The signal is spent, `ready` is true, and the waiter sleeps forever. The fix is not to "check faster" — no amount of narrowing removes the window. It is to make the window **unreachable by the producer**, by covering the check *and* the transition into the wait set with the mutex the producer must hold: ``` lock(m) while not ready: // tested under m cond.wait(m) // atomically: release m + enter wait set unlock(m) ``` Now the producer either acquires the mutex *before* the waiter's test — so the test sees `ready == true` and no wait happens — or *after* the waiter is already registered — so its signal finds a waiter. There is no third interleaving. This is why `wait` requires the mutex to be held: the requirement exists to make this exact race impossible. ## Variant 2: signalling without the lock, with a racy predicate ``` // SUSPECT producer: ready = true // mutated without m cond.signal() // signalled without m ``` Signalling *after* releasing the mutex is legal and sometimes desirable, but mutating the predicate's state outside the mutex is not. If `ready` is written without the lock, the waiter can evaluate it as false and enter the wait set in a window where the producer's write and signal both slip past. The rule: **the predicate's state must be mutated under the mutex**; the signal itself may be inside or immediately after the critical section, but the state change may not be outside it. ## Variant 3: the missing notification (same symptom, different cause) A thread hangs not because the signal was lost in a race, but because no signal was ever sent: - A new code path was added that makes the predicate true (an error injection, a shutdown flag, a capacity increase) and nobody added the notification. - `signal` woke *one* waiter whose predicate was false while a different waiter's predicate was true — the wake-up went to the wrong thread and was consumed. Sharing one condition variable between distinct predicates makes this routine; a broadcast, or one condition per predicate, avoids it. - Shutdown: threads waiting on "queue non-empty" are never woken because shutdown only sets a flag. Termination must be part of the predicate (`while queue.empty() and not shuttingDown`) and must broadcast. Waiting in a loop does **not** help here — the loop only makes wake-ups safe, it cannot invent one. This is why review checklists pair the two rules: wait in a loop, and notify from every state transition that could satisfy someone's predicate. ## Diagnosing it in a running system Symptoms: throughput drops to zero or a subset of workers goes permanently idle while work is queued; CPU is *low* (distinguishing it from a livelock or spin); no exception anywhere. Procedure: 1. Dump all threads. Threads parked in a condition wait, with the guarded state visibly satisfying their predicate, is the signature. 2. Confirm the state: if the queue is non-empty while consumers wait on "not empty", the wake-up was lost or never sent. 3. Enumerate every writer of that state and check each path signals under the correct mutex — including error paths, shutdown paths and recently added branches. 4. Check whether one condition variable serves multiple predicates; if so, either split it or broadcast. Mitigation while you hunt: switching `signal` to `broadcast` often makes the hang disappear, which is diagnostic (it points to a wrong-waiter wake-up) but is a band-aid, not a fix — it does not help if no notification is sent at all. ## Defensive design - **Bounded waits.** A wait with a deadline converts an eternal hang into a detectable, loggable timeout — the difference between a support ticket saying "it stopped" and an alert naming the condition. - **Encapsulate.** A reviewed blocking queue or a well-tested monitor class removes the opportunity for each call site to get this wrong. - **Prefer level-triggered where it fits.** If your condition is naturally a count of available items or permits, a semaphore's persistent permits sidestep lost wakeups entirely. - **Make termination a first-class predicate.** Every waiting loop should have a way to be woken for shutdown, or your process will hang on exit.