Condition Variables

How a thread sleeps until shared state changes: the wait protocol, why the wait sits in a while loop, lost and spurious wakeups shown in running code, notify versus notify-all, and Java monitors versus Condition objects.

Overview

A condition variable lets a thread sleep until some shared state becomes true: the buffer is not empty, the job is done, it is my turn. It is always used with a lock. The thread holds the lock, checks the state, and if it has to wait, calls wait(), which releases the lock and puts the thread to sleep in one atomic step. Another thread takes the lock, changes the state, and calls notify to wake a waiter, which re-acquires the lock before wait() returns.

The alternative is polling: loop, check, sleep a little, check again. Polling either burns CPU (short sleeps) or reacts late (long sleeps). A condition variable wakes the waiter when something changed and costs nothing while it sleeps.

Busy loop on a flag — A full core — Immediate — Needs atomics or volatile; burns power
Loop with sleep — Low — Up to one sleep interval late — Easy, but always late or wasteful
Condition variable — None — As soon as a notify happens and the lock is free — The wait protocol below must be followed exactly

The wait protocol

Both sides follow a fixed recipe, and every bug in this area is a step skipped.

The state lives in ordinary variables, protected by the lock — The condition variable has no memory; it only wakes threads
Check the state before waiting, under the lock — A notify sent before you wait is lost, and you sleep forever
Wait in a while loop, not an if — You act on a state that is no longer true (next section)
Change the state under the same lock, then notify — The waiter can check, miss the change, and sleep through the notify
A woken thread re-acquires the lock before wait() returns — Nothing to do; this is why the loop's re-check is safe

Python's docs note that notify does not release the lock: the woken thread returns from wait() only when the notifier lets go.

Why the loop: two ways to wake with nothing to do

Waking up does not mean the state is ready. Two things cause it.

Another thread got there first. A consumer is woken because an item arrived, but between the notify and re-acquiring the lock, a different consumer that never slept takes the item.
Spurious wakeups. POSIX, Java's Object.wait and Java's Condition all allow wait to return with no notify at all, and all three say to wait in a loop. Python's docs also require the loop, for a related reason: wait can return a long time after the notify, when the condition that prompted it may no longer hold.

A trace of case 1 with an if.

1 — empty: waits (lock released) — []
2 — puts x, notifies C1 — [x]
3 — woken, queued for the lock — takes the lock first, takes x — []
4 — gets the lock; with if, pops from an empty buffer — error
4' — with while, sees empty, waits again — []

The program below forces the situation: the consumer is woken once with no item, then the item arrives. The if version goes ahead with nothing; the while version goes back to sleep and gets the item. The last lines show the other half of the protocol: a notify with nobody waiting is lost, but a check of the state is not.

wait_for(predicate) is Python's built-in form of the loop: it re-checks the predicate after every wakeup and returns its last value, which is False on timeout.

One condition or several

A condition variable is a queue of sleeping threads. When different threads wait for different things (producers for space, consumers for items), they can share one queue or each have their own.

Java — The object's monitor: synchronized with wait / notifyAll — ReentrantLock with several newCondition(); the Condition docs describe this as multiple wait sets per object
Python — One Condition — Several Condition objects built on the same Lock
Which notify — Must use notify-all: a single notify may wake a thread of the wrong kind, which goes back to sleep, and the right one never wakes — A single notify / signal is enough when one state change lets exactly one waiter proceed
Cost — Every waiter wakes and re-checks — Only the threads that can use the change wake

What you will be able to do

Write the wait protocol: lock, loop on the state, wait, act; and on the other side lock, change, notify.
Explain spurious wakeups and stolen wakeups, and why while fixes both.
Explain the lost wakeup and why the state, not the signal, is the source of truth.
Choose between notify and notify-all, and between one condition and several.
Implement a bounded buffer and a turn-taking protocol with conditions.

Interview questions

What is a condition variable and how does it work?
Why must you wait in a while loop instead of an if?
What is the difference between notify() and notifyAll(), and which should you use?
How do Java monitors (wait/notify) differ from Lock and Condition?
Condition variable, semaphore or event: which do you use?