Free lesson · Operating Systems
BROKEN approach - busy waiting with a mutex
When a Lock Is Not Enough
A mutex lets you protect shared data. A semaphore lets you limit how many threads access a resource. But neither one gives you a clean way to express this: "I need to wait until a specific condition becomes true, and I want to sleep efficiently while I wait."
Consider a thread that processes items from a shared queue. The thread needs to wait until the queue is non-empty, take an item, and process it. With just a mutex, the best you can do is a busy-wait loop:
# BROKEN approach - busy waiting with a mutex
while True:
mutex.acquire()
if len(queue) > 0:
item = queue.pop(0)
mutex.release()
process(item)
break
mutex.release()
# Loop back and check again - wastes CPU
This works, but it is wasteful. The thread repeatedly acquires the mutex, checks the queue, finds it empty, releases the mutex, and loops back - burning CPU cycles doing nothing useful. If the producer is slow, the consumer might spin for seconds or minutes, consuming an entire CPU core.
You might think a semaphore solves this - and for the simple producer-consumer case, it does. But what about more complex conditions? "Wait until the queue has at least 10 items." "Wait until the buffer is less than half full." "Wait until a specific key appears in the dictionary." Semaphores count permits - they cannot express arbitrary boolean conditions.
A condition variable solves this problem. It is a synchronization primitive that allows a thread to atomically release a mutex and go to sleep, waiting for another thread to signal that a condition might have changed. When the signal arrives, the sleeping thread wakes up, re-acquires the mutex, and checks the condition again.
The combination of a mutex and a condition variable gives you the most general-purpose synchronization pattern in concurrent programming: "hold a lock, check a condition, if the condition is not met then sleep until someone tells me to check again."
How Condition Variables Work
A condition variable is always used together with a mutex. The mutex protects the shared data that the condition depends on. The condition variable provides the wait/signal mechanism. They are two separate objects that work in concert.
The three operations on a condition variable are:
Wait - the thread must hold the mutex when calling wait. The wait operation atomically releases the mutex and puts the thread to sleep. "Atomically" is critical here - no other thread can acquire the mutex between the release and the sleep. When the thread is woken up, it re-acquires the mutex before returning from wait. After wait returns, the thread holds the mutex again and can safely check the condition.
Signal (also called notify) - wakes up one thread that is waiting on the condition variable. If no threads are waiting, the signal is lost (it does not accumulate like a semaphore's signal). The signaling thread should hold the mutex when signaling to avoid race conditions between the signal and the condition change.
Broadcast (also called notify_all) - wakes up all threads waiting on the condition variable. Each woken thread re-acquires the mutex one at a time and checks the condition. This is used when the condition change might allow multiple waiters to proceed, or when different waiters are waiting for different conditions on the same data.
sequenceDiagram
participant C as Consumer Thread
participant M as Mutex
participant CV as Condition Variable
participant Q as Shared Queue
participant P as Producer Thread
C->>M: lock()
C->>Q: Check: is queue empty?
Note over Q: Queue is empty
C->>CV: wait(mutex)<br/>Atomically: release mutex + sleep
Note over C: SLEEPING
Note over M: Mutex is UNLOCKED
P->>M: lock()
P->>Q: queue.append(item)
Note over Q: Queue has 1 item
P->>CV: signal() - wake one waiter
P->>M: unlock()
Note over C: Woken up
C->>M: Re-acquire mutex (automatic)
C->>Q: Check again: is queue empty?
Note over Q: Queue has 1 item
C->>Q: item = queue.pop()
C->>M: unlock()
Note over C: Process item
This sequence diagram shows how a condition variable works. The consumer thread locks the mutex, checks the shared queue, finds it empty, and calls wait on the condition variable. The wait call atomically releases the mutex and puts the consumer to sleep. The producer thread then locks the mutex, adds an item to the queue, signals the condition variable to wake the consumer, and unlocks the mutex. The consumer wakes up, automatically re-acquires the mutex, checks the queue again (finding an item this time), removes the item, unlocks the mutex, and processes the item.
The Wait-in-a-Loop Pattern
There is one rule about condition variables that is so important it deserves its own section: always wait in a while loop, never in an if statement.
# WRONG - using if
mutex.acquire()
if queue_is_empty():
condition.wait() # Wakes up - assumes condition is now true
item = queue.pop() # DANGER: condition might not be true!
mutex.release()
# CORRECT - using while
mutex.acquire()
while queue_is_empty():
condition.wait() # Wakes up - checks condition again
item = queue.pop() # Guaranteed: queue is not empty
mutex.release()
Why is while necessary? Three reasons:
Spurious wakeups. The POSIX specification allows pthread_cond_wait to return even when no thread has called signal or broadcast. The OS might wake your thread for internal reasons. This is rare but legal, and your code must handle it. The while loop re-checks the condition and goes back to sleep if the wakeup was spurious.
Stolen wakeups. If you use broadcast (notify_all) to wake multiple waiters, all of them re-acquire the mutex one at a time. The first one checks the condition, finds it true, and acts on it. The second one checks the condition - but the first waiter already consumed the item, so the condition is false again. Without the while loop, the second waiter would proceed on a false condition.
Multiple conditions on the same variable. Sometimes different threads wait on the same condition variable for different conditions. A broadcast wakes all of them, but only some conditions might be true. The while loop ensures each thread re-checks its specific condition.
Important: The while loop is not optional. Every condition variable tutorial, every OS textbook, and every production codebase uses
while. Usingifinstead ofwhileis a bug that will eventually cause data corruption. Interviewers know this - if you write a condition variable withif, it signals that you have not actually used condition variables in real code.
Using Condition Variables in Practice
Python (threading.Condition)
Python wraps the mutex and condition variable into a single Condition object. The Condition has an internal lock that is acquired and released using with syntax.
import threading
import time
import random
queue = []
MAX_SIZE = 5
condition = threading.Condition() # Includes an internal Lock
def producer(producer_id, num_items):
for i in range(num_items):
item = f"P{producer_id}-{i}"
with condition:
while len(queue) >= MAX_SIZE:
print(f"Producer {producer_id}: Queue full, waiting...")
condition.wait() # Release lock + sleep
queue.append(item)
print(f"Producer {producer_id}: Added {item} | Queue: {list(queue)}")
condition.notify_all() # Wake consumers (and other producers)
time.sleep(random.uniform(0.05, 0.15))
def consumer(consumer_id, num_items):
for i in range(num_items):
with condition:
while len(queue) == 0:
print(f"Consumer {consumer_id}: Queue empty, waiting...")
condition.wait() # Release lock + sleep
item = queue.pop(0)
print(f"Consumer {consumer_id}: Got {item} | Queue: {list(queue)}")
condition.notify_all() # Wake producers (and other consumers)
time.sleep(random.uniform(0.05, 0.2))
threads = [
threading.Thread(target=producer, args=(1, 5)),
threading.Thread(target=producer, args=(2, 5)),
threading.Thread(target=consumer, args=(1, 5)),
threading.Thread(target=consumer, args=(2, 5)),
]
for t in threads:
t.start()
for t in threads:
t.join()
print(f"\nFinal queue: {queue}")
Java (wait/notify and Condition)
Java has two approaches. The older one uses wait() and notify() methods built into every object (tied to the synchronized keyword). The newer one uses explicit Condition objects from java.util.concurrent.locks.
// Modern Java - explicit Lock and Condition
import java.util.concurrent.locks.*;
import java.util.LinkedList;
import java.util.Queue;
public class BoundedQueue<T> {
private final Queue<T> queue = new LinkedList<>();
private final int capacity;
private final Lock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
public BoundedQueue(int capacity) {
this.capacity = capacity;
}
public void put(T item) throws InterruptedException {
lock.lock();
try {
while (queue.size() == capacity) {
notFull.await(); // Wait until not full
}
queue.add(item);
notEmpty.signal(); // Signal: queue is not empty
} finally {
lock.unlock();
}
}
public T take() throws InterruptedException {
lock.lock();
try {
while (queue.isEmpty()) {
notEmpty.await(); // Wait until not empty
}
T item = queue.remove();
notFull.signal(); // Signal: queue is not full
return item;
} finally {
lock.unlock();
}
}
}
Notice that Java's explicit Condition objects allow you to have multiple condition variables on the same lock - notFull and notEmpty in this example. This is more efficient than using a single condition variable with notify_all(), because you can wake only the threads that are waiting for the specific condition that changed. Producers wait on notFull and signal notEmpty. Consumers wait on notEmpty and signal notFull. No thread is woken up unnecessarily.
C (POSIX pthreads)
#include <pthread.h>
#define MAX_SIZE 10
int queue[MAX_SIZE];
int count = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;
void produce(int item) {
pthread_mutex_lock(&mutex);
while (count == MAX_SIZE) {
pthread_cond_wait(¬_full, &mutex); // Atomically release mutex + sleep
}
queue[count++] = item;
pthread_cond_signal(¬_empty); // Wake a consumer
pthread_mutex_unlock(&mutex);
}
int consume() {
pthread_mutex_lock(&mutex);
while (count == 0) {
pthread_cond_wait(¬_empty, &mutex); // Atomically release mutex + sleep
}
int item = queue[--count];
pthread_cond_signal(¬_full); // Wake a producer
pthread_mutex_unlock(&mutex);
return item;
}
Condition Variables vs Semaphores
Both condition variables and semaphores can solve the producer-consumer problem. So when should you use which?
Semaphores are better when you are counting resources. "There are N permits available" maps directly to a semaphore's counter. Connection pools, bounded buffers where the constraint is just capacity, and rate limiters are all natural semaphore territory.
Condition variables are better when the condition is arbitrary. "Wait until the queue has at least 10 items." "Wait until the hash map contains key X." "Wait until the buffer is less than 30% full." These conditions do not map to a simple counter - they require the thread to evaluate an arbitrary boolean expression on shared data. A condition variable lets the thread hold the lock, evaluate the expression, and sleep if it is false.
Condition variables are more composable. You can have multiple condition variables on the same lock, each representing a different condition. This allows targeted signaling - wake only the threads waiting for the condition that changed. Semaphores are single-purpose: each semaphore tracks one counter.
Semaphores are simpler for simple problems. If your problem is "limit to N concurrent accesses," a semaphore is one line of code. A condition variable solution for the same problem requires a mutex, a counter, a condition variable, and a while loop.
| Feature | Semaphore | Condition Variable |
|---|---|---|
| Condition type | Counter (≤ N) | Arbitrary boolean |
| Signals accumulate | Yes | No (lost if no waiter) |
| Must hold lock to wait | No | Yes (always) |
| Paired with mutex | No (self-contained) | Yes (always) |
| Multiple conditions per lock | N/A | Yes |
| Best for | Resource counting | Complex state conditions |
Interview: "When would you use a condition variable instead of a semaphore?"
"I use condition variables when the wait condition is more complex than a simple counter. A semaphore counts permits - great for 'at most N threads can access this resource.' But if the condition is 'wait until the queue has at least 10 items' or 'wait until the ratio of readers to writers drops below a threshold,' I need a condition variable because those conditions require evaluating an expression on shared state, not just checking a counter.
Condition variables also give me more control over signaling. I can have multiple condition variables on the same lock - one for 'not full' and one for 'not empty' - and signal only the relevant waiters. With semaphores, I would need separate semaphores for each condition, and coordinating them correctly is harder.
The tradeoff is complexity: condition variables always require a mutex, a while loop, and careful signal placement. For simple counting problems, a semaphore is cleaner."
Common Mistakes with Condition Variables
Not Holding the Mutex When Waiting
The entire point of the condition variable's wait operation is that it atomically releases the mutex and sleeps. If you are not holding the mutex when you call wait, the "release" part is meaningless, and there is a race condition between checking the condition and going to sleep.
# BROKEN - not holding the lock when waiting
if queue_is_empty(): # Check without lock - RACE
condition.wait() # Wait without lock - UNDEFINED BEHAVIOR
# CORRECT
with condition: # Acquires the internal lock
while queue_is_empty(): # Check with lock held
condition.wait() # Atomically releases lock + sleeps
Signaling Without Changing the Condition
A signal tells waiting threads to re-check their condition. If you signal without actually changing the shared data, the waiting thread wakes up, checks the condition, finds it unchanged, and goes back to sleep - wasting two context switches for nothing.
Always signal after you have modified the shared data that the condition depends on. The signal says "I changed something that might affect your wait condition - check again."
Using notify() When notify_all() Is Needed
notify() wakes one waiting thread. If multiple threads are waiting for different conditions on the same condition variable, the one that wakes up might not be the one whose condition became true. It checks, finds its condition still false, and goes back to sleep - while the thread whose condition is actually true remains asleep.
The safe default is notify_all(). Use notify() only when you are certain that any waiting thread can handle the condition change - for example, when all waiters are identical consumers waiting for the same "queue not empty" condition.
Building Higher-Level Patterns with Condition Variables
Condition variables are low-level primitives. In practice, you build higher-level patterns on top of them.
Barrier
A barrier makes N threads wait until all N have reached the barrier point, then releases all of them simultaneously. Think of it as "everyone waits for the last person to arrive."
import threading
class Barrier:
def __init__(self, n):
self.n = n
self.count = 0
self.condition = threading.Condition()
def wait(self):
with self.condition:
self.count += 1
if self.count == self.n:
self.count = 0 # Reset for reuse
self.condition.notify_all() # Everyone arrived - release all
else:
self.condition.wait() # Wait for the last thread
barrier = Barrier(3)
def worker(thread_id):
print(f"Thread {thread_id}: doing phase 1 work")
barrier.wait()
print(f"Thread {thread_id}: all threads done with phase 1, starting phase 2")
threads = [threading.Thread(target=worker, args=(i,)) for i in range(3)]
for t in threads:
t.start()
for t in threads:
t.join()
Barriers are used in parallel computing when a computation is divided into phases, and each phase must complete across all threads before the next phase begins. Matrix operations, physics simulations, and MapReduce-style computations use barriers between stages.
Event / One-Shot Signal
An event is a condition variable that remembers whether it has been signaled. Once set, all current and future waiters proceed immediately. This is useful for one-time initialization signals - "the database connection is ready" or "the configuration file has been loaded."
graph TD
subgraph BARRIER["Barrier (N=3)"]
T1["Thread 1<br/>arrives, waits"] --> CHECK{"count == N?"}
T2["Thread 2<br/>arrives, waits"] --> CHECK
T3["Thread 3<br/>arrives - last one!"] --> CHECK
CHECK -->|"Yes"| RELEASE["notify_all()<br/>All threads proceed"]
CHECK -->|"No"| WAIT["condition.wait()<br/>Sleep until last thread"]
end
RELEASE --> PHASE2["All threads enter Phase 2"]
WAIT -.->|"woken by notify_all"| PHASE2
This diagram shows how a barrier works with three threads. Thread 1 arrives and waits because the count has not reached 3. Thread 2 arrives and also waits. Thread 3 arrives last, making the count equal to 3. Thread 3 calls notify_all to wake all waiting threads. All three threads then proceed to Phase 2 together. The barrier ensures no thread starts Phase 2 until all threads have finished Phase 1.
Condition Variables in Production Systems
Condition variables are the workhorse behind many systems you use every day:
Thread pools. Worker threads in a thread pool wait on a condition variable for new tasks. When a task is submitted, the submitter signals the condition variable, and one worker wakes up to execute it. Java's ThreadPoolExecutor, Python's concurrent.futures.ThreadPoolExecutor, and Go's goroutine scheduler all use this pattern internally.
Database connection pools. When all connections are in use, requesting threads wait on a condition variable until a connection is returned. The condition is "at least one connection is available," which is checked in a while loop after each wakeup.
Logging frameworks. Asynchronous loggers use a bounded buffer between the application thread (producer) and the I/O thread (consumer). The I/O thread waits on a condition variable for new log entries. Batch signaling (notify after N entries accumulate) reduces context-switch overhead.
Operating system internals. The kernel uses condition variables (or equivalent mechanisms) extensively. Process wait queues, I/O completion notifications, and the scheduler's run queue all use condition-variable-style wait/signal patterns.
Exercise: Starter: Using Python's
threading.Condition, implement a simple producer-consumer. The producer adds numbers 1 through 10 to a shared list (one per second). The consumer waits for items to appear and prints them. Usecondition.wait()in a while loop andcondition.notify()to signal.Intermediate: Implement a bounded buffer using a
threading.Conditionwith two explicit conditions: "not full" and "not empty." Since Python'sConditionobject supports only one underlying condition, usenotify_all()and have each thread re-check its own condition in a while loop. Create 3 producers and 2 consumers with a buffer of size 5. Verify that the buffer never exceeds its capacity and never goes negative.Advanced: Implement a reusable barrier for N threads using a condition variable (without using Python's built-in
threading.Barrier). The barrier should support multiple rounds - after all threads pass through, the barrier resets for the next round. Test it with 4 threads executing 5 rounds, printing their thread ID and round number. Verify that all threads complete round K before any thread starts round K+1.