Condition-variable designs differ in what happens at the moment of signalling: under Hoare (signal-and-wait) semantics the signaller immediately yields the lock and the CPU to the woken thread, while under Mesa (signal-and-continue) semantics the signaller keeps running and the woken thread must re-acquire the lock later. Explain how each choice affects the waiter's code, and whether signalling before or after releasing the mutex matters.

## Two answers to one question The question a monitor design must answer is: *at the instant a thread signals a condition, who holds the lock next?* Historically there are two answers, and they lead to visibly different waiter code. ## Hoare semantics — signal-and-wait (signal-and-urgent-wait) Signalling is an immediate, atomic handoff: 1. The signaller is suspended and placed on an **urgent** queue. 2. One waiter is woken and given the mutex directly. 3. When that waiter leaves the monitor (or itself waits), threads on the urgent queue get priority over threads merely trying to enter. Because nothing else can execute between the signal and the waiter's resumption, the predicate that motivated the signal is **still true** when the waiter resumes. Consequences: - `if (!predicate) wait();` is sufficient — the waiter needs no re-test. - Reasoning is clean: signalling is an assertion the receiver can trust. - **Cost:** at minimum two extra context switches per signal, plus a lock handoff that defeats fast uncontended lock paths. - **Awkwardness:** the signaller is suspended mid-critical-section, so its own invariants must hold at the point of signalling — a real burden if the signal sits in the middle of a multi-step state update. In practice signals get pushed to the end of the critical section anyway, which erodes the benefit. - The urgent queue's priority rule is extra machinery, and nesting monitors makes it harder still. ## Mesa semantics — signal-and-continue Signalling is a *hint*: 1. One (or all) waiters are moved from the condition's wait set to the mutex's entry queue. 2. The signaller keeps the mutex and continues to the end of its critical section. 3. The woken waiter competes for the mutex like anyone else. Between the signal and the waiter's re-acquisition, arbitrary work can happen: the signaller continues; other threads that were never waiting can acquire the lock first (**barging**); another woken waiter can consume the state. So the predicate may be false when the waiter resumes. Consequences: - `while (!predicate) wait();` is **mandatory**. - Signals become cheap: no handoff, no forced context switch, and the fast uncontended mutex path is preserved. - Implementations may also allow **spurious** wakeups, which cost nothing extra because the loop is already required. - Barging is a deliberate performance choice: allowing a running thread to take a briefly-free lock avoids a context switch, at the cost of fairness. There is a third historical variant, **Brinch Hansen** semantics, which requires the signal to be the *last* action before leaving the monitor — so no ambiguity arises at all. It is the easiest to reason about and the most restrictive to program against; it survives mostly in language designs rather than general-purpose libraries. ## Which one do real systems use? Essentially all modern condition-variable implementations — OS-level and language-level — are Mesa-style signal-and-continue, possibly with spurious wakeups. That is *why* "always wait in a loop" is universal advice: the advice is a direct consequence of the semantics the industry chose. Knowing the Hoare alternative is what lets you explain *why* the loop is required rather than reciting it, and it correctly predicts that under Hoare semantics the loop would be optional. A practical corollary: portable code must be written for the weakest guarantee. Even on a hypothetical no-spurious-wakeup platform, barging alone still forces the loop. ## Signal inside or outside the critical section? A separate question, often confused with the above. ``` // A: signal while holding the mutex lock(m); state.change(); cond.signal(); unlock(m) // B: signal just after releasing lock(m); state.change(); unlock(m); cond.signal() ``` Both are **correct**, provided the state change itself happened under the mutex — that is the part that closes the lost-wakeup race. The difference is scheduling: - **A** may wake a thread that immediately blocks on the mutex the signaller still holds (a "hurry up and wait" hop). Many implementations optimize this away by moving the waiter directly to the mutex queue instead of making it runnable. - **B** avoids that hop, but widens the window in which a barging thread can take the lock and consume the state before the woken waiter arrives — more wasted wake-ups, and worse fairness. What is **not** optional: mutating the predicate's state outside the mutex. Do that and no placement of the signal can save you, because a waiter can evaluate the predicate as false and enter the wait set in the gap. Also note: some platforms *require* holding the lock to signal at all; others merely allow it. Portable code that signals after unlocking must confirm the platform permits it. ## What this buys you as a designer - It explains the loop from first principles instead of as a rule. - It predicts barging and therefore that fairness is not free: if you need bounded waiting, build it (ticketing, per-thread conditions, explicit handoff) rather than expecting the primitive to provide it. - It clarifies that priority and wake-up order are policy, not semantics — nothing about signalling guarantees which waiter runs. - It frames the signal-placement question honestly as a measurable micro-optimization rather than a correctness rule people can argue about indefinitely.