Condition Variables

A condition variable is an object supporting three operations — `wait`, `signal` (sometimes called `notify`), and `broadcast` (sometimes called `notify_all`) — that always operate in conjunction with an associated mutex. The condition variable itself holds no data; it is conceptually a queue of threads waiting for some condition — a boolean predicate over variables protected by the lock — to become true. Threads never wait on a raw boolean value; they wait on the CV, while the boolean predicate is checked by inspecting ordinary shared variables that the lock protects. The essential operation is `wait(cv, mutex)`. A thread calls this while holding `mutex`, having just checked that the condition it needs is false. The call atomically releases `mutex` and puts the calling thread to sleep on `cv`'s queue. "Atomically" here is the crux: if release-then-sleep were two separate steps, another thread could acquire the lock, make the condition true, and call `signal` in the gap between the release and the sleep — and that signal would be lost forever, because no thread was yet on the queue to receive it. The CV implementation guarantees this cannot happen: by the time `wait` has released the lock, the calling thread is already registered as a waiter. When some other thread changes shared state such that the condition might now hold, it calls `signal(cv)` (wake one waiter) or `broadcast(cv)` (wake all waiters), typically just before or after releasing the lock. A woken thread does not resume running immediately with the lock in hand and the condition guaranteed true; it merely becomes eligible to compete for the lock again. Once it reacquires the lock, `wait` returns, and — critically — the thread must re-check the condition, because in the interval between being woken and reacquiring the lock, some other thread may have grabbed the lock first and changed the state again (a "stolen wakeup"), or the underlying implementation may permit spurious wakeups (returning from `wait` with no signal at all, permitted by POSIX for implementation efficiency on multiprocessors). This is why the mandatory idiom is: ``` while (!condition) { wait(cv, mutex) } ``` never ``` if (!condition) { wait(cv, mutex) } ``` The `while` loop is not a defensive style choice — it is a correctness requirement rooted in the exact atomicity guarantees the CV offers and does not offer.

The mechanism rests on the interaction between a lock (guarding a piece of shared state and the predicate over it) and a CV (a wait queue with `wait`/`signal`/`broadcast`). Here is the discipline, stated as an algorithm.

Invariant maintained by the pattern: whenever a thread is not holding the lock and not asleep inside `wait`, all reads/writes to the shared state it cares about have gone through critical sections protected by that same lock. The CV never touches the shared state itself — it only ever puts a thread to sleep and wakes it up, always in the context of holding (or about to hold, or having just released) the lock. ```pseudocode

# Shared state, protected by `lock` shared_state # e.g., buffer contents, count, flag lock # a mutex cv # a condition variable tied to `lock`

# --- Consumer / Waiter side --- procedure ConsumeWhenReady(): acquire(lock) while not ConditionHolds(shared_state): wait(cv, lock) # atomically: release(lock); sleep on cv

# on wakeup: reacquire(lock) before returning DoWorkAssumingConditionTrue(shared_state) release(lock)

# --- Producer / Signaler side --- procedure ProduceAndNotify(): acquire(lock) ModifyState(shared_state) # makes ConditionHolds possibly true if ConditionHolds(shared_state): signal(cv) # or broadcast(cv) — wake waiter(s) release(lock) ``` Step-by-step semantics of `wait(cv, lock)`, which is the operation demanding the most care: 1. The calling thread must already hold `lock` (a precondition — calling `wait` without the lock is undefined behavior / a programming error in virtually every real implementation). 2. `wait` atomically: (a) adds the calling thread to `cv`'s internal waiting-thread queue, and (b) releases `lock`. No other thread can observe the calling thread as "not yet queued but also not holding the lock" — that gap is exactly what atomicity forbids. 3. The thread is descheduled by the OS (it consumes no CPU while asleep — this is the entire point versus spin-waiting). 4. Some other thread later calls `signal(cv)` or `broadcast(cv)` while holding `lock`. This moves one (for `signal`) or all (for `broadcast`) waiting threads from "asleep" to "runnable," but does not hand them the lock directly nor guarantee they run next. 5. When the OS scheduler eventually runs a woken thread, `wait` reacquires `lock` (blocking if necessary, since the signaler or some other thread may hold it) before returning control to the caller. 6. Control returns to the `while` loop, which re-checks the condition — and only exits the loop, proceeding to use `shared_state`, once the condition is verified true while holding the lock. Why `signal` alone is not enough without the lock discipline: signaling changes the runnable set, but the thread that calls `signal` typically still holds the lock at that moment (in the common "signal-and-continue" semantics used by POSIX and most real systems), so the woken thread cannot actually proceed until the signaler releases the lock. This ordering guarantee — that the woken thread only resumes its critical section after reacquiring the lock — is what prevents two threads from ever believing the condition is true simultaneously when it isn't. Two wake primitives, two use cases:

