Condition Variables: Mesa vs Hoare

flowchart TB
  consumer["Consumer Holding"]
  mutex["Mutex Held"]
  producer["Producer Idle"]
  consumer_2["Consumer 2 Idle"]
  consumer -->|Lock| mutex
  consumer -->|Wait| mutex
  producer -->|Push| mutex
  producer -->|Signal| consumer
  producer -->|Unlock| mutex
  consumer -->|Reacquire| mutex
  consumer -->|Pop| mutex
  consumer -->|Skips if| mutex
  consumer_2 -->|Steals| mutex
  consumer -->|Empty pop| consumer_2
  producer -->|Hoare| consumer
  consumer -->|Stale if| producer

Overview

This is one of the most common concurrency questions because the bug is invisible in a simple test. Code that waits with if works until a second consumer, a broadcast, or a spurious wakeup shows up in production.

The same protocol (predicate, mutex, while, signal or broadcast, shutdown flag) underlies bounded queues, thread pools, and connection pools. A lost or stolen wakeup there is a hung worker or a crash on an empty queue.

By the end you should be able to:

• Write the Mesa wait loop from memory
• Contrast Hoare's immediate handoff with Mesa's hint
• Choose signal or broadcast from the predicates on the CV
• Draw a lost wakeup when unlock and sleep are two steps
• Implement a bounded queue with one mutex and two condition variables

Diagrams - step by step

Three small diagrams for condition variables under Mesa and Hoare semantics. Step numbers in the labels give the animation order.

Diagram 1 - Happy path: Mesa wait and signal on a queue

Under Mesa semantics, signal just moves the waiter to runnable; the signaler keeps running and holding the mutex. The waiter reacquires the mutex later and must recheck the predicate before acting. Waiting releases the mutex atomically, so a signal sent while the producer holds the mutex cannot be lost between check and sleep.

Diagram 2 - Failure path: if instead of while lets a stolen wakeup through

Between the signal and the moment the woken thread gets the mutex, another thread can run and consume the item. Spurious wakeups, which POSIX and Java allow, cause the same problem with no signal at all. A while loop turns both into a harmless extra check.

Diagram 3 - Decision: Mesa or Hoare, and what goes wrong if you assume the other

Hoare semantics hand the mutex straight to the woken waiter, so the predicate is still true when it runs. Almost every real runtime is Mesa, where that guarantee does not exist. A while loop is correct under both, so always write while.

The protocol

Lock the mutex. While the predicate is false, wait on the CV. wait atomically releases the mutex and sleeps, then re-acquires it before returning. Act on the state. Unlock.

The producer locks, changes the state, signals or broadcasts, and unlocks. The predicate lives in shared state, never in the CV. A CV has no memory, so a signal with no waiter is simply lost.

put(x):
  lock
  while full: not_full.wait
  q.push(x)
  not_empty.signal
  unlock

get():
  lock
  while empty: not_empty.wait
  x = q.pop()
  not_full.signal
  unlock

Add a closed flag checked in both loops, and broadcast it on shutdown, so no thread sleeps forever after the producers exit.

Hoare vs Mesa

Between the signal and the moment the woken thread gets the mutex, another thread can run and consume the item (a stolen wakeup). A broadcast can wake several waiters for one item. The waiter can also wake with no signal at all. POSIX explicitly allows spurious wakeups, and Java, C++, and Go document the same rule. The while loop turns all three into an extra check.

while is also correct under Hoare, so write while even if you are reading a textbook that uses if.

signal vs broadcast

signal (notify, notify_one) wakes one waiter. It is the right call when every waiter waits for the same predicate and any one of them can make progress: one item, one consumer.

broadcast (notify_all) wakes all of them. You need it when waiters wait for different predicates on the same CV, or when one change can satisfy many (shutdown, a batch of capacity freed). Under Mesa, broadcast is always correct and just slower, because every waiter re-checks.

With one shared CV for both not_full and not_empty, signal can wake the wrong kind of thread and stall the system. Use two CVs, or broadcast. Two CVs plus signal is the classic bounded buffer. One CV plus broadcast is simpler to prove. Optimize later.

