Condition variables need a predicate loop
Explain the condition-variable predicate loop with two consumers, a stolen item and an atomic unlock-and-wait boundary.

A condition variable lets a thread sleep until shared state may have changed. The thread must recheck that state after waking while holding the associated mutex. If you write a blocking queue, the predicate is something like the queue being nonempty; the notification itself is not permission to remove an item.
The OSTEP condition-variable chapter makes the state predicate central to the design. Waiting combines releasing the mutex with joining the wait mechanism. Returning from the wait reacquires the mutex, so the thread can examine a coherent state before acting.
A notification can arrive before another consumer wins
Consider consumers A and B and one producer. A holds the mutex, finds the queue empty and waits. Waiting releases the mutex. The producer acquires it, adds job 7, releases it and notifies a waiter.
Before A reacquires the mutex, B gets the mutex and removes job 7. B releases the mutex. A finally resumes with the mutex held, but the queue is empty again. Its wakeup was legitimate: the producer really added work. That fact did not reserve the work for A.
| Event | Queue state | Consumer A |
|---|---|---|
| A checks | Empty | Enters wait |
| Producer enqueues 7 | One item | Eligible to wake |
| B acquires mutex | Empty after B pops | Still waiting to reacquire |
| A reacquires mutex | Empty | Must check again |
This schedule is sufficient to require a loop even without a spurious wakeup. Some condition-variable interfaces also permit spurious wakeups, which provide another reason to recheck. The robust rule comes from the predicate: proceed only while holding the mutex and observing the condition that makes the operation valid.
Express the predicate directly
This C++ fragment shows a queue with a shutdown flag. The state objects must outlive all waiting threads, and every access to the queue and flag follows the same mutex discipline.
std::unique_lock<std::mutex> lock(queue_mutex);
queue_changed.wait(lock, [&] { return closed || !jobs.empty(); });
if (jobs.empty()) {
return false; // closed and drained
}
int job = jobs.front();
jobs.pop_front();
The C++ predicate overload behaves as a loop around waiting. A wakeup that leaves both conditions false leads to another wait. When the function returns from wait, the mutex is held. The consumer can check whether it should stop or remove an item without another queue operation changing the state between those steps.
The shutdown flag is part of the waiting predicate because a consumer must also wake when no more jobs will arrive. A thread closing the queue changes the flag under the mutex and notifies all relevant waiters. Otherwise a consumer can remain asleep forever after the producer has stopped.
The return policy here drains queued jobs before reporting closure: if closed is true but jobs remain, the consumer still removes one. An immediate-stop policy would check closed first. Both can be valid, but producers and callers need one explicit contract.
The check-and-sleep gap must be closed
Suppose a custom implementation checks an empty queue, unlocks the mutex and only later registers itself as sleeping. A producer can enqueue and signal during that gap. If the signal has no registered waiter, the consumer can then sleep despite available work.
A condition variable’s wait operation addresses this race by making the release-and-wait transition atomic with respect to the synchronization protocol. The producer still changes the predicate under the mutex. Without that shared lock discipline, the code can create another race between the state check and the state update.
A notification is not generally stored as a token for the next future waiter. If the producer changes the state before any consumer waits, a later consumer observes the state under the mutex and skips waiting. Correctness follows from retained shared state, not from remembering an earlier notification.
That is a useful distinction from a semaphore, whose permit count has its own retained meaning. Replacing one primitive with the other requires a new state model. Similar-looking wait and signal function names do not guarantee interchangeable behavior.
Notify one or notify all according to the predicate
Adding one job can justify notifying one consumer if every consumer waits for the same kind of work. Closing the queue usually requires notifying all consumers because every waiter must reconsider whether it should exit. Heterogeneous predicates can require more care: waking a thread whose predicate remains false may leave another eligible thread asleep.
Notification can often happen after unlocking, provided the predicate change was protected and the object remains alive. Doing so can reduce immediate contention for the mutex, but correctness and object lifetime come first. Some APIs or application protocols impose additional requirements, so follow the chosen interface’s contract.
Timeouts also return the thread to the predicate. A timeout and a producer update can race near the deadline. Decide whether the operation may consume work that is present when it reacquires the lock or must enforce a strict external deadline. Use a stable absolute deadline when repeated waits must share one budget; restarting a full relative timeout after each wake can extend the total wait unexpectedly.
For tests, orchestrate the two-consumer schedule in the table and close the queue while several consumers are waiting. Test a notification before the first wait as well. A correct implementation handles all three through the same state predicate, without assuming that waking means an item belongs to the current thread.
Implement and test an explicit drain policy
The following standalone Python example accepts integer jobs and uses None only for the closed-and-drained result. It deliberately leaves capacity management out so the waiting predicate stays visible. Python’s condition-object documentation specifies that wait_for repeatedly tests its predicate with the lock held and that notification does not itself release the lock.
from collections import deque
from threading import Condition, Thread
class WorkQueue:
def __init__(self):
self._jobs = deque()
self._closed = False
self._changed = Condition()
def put(self, job):
if type(job) is not int:
raise TypeError("this example accepts integer jobs")
with self._changed:
if self._closed:
raise RuntimeError("queue is closed")
self._jobs.append(job)
self._changed.notify()
def get(self):
with self._changed:
self._changed.wait_for(
lambda: self._closed or bool(self._jobs)
)
if not self._jobs:
return None
return self._jobs.popleft()
def close(self):
with self._changed:
self._closed = True
self._changed.notify_all()
queue = WorkQueue()
consumed = []
def consume():
while True:
job = queue.get()
if job is None:
return
consumed.append(job)
worker = Thread(target=consume)
worker.start()
queue.put(7)
queue.close()
worker.join()
assert consumed == [7]
assert queue.get() is None
try:
queue.put(8)
except RuntimeError:
pass
else:
raise AssertionError("put after close was accepted")
This program has one consumer, so only that consumer appends to the result list; the main thread reads the list after joining it. There is no timing delay. The producer may add the item before the consumer first waits, or the consumer may already be asleep. The retained queue state makes both orders work. The program checks the contract without claiming to force either scheduler choice.
There are four relevant combinations, as the second figure shows. Closing a nonempty queue does not discard work in this API. A consumer continues removing existing jobs, then observes None only after the queue is empty. Once closed, the queue cannot reopen and put fails under the same lock, so a consumer cannot see terminal closure followed by a newly accepted job. Repeated close calls are harmless here and notify the current waiters again.
To vary the exercise, enqueue two jobs and close the queue before starting the consumer. Expect both jobs in FIFO order and then termination. This specifically exercises notifications that occur before waiting begins. Next start several consumers and close an empty queue: all must be allowed to finish, which is why closure uses notify_all. Check aggregate job identities rather than expecting a particular consumer to receive a particular job; mutex reacquisition order is not a distribution contract.
A finite successful run cannot prove every wakeup interleaving correct. The proof is the guarded state table: each consumer acts only after observing an allowed state while it owns the lock, and each transition that may satisfy a waiting predicate notifies the relevant waiters. In a timed test, distinguish a real queue failure from a test harness that stopped scheduling its workers. Thread lifetime, cancellation and resource cleanup remain part of the surrounding application’s shutdown design.