The question this answers
Why does a task wait forever for a condition that is already true, and what exactly must be under the lock to prevent it?
A worker task waiting for jobs on a shared queue, and a producer that enqueues one job and notifies — with the worker checking queue.isEmpty() outside the lock as a "fast path optimisation".
The queue and its length, guarded by a mutex; the condition variable attached to that mutex. The condition variable itself holds no state, which is the entire point of this lesson.
If the queue is non-empty, at least one worker is either running or about to be woken — no worker sleeps while work is available.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The window, and what falls into it
Every lost wakeup has the same anatomy: a gap between deciding to wait and actually being registered as a waiter. If the state change and the notification both happen inside that gap, the notification finds an empty wait set and is thrown away — because a condition variable is not a queue, not a counter and not a mailbox. It is a set of currently parked tasks and a way to wake them. A notify with nobody parked is a no-op.
The gap comes from exactly one thing: evaluating the predicate outside the lock that guards the state it reads. The "optimisation" is seductive and appears in code review constantly — checking queue.isEmpty() without locking looks free, and on the happy path it is. What it actually does is split the check and the wait into two separate atomic actions with a window between them, which is the check-then-act shape from Reasoning About Races: A Method, Not an Instinct applied to the act of going to sleep.
The trace below is that window doing its work. Note that the worker never does anything stupid: it checks, finds nothing, and waits. The producer never does anything stupid either: it enqueues and notifies. The two are individually correct and the system hangs with a job sitting in a non-empty queue.
| # | Worker — waiting for a job | Producer — enqueues one job | State |
|---|---|---|---|
| 1 | check queue.isEmpty() → true [NO LOCK HELD] | · | queue=0 waiters=0 lock=free |
| 2 | · | acquire lock; queue.push(job-1) | queue=1 waiters=0 lock=P |
| 3 | · | cond.notify() — wait set is EMPTY, notification discarded | queue=1 waiters=0 lock=P ✕ The notification is gone. It was not buffered, not counted, not queued — the condition variable had no waiters, so there was nothing to wake and no record kept. |
| 4 | · | release lock; producer exits | queue=1 waiters=0 lock=free |
| 5 | acquire lock; cond.wait() — parks on the (now stale) decision | · | queue=1 waiters=1 lock=free ✕ The worker is asleep. The queue holds one job. No further notification will ever be sent, because the producer has already run. |
| 6 | ...forever... | · | queue=1 waiters=1 |
| 7 | · | FIX: check the predicate INSIDE the lock, in a while loop | queue=1 waiters=0 |
| 8 | acquire lock; while (queue.isEmpty()) → false; take job-1 | · | queue=0 waiters=0 |
What must be under the lock
The rule is short and admits no exceptions: the predicate check and the `wait` must be in the same critical region, and the state change and the `notify` must be under the same lock. wait releasing the mutex atomically is what closes the window on the waiting side — there is no instant at which the task has decided to sleep but is not yet registered.
The signalling side has a softer rule that is worth stating precisely, because it is a common source of over-cautious code. The *state change* must be under the lock, without exception. The notify itself may be issued after releasing, and some implementations perform marginally better that way because the woken task does not immediately block on a mutex the signaller still holds. But notifying after release opens no window as long as the state change was locked, because the waiter re-checks the predicate under the lock and will see the new state. Notifying while holding is simpler to reason about and is the right default.
The pair below is the whole lesson in code. What makes the bad version so persistent in real codebases is that it usually starts life as the good version, and the unlocked pre-check is added later by someone profiling lock acquisition.
1std::mutex m;2std::condition_variable cv;3std::deque<Job> queue;4 5void worker() {6 for (;;) {7 if (queue.empty()) { // <-- UNLOCKED read. The window opens here.8 std::unique_lock lk(m); // Between these two lines the producer9 cv.wait(lk); // can push AND notify, and the notify10 } // is discarded because nobody is parked.11 std::unique_lock lk(m);12 if (queue.empty()) continue;13 Job j = std::move(queue.front()); queue.pop_front();14 lk.unlock();15 run(j);16 }17}18 19void producer(Job j) {20 { std::lock_guard lk(m); queue.push_back(std::move(j)); }21 cv.notify_one();22}23 24// Two independent bugs in one function:25// 1. the unlocked queue.empty() is also a DATA RACE - unsynchronized read26// concurrent with the producer's write. In C++ that is undefined27// behaviour, not merely a stale value. See [[data-races]].28// 2. the check and the wait are not atomic, so a notify in between is lost.29// Removing (1) by locking the pre-check does not remove (2) unless the lock30// is HELD CONTINUOUSLY from the check into the wait.1void worker() {2 for (;;) {3 std::unique_lock lk(m); // acquired ONCE4 cv.wait(lk, [&]{ return !queue.empty() || done; });5 // ^ the predicate overload is exactly:6 // while (!pred()) cv.wait(lk);7 // checked under the lock, before waiting and after every wake.8 if (done && queue.empty()) return;9 Job j = std::move(queue.front()); queue.pop_front();10 lk.unlock(); // release BEFORE the slow part11 run(j); // outside the region - see [[lock-scope]]12 }13}14 15void producer(Job j) {16 { std::lock_guard lk(m); queue.push_back(std::move(j)); } // state change: LOCKED17 cv.notify_one(); // notify after release: fine, because18} // the waiter re-checks under the lock.19 20void shutdown() {21 { std::lock_guard lk(m); done = true; }22 cv.notify_all(); // concerns EVERY waiter -> notify_all23}24 25// There is no window: the worker holds the lock from the moment it evaluates26// the predicate until wait() atomically releases it and parks. A producer27// cannot push between those two events, because pushing requires the lock.The good version never releases the lock between evaluating the predicate and parking — wait performs the release atomically as part of registering the waiter. That single property is what makes a lost wakeup impossible. The bad version's unlocked pre-check buys one avoided lock acquisition on the happy path (tens of nanoseconds) and pays for it with a hang under load, plus a data race that is undefined behaviour in C++ regardless of the timing.
What it looks like in production
Lost wakeups are diagnosed from a thread dump, not from logs, because there is nothing to log. The characteristic artefact is a set of workers parked in wait alongside a metric showing the queue is not empty — a contradiction that the invariant forbids and that immediately narrows the cause to one of two things: a missed notification, or a notify where notify_all was needed.
The dump below is what that looks like. Note the two supporting signals: queue depth is flat and non-zero, and the last dequeue timestamp is old. Neither alone is conclusive; together with parked workers they are close to a proof. The same evidence distinguishes this from a deadlock, where you would see threads blocked on a *monitor* with an identifiable owner rather than parked in a condition wait with none.
The prevention that pays for itself is a timeout on every production wait, paired with a counter. A wait_for that returns "timed out" and then re-checks the predicate turns a permanent hang into a bounded-latency recovery *and* emits a metric that says the bug exists. It does not fix the lost wakeup — the predicate loop does that — but it converts a silent, unbounded outage into a counted, survivable one, which is the right posture for a failure whose window you can never fully test.
$ jstack 3117 (excerpt) wall clock 03:41:07
"worker-1" #21 prio=5 tid=0x... nid=0x5a03 in Object.wait() [0x00007f...]
java.lang.Thread.State: WAITING (on object monitor)
at java.lang.Object.wait(Native Method)
- waiting on <0x000000076ab21f30> (a JobQueue)
at com.acme.JobQueue.take(JobQueue.java:44)
at com.acme.Worker.run(Worker.java:19)
"worker-2" #22 ... WAITING (on object monitor) - same monitor, same line
"worker-3" #23 ... WAITING (on object monitor) - same monitor, same line
"worker-4" #24 ... WAITING (on object monitor) - same monitor, same line
NOTE: WAITING (on object monitor) with no owner listed = parked in wait().
BLOCKED (on object monitor) with "owned by ..." = deadlock/contention.
The distinction is the whole diagnosis.
$ curl -s localhost:9090/metrics | grep job_queue
job_queue_depth 3
job_queue_enqueued_total 18421
job_queue_dequeued_total 18418
job_queue_last_dequeue_age_s 4127 # 68 minutes since anything was taken
diagnosis
4 workers parked in wait() )
queue depth 3, stable, non-zero )-> the invariant "queue non-empty implies
no dequeue for 68 minutes ) a worker is running" is false.
no errors, no exceptions, no retries
Two candidate causes, both in this family:
(a) notify() sent while the wait set was empty -> discarded [this lesson]
(b) notify() used where notify_all() was needed -> 1 of 4 woken, 3 still parked
Distinguish by reading the producer: is the predicate checked under the
same lock as the state change, and does shutdown/close use notify_all?
Why nothing alerted: error rate 0, latency of COMPLETED jobs normal, CPU
near zero. Every RED-style dashboard looks healthy. The signal that would
have fired is job_queue_last_dequeue_age_s, and almost nobody graphs it.
CAVEAT (ILLUSTRATIVE): dump text is representative of the artefact's shape,
not a capture from a specific incident.Key points
- A condition variable stores nothing. A
notifywith an empty wait set is discarded — not buffered, not counted, not delivered later. - The window is the gap between deciding to wait and being registered as a waiter. It opens whenever the predicate is evaluated outside the lock.
- The rule: hold the lock continuously from the predicate check into
wait.waitreleases it atomically as part of registering, so no window exists. - On the signalling side the *state change* must be under the lock. The
notifyitself may be issued after releasing, because the waiter re-checks under the lock. - An unlocked "fast path" pre-check is the single most common cause, and in C++ it is a data race as well as a lost wakeup.
- The symptom is a hang with no error: queue depth flat and non-zero, workers parked, CPU near zero, every error dashboard green.
- A timeout on every production wait converts a permanent hang into a counted, bounded-latency event. It is mitigation, not a fix.
- The other cause of the same symptom is
notifywherenotify_allwas needed. Check both.
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 evaluates the predicate. If the check happens outside the lock, the value it obtains is a fact about the past.
- • Between that evaluation and the call to
wait, the signaller may acquire the lock, change the state, and notify. - • The notification looks for parked tasks on the condition variable's wait set. It is empty, because the waiter has not registered yet. The notification is discarded with no record.
- • The waiter then calls
waitand parks, based on a predicate value that is now stale. - • No further notification arrives, because the state change that would have triggered one has already happened. The waiter sleeps until the process restarts.
- • Unlocked check → producer pushes and notifies → waiter parks. The job sits in the queue forever. The canonical lost wakeup.
- • Locked check in a
whileloop → the producer cannot push between the check and the park, because pushing needs the lock. No window exists. - • Locked check, producer pushed *before* the waiter arrived: the waiter acquires the lock, evaluates the predicate, finds the queue non-empty, and never waits. Correct without any notification at all.
- • Four waiters, shutdown signalled with
notifyinstead ofnotify_all: one wakes and exits; three remain parked forever. Same symptom, different cause. - • State changed outside the lock, notify sent under it: the waiter can evaluate the predicate before the change is visible and park anyway. Locking the notify does not help if the state change is unlocked.
- • With
wait_for(500ms)in a loop: the wakeup is still lost, but the waiter re-checks after 500 ms, finds the job and processes it. Latency spike instead of a hang, and a timeout counter that says the bug is there.
- •
waitguarantees the mutex is released and the task registered atomically — there is no instant in which it has committed to sleeping but is not yet visible to a notifier. - • That guarantee applies only from the moment
waitis called. Everything you did before calling it, including a predicate check, is outside it. - • A condition variable guarantees nothing about notifications sent when no task is waiting. They are discarded by design.
- •
notifyguarantees at most one waiter is woken. It does not guarantee which one, and it does not guarantee any if the set is empty. - • A timeout guarantees the waiter eventually re-evaluates the predicate. It does not guarantee the notification is delivered, and it does not make the code correct — the predicate loop does that.
- • Nothing guarantees the predicate is still true when the woken task re-acquires the lock, which is why the loop is required regardless. See Spurious Wakeups: Why It Is `while`, Not `if`.
- • The unlocked pre-check exists to avoid a lock acquisition, which costs tens of nanoseconds uncontended. That is the entire benefit being traded for a hang.
- • If lock acquisition on the queue really is a bottleneck, the answer is sharding the queue or batching the dequeue, not skipping the lock on the wait path.
- • A timeout-based wait loop adds periodic wakeups proportional to waiter count divided by the timeout. With four workers and a 500 ms timeout that is eight wakeups per second — negligible, and cheap insurance.
- • Holding the lock while notifying briefly delays the woken task, which is normally irrelevant; the pathological case is notifying while holding a second, heavily contended lock.
- • Lost wakeup — a permanent hang with a non-empty queue and no error of any kind.
- • Partial hang from
notifywherenotify_allwas required, which looks identical from the outside and has a different fix. - • Data race on the unlocked predicate read, which in C++ is undefined behaviour independent of the timing. See Data Race Is Not Race Condition.
- • Deadlock misdiagnosis — the team looks for a cycle that does not exist, because a parked waiter looks superficially like a blocked one in a dump.
- • Silent throughput collapse: workers are lost one at a time as each hits the window, so the pool degrades over hours and the service looks merely slow.
- • Recovery-by-restart, which "fixes" it and destroys the evidence, so the bug survives many incidents before anyone captures a dump.
- • Understanding this is what makes the "check under the lock" rule non-negotiable rather than stylistic, which is the difference between a rule that survives review and one that gets optimised away.
- • It gives a precise reading of a thread dump: parked waiters plus a non-empty queue has two candidate causes and no others.
- • It justifies the timeout-plus-counter pattern on every production wait, which is cheap and converts an unbounded outage into a bounded one.
- • The knowledge invites over-correction: notifying while holding several locks, notifying on every state change, or using
notify_alleverywhere. Each has its own cost, and the herd from a blanketnotify_allis real. See Thundering Herd. - • Timeouts are mitigation and are sometimes mistaken for the fix. A wait loop with a timeout and a broken predicate check is still broken; it just hangs for 500 ms at a time.
- • Chasing a lost wakeup when the actual bug is
notifyversusnotify_allwastes time. Read the shutdown path first — it is the more common of the two.
- • Queue depth together with the age of the last successful dequeue. Depth alone is ambiguous; depth plus a stale dequeue timestamp is the signature.
- • Count of tasks currently parked on each condition variable, exported as a gauge. Parked workers plus non-empty queue is the contradiction that names the bug.
- • Thread or async task dumps captured automatically on a health-check failure, so the evidence survives the restart that hides it. See Reading a Thread Dump and Task Dumps: When the Threads Look Idle and Nothing Is Moving.
- • Timeout counters on every wait. A non-zero count is the code reporting its own defect, and it appears long before a hang does.
- • Notify count versus wake count. A notify issued with an empty wait set is a discarded notification, and instrumenting that ratio directly detects the window.
- • The correctness argument is subtle and lives entirely in the ordering of three operations, none of which looks important in isolation — which is why the unlocked pre-check keeps being reintroduced.
- • Timeout-based waits add a third outcome to every wait and a periodic wakeup cost that must be budgeted.
- • Shutdown becomes a separate design concern, because it is the case where
notify_allis mandatory and where a lost wakeup hangs the process at exit rather than at runtime. - • The mitigation and the fix are different changes, and shipping only the mitigation leaves a latent bug behind a 500 ms latency spike.
- • Use a standard blocking queue or channel instead of hand-rolling the wait. The library version has this bug already fixed and tested. See Concurrent Queues and Channels.
- • Use a semaphore when the condition is a count: permits are *stored*, so a release before any acquire is banked rather than discarded. This structurally cannot lose a wakeup. See Semaphores: Counting Permits as a Resource Limit.
- • Use a latch or event for one-shot readiness: it stays set, so a late waiter sees the signal instead of missing it. See Latches & Countdowns.
- • Use an awaited future on a single-threaded runtime, where resolution is remembered and awaiting an already-resolved promise completes immediately. See Futures & Promises.
- • Where the coordination is between processes, use the queueing system's own delivery semantics rather than any in-process primitive. See Message Passing.
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 lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
What people believe, and what is true
The notification will be delivered when the waiter arrives.
It will not. A condition variable has no buffer. A notify with an empty wait set is discarded with no record that it ever happened.
Checking the predicate before locking is a harmless optimisation.
It creates the window that loses the wakeup, and in C++ the unlocked read is also a data race and therefore undefined behaviour.
Adding a timeout fixes it.
It bounds the damage and gives you a metric. The wakeup is still lost; the code recovers by polling. Fix the predicate check as well.
It must be a deadlock — the threads are stuck.
A dump distinguishes them: parked in a condition wait with no monitor owner is a lost wakeup or a missing notify_all; blocked on a monitor with a named owner is contention or deadlock.
Go deeper
Overview
The signal arrived before anyone was listening, so it was thrown away, and the listener waits forever for a signal that already came.
Practical
Hold the lock continuously from checking the predicate into wait. Change state under the lock before notifying. Use notify_all for changes that concern every waiter. Add a timeout and a counter to every production wait.
Advanced
Two distinct causes produce the same dump: a discarded notification, and notify where notify_all was needed. Read the producer for the first and the shutdown path for the second. Alert on last-dequeue age, not on error rate — nothing errors.
Internals
The atomicity of release-and-park is why the primitive can be correct at all: the implementation enqueues the waiter on the condition's wait set and drops the mutex as one operation, typically via a futex wait keyed on a sequence counter. Any userland reimplementation that releases the lock and then parks has re-created the window in the primitive itself.