Condition Variables and Predicate-Based Waiting

Condition variables solve one problem: a thread needs to wait until some fact about shared data becomes true (“the queue isn’t empty”, “all three services are ready”, “the buffer has room”), and it shouldn’t burn a CPU checking in a loop while it waits. The API is small, a wait and a notify, but almost every bug people write with it comes from misunderstanding what a condition variable is. It isn’t the condition. It’s a waiting room attached to a mutex. The condition is a predicate over your own data, and you must check it yourself.

The pattern, and why each part is there

Every correct use looks like this, in any language:

waiter:                          changer:
  lock(m)                          lock(m)
  while not predicate():           change the shared state
      wait(cv, m)                  notify(cv)   or notify_all(cv)
  act on the state                 unlock(m)
  unlock(m)

wait(cv, m) does three things: it releases the mutex, puts the thread to sleep on the condition variable, and when woken, reacquires the mutex before returning. The release and the sleep happen atomically, which is what prevents a changer from slipping in between “I checked” and “I’m asleep”. Because the waiter holds the mutex when wait returns, it can recheck the predicate safely.

Each piece of the pattern prevents a specific failure, and all three are easy to reproduce. The experiments below ran on Python 3.14 on macOS, where threading.Condition wraps a lock and implements exactly this protocol.

Why if breaks: the stolen wakeup

Two consumers wait for items. A producer adds one item and calls notify_all. Both consumers wake, but only one item exists. With if not items: cond.wait(), each consumer assumes that being woken means an item is waiting for it:

def consumer(name):
    with cond:
        if use_while:
            while not items:
                cond.wait()
        else:
            if not items:
                cond.wait()
        try:
            results.append(f"{name} got {items.pop(0)}")
        except IndexError as e:
            results.append(f"{name} crashed: IndexError: {e}")

if    ['c1 got job-1', 'c2 crashed: IndexError: pop from empty list']
while ['c1 got job-1', 'c2 got job-2']

The first consumer to reacquire the lock took the item. The second returned from wait into a world where the predicate was false again. With while, it rechecked, found the list empty and went back to sleep until the producer added a second job.

That’s the main reason for the loop: a wakeup means “the state changed, look again”, not “the thing you want is yours”. Another thread can always run first, even with plain notify, because a third thread can grab the lock between the notify and the woken thread getting it. POSIX adds a second reason: pthread_cond_wait is allowed to return with no notify at all (a spurious wakeup), and Java’s Object.wait documentation says the same. The loop handles both, so there’s never a reason to write if.

Lost wakeups: checking outside the lock

A condition variable remembers nothing. If you notify when nobody is waiting, the notification vanishes. That’s fine when waiters check the predicate under the lock, because they’ll see the new state. It breaks when the check happens outside the lock:

def consumer():
    if not items:                    # predicate read WITHOUT the lock
        time.sleep(0.1)              # widen the window between check and wait
        with cond:
            woke = cond.wait(timeout=2)
            print("consumer woke by notify" if woke else "consumer timed out: the notify was lost")
    print("items:", items)

def producer():
    time.sleep(0.05)
    with cond:
        items.append("job-1")
        cond.notify()
        print("producer notified at t=0.05s, nobody was waiting yet")

producer notified at t=0.05s, nobody was waiting yet
consumer timed out: the notify was lost
items: ['job-1']
elapsed 2.11s

The consumer saw an empty list, the producer added an item and notified an empty waiting room, and then the consumer went to sleep with an item sitting right there. The sleep just makes the gap visible; in real code the scheduler creates the same gap at random. Without the timeout this consumer would sleep forever. Python refuses the most blatant version: calling wait without holding the lock raises RuntimeError: cannot wait on un-acquired lock. C won’t stop you, and the changer side has the same rule: modify the shared state while holding the mutex, or a waiter can check, miss your change, and sleep through your notify.

