The question this answers
How does a task wait for a *condition* on shared state without holding the lock and without spinning?
A bounded work queue of capacity 100 between an HTTP ingest handler (producer) and four worker tasks (consumers): consumers must wait when it is empty, producers must wait when it is full.
The queue itself, its length, and a closed flag — all guarded by one mutex. The condition variables guard nothing; they are the waiting rooms attached to that mutex.
0 <= queue.length <= 100 at every instant; no consumer dequeues from an empty queue; no producer enqueues into a full one; and a task waiting for a condition that becomes true is eventually woken.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The three-part shape, and why each part is mandatory
A condition variable is always used with a mutex, and always in the same shape. The waiter holds the lock, checks a predicate, and if the predicate is false calls wait — which *atomically* releases the lock and sleeps. When woken, wait re-acquires the lock before returning, and the waiter re-checks the predicate. The signaller holds the same lock, changes the state that makes the predicate true, and notifies.
Each piece is load-bearing. The atomicity of release-and-sleep is what prevents a notification slipping into the gap between "I decided to wait" and "I am waiting" — without it you get a lost wakeup, which is its own lesson (Lost Wakeups: The Notify That Arrived Before the Wait). Re-acquiring before returning is what lets the woken task safely touch the state it was waiting on. And the loop rather than an if is what makes the code correct under spurious wakeups, under multiple waiters competing for one item, and under any future change that adds a second reason to notify (Spurious Wakeups: Why It Is `while`, Not `if`).
The bounded queue below is the canonical example because it needs two conditions on one mutex: consumers wait for not-empty, producers wait for not-full. That is the normal case, not an advanced one — a condition variable is a waiting room *for a predicate*, and different predicates want different rooms so that a notification wakes tasks that can actually proceed.
1import threading2from collections import deque3 4class BoundedQueue:5 def __init__(self, capacity=100):6 self._lock = threading.Lock()7 self._not_full = threading.Condition(self._lock) # both conditions share8 self._not_empty= threading.Condition(self._lock) # ONE mutex. Required.9 self._items = deque()10 self._cap = capacity11 self._closed = False12 13 def put(self, item):14 with self._not_full: # acquires the shared lock15 while len(self._items) >= self._cap and not self._closed:16 self._not_full.wait() # atomically: release + sleep;17 # on wake: re-acquire, loop again18 if self._closed:19 raise QueueClosed()20 self._items.append(item) # invariant temporarily... still true21 self._not_empty.notify() # one item added -> wake ONE consumer22 23 def get(self):24 with self._not_empty:25 while not self._items and not self._closed:26 self._not_empty.wait()27 if not self._items: # closed and drained28 raise QueueClosed()29 item = self._items.popleft()30 self._not_full.notify() # one slot freed -> wake ONE producer31 return item32 33 def close(self):34 with self._lock:35 self._closed = True36 self._not_full.notify_all() # a state change EVERY waiter37 self._not_empty.notify_all() # must re-evaluate -> notify_all38 39# The three rules this code obeys, in order of how often they are broken:40# 1. wait() is inside a `while`, never an `if`. [[spurious-wakeups]]41# 2. the state change and the notify are both under the lock. [[lost-wakeups]]42# 3. notify() when one waiter can proceed; notify_all() when the state43# change is relevant to all of them (like closing).The handoff, traced
The schedule below is the empty-queue case: two consumers waiting, a producer arriving with one item. The steps worth watching are 3 and 4 — the atomic release-and-sleep — and step 8, where the woken consumer re-checks the predicate rather than assuming the item is still there.
That re-check is not paranoia. In the trace, notify wakes one consumer, but between the notify and that consumer actually re-acquiring the lock, a *different* consumer that was just arriving takes the lock, finds the queue non-empty, and takes the item. The woken consumer then re-acquires, finds the queue empty again, and goes back to waiting. With an if instead of a while it would have popped from an empty deque and crashed — an IndexError at 03:00 with a stack trace that makes no sense, because the queue was demonstrably non-empty when the wakeup was sent.
This is why the predicate loop is the *definition* of correct condition-variable use rather than a defensive habit. A notification is a hint that the state may have changed. It is never a promise that the state is still changed by the time you look.
| # | Consumer 1 — waiting | Producer — one item | Consumer 2 — arriving fresh | State |
|---|---|---|---|---|
| 1 | acquire lock; check `while not items` → true | · | · | items=0 lock=C1 waiting=0 |
| 2 | wait() — atomically releases lock and sleeps | · | · | items=0 lock=free waiting=1 |
| 3 | · | acquire lock; items.append(job-1) | · | items=1 lock=P waiting=1 |
| 4 | · | not_empty.notify() — marks C1 runnable | · | items=1 lock=P waiting=0 |
| 5 | · | release lock | · | items=1 lock=free |
| 6 | · | · | acquire lock (barges ahead of C1); check `while not items` → false | items=1 lock=C2 |
| 7 | · | · | popleft() → job-1; not_full.notify(); release | items=0 lock=free |
| 8 | wait() returns; re-acquires lock; RE-CHECKS `while not items` → true | · | · | items=0 lock=C1 |
| 9 | wait() again — releases lock and sleeps | · | · | items=0 lock=free waiting=1 |
| 10 | · | IF `if` WERE USED: C1 would call popleft() on an empty deque | · | items=0 ✕ IndexError from an empty deque, in a consumer that was correctly notified about an item that genuinely existed. The stack trace points at the queue and the cause is three steps earlier in another task. |
while (!predicate) wait() is therefore the only correct shape — not a defensive extra, but the definition of using the primitive properly.What a condition variable does and does not promise
The most common design error after the if/while mistake is treating the condition variable as though it carried the data. It does not carry anything. It has no state, no memory and no queue of values. All the state lives in the variables the mutex protects; the condition variable is purely a parking area with a wake-up mechanism.
The second most common is notify versus notify_all. notify wakes one waiter and is correct when exactly one waiter can proceed per state change — one item added, one consumer woken. notify_all wakes everyone and is correct when the state change is relevant to all of them, such as closing the queue, or when several distinct predicates share one condition variable and you cannot tell which waiter to wake. Using notify where notify_all is needed produces a hang; using notify_all where notify suffices produces a thundering herd where N waiters wake, N−1 re-check, fail, and sleep again. See Thundering Herd.
| What people assume | What is actually true | What breaks if you assume wrongly |
|---|---|---|
wait() returns when the condition is true | It returns when it was *notified*, or spuriously. The condition may already be false again. | Popping from an empty queue. This is the if versus while bug. |
notify() wakes all waiters | It wakes one, chosen by the implementation. notify_all wakes all. | A close or shutdown signal reaches one waiter; the rest hang forever. |
| The notified waiter runs next | It becomes runnable and must still re-acquire the mutex. Any other task can take the lock first. | The item you notified about is gone when the waiter looks. Hence the loop. |
| Waiters are woken in arrival order | No ordering is promised by typical implementations; barging is normal. | Starvation of one waiter under sustained load. See Starvation. |
| The condition variable stores the signal | It stores nothing. A notify with no waiter is discarded entirely. | A lost wakeup: the state changed, nobody was waiting yet, and the notify evaporated. See Lost Wakeups: The Notify That Arrived Before the Wait. |
wait() can be called without the lock | It requires the lock held; calling without it is an error or undefined behaviour. | An immediate crash, or silent corruption in implementations that do not check. |
| The condition variable protects the state | The *mutex* protects the state. The condition variable only parks and wakes. | Reading the predicate outside the lock, which reintroduces every race in Reasoning About Races: A Method, Not an Instinct. |
Key points
- A condition variable is a waiting room attached to a mutex. It holds no state and carries no data; the mutex-protected variables hold everything.
- The shape is fixed: hold the lock,
while (!predicate) wait(), and on the signalling side change the state and notify while holding the same lock. wait()atomically releases the lock and sleeps, then re-acquires before returning. That atomicity is what prevents lost wakeups.- A notification is a hint that the state may have changed — never a promise that it is still changed when you look. Hence the loop, always.
notifywakes one waiter;notify_allwakes all. Usenotifywhen one waiter can proceed per change,notify_allwhen the change concerns everyone (shutdown) or when several predicates share one variable.- Use a separate condition variable per predicate where you can, so a notification wakes tasks that can actually proceed.
- Waiters are not queued fairly; barging is normal and a fresh arrival can take the item a waiter was just notified about.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • The waiter acquires the mutex and evaluates the predicate over the protected state.
- • If the predicate is false it calls
wait, which atomically adds the task to the condition variable's wait set and releases the mutex — no window exists between those two. - • A signaller acquires the same mutex, mutates the state so the predicate can become true, and calls
notifyornotify_allbefore or immediately after releasing. - • A notified task is moved from the wait set to the runnable set. It must then re-acquire the mutex, which may mean waiting behind the signaller and behind any barging task.
- •
waitreturns with the mutex held; the waiter re-evaluates the predicate and either proceeds or waits again.
- • Consumer waits on empty; producer appends and notifies; consumer wakes, re-checks, finds the item, takes it. The intended path.
- • Consumer waits; producer appends and notifies; a fresh consumer barges, takes the item; the notified consumer wakes, re-checks, finds empty, waits again. Correct only because of the loop.
- • With
ifinstead ofwhilein the same schedule: the notified consumer pops from an empty deque and raises, in code that was correctly notified about a real item. - • Producer notifies with no consumer waiting: the notification is discarded. If the consumer then checks the predicate before waiting, it sees the item and proceeds; if it checks outside the lock, it can miss both. See Lost Wakeups: The Notify That Arrived Before the Wait.
- • Four consumers wait;
close()callsnotifyinstead ofnotify_all: one consumer wakes and exits, three hang forever on a queue that will never receive another item. - • One condition variable shared by producers and consumers with
notify: a full-queue producer notifies and the wakeup lands on another producer, which re-checks, finds it still full, and sleeps. Nobody progresses until a consumer happens to be chosen. This is whynotify_allis required when predicates share a variable.
- • Guarantees that
waitreleases the mutex and blocks atomically, so no notification can be lost between the predicate check and the sleep — provided the check and the wait are both under the lock. - • Guarantees the mutex is held when
waitreturns. - • Does NOT guarantee the predicate is true on return. It may be false due to a spurious wakeup, a barging task, or several waiters competing for one item.
- • Does NOT guarantee that the notified waiter runs before any other task. It must re-acquire the mutex like everyone else.
- • Does NOT guarantee fairness or wake order among waiters.
- • Does NOT store notifications. A notify with no waiter is discarded, which is exactly the lost-wakeup mechanism.
- • Does NOT protect any state. That is the mutex's job, and reading the predicate outside the lock voids the whole construction.
- • All waiters on a condition variable contend for the same mutex when woken, so
notify_allwith many waiters produces a burst of lock acquisitions where all but a few fail their predicate and go back to sleep. - • That burst is a thundering herd in miniature: N wakeups, N lock acquisitions, N−1 useless predicate evaluations. Prefer
notifyplus per-predicate condition variables where the semantics allow. See Thundering Herd. - • The mutex hold time on the signalling side matters as much as anywhere else: notifying while holding the lock briefly delays the woken task, which is usually harmless, but doing real work while holding it delays every waiter.
- • A queue at its capacity limit means producers wait, which is backpressure working correctly rather than contention going wrong. See Backpressure.
- • Lost wakeup — the state changed and the notify was sent before anyone waited, so it was discarded and the waiter sleeps forever. See Lost Wakeups: The Notify That Arrived Before the Wait.
- • Spurious wakeup handled with
if— the waiter proceeds on a false predicate and operates on state that is not ready. See Spurious Wakeups: Why It Is `while`, Not `if`. - • Missed shutdown —
notifywherenotify_allwas needed, so one waiter exits and the rest hang. - • Predicate checked outside the lock, reintroducing a check-then-act race between the evaluation and the wait.
- • Deadlock from notifying while holding a second lock the woken task needs. See Lock Ordering.
- • Starvation of a particular waiter under barging, where a fresh arrival repeatedly takes the item a waiter was notified about.
- • Wakeup storm from
notify_allon a hot queue, where the cost of waking and re-checking exceeds the work being coordinated.
- • Whenever a task must wait for a *state condition* rather than for exclusive access — a bounded queue, a resource becoming available, an initialisation completing, a batch reaching a threshold.
- • When the alternative is polling. A condition variable replaces a sleep-and-check loop with an event-driven wake, removing both the latency of the polling interval and the CPU of the checks. See Busy Waiting.
- • When several distinct conditions apply to one piece of shared state and you want waiters parked separately per condition.
- • As the building block under a bounded queue — most standard blocking queues are exactly this construction. See Producer / Consumer.
- • When a ready-made blocking queue or channel exists. Hand-rolling this is a well-known source of subtle bugs and the standard library version is already correct. See Channels.
- • On a single-threaded async runtime, where the primitive to use is the runtime's async condition or simply an awaited promise; a blocking condition variable there stops the world.
- • When the wait should be bounded but is not — a
waitwith no timeout on a user-facing path can hang a request indefinitely if a notify is ever missed. - • When the coordination is really a one-shot readiness signal, where a latch or a resolved promise is simpler and wakes every waiter by construction. See Latches & Countdowns.
- • Queue depth over time, plus the count of tasks currently waiting on each condition. Persistently full means the consumers are undersized; persistently empty means the producers are.
- • Wait duration at p99 per condition variable. A waiter that never wakes shows as an unbounded maximum, which is the lost-wakeup signature.
- • Wakeups versus successful predicate evaluations. A large gap means
notify_allis waking tasks that cannot proceed — a herd worth fixing. - • A thread dump during a hang: tasks parked in
waiton a named condition, with the queue observably non-empty, is a lost wakeup or a missingnotify_all. See Reading a Thread Dump. - • Always give production waits a timeout and count the timeouts. A non-zero timeout count is a bug report from the code itself.
- • Three interacting pieces — mutex, predicate, condition variable — must all be correct together, and the failure from getting any of them wrong is a hang rather than an exception.
- • The number of condition variables and which predicate each carries is a design decision that must be documented, because a later
notifyon the wrong one produces a hang with no stack trace pointing at the mistake. - • Shutdown is a separate design problem: every waiter must be woken and must distinguish "the state changed" from "we are closing", which is why the
closedflag appears in both predicates above. - • Timeouts add a third outcome to every wait — proceeded, timed out, or closed — and each needs a caller-side decision.
- • A standard blocking queue or channel, which is this construction already written and tested. Prefer it unless you need a predicate the library cannot express. See Concurrent Queues and Channels.
- • A semaphore, when the condition really is a count of available items rather than an arbitrary predicate. Simpler, and the count is the state. See Semaphores: Counting Permits as a Resource Limit.
- • A latch or event for one-shot readiness, which wakes every waiter and stays set for late arrivals. See Latches & Countdowns.
- • An async future or promise on a single-threaded runtime, where awaiting the value is the whole mechanism and no lock is involved. See Futures & Promises.
- • Polling with a sleep, when the wait is rare, the latency budget is loose and simplicity matters more than either. It is worse on both axes and it is honest to name it as an option. See Busy Waiting.
wait() in an if, or wait() in a while
lock()
if (items == 0): # checked once, before sleeping
cond.wait(lock) # releases the lock, sleeps, reacquires
take(item) # <- assumes the predicate is still true
unlock()| # | Producer | Consumer 1 | Consumer 2 | Runtime | State |
|---|---|---|---|---|---|
| 1 | · | lock(); if (items == 0) wait() | · | · | items=0 waiters=1 |
| 2 | · | · | lock(); if (items == 0) wait() | · | items=0 waiters=2 |
| 3 | lock(); items = 1; notifyAll(); unlock() | · | · | · | items=1 waiters=0 |
| 4 | · | proceed: take(item) | · | · | items=0 waiters=0 |
| 5 | · | · | proceed: take(item) | · | items=-1 waiters=0 ✕ two consumers took one item — items = -1 |
Producers, a bounded queue, consumers
The producer is faster than the consumer
What people believe, and what is true
When wait() returns, the condition is true.
It returns because it was notified, or spuriously. Another task may have consumed the state in between. Re-check in a loop, always.
notify() wakes all the waiters.
It wakes one. Using it for a shutdown signal leaves every other waiter hanging forever.
The condition variable holds the item or the signal.
It holds nothing. A notify with no waiter is discarded entirely — which is precisely how lost wakeups happen.
I can check the predicate before taking the lock to make it faster.
That reintroduces the check-then-act gap between the check and the wait, which is the lost-wakeup bug in its most common form.
Go deeper
Overview
Wait until something becomes true, without spinning. Another task changes the state and says "look again".
Practical
Always: hold the lock, while (!predicate) wait(), and change-state-then-notify under the same lock. Separate condition variables per predicate, notify_all for state changes that concern everyone.
Advanced
A notification is a hint. Between the notify and the waiter running, any task may acquire the lock and undo the condition. Design for that rather than around it, and give production waits a timeout so a missed notify surfaces as a counted event instead of a hang.
Internals
The atomic release-and-sleep is the whole trick, and it is why a condition variable must be paired with a specific mutex: the implementation needs to enqueue the waiter and drop the lock without a window in between. Underneath it is typically a futex wait on the condition's sequence counter, with the mutex handed back on wake. See Lost Wakeups: The Notify That Arrived Before the Wait for what the window would cost if it existed.