• `signal` wakes at most one waiting thread. Appropriate when any one waiter can make progress and waking others would be wasted work (e.g., a single-slot mailbox where only one consumer needs the item).
• `broadcast` wakes every waiting thread. Necessary when different waiters are waiting for different sub-conditions on the same CV, or when a single signal cannot correctly guarantee that the "right" waiter (of possibly several eligible ones) proceeds — each woken thread re-checks its own predicate and either proceeds or goes back to sleep. Broadcast is always safe (never a correctness bug) — it can only ever cost extra wakeups. Signal, if misused (waking one thread when the correct behavior requires waking a specific different one), can cause deadlock: threads that could have been woken remain permanently asleep.

Time complexity. In a well-implemented CV, `wait`, `signal`, and `broadcast` are all $O(1)$ amortized per call for the queue manipulation itself (enqueue/dequeue a thread control block, typically a doubly linked list or similar), plus the unavoidable cost of an OS context switch to actually deschedule/reschedule a thread — a constant but comparatively large cost (microseconds), independent of the number of other threads in the system. `broadcast` costs $O(k)$ where $k$ is the number of currently waiting threads, since each must individually be marked runnable; this is the honest cost, not $O(1)$, though it is still linear and typically small. Compare this to a busy-wait/polling alternative: ```pseudocode while not ConditionHolds(shared_state): release(lock); acquire(lock) # or: spin without releasing ``` This costs $O(1)$ per poll but an unbounded number of polls — the thread consumes CPU cycles proportional to the wall-clock wait time divided by the polling interval, wasting cycles that could run other threads. On a single-core machine spinning while holding the lock is not merely wasteful but can deadlock the system entirely (no other thread can run to make the condition true). CVs asymptotically dominate polling whenever the wait time is not tiny relative to a context switch, which is essentially always true in real systems.

Space complexity. $O(w)$ where $w$ is the number of threads currently waiting on the CV — each waiting thread occupies one slot in the CV's internal queue (in practice, the thread's own kernel stack/control block, referenced by the queue, so marginal cost per waiter is small and constant).

Correctness argument. The central claim to prove is: no thread ever proceeds past its `while` loop believing the condition holds when it does not, and no wakeup is ever permanently lost. *No false proceed: the `while` loop only exits when `ConditionHolds(shared_state)` is evaluated as true, and this evaluation happens strictly after `wait` has reacquired `lock`. Since all writes to `shared_state` occur only while `lock` is held (the mutual-exclusion discipline inherited from ordinary locking), and the reading thread now holds `lock` too, the read is not racing any writer — it observes a definite, consistent value at the moment of the check. Mutual exclusion, proven for <a class="wiki-link" href="/wiki/cs-os-locks-and-mutual-exclusion" data-track="wiki_article.body.wiki_link">Locks and Mutual Exclusion</a> independently, is exactly what makes this check trustworthy. No stale cached view, no partial write, no race: the property being checked is the actual current state. No lost wakeup: this reduces to the atomicity of `wait`'s release-and-sleep step. Suppose for contradiction a signal is lost — meaning some thread T calls `signal` (or `broadcast`) while the intended waiter W is conceptually waiting but the signal reaches an empty queue and does nothing, after which W goes to sleep and is never woken. For this to happen, W must call `wait`'s internal enqueue operation after T's signal has already scanned the queue and found it empty. But W's `wait` call enqueues itself and releases the lock as one atomic action; T cannot be executing `signal` concurrently with that atomic action, because `signal` requires holding the same `lock`, and W still holds `lock` until the atomic release-and-enqueue completes. Hence T's `signal` (which must acquire `lock` first) is strictly ordered either entirely before W enqueues (in which case T's write to `shared_state` happens first, and W's subsequent `while`-check on re-entering will see the true condition next time it wakes on some later signal or even without needing to sleep) or strictly after W has already enqueued (in which case T's `signal` finds W in the queue and wakes it). There is no interleaving in which the signal is dispatched to an empty queue while W's wait-enqueue is logically pending — the lock forbids the race. This is precisely the guarantee that fails for a naive hand-rolled sleep/wake flag without this atomicity, producing the classic lost-wakeup bug. Termination / no permanent starvation for `broadcast` designs:* since broadcast wakes every waiter, any waiter whose condition has become true will, upon reacquiring the lock (in some order, eventually, assuming a fair scheduler and fair lock), observe it true and proceed; waiters whose condition remains false simply go back to sleep at negligible cost, preserving correctness while very slightly bounding efficiency (extra wakeups do $O(k)$ wasted work per broadcast, which is the honest tradeoff against `signal`'s ambiguity risk).

Tradeoffs. `signal` is cheaper per call than `broadcast` but requires the programmer to prove that waking any single waiter is always sufficient and correct — subtle when multiple distinct conditions share one CV, a common source of real bugs. `broadcast` is always safe but pays $O(k)$ wakeup cost even when only one waiter can actually proceed, causing a "thundering herd" if $k$ is large and only one thread's predicate is actually satisfiable — mitigated in practice by giving each logically distinct condition its own CV rather than multiplexing many predicates onto one.

Trace a bounded buffer of capacity 2 shared by one producer P and one consumer C, using two condition variables — `notFull` and `notEmpty` — both tied to the same `lock`. `count` tracks items currently in the buffer. ```pseudocode count = 0; CAPACITY = 2 lock; notFull; notEmpty # CVs share `lock` procedure Produce(item): acquire(lock) while count == CAPACITY: wait(notFull, lock) buffer.enqueue(item); count += 1 signal(notEmpty) release(lock) procedure Consume(): acquire(lock) while count == 0: wait(notEmpty, lock) item = buffer.dequeue(); count -= 1 signal(notFull) release(lock) return item ```

Now trace the case that demonstrates why `while`, not `if`, is required. Suppose two consumers C1 and C2 both wait on `notEmpty`, and a single producer signals only once.

With `while`, C2 — if it happens to wake spuriously, or was mistakenly signaled twice, or wakes up after C1 already consumed the one item — re-checks `count==0`, finds it still true, and correctly goes back to sleep instead of dequeuing from an empty buffer (which would be a serious bug, e.g., an underflow or reading garbage). This is exactly the scenario the invariant argument in the previous section predicts must be handled, and it is why production code (POSIX `pthread_cond_wait`, Java's `Condition.await`, C++'s `std::condition_variable::wait`) all document that spurious wakeups are possible and the `while` idiom is mandatory, not optional style.

The condition variable as a formal primitive emerged from the broader effort to structure concurrent programs safely, moving beyond raw semaphores toward higher-level, more error-resistant abstractions — the Monitors concept, of which condition variables are the core waiting mechanism.

Condition variables underpin the sleeping/waking logic inside almost every concurrent system component built above raw locks. Operating system kernels use them (or kernel-level equivalents) to implement wait queues for I/O completion, process termination (`wait()` on a child process conceptually blocks until a condition — child exited — becomes true), and blocking system calls. Language runtimes expose them directly: POSIX `pthread_cond_t`, Java's `Object.wait/notify` and `java.util.concurrent.locks.Condition`, C++'s `std::condition_variable`, Python's `threading.Condition`, and Go's channels (which provide similar semantics through a different interface) all reduce, at the implementation level, to this wait/signal/broadcast pattern paired with a lock. Thread pools use condition variables so idle worker threads sleep on an empty task queue rather than spinning, waking precisely when a task is submitted — a foundational pattern in web servers, database connection pools, and job schedulers. Producer-consumer pipelines throughout data processing systems (message queues, streaming frameworks, buffered I/O layers) use the exact bounded-buffer pattern traced above. Higher-level concurrency abstractions such as Monitors, barriers, read-write locks, and thread-safe blocking collections (e.g., Java's `BlockingQueue`) are all built internally from condition variables, making this primitive one of the load-bearing walls of concurrent systems design — quietly present under almost every "a thread waits until X happens" behavior in modern software.

Ask the tutor: How would the bounded-buffer producer-consumer example change if we used a single condition variable instead of two separate ones (`notFull` and `notEmpty`)?