When releasing threads blocked on a condition variable, when is waking a single waiter correct and when must you wake all of them? Describe what goes wrong in each direction.

## The decision rule Wake **one** only if all three hold: 1. **Single predicate** — every thread waiting on this condition variable is waiting for the same logical thing. 2. **Interchangeable waiters** — it does not matter which one proceeds. 3. **One-for-one enabling** — the state change satisfies exactly one waiter (one item pushed ⇒ one consumer can run). Otherwise **wake all**. When in doubt, wake all: over-waking costs performance, under-waking costs correctness. ## Failure mode A: the wrong waiter consumes the notification The classic case is a bounded buffer with a single condition variable: ``` // BROKEN: one condition, two predicates put(x): lock(m); while size == C: cond.wait(m) push(x); cond.signal(); unlock(m) take(): lock(m); while size == 0: cond.wait(m) pop(); cond.signal(); unlock(m) ``` With a full buffer and several blocked producers, a consumer takes an item and signals — and the wake-up may go to *another producer* if producers and consumers share the wait set. That producer re-checks, sees the buffer still effectively full or races and loses, and goes back to sleep. The notification is spent; a producer that could have proceeded never learns. Enough of these and the system deadlocks with work available. This is not a bug in the waiting loop — the loop behaves correctly by re-checking and sleeping. The bug is that a single wake-up was aimed at a wait set containing threads with different predicates. Two fixes: - **Broadcast** — correct, and the reason "changing signal to notifyAll made the hang go away" is such a common war story. But it is treating the symptom. - **Two condition variables, one per predicate** (`notFull`, `notEmpty`) — now a signal is precisely targeted, and a single wake-up is both correct and cheap. This is the structurally right answer. ## Failure mode B: one change enables many waiters Even with a single predicate, one wake-up is wrong if the change satisfies more than one waiter: - A latch or gate opens: everybody waiting should proceed, so broadcast. - Shutdown begins: every waiter must observe termination, so broadcast. - A resource pool's capacity is raised by K, or K items are added in a batch: either signal K times or broadcast. - A barrier's generation advances: all parties must be released. A useful test: "after this state change, how many waiters could make progress?" If the answer can exceed one, one wake-up is insufficient. ## The cost of broadcasting Broadcast makes all N waiters runnable. They then serialize on the single mutex — one succeeds, the rest re-test a false predicate and go back to sleep. Costs: - **O(N) context switches** per useful state change. - **Cache-line ping-pong** on the mutex and the guarded state across cores. - **Latency spike** for the one thread that can actually proceed, because it competes with N−1 threads doing pointless work. - **Worse under scale**: with a producer signalling frequently and hundreds of waiters, broadcast can dominate the workload — the thundering-herd problem. Some implementations mitigate with "wait morphing" — moving broadcast waiters directly to the mutex's queue rather than making them all runnable at once — which reduces but does not eliminate the cost. ## Fairness and starvation A single wake-up says nothing about *which* waiter is chosen. Implementations vary from FIFO to arbitrary, and barging threads that never waited can win the mutex anyway, so under signal-and-continue semantics a specific waiter can in principle be passed over repeatedly. If your design needs a fairness guarantee — bounded waiting for every thread — you must build it explicitly (ticket ordering, or a per-thread condition/handoff), not assume it from `signal`. For most workloads this is a non-issue, but it matters for latency SLOs at the tail. ## Advanced: one condition variable per waiter When waiters are *not* interchangeable — each waits for a specific resource, a specific key, or a specific turn — the general solution is to give each waiter (or each key) its own condition and wake exactly the right one. This is how fair handoff and specific-resource-ready notifications are built. It costs a condition object per waiter/key and more bookkeeping, and pays for itself when N is large and wake-ups are frequent. ## What to say in an interview State the decision rule, name both failure directions (missed wake-up leading to a hang; thundering herd leading to wasted CPU), and then give the structural answer: **one condition variable per predicate** is what lets you signal one waiter safely. Add that when in doubt, broadcast, because a performance problem is diagnosable and a hang may not be.