This is the deepest difference from a semaphore. A semaphore counts posts, so a post with no waiter is saved for later. A condition variable relies entirely on the predicate in your data to carry that information.

notify or notify_all, and the one-variable deadlock

notify wakes one waiter; notify_all wakes them all. notify is cheaper, but it’s only safe when any waiter can make use of the change. OSTEP describes a bounded buffer that goes wrong when producers and consumers share one condition variable, and Python reproduces it exactly. The buffer holds one item; two consumers start waiting before one producer begins:

notify    : C1 waits (empty) | C2 waits (empty) | P put 0 | P waits (full) | C1 took 0 | C1 waits (empty) | C2 waits (empty)
            still blocked after 1s: ['P', 'C1', 'C2']
notify_all: C1 waits (empty) | C2 waits (empty) | P put 0 | P waits (full) | C1 took 0 | C1 waits (empty) | C2 waits (empty) | P put 1 | P waits (full) | C1 took 1 | C2 waits (empty) | P put 2 | P waits (full) | C2 took 2 | C2 waits (empty) | P put 3 | C2 took 3
            still blocked after 1s: none

Trace the first line. The producer’s notify wakes C1, then the producer finds the buffer full and waits. C1 takes the item and notifies, intending to wake the producer. But the waiting room holds C2 and the producer, and Python wakes the longest waiter, C2. C2 finds the buffer empty and waits again. Nobody is left to wake anybody, and all three threads sleep forever, every while loop correct.

There are two fixes. notify_all works, at the cost of waking threads that will just go back to sleep. The better design uses two condition variables on the same mutex, one for “not empty” (consumers wait on it, producers notify it) and one for “not full” (the reverse), so a notify always reaches a thread that can act. Python’s own queue.Queue is built exactly this way: one mutex with not_empty and not_full conditions.

Timeouts and helpers

Real code rarely waits forever. wait(timeout) returns False on timeout in Python (POSIX returns ETIMEDOUT from pthread_cond_timedwait). The trap is resetting the full timeout each time the loop goes round, which lets a stream of unhelpful wakeups extend a two-second wait indefinitely. Compute a deadline once and wait for the remaining time. Python’s wait_for(predicate, timeout) does the loop and the deadline arithmetic for you, as does C++’s cv.wait(lock, pred).

Exercise: build a countdown latch

Implement a countdown latch with a condition variable: it starts at N, count_down() decrements it, and wait(timeout) blocks until the count reaches zero or the timeout passes, returning whether it reached zero. Explain your choices.

Answer

The predicate is count == 0, and both the count and the predicate check live under the condition’s lock:

import threading

class CountDownLatch:
    def __init__(self, count):
        self._count = count
        self._cond = threading.Condition()

    def count_down(self):
        with self._cond:
            if self._count > 0:
                self._count -= 1
                if self._count == 0:
                    self._cond.notify_all()      # every waiter can proceed now

    def wait(self, timeout=None):
        with self._cond:
            return self._cond.wait_for(lambda: self._count == 0, timeout)

With three services finishing at 0.1, 0.2 and 0.3 seconds, a wait(timeout=0.15) returned False, and a following wait(timeout=2) returned True 0.15 seconds later, right after the last service reported in.

The reasoning to say out loud: count_down changes the count under the lock, so a waiter can’t check between the decrement and the notify. It uses notify_all because reaching zero is a broadcast event: every waiter should proceed, and notify would release only one. It only notifies on the transition to zero, since earlier decrements can’t make the predicate true. wait_for supplies the while loop, which protects against spurious wakeups, and computes one deadline for the timeout. Calling wait after the count has already reached zero returns True immediately, because the predicate is checked before sleeping. That’s the property a condition variable can’t give you on its own and your data does.

Where to go next

• Operating Systems interview questions
• Operating Systems MCQs
• Mutexes Versus Semaphores and Resource Ownership
• Race Conditions and Atomic State Transitions
• OSTEP, Condition Variables, the source of the one-variable bounded-buffer deadlock traced above