Condition variables and semaphores

A lock makes a thread wait for another thread to finish with some state. Just as often, a thread has to wait for something to happen: an item to arrive in a queue, a result to be computed, a connection to free up. You could wait with a loop that keeps checking (while (queue.isEmpty()) {}). But that burns a whole CPU core doing nothing. And without a lock, it reads stale data.

This page covers the two tools for waiting properly:

• A condition variable lets a thread sleep until another thread says the state it’s waiting on has changed.
• A semaphore is a counter of permits. Threads take permits and give them back, and wait when there are none.

Together, they build every other waiting tool: blocking queues, latches, barriers, futures and connection pools.

What makes this hard

• A condition variable is always used with a lock. wait() releases that lock while the thread sleeps, and retakes it before returning. That’s what makes “check, then sleep” atomic.
• Always wait in a while loop that re-checks the condition, never an if. A woken thread can find the condition false again. Another thread got there first, or the wakeup was spurious.
• notifyAll is the safe default. notify wakes one thread. If it wakes the wrong kind, the wakeup is wasted, and the program can stall with everyone asleep.
• A semaphore counts permits and has no owner. It bounds how many threads do something at once. A mutex bounds it to one, and belongs to the thread that took it.

Condition variables

A condition variable has three operations, all called while holding its lock:

• wait(): release the lock and go to sleep, as one atomic step. When woken, retake the lock, then return. Because the release and the sleep are one step, no notification can slip in between them and be missed.
• signal() (Java notify, C# Pulse): wake one waiting thread, if any.
• signalAll() (Java notifyAll, C# PulseAll, Python notify_all): wake all of them.

A woken thread doesn’t run right away. It has to get the lock back first, and the thread that signaled still holds it. Only when the signaler unlocks does a woken thread compete for the lock. Other threads that arrived in the meantime may compete too.

A thread's life around a lock and a condition variable

Scroll or pinch to zoom, drag to pan

• Color key
• State

A monitor is that whole package: one lock, the state it guards, and one or more condition variables over that state. Every Java object is a monitor (synchronized, wait, notify). C#’s Monitor class is the same idea.

Stage 1: wait for a result

Several threads need a result that another thread computes once. Each waiter checks whether the result is there. If not, it sleeps on the condition. The producer sets the result, and wakes all of them.

JResultSlot.javaPyresult_slot.pyC#ResultSlot.csGoresult_slot.goTSresult-slot.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.List;

// Several threads wait for a result that another thread will produce once.
public class Main {
    public static void main(String[] args) throws Exception {
        ResultSlot<Integer> slot = new ResultSlot<>();
        List<Thread> waiters = new ArrayList<>();
        int[] seen = new int[3];
        for (int i = 0; i < 3; i++) {
            final int me = i;
            Thread t = new Thread(() -> {
                try { seen[me] = slot.get(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            });
            t.start();
            waiters.add(t);
        }
        Thread.sleep(50);  // the waiters are asleep now, using no CPU
        slot.set(42);      // one call wakes all three
        for (Thread t : waiters) t.join();
        for (int v : seen) if (v != 42) throw new AssertionError("a waiter missed the result");

        // A get with a deadline on a slot nobody fills returns empty instead of hanging.
        Integer none = new ResultSlot<Integer>().get(50);
        if (none != null) throw new AssertionError();
        System.out.println("all waiters got 42; the timed get gave up"); // all waiters got 42; the timed get gave up
    }
}

// A one-shot result: set once, read by any number of threads that block until it's there.
// This is a monitor: one lock, the state it guards, and waiting on a condition of that state.
class ResultSlot<T> {
    private final Object lock = new Object(); // private, so nobody else can notify on it
    private T value;       // guarded by lock
    private boolean done;  // guarded by lock

    void set(T v) {
        synchronized (lock) {
            if (done) throw new IllegalStateException("already set");
            value = v;
            done = true;
            // notifyAll, not notify: every waiter is waiting for this same event, and notify()
            // would wake one and leave the rest asleep forever.
            lock.notifyAll();
        }
    }

    T get() throws InterruptedException {
        synchronized (lock) {
            // while, never if: a thread can wake without the condition being true (a spurious
            // wakeup, or another thread changed the state before this one got the lock back).
            while (!done) lock.wait(); // releases the lock while asleep, retakes it before returning
            return value;
        }
    }

    // Waits at most timeoutMs. Each wakeup recomputes the time left, so a spurious wakeup
    // doesn't restart the full timeout.
    T get(long timeoutMs) throws InterruptedException {
        long deadline = System.nanoTime() + timeoutMs * 1_000_000;
        synchronized (lock) {
            while (!done) {
                long leftMs = (deadline - System.nanoTime()) / 1_000_000;
                if (leftMs <= 0) return null;
                lock.wait(leftMs);
            }
            return value;
        }
    }
}

What each version shows:

• Java and C#: the classic monitor. while (!done) lock.wait(), with notifyAll because every waiter is waiting for the same event. The timed version computes the time left from one deadline on each pass. So a spurious wakeup doesn’t restart the whole timeout.
• Python: Condition.wait_for(predicate, timeout) writes the while loop and the deadline for you. Prefer it to a bare wait().
• Go: Go has sync.Cond, but idiomatic Go closes a channel instead. A receive on a closed channel returns right away, for every receiver, forever. It’s a broadcast that can’t be missed, with no loop to forget. select with time.After gives the timeout.
• TypeScript: in single-threaded async code, “wait until something happens” is just a promise. Resolving it wakes every caller that awaits it.

That code already contains the two rules people get wrong. Here they are, one at a time.

Stage 2: why it’s always while, never if

Between being signaled and getting the lock back, a woken thread is not running. Anything can happen in that time. In the stepper below, two consumers (A, B) each take one item, and a producer (C) makes two. Press Play the stolen wakeup:

1. A takes the lock, sees zero items, and waits (which releases the lock).
2. C produces an item and signals. A wakes up, but C still holds the lock.
3. Before A gets the lock back, B arrives, sees one item, and takes it.
4. A finally gets the lock. With if, it doesn’t check again and takes an item that isn’t there.

if (items == 0) waitwhile (items == 0) wait

A · ConsumerStep A

1. lock(m)
2. if (items == 0)
3. notEmpty.wait(m)
4. items = items - 1 // take one
5. unlock(m)

ready

B · ConsumerStep B

1. lock(m)
2. if (items == 0)
3. notEmpty.wait(m)
4. items = items - 1 // take one
5. unlock(m)

ready

C · ProducerStep C

1. lock(m)
2. items = items + 1
3. notEmpty.signal()
4. unlock(m)
5. if (made < 2) repeat

ready

Play the stolen wakeupRun 1,000 schedulesSpurious wakeupReset

Two consumers (A, B) each take one item; the producer (C) makes two. Press Play for the order that breaks "if", or use the Wake button to fire a spurious wakeup at a sleeping consumer.

Switch to while, and play the same order. A re-checks, sees zero, and goes back to sleep until the second item.

The Spurious wakeup button shows the other reason. POSIX, Java and C# all allow a waiting thread to wake with no signal at all. It’s a detail of how the OS parks threads. With while, a spurious wakeup is harmless. With if, it’s the same bug.

Common mistake

Waiting with if

if (!ready) cond.wait() works in every test and fails in production. Both the stolen wakeup and the spurious wakeup need precise timing, so tests rarely hit them. Every condition wait is while (!condition) wait(). Java’s own documentation for Object.wait() says so.

Stage 3: signal or signalAll?

signal() wakes one waiter. That’s efficient when every waiter is waiting for the same thing, and any one of them can use the event. For example, one item arrived, so one consumer should wake.

It goes wrong when waiters wait for different things on the same condition variable. Say producers wait for space, and consumers wait for items. The one wakeup can go to a thread that can’t use it. That thread re-checks and goes back to sleep. And the thread that could have used it never hears about it. The producer-consumer page shows that exact stall, step by step.

The rules that follow:

• With one condition variable, and waiters for different conditions, use signalAll.
• Better: give each condition its own condition variable (notFull and notEmpty). Then signal the one that matches what changed. Java’s ReentrantLock.newCondition() and Go’s sync.Cond allow several conditions on one lock. Java’s built-in wait/notify allows only one per object. That’s why notifyAll is the default there.
• Signal after changing the state, while holding the lock (or right after releasing it). A signal sent when nobody is waiting is lost. That’s fine only because waiters check the state before sleeping, under the same lock.

Interviewer

Why does wait() have to be called while holding the lock?

What they are testing

Whether you understand the lost wakeup. Say a thread checked the condition without the lock. The other thread could change the state and signal in the gap, before the first thread sleeps. That signal goes to nobody. Holding the lock across the check closes the gap, because wait() releases it atomically as it sleeps. The red flag is answering “because the API requires it”.

Semaphores

A semaphore holds a number of permits. acquire() takes one, and blocks while there are none. release() returns one, and wakes a waiter. Two things set it apart from a lock:

• It counts. A semaphore with 10 permits lets 10 threads in at once. It bounds concurrency, where a mutex forbids it.
• It has no owner. Any thread can release a permit, even one that never acquired it. So a semaphore is a signaling tool between threads, as well as a limiter.

Here are three request threads, and a database that accepts two connections. Play A, B, C in turn, with no limit, and the peak reaches three. Then switch to a semaphore with two permits. The third request waits on acquire until a permit comes back.

No limitSemaphore(2)

A · RequestStep A

1. open++ // connection in use
2. runQuery()
3. open--

ready

B · RequestStep B

1. open++ // connection in use
2. runQuery()
3. open--

ready

C · RequestStep C

1. open++ // connection in use
2. runQuery()
3. open--

ready

Play A, B, C in turnRun 1,000 schedulesReset

The database accepts 2 connections; three request threads want one each. Play A, B, C in turn.

Here is the same thing in code, with ten requests and three permits. This is how connection pools, rate limiters for outbound calls, and “at most 4 concurrent uploads” are built.

JMain.javaPyexample.pyC#Program.csGomain.goTSsemaphore.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

// Ten threads want the database; it allows three connections at once.
public class Main {
    // Three permits. acquire() takes one or blocks until one is returned; release() returns one.
    // Unlike a lock, a permit has no owner: any thread may release it.
    static final Semaphore connections = new Semaphore(3);
    static final AtomicInteger inUse = new AtomicInteger();
    static final AtomicInteger peak = new AtomicInteger();

    static void query() throws InterruptedException {
        connections.acquire();
        try {
            int now = inUse.incrementAndGet();
            peak.accumulateAndGet(now, Math::max);
            Thread.sleep(20); // the query
            inUse.decrementAndGet();
        } finally {
            connections.release(); // in finally: a failed query must still return its permit
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] requests = new Thread[10];
        for (int i = 0; i < requests.length; i++) {
            requests[i] = new Thread(() -> {
                try { query(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            });
            requests[i].start();
        }
        for (Thread t : requests) t.join();
        if (peak.get() > 3) throw new AssertionError("limit broken: " + peak.get());
        System.out.println("peak connections = " + peak.get()); // peak connections = 3
    }
}

• Java: Semaphore(3), with release() in finally, so a failed query still returns its permit. tryAcquire(100, MILLISECONDS) turns waiting into shedding load: fail fast, instead of queuing forever.
• Python: BoundedSemaphore raises on an extra release. That catches a bug that would otherwise silently raise the limit to four.
• C#: SemaphoreSlim.WaitAsync(), so a request waiting for a permit doesn’t hold a thread. It’s also the standard way to get a lock that works across await, since lock can’t contain one.
• Go: a buffered channel of capacity 3 is the idiomatic semaphore. Sending takes a slot, and receiving gives it back.
• TypeScript: a counter and a queue of resolvers. It’s the same shape as p-limit, which you’d use in practice.

TradeoffSemaphore vs a pool of objects

We gain

A semaphore limits how many threads do something at once, with a single counter, whatever the something is. It needs no knowledge of the resource.

We give up

It only counts. It doesn’t hand you a connection, or check that it’s healthy. It doesn’t notice a thread that acquired and never released, so a leak slowly lowers the limit to zero. A real connection pool keeps the objects themselves in a blocking queue. That one structure counts, hands out and takes back. The pool also adds leak detection and timeouts.

Binary semaphore vs mutex

A semaphore with one permit looks like a lock. In an interview, “what’s the difference?” is a standard question. The answer is ownership.

• A mutex is held by a thread. Only that thread may unlock it, and it can be reentrant. Some implementations raise the holder’s priority when a higher-priority thread waits. This is called priority inheritance.
• A binary semaphore is just a count of 1, and any thread can release it. When you mean mutual exclusion, that’s a bug magnet, because anyone can let a second thread in. But it’s exactly right when one thread signals another: “the data is ready, go”.

Latches, barriers and wait groups

Three more waiting tools are built from the two above, and each answers one common need:

Tool	What it does	Java	C#	Go	Python
Latch / wait group	Wait until N things have finished. One use, counts down to zero.	CountDownLatch	CountdownEvent	sync.WaitGroup	join() each thread, or futures
Barrier	N threads each wait until all N arrive, then all continue. Reusable.	CyclicBarrier	Barrier	Build it from a sync.Cond	threading.Barrier
Future / promise	Wait for one result that another thread will produce.	CompletableFuture	Task<T>	A channel	concurrent.futures.Future

The result slot in stage 1 is a hand-built future. Use the library’s version in real code. It handles exceptions, cancellation and timeouts, which a hand-built one usually forgets. The barrier is the tool that held two threads inside the race window on the race conditions page. Tests are its most common use.

Say this out loud

The consumer waits on the condition in a while loop, because a woken thread can find the queue empty again. The producer changes the state under the lock, and then signals. Producers and consumers wait for different things. So I’d use two conditions, or signalAll with one.

Mid-level covers

Uses a condition variable with its lock. Waits in a while loop, and signals after changing state. Uses a semaphore to bound concurrency, with release in finally.

Senior adds

Also explains why wait must hold the lock (lost wakeups). Knows when signal can stall a system, and how signalAll or separate conditions fix it. Times waits against one deadline. Explains why a mutex and a binary semaphore differ (ownership, priority inheritance).

Each language, honestly

Language	Condition variable	Semaphore	Notes
Java	wait/notifyAll on any object; lock.newCondition() for several	Semaphore	Virtual threads park cheaply in all of these
Python	threading.Condition, with wait_for	Semaphore, BoundedSemaphore	asyncio has its own Condition and Semaphore for coroutines
C#	Monitor.Wait/PulseAll	SemaphoreSlim (with WaitAsync), Semaphore (cross-process)	lock can’t contain await; use SemaphoreSlim(1, 1) as an async lock
Go	sync.Cond, rarely; channels instead	A buffered channel; x/sync/semaphore	Closing a channel is the broadcast; select adds timeouts and cancellation
TypeScript	A promise; resolve it to wake every awaiter	A counter plus a queue of resolvers	Atomics.wait and Atomics.notify between workers

How waiting fails

Failure	What happens	Prevention
if instead of while	A woken thread acts on a condition that is no longer true	Always while, or wait_for / a predicate overload
Lost wakeup	The signal comes before the wait (check without the lock), the thread sleeps forever	Check and wait under the same lock
Wrong thread woken	signal wakes a waiter for a different condition; everyone ends up asleep	signalAll, or one condition variable per condition
Leaked permit	An exception skips release(); the limit shrinks until everything blocks	finally, with, defer
Wait with no timeout	A crashed producer leaves consumers asleep forever	Timed waits, and a deadline per request

Interview questions

Interviewer asksWhat is a spurious wakeup, and how do you handle it?

A thread waiting on a condition variable can return from wait() without anyone signaling. POSIX, Java and C# all permit it, because it lets the OS park and unpark threads more efficiently. You handle it the same way as a stolen wakeup. Wait in a while loop that re-checks the condition. Then a wakeup with nothing to do just goes back to sleep.

Interviewer asksWhat's the difference between wait() and sleep()?

wait() releases the lock it’s called on, and sleeps until signaled (or until a timeout). It’s for waiting on a condition another thread will change. sleep() pauses for a fixed time, and releases nothing. So calling it while holding a lock makes every other thread wait too. Polling with sleep() in a loop is a sign that a condition variable or a blocking queue was needed.

Interviewer asksSemaphore vs mutex: when do you use each?

Use a mutex for mutual exclusion over shared state: one thread at a time. It’s owned by the thread that locked it, and unlocked by the same thread. Use a semaphore to bound how many threads do something at once (a pool of N connections). Or use it to signal between threads, since any thread can release a permit. A binary semaphore used as a mutex works, until some code path releases it from the wrong thread.

Interviewer asksHow would you implement a CountDownLatch?

A count and a condition variable, under one lock. countDown() takes the lock and decrements. If the count reached zero, it calls signalAll. await() takes the lock, and waits in while (count > 0). Once the count is zero, it stays zero, so late callers return right away. In Go, sync.WaitGroup is exactly this.

Go deeperWhy some languages split the lock from the condition2 min

Java’s built-in monitor gives each object one lock and one wait set. That forces notifyAll whenever threads wait for different reasons. And every notifyAll wakes threads that will only re-check and sleep again. This is called the “thundering herd”. With 200 waiters, one item wakes 200 threads, to hand the item to one of them.

ReentrantLock with several Condition objects, POSIX pthread_cond_t, Go’s sync.Cond and Python’s Condition(lock) all let you attach several wait sets to one lock. Producers wait on notFull, and consumers on notEmpty. Each event wakes only a thread that can use it. That’s why java.util.concurrent.ArrayBlockingQueue is built on one lock with two conditions.

Recap

Idea	Remember
Condition variable	Sleep until another thread changes state; always used with its lock
wait()	Releases the lock and sleeps in one step; retakes the lock before returning
while, not if	Stolen and spurious wakeups mean the condition may be false again
signal vs signalAll	signal only when any waiter can use the event; otherwise signalAll or two conditions
Monitor	Lock + guarded state + condition variables, as one unit
Semaphore	N permits, no owner; bounds concurrency or signals between threads
Latch, barrier, future	Wait for N to finish, for N to arrive, for one result

Further reading

• Brian Goetz et al., Java Concurrency in Practice, chapter 14 (building custom synchronizers).
• Allen B. Downey, The Little Book of Semaphores, free, and full of puzzles built from nothing but semaphores.
• Next: Deadlock, what happens when threads wait for each other in a circle.