Signalling under the lock is the simplest to reason about. Signalling just after unlock can avoid a wasted wakeup where the waiter immediately blocks on the mutex the producer still holds. Both are correct on Mesa CVs as long as the state change itself happens under the mutex. Mutate, then signal. A signal that races the state change is a lost wakeup.

Lost wakeup

waiter:  sees empty
producer: pushes, signals    (nobody is sleeping yet)
waiter:  sleeps               (sleeps with the condition already true)

wait takes the mutex so that "check the predicate, then sleep" is one step. If you unlock and then sleep as two steps, the producer can change the state and signal in the gap, and the wakeup is lost forever. You must hold the mutex when you wait. APIs that split unlock and sleep are incorrect unless they park on the value still matching (a futex, or Atomics.wait).

The mutex re-acquire is also the happens-before edge that makes the producer's writes visible. See happens-before. A bare atomic flag is not this protocol: atomics vs locks.

A timed-out wait is the same rule. Timeout, spurious return, or a real signal: re-check the predicate under the mutex. Do not treat timeout as "still false" without looking.

What goes wrong with the wrong pick

if-based code that would be correct under Hoare, running on a Mesa runtime, acts on a stale predicate. It pops an empty queue or overfills a bounded buffer.

Building Hoare-style direct handoff everywhere costs extra context switches and makes broadcast awkward. You still see that shape in synchronous queues and fair locks that hand ownership straight to the next waiter. The TypeScript HoareQueue below does that, so if is safe there: the woken waiter owns the item and nobody can barge.

Practical rule: assume Mesa, write while, and use one CV per predicate.

Pros and cons

Working Python

Run python3 cv_mesa.py (stdlib only, under a second). threading.Condition has Mesa semantics. notify_all wakes both consumers for one item. With if, the second consumer pops an empty deque. With while, it sees the empty queue and waits for the next item. Run it locally. The in-page sandbox has no operating-system threads.

"""Mesa condition variables: why the wait goes in a while loop, not an if.

Run: python3 cv_mesa.py  (stdlib only, under 1 second)
threading.Condition has Mesa semantics (like pthreads, Java, Go, Rust): notify only marks
a waiter runnable; the notifier keeps the lock and the waiter must re-acquire it later.
By then the predicate may be false again (another consumer took the item, or a spurious wakeup).
"""
import collections
import threading
import time


class BoundedQueue:
    def __init__(self, capacity: int, use_while: bool) -> None:
        self.items: collections.deque = collections.deque()
        self.capacity = capacity
        self.use_while = use_while
        self.lock = threading.Lock()
        self.not_empty = threading.Condition(self.lock)  # both CVs share one mutex
        self.not_full = threading.Condition(self.lock)

    def put(self, item) -> None:
        with self.lock:
            while len(self.items) >= self.capacity:
                self.not_full.wait()           # releases the lock and sleeps atomically
            self.items.append(item)
            self.not_empty.notify_all()        # broadcast: every waiting consumer wakes

    def get(self):
        with self.lock:
            if self.use_while:
                while not self.items:          # CORRECT: re-check after every wakeup
                    self.not_empty.wait()
            else:
                if not self.items:             # BUG: assumes the item is still there
                    self.not_empty.wait()
            item = self.items.popleft()        # raises IndexError if the item was stolen
            self.not_full.notify()
            return item


def scenario(use_while: bool) -> None:
    q = BoundedQueue(capacity=1, use_while=use_while)
    results = []

    def consumer(name: str) -> None:
        try:
            results.append((name, q.get()))
        except IndexError:
            results.append((name, "IndexError: woke up to an empty queue"))

    c1 = threading.Thread(target=consumer, args=("c1",))
    c2 = threading.Thread(target=consumer, args=("c2",))
    c1.start(); c2.start()
    time.sleep(0.1)                            # both consumers are now waiting
    q.put("job-1")                             # one item, two woken consumers
    time.sleep(0.1)
    if use_while:
        q.put("job-2")                         # the re-waiting consumer gets the next item
    c1.join(1); c2.join(1)
    label = "while" if use_while else "if   "
    print(f"{label}: {sorted(results)}")


if __name__ == "__main__":
    scenario(use_while=False)   # one consumer pops an empty deque
    scenario(use_while=True)    # the loser sees an empty queue and simply waits again

Sample run: with if, one consumer got job-1 and the other raised IndexError (it woke up to an empty queue after notify_all). With while, both consumers got a job, because the loser waited again. The same result held on 3 of 3 runs.

Working TypeScript

Run npx tsx cv_mesa.ts (no dependencies). MesaQueue only marks the waiter runnable, so another task can take the item before the waiter resumes. HoareQueue hands the item straight to the waiter. Run it locally so the turn-taking with setTimeout matches the sample.

// Mesa vs Hoare condition variables, shown with async tasks in Node.
// Run: npx tsx cv_mesa.ts  (no dependencies)
// Mesa: notify() only makes the waiter runnable; it resumes later, after other code ran.
// Hoare: the signaler hands the state straight to the waiter, so the predicate still holds.

class MesaCondition {                       // async analogue of pthread_cond / Java wait()
  private waiters: Array<() => void> = [];
  wait(): Promise<void> { return new Promise((r) => this.waiters.push(r)); }
  notify(): void { this.waiters.shift()?.(); }  // a hint: "something changed, go re-check"
}

class MesaQueue<T> {
  private items: T[] = [];
  private notEmpty = new MesaCondition();
  constructor(private useWhile: boolean) {}
  put(x: T): void { this.items.push(x); this.notEmpty.notify(); }
  async get(): Promise<T> {
    if (this.useWhile) {
      while (this.items.length === 0) await this.notEmpty.wait();  // CORRECT
    } else {
      if (this.items.length === 0) await this.notEmpty.wait();     // BUG under Mesa
    }
    const x = this.items.shift();
    if (x === undefined) throw new Error("woke up to an empty queue (wakeup was stolen)");
    return x;
  }
}

class HoareQueue<T> {                       // Hoare-style: direct handoff to the waiter
  private items: T[] = [];
  private waiters: Array<(x: T) => void> = [];
  put(x: T): void {
    const w = this.waiters.shift();
    if (w) w(x); else this.items.push(x);   // the woken waiter owns the item, nobody can barge
  }
  get(): Promise<T> {
    const x = this.items.shift();
    return x !== undefined ? Promise.resolve(x) : new Promise((r) => this.waiters.push(r));
  }
}

interface Q { put(x: string): void; get(): Promise<string>; }

async function scenario(label: string, q: Q): Promise<void> {
  const log: string[] = [];
  const a = q.get().then((x) => log.push(`A got ${x}`), (e: Error) => log.push(`A failed: ${e.message}`));
  await Promise.resolve();                  // A is now waiting
  q.put("job-1");                           // step 1: producer signals A
  const b = q.get().then((x) => log.push(`B got ${x}`));  // step 2: B barges in before A resumes
  await new Promise((r) => setTimeout(r, 0));  // step 3: A finally resumes
  q.put("job-2");                           // step 4: a second item so nobody waits forever
  await Promise.all([a, b]);
  console.log(`${label.padEnd(11)}: ${log.join(" | ")}`);
}

async function main(): Promise<void> {
  await scenario("Mesa + if", new MesaQueue<string>(false));
  await scenario("Mesa + while", new MesaQueue<string>(true));
  await scenario("Hoare + if", new HoareQueue<string>());
}
main();

Sample run: Mesa plus if let B take job-1 and A fail, because the wakeup was stolen. Mesa plus while let B take job-1 and A take job-2. Hoare plus if let A take job-1 and B take job-2, because direct handoff means nobody can barge in.

Interview Q&A

Pitfalls

Go Deeper

• OSTEP, Condition Variables (Mesa vs Hoare, while not if)
• POSIX pthread_cond_wait (spurious wakeups)
• Python threading.Condition
• Go sync.Cond (wait in a loop)
• Monitor (synchronization), Wikipedia

Cluster: RWLock · next deadlock · hub