Classic Synchronization Problems, Solved
A small set of puzzles, most of them written between 1965 and 1971, still underpins every operating-systems course and a good share of concurrency interviews. They are not academic trivia. Each one isolates a single hazard you will meet in production: lost wakeups, writer starvation, circular wait, a convoy forming behind a barrier. If you learn to see a new bug as "this is readers–writers again", you already know the standard fixes and their costs.
This page works through all of them using one template:
- Statement: the story and what the code has to do.
- Invariants: the safety property that must always hold, and the liveness failures to rule out (deadlock, starvation, busy waiting).
- A naive attempt and the exact interleaving that breaks it.
- Correct solution(s): semaphore pseudocode first, then real code in Java, Python or Go.
- Correctness argument: why it cannot deadlock, and whether it can starve anyone.
- Trade-offs: complexity, fairness, throughput.
- Where it shows up in real systems.
The primitives themselves (mutexes, counting semaphores, monitors, condition variables) are covered in Mutex, Semaphore & Monitor. The four deadlock conditions are in Deadlocks, Livelocks & Starvation, and the hardware underneath (atomics, cache coherence, memory barriers, futexes) is in Kernel Synchronization. LeetCode-style exercises (print in order, alternate output, and so on) are on the companion page, Concurrency Interview Problems.
Notation
All pseudocode uses Dijkstra's semaphore operations:
| Pseudocode | Meaning | Python | Java | Go (buffered-channel semaphore) |
|---|---|---|---|---|
P(s) / wait(s) | If s > 0 decrement and continue, else block | s.acquire() | s.acquire() | s <- struct{}{} |
V(s) / signal(s) | Increment s, waking one blocked waiter if any | s.release() | s.release() | <-s |
semaphore s = k | Initial count k | threading.Semaphore(k) | new Semaphore(k) | make(chan struct{}, k) |
(P and V come from the Dutch proberen, "to test", and verhogen, "to increment".) A semaphore initialised to 1 and used as P(m) ... V(m) acts as a mutex. A semaphore initialised to 0 is a signal: one thread waits on it until another posts. Unlike a condition variable, a semaphore remembers a V that happens before the matching P. Several problems below are solved by exactly that property.
Two vocabulary points used throughout:
- A weak semaphore wakes an arbitrary waiter. A strong (FIFO) semaphore wakes the longest waiter. Whether a solution is starvation-free often depends on which kind you have.
threading.Semaphoremakes no FIFO promise.java.util.concurrent.Semaphore(n, true)is FIFO. POSIXsem_twakes waiters by scheduling policy. - Busy waiting (spinning) means looping on a condition while burning CPU. It is acceptable only when the expected wait is shorter than a context switch. See When Spinning Beats Sleeping.
1. The Critical-Section Problem
Statement
n processes each run a loop:
loop forever:
entry section ← what we must design
critical section ← touches shared state
exit section ← what we must design
remainder section ← anything else, may run forever or halt
Design the entry and exit sections using only ordinary loads and stores to shared variables (later we allow atomic instructions too).
Invariants
A correct solution must satisfy three requirements, as stated in Silberschatz's Operating System Concepts:
| Requirement | Kind | Meaning |
|---|---|---|
| Mutual exclusion | Safety | At most one process is in its critical section at any instant. |
| Progress | Liveness (no deadlock) | If nobody is in the critical section and some processes want in, the choice of who enters next involves only the processes trying to enter, and it cannot be postponed indefinitely. A process idling in its remainder section must not block others. |
| Bounded waiting | Liveness (no starvation) | Once a process has asked to enter, there is a bound on how many times others may enter before it does. |
We assume nothing about relative speeds and nothing about how many CPUs there are. A process may be preempted between any two instructions.
Why the Obvious Attempts Fail
Attempt 0: disable interrupts. On a uniprocessor, if a process disables interrupts on entry and re-enables them on exit, the scheduler cannot preempt it, so mutual exclusion holds. Early Unix kernels worked this way (spl() levels). It fails in general because:
- On a multiprocessor, disabling interrupts on CPU 0 does nothing to CPU 1.
- User processes cannot do it, and should not be able to, since one buggy loop would freeze the machine.
- Interrupt latency grows with the length of the critical section, which hurts timers, network cards and audio.
Kernels still disable local interrupts briefly (local_irq_save) to protect per-CPU data from their own interrupt handlers, alongside a spinlock for other CPUs. See IRQ-Safe Variants.
Attempt 1: a lock flag.
bool locked = false
entry: while (locked) { } // spin
locked = true
exit: locked = false
The check and the set are two separate steps:
| Step | P0 | P1 | locked |
|---|---|---|---|
| 1 | reads locked → false | false | |
| 2 | preempted | reads locked → false | false |
| 3 | sets locked = true, enters CS | true | |
| 4 | sets locked = true, enters CS | true | |
| 5 | in CS | in CS | mutual exclusion violated |
This is the check-then-act race from Race Conditions, applied to the lock itself.
Attempt 2: strict alternation.
int turn = 0
P_i entry: while (turn != i) { }
P_i exit: turn = 1 - i
Mutual exclusion holds, because turn has a single value and only the process it names may pass. Progress fails, though. Suppose P0 leaves the critical section (setting turn = 1), then wants to enter again, while P1 is in a long remainder section and does not want the critical section at all. P0 now waits for P1, a process that is not competing. The two processes are forced into lockstep at the speed of the slower one.
Attempt 3: announce intent, then wait.
bool flag[2] = {false, false}
P_i entry: flag[i] = true
while (flag[j]) { }
P_i exit: flag[i] = false
Mutual exclusion holds now, but the processes can deadlock:
| Step | P0 | P1 |
|---|---|---|
| 1 | flag[0] = true | |
| 2 | flag[1] = true | |
| 3 | spins: flag[1] is true | spins: flag[0] is true |
| 4 | spins forever | spins forever |
Each process politely waits for the other. If you swap the order (check first, then set the flag), you are back to Attempt 1's race. The fix is to combine Attempt 2 and Attempt 3: announce intent, and use turn only to break ties.
Peterson's Algorithm (1981)
bool flag[2] = {false, false}
int turn
P_i (j = 1 - i):
entry: flag[i] = true // I want in
turn = j // but you go first if you also want in
while (flag[j] && turn == j) { }
exit: flag[i] = false
The key move is the self-sacrificing write to turn. Whoever writes turn last is the one who waits.
sequenceDiagram
participant P0
participant M as Shared memory
participant P1
P0->>M: flag[0] = true
P1->>M: flag[1] = true
P0->>M: turn = 1
P1->>M: turn = 0 (last writer)
P0->>M: read flag[1]=true, turn=0
Note over P0: turn is not 1 so P0 enters
P1->>M: read flag[0]=true, turn=0
Note over P1: turn == 0 so P1 spins
P0->>M: exit, flag[0] = false
P1->>M: read flag[0]=false
Note over P1: P1 enters
Proof sketch.
- Mutual exclusion. Suppose both P0 and P1 are in the critical section. Both set their flag before entering, so
flag[0] = flag[1] = truethroughout. P0 passed its loop, so it sawflag[1] == falseorturn == 0. P1 passed, so it sawflag[0] == falseorturn == 1. The flags are both true, so P0 sawturn == 0and P1 sawturn == 1.turnis one variable, so the writes and reads must be ordered. Say P1 wroteturn = 0last. After that,turnstays 0 until somebody exits. P1 then readturn == 1after its own write, which is impossible. The symmetric case is the same. Contradiction. - Progress. If only P0 wants in,
flag[1]is false and P0 passes immediately. If both want in,turnis either 0 or 1, so exactly one of the two loop conditions is false and that process enters. - Bounded waiting (bound = 1). If P0 is waiting, P1 can enter at most once more. When P1 tries again it sets
turn = 0, which lets P0 through, and P1 waits in turn.
Peterson's algorithm is broken on real CPUs without fences
The proof assumes sequential consistency: every process sees every other process's writes in program order. Modern hardware does not provide this. On x86, the store flag[i] = true can sit in the store buffer while the later load of flag[j] reads the old value from cache. This is the store-buffer litmus test: both processes can read flag[other] == false and both enter. ARM and POWER reorder even more. Compilers are also free to cache flag[j] in a register and never reload it.
The fix is a full barrier (MFENCE on x86, DMB ISH on ARM) between the stores and the loop, or declaring the shared variables as sequentially consistent atomics. See Memory Ordering and Barriers, which uses exactly this example.
Runnable Java version. In Java, volatile fields and Atomic* classes are sequentially consistent with respect to each other, so this version is correct on any JVM:
// Peterson.java — javac Peterson.java && java Peterson
import java.util.concurrent.atomic.AtomicIntegerArray;
public class Peterson {
private final AtomicIntegerArray flag = new AtomicIntegerArray(2); // SC accesses
private volatile int turn;
void lock(int i) {
int j = 1 - i;
flag.set(i, 1);
turn = j;
while (flag.get(j) == 1 && turn == j) {
Thread.onSpinWait(); // PAUSE hint on x86, YIELD on ARM
}
}
void unlock(int i) {
flag.set(i, 0);
}
static int counter = 0; // protected by the Peterson lock
public static void main(String[] args) throws InterruptedException {
Peterson p = new Peterson();
Thread[] ts = new Thread[2];
for (int t = 0; t < 2; t++) {
final int id = t;
ts[t] = new Thread(() -> {
for (int k = 0; k < 1_000_000; k++) {
p.lock(id);
counter++;
p.unlock(id);
}
});
ts[t].start();
}
for (Thread t : ts) t.join();
System.out.println(counter); // always 2000000
}
}
If you replace AtomicIntegerArray with a plain int[] and drop volatile, the count drops below 2,000,000 within a few runs on a multicore machine.
Dekker's Algorithm (1965)
Dekker's algorithm, credited by Dijkstra to the Dutch mathematician Th. J. Dekker, was the first correct software solution for two processes. It is Attempt 3 plus a rule for backing off:
bool flag[2] = {false, false}
int turn = 0
P_i (j = 1 - i):
flag[i] = true
while (flag[j]):
if (turn == j):
flag[i] = false // back off
while (turn == j) { } // wait for my turn
flag[i] = true // try again
// critical section
turn = j
flag[i] = false
When both processes want in, the one whose turn it is not withdraws its flag, which breaks the Attempt 3 deadlock. turn is handed over on exit, so a waiting process gets in next (bounded waiting). Peterson's version replaced the nested loop with one condition, which is why it is the one taught today. Both need the same memory barriers on modern hardware.
Lamport's Bakery Algorithm (1974): n Processes
The algorithm is modelled on a bakery ticket dispenser. Each customer takes a number higher than every number currently held, and the lowest number is served first. Ties (two people computing the same number at the same moment) are broken by process ID.
bool choosing[n] = {false}
int number[n] = {0} // 0 = not interested
P_i:
choosing[i] = true // doorway start
number[i] = 1 + max(number[0], ..., number[n-1])
choosing[i] = false // doorway end
for j in 0 .. n-1:
while (choosing[j]) { } // wait for j to finish picking
while (number[j] != 0 and (number[j], j) < (number[i], i)) { }
// critical section
number[i] = 0
(a, b) < (c, d) means a < c, or a == c and b < d.
Why choosing is needed. Without it, here is the interleaving that breaks mutual exclusion, with P1 and P2 both starting from all-zero tickets:
| Step | P1 | P2 | number |
|---|---|---|---|
| 1 | reads max = 0 | [0, 0] | |
| 2 | reads max = 0, writes number[2] = 1 | [0, 1] | |
| 3 | scans: number[1] == 0, so passes it, enters CS | [0, 1] | |
| 4 | writes number[1] = 1 | in CS | [1, 1] |
| 5 | scans: (1, 2) < (1, 1) is false, so passes, enters CS | in CS | both in CS |
P2 looked at P1 while P1 was between reading the max and writing its ticket. choosing[1] = true would have made P2 wait at step 3 until P1's ticket was visible, and then the tie-break by ID would have stopped P2.
Properties.
- Mutual exclusion and FCFS fairness. If P_i finishes the doorway before P_k starts it, P_i's ticket is strictly smaller, so P_i enters first. That is first-come-first-served, which is stronger than bounded waiting.
- No atomic read-modify-write needed. Lamport proved the algorithm correct even with safe registers, where a read that overlaps a write may return any value. It is one of the few mutual exclusion algorithms that does not depend on atomic memory at all. The same idea of totally ordering events by (counter, ID) reappears in Lamport timestamps.
- Cost. Entry is O(n) reads even with no contention. Ticket numbers are unbounded in principle: they grow without limit as long as the critical section is never empty. Each process needs its own shared variables, so the space is O(n). As with Peterson, a real implementation needs SC atomics.
// Bakery.java — n-thread Lamport bakery lock
import java.util.concurrent.atomic.AtomicIntegerArray;
public class Bakery {
private final int n;
private final AtomicIntegerArray choosing, number;
Bakery(int n) {
this.n = n;
choosing = new AtomicIntegerArray(n);
number = new AtomicIntegerArray(n);
}
void lock(int i) {
choosing.set(i, 1);
int max = 0;
for (int k = 0; k < n; k++) max = Math.max(max, number.get(k));
number.set(i, max + 1);
choosing.set(i, 0);
for (int j = 0; j < n; j++) {
while (choosing.get(j) == 1) Thread.onSpinWait();
while (true) {
int nj = number.get(j), ni = number.get(i);
if (nj == 0 || nj > ni || (nj == ni && j >= i)) break;
Thread.onSpinWait();
}
}
}
void unlock(int i) { number.set(i, 0); }
static long counter = 0;
public static void main(String[] args) throws InterruptedException {
int n = 4;
Bakery b = new Bakery(n);
Thread[] ts = new Thread[n];
for (int t = 0; t < n; t++) {
final int id = t;
ts[t] = new Thread(() -> {
for (int k = 0; k < 100_000; k++) { b.lock(id); counter++; b.unlock(id); }
});
ts[t].start();
}
for (Thread t : ts) t.join();
System.out.println(counter); // 400000
}
}
The j >= i in the break condition covers j == i (a process never waits for itself) and the ID tie-break.
Hardware Solutions: Test-and-Set and Compare-and-Swap
Software-only algorithms are elegant but slow (O(n) entry) and need fences anyway. Every modern CPU offers an atomic read-modify-write instruction, which makes Attempt 1 correct because the check and the set happen as one indivisible step:
// test_and_set(&x): atomically { old = x; x = true; return old }
entry: while (test_and_set(&locked)) { }
exit: locked = false
// compare_and_swap(&x, expected, new): atomically
// { if (x == expected) { x = new; return true } return false }
entry: while (!compare_and_swap(&locked, false, true)) { }
exit: locked = false
These give mutual exclusion and progress, but not bounded waiting: a process that loses the race can lose it indefinitely. There are two standard fixes:
- Pass the baton (Silberschatz). On exit, scan
waiting[(i+1) % n], waiting[(i+2) % n], ...and hand the lock directly to the first waiter instead of releasing it. Any waiter enters within n − 1 turns. - Ticket lock.
my = fetch_and_add(&next, 1); while (serving != my) { }, and on exitserving++. This is the Bakery algorithm with an atomic dispenser: FIFO, two counters. Linux used ticket spinlocks before switching to queued (MCS) spinlocks, which avoid every waiter spinning on the same cache line. See Fairness: Ticket and Queued Spinlocks.
// TASLock.java — test-and-set and test-and-test-and-set spinlocks
import java.util.concurrent.atomic.AtomicBoolean;
class TASLock {
private final AtomicBoolean locked = new AtomicBoolean(false);
void lock() { while (locked.getAndSet(true)) Thread.onSpinWait(); }
void unlock() { locked.set(false); }
}
class TTASLock { // spin on a plain read first, so waiters share the cache line instead of bouncing it
private final AtomicBoolean locked = new AtomicBoolean(false);
void lock() {
while (true) {
while (locked.get()) Thread.onSpinWait();
if (locked.compareAndSet(false, true)) return;
}
}
void unlock() { locked.set(false); }
}
Trade-offs
| Solution | Processes | Needs atomics? | Bounded waiting | Uncontended cost | Notes |
|---|---|---|---|---|---|
| Disable interrupts | any (uniprocessor) | no | n/a | 2 instructions | Kernel-only, single CPU only |
| Peterson / Dekker | 2 | SC loads/stores + fence | yes (1) | a few stores + fence | Teaching tool; generalises poorly |
| Bakery | n | no (safe registers suffice) | yes, FCFS | O(n) reads | Unbounded tickets |
| TAS / CAS spinlock | n | yes | no | 1 atomic | Cache-line ping-pong under contention |
| Ticket lock | n | fetch-and-add | yes, FIFO | 1 atomic | All waiters spin on one line |
| MCS / queued lock | n | swap/CAS | yes, FIFO | 1 atomic | Each waiter spins locally; Linux qspinlock |
| Futex mutex | n | CAS + syscall | depends on wake policy | 1 atomic, no syscall | What pthread_mutex really is |
Where It Shows Up
Everywhere a lock exists. Peterson and Bakery are rarely deployed, but they teach the two points that matter: safety proofs assume a memory model, and mutual exclusion is easy while fairness is the hard part. The memory-model lesson explains why lock-free code written for x86 breaks on ARM servers. The fairness lesson explains why Linux replaced test-and-set spinlocks first with ticket locks and then with queued locks.
2. Producer–Consumer (Bounded Buffer)
Statement
One or more producers create items and put them into a shared buffer that holds at most N items. One or more consumers take items out. Producers must wait when the buffer is full, and consumers must wait when it is empty. Dijkstra posed it in 1965 and it is the most widely deployed synchronization pattern there is. For the application-level pattern, see Concurrency Patterns. Here we look at how it is built.
Invariants
- Safety:
0 ≤ count ≤ Nat all times. No item is lost or consumed twice. The buffer indices are never updated concurrently. - No busy waiting: a producer facing a full buffer sleeps, and does not poll.
- No deadlock: if the buffer is neither full nor empty, every thread can make progress. A sleeping thread must be woken when its condition becomes true (no lost wakeups).
Naive Attempt: Check the Count, Then Sleep
producer: consumer:
if (count == N) sleep() if (count == 0) sleep()
insert(item); count++ item = remove(); count--
if (count == 1) wakeup(consumer) if (count == N - 1) wakeup(producer)
The lost wakeup:
sequenceDiagram
participant C as Consumer
participant B as Buffer (count)
participant P as Producer
C->>B: read count = 0
Note over C: preempted before sleep()
P->>B: insert, count = 1
P->>C: wakeup(consumer)
Note over C: not asleep yet, so wakeup is lost
C->>C: sleep()
P->>B: fills buffer, count = N
P->>P: sleep()
Note over C,P: both asleep forever
The consumer decided to sleep based on a value that changed before it actually slept. The wakeup had nothing to wake. A semaphore fixes this because it counts: a V that arrives early is not lost, it is waiting for the next P.
Semaphore Solution
semaphore mutex = 1 // protects buffer, in, out
semaphore empty = N // number of free slots
semaphore full = 0 // number of filled slots
producer: consumer:
item = produce() P(full) // wait for an item
P(empty) // wait for a slot P(mutex)
P(mutex) item = buf[out]
buf[in] = item out = (out + 1) % N
in = (in + 1) % N V(mutex)
V(mutex) V(empty) // one more free slot
V(full) // one more item consume(item)
empty and full are counting semaphores that carry the condition. mutex protects the data structure. At all times empty + full + (items in transit inside a critical section) = N.
Why the Order of the P Operations Matters
Swap the two Ps in the producer, taking the mutex first:
producer (WRONG):
P(mutex)
P(empty) // may block while holding mutex
...
When the buffer is full:
| Step | Producer | Consumer | mutex | empty | full |
|---|---|---|---|---|---|
| 0 | 1 | 0 | N | ||
| 1 | P(mutex) succeeds | 0 | 0 | N | |
| 2 | P(empty) blocks, still holding mutex | 0 | 0 | N | |
| 3 | P(full) succeeds | 0 | 0 | N−1 | |
| 4 | P(mutex) blocks | 0 | 0 | N−1 | |
| 5 | waits for a consumer to V(empty) | waits for the producer to V(mutex) | deadlock |
sequenceDiagram
participant P as Producer
participant M as mutex
participant E as empty (0)
participant C as Consumer
P->>M: P(mutex) acquired
P->>E: P(empty) blocks
C->>M: P(mutex) blocks
Note over P,C: P holds mutex and waits for empty. C needs mutex to free a slot.
This is hold-and-wait plus circular wait, two of the Coffman conditions. The rule: never block on a condition while holding the lock that the condition's signaller needs. Acquire the counting semaphore first and the mutex last. The order of the V operations does not matter for correctness, because V never blocks.
Runnable Python:
# bounded_buffer_sem.py — python3 bounded_buffer_sem.py
import threading
N = 5
buf = [None] * N
in_idx = out_idx = 0
mutex = threading.Semaphore(1)
empty = threading.Semaphore(N)
full = threading.Semaphore(0)
PRODUCERS, CONSUMERS, ITEMS_EACH = 3, 3, 1000
consumed = []
consumed_lock = threading.Lock()
def producer(pid):
global in_idx
for k in range(ITEMS_EACH):
item = (pid, k)
empty.acquire() # P(empty) first
mutex.acquire() # then P(mutex)
buf[in_idx] = item
in_idx = (in_idx + 1) % N
mutex.release()
full.release() # V(full)
def consumer(_):
global out_idx
for _ in range(PRODUCERS * ITEMS_EACH // CONSUMERS):
full.acquire()
mutex.acquire()
item = buf[out_idx]
out_idx = (out_idx + 1) % N
mutex.release()
empty.release()
with consumed_lock:
consumed.append(item)
threads = [threading.Thread(target=producer, args=(i,)) for i in range(PRODUCERS)]
threads += [threading.Thread(target=consumer, args=(i,)) for i in range(CONSUMERS)]
for t in threads: t.start()
for t in threads: t.join()
assert sorted(consumed) == sorted((p, k) for p in range(PRODUCERS) for k in range(ITEMS_EACH))
print("ok:", len(consumed), "items, none lost or duplicated")
Monitor / Condition-Variable Solution
With a monitor, one lock protects the state and two condition variables carry the two conditions. This is how java.util.concurrent.ArrayBlockingQueue is built.
// BoundedBuffer.java
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
public class BoundedBuffer<T> {
private final Object[] items;
private int putIdx, takeIdx, count;
private final ReentrantLock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
public BoundedBuffer(int capacity) { items = new Object[capacity]; }
public void put(T x) throws InterruptedException {
lock.lock();
try {
while (count == items.length) // WHILE, not if
notFull.await(); // atomically releases lock and sleeps
items[putIdx] = x;
putIdx = (putIdx + 1) % items.length;
count++;
notEmpty.signal();
} finally {
lock.unlock();
}
}
@SuppressWarnings("unchecked")
public T take() throws InterruptedException {
lock.lock();
try {
while (count == 0)
notEmpty.await();
T x = (T) items[takeIdx];
items[takeIdx] = null;
takeIdx = (takeIdx + 1) % items.length;
count--;
notFull.signal();
return x;
} finally {
lock.unlock();
}
}
public static void main(String[] args) throws InterruptedException {
BoundedBuffer<Integer> bb = new BoundedBuffer<>(4);
int producers = 3, consumers = 2, perProducer = 10_000;
java.util.concurrent.atomic.AtomicLong sum = new java.util.concurrent.atomic.AtomicLong();
Thread[] ts = new Thread[producers + consumers];
for (int p = 0; p < producers; p++)
ts[p] = new Thread(() -> {
try { for (int i = 1; i <= perProducer; i++) bb.put(i); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
int total = producers * perProducer;
for (int c = 0; c < consumers; c++)
ts[producers + c] = new Thread(() -> {
try { for (int i = 0; i < total / consumers; i++) sum.addAndGet(bb.take()); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
for (Thread t : ts) t.start();
for (Thread t : ts) t.join();
long expected = (long) producers * perProducer * (perProducer + 1) / 2;
System.out.println(sum.get() == expected ? "ok" : "BROKEN");
}
}
await() removes the lost-wakeup race from the naive version, because releasing the lock and going to sleep happen as one atomic step. A signaller cannot slip in between the check and the sleep, since it needs the lock to change count.
Why while, Not if
Java, POSIX and nearly every real system use Mesa semantics: signal() is a hint that moves a waiter to the lock's entry queue. It does not hand over the lock. (Hoare's original monitors transferred the lock directly to the woken thread, which made if safe but cost extra context switches.) Between the signal and the moment the woken thread gets the lock back, another thread can change the state:
| Step | C1 | C2 | P | count |
|---|---|---|---|---|
| 1 | locks, sees count == 0, awaits (releases lock) | 0 | ||
| 2 | locks, inserts, signal(), unlocks | 1 | ||
| 3 | woken, waiting to reacquire lock | locks first, sees count == 1, takes the item | 0 | |
| 4 | reacquires lock. With if, it does not re-check and takes from an empty buffer | −1 |
POSIX (pthread_cond_wait) and Java (Object.wait, Condition.await) also explicitly allow spurious wakeups: a waiter may return with nobody having signalled, for example because the futex was woken by a signal handler or a multi-waiter broadcast. A while loop covers both the stolen wakeup and the spurious one. The rule: always re-check the predicate after waking.
One condition variable or two?
With a single condition (plain synchronized plus wait/notify), producers and consumers share one wait set. notify() might wake a producer when only consumers can make progress. That producer re-checks, waits again, and the wakeup is wasted. If the same thing happens repeatedly, every thread can end up waiting. With one condition you must use notifyAll(), which is correct but causes a thundering herd. Two conditions (notFull, notEmpty) let you signal() exactly the kind of thread that can proceed.
Go Channel Solution
A buffered channel is a bounded buffer: the runtime implements the mutex, the two wait queues and the ring buffer for you. With multiple producers, the standard shutdown pattern is a WaitGroup followed by a single close:
// boundedbuffer.go — go run boundedbuffer.go
package main
import (
"fmt"
"sync"
)
func main() {
const producers, consumers, perProducer = 3, 4, 10000
buf := make(chan int, 5) // capacity N = 5
var prodWG sync.WaitGroup
for p := 0; p < producers; p++ {
prodWG.Add(1)
go func() {
defer prodWG.Done()
for i := 1; i <= perProducer; i++ {
buf <- i // blocks when full
}
}()
}
go func() { prodWG.Wait(); close(buf) }() // only after ALL producers finish
sums := make(chan int)
for c := 0; c < consumers; c++ {
go func() {
s := 0
for v := range buf { // blocks when empty, exits when closed and drained
s += v
}
sums <- s
}()
}
total := 0
for c := 0; c < consumers; c++ {
total += <-sums
}
fmt.Println(total == producers*perProducer*(perProducer+1)/2) // true
}
Closing a channel from a producer while other producers are still sending causes a panic (send on closed channel). That is why exactly one goroutine closes it, after the WaitGroup says all producers are done. In Java or Python, the equivalent shutdown is one poison pill per consumer.
Correctness Argument
- No deadlock: every
P(full)is matched by a producer'sV(full)and everyP(empty)by a consumer'sV(empty). The mutex is never held while waiting on a counting semaphore. So if the buffer has an item, some consumer can completeP(full)and thenP(mutex), because the mutex is only held for a bounded, non-blocking critical section. - No starvation: this depends on the semaphore or lock being fair. With weak semaphores, one unlucky consumer could keep losing to the others. That is starvation of an individual thread, not of the system.
new ReentrantLock(true)or a FIFO semaphore removes it, at a throughput cost. - No busy waiting: all waits block.
Trade-offs and Variants
| Variant | When | Notes |
|---|---|---|
| SPSC ring buffer, no lock | Exactly one producer and one consumer | Producer writes only in, consumer only out. Needs only acquire/release atomics. See Lock-Free Programming. |
| Two locks (head and tail) | Linked queue, MPMC | LinkedBlockingQueue uses putLock and takeLock, so producers and consumers do not contend with each other |
| One lock, two conditions | Array queue, MPMC | ArrayBlockingQueue. Simpler, but one cache line under contention |
| Unbounded queue | Never in production | No backpressure, so memory grows until the OOM killer arrives |
| Disruptor | Ultra-low latency | Pre-allocated ring, sequence counters, batching, no locks |
Where It Shows Up
- Unix pipes: the kernel pipe buffer (64 KiB by default on Linux).
writeblocks when it is full andreadblocks when it is empty. - TCP: the receive window is a bounded buffer stretched across a network, and flow control is
P(empty). - Thread pools:
ThreadPoolExecutor's work queue,asyncio.Queue(maxsize=...), Go worker pools. - io_uring and NIC rings: single-producer/single-consumer rings shared between user space and kernel, or between kernel and device.
- Kafka and message queues are a bounded buffer stretched over disks, and consumer lag is the
fullcount.
3. Readers–Writers
Statement
A shared resource (a database table, a config map, a cache) is read often and written rarely. Any number of readers may access it at the same time, but a writer needs exclusive access: no other writer and no reader. Courtois, Heymans and Parnas posed the first two variants in 1971. The difference between them is entirely about who waits when both kinds are waiting.
Invariants
- Safety: at every instant, either (any number of readers and zero writers) or (zero readers and exactly one writer).
- Liveness: depends on the variant. Each classical variant picks one side to protect, and the other side can starve.
| Variant | Priority | Who can starve |
|---|---|---|
| First readers–writers | Readers. A new reader joins as long as any reader is active | Writers |
| Second readers–writers | Writers. Once a writer is waiting, no new reader may start | Readers |
| Third readers–writers | Arrival order (FIFO) | Nobody, given a FIFO semaphore |
Naive Attempt: One Mutex
Wrap every read and write in the same mutex. This is perfectly safe and has no starvation if the mutex is fair, but it serializes readers and throws away all the concurrency the problem allows. This "naive" solution is often the right production answer, as discussed below.
First Readers–Writers (Readers-Preference)
int read_count = 0
semaphore mutex = 1 // protects read_count
semaphore rw_mutex = 1 // held by "the readers as a group" or by one writer
writer:
P(rw_mutex)
write()
V(rw_mutex)
reader:
P(mutex)
read_count++
if (read_count == 1) P(rw_mutex) // first reader locks writers out
V(mutex)
read()
P(mutex)
read_count--
if (read_count == 0) V(rw_mutex) // last reader lets writers in
V(mutex)
This is the lightswitch pattern: the first reader into the room turns the light on (P(rw_mutex)) and the last one out turns it off. rw_mutex must be a semaphore, not an owned mutex, because the reader who acquires it is often not the reader who releases it.
How writers starve: as long as reader lifetimes overlap, read_count never reaches 0.
sequenceDiagram
participant R1
participant R2
participant R3
participant L as rw_mutex
participant W as Writer
R1->>L: first reader, P(rw_mutex)
W->>L: P(rw_mutex) blocks
R2->>R2: read_count = 2, no wait
R1->>R1: leaves, read_count = 1
R3->>R3: read_count = 2, no wait
R2->>R2: leaves, read_count = 1
Note over W: read_count never reaches 0 while readers keep overlapping
A detail worth knowing: while a writer holds rw_mutex, the first reader blocks on P(rw_mutex) while holding mutex. Every other reader then queues on mutex. This is intended, but it means readers are released one at a time in a chain once the writer leaves.
Second Readers–Writers (Writers-Preference)
Courtois et al.'s writers-preference solution adds a gate (read_try) that the first waiting writer closes against new readers, and a second lightswitch for writers:
int read_count = 0, write_count = 0
semaphore r_mutex = 1 // protects read_count
semaphore w_mutex = 1 // protects write_count
semaphore read_try = 1 // closed while any writer is waiting or writing
semaphore resource = 1 // the data
semaphore z = 1 // only one reader at a time may queue on read_try
reader:
P(z)
P(read_try)
P(r_mutex)
read_count++
if (read_count == 1) P(resource)
V(r_mutex)
V(read_try)
V(z)
read()
P(r_mutex)
read_count--
if (read_count == 0) V(resource)
V(r_mutex)
writer:
P(w_mutex)
write_count++
if (write_count == 1) P(read_try) // first writer closes the gate
V(w_mutex)
P(resource)
write()
V(resource)
P(w_mutex)
write_count--
if (write_count == 0) V(read_try) // last writer reopens it
V(w_mutex)
Why z? Without it, many readers could be queued on read_try along with the arriving writer. A weak semaphore might then let all those readers through ahead of the writer. With z, at most one reader is ever waiting on read_try, so a writer competes against at most one reader there.
How readers starve: a steady stream of writers keeps write_count ≥ 1, so read_try never reopens. With writes being rare by assumption this is less likely, but it is the mirror image of the first problem.
Third Readers–Writers (Fair, FIFO Turnstile)
Add one turnstile (also called a service queue) that everyone passes through in arrival order. A writer waiting in the turnstile blocks everyone who arrives after it, but not the readers already inside.
int read_count = 0
semaphore resource = 1
semaphore r_mutex = 1
semaphore service_queue = 1 // MUST be FIFO for the fairness guarantee
reader:
P(service_queue) // wait in line
P(r_mutex)
read_count++
if (read_count == 1) P(resource)
V(r_mutex)
V(service_queue) // let the next arrival line up
read()
P(r_mutex)
read_count--
if (read_count == 0) V(resource)
V(r_mutex)
writer:
P(service_queue)
P(resource) // waits for readers already inside to drain
V(service_queue)
write()
V(resource)
Correctness argument.
- Safety: readers and writers exclude each other through
resource, exactly as in the first solution. - No starvation: suppose a writer W gets
service_queue. Every later arrival, reader or writer, blocks onservice_queuebehind W. Readers already inside eventually finish (reads are finite),read_countreaches 0, W getsresource, then releasesservice_queue. A waiting reader is in the same position: it is in the FIFO queue, so a bounded number of arrivals ahead of it are served first. The guarantee needsservice_queueto be strong (FIFO). With a weak semaphore you get "usually fair". - No deadlock: the semaphores are always acquired in the order
service_queue→r_mutex→resource, which is a global order, so no cycle is possible.
Runnable Java. new Semaphore(1, true) is FIFO:
// FairRW.java — third readers-writers with a FIFO turnstile
import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;
public class FairRW {
private final Semaphore resource = new Semaphore(1, true);
private final Semaphore rMutex = new Semaphore(1, true);
private final Semaphore serviceQueue = new Semaphore(1, true); // FIFO
private int readCount = 0;
public void startRead() throws InterruptedException {
serviceQueue.acquire();
rMutex.acquire();
if (++readCount == 1) resource.acquire();
rMutex.release();
serviceQueue.release();
}
public void endRead() throws InterruptedException {
rMutex.acquire();
if (--readCount == 0) resource.release();
rMutex.release();
}
public void startWrite() throws InterruptedException {
serviceQueue.acquire();
resource.acquire();
serviceQueue.release();
}
public void endWrite() { resource.release(); }
// Demo: checks the invariant (readers > 0 implies writers == 0, writers <= 1)
static final AtomicInteger readers = new AtomicInteger(), writers = new AtomicInteger();
public static void main(String[] args) throws Exception {
FairRW rw = new FairRW();
Runnable reader = () -> {
try {
for (int i = 0; i < 2000; i++) {
rw.startRead();
readers.incrementAndGet();
if (writers.get() != 0) throw new IllegalStateException("reader saw a writer");
readers.decrementAndGet();
rw.endRead();
}
} catch (InterruptedException e) { Thread.currentThread().interrupt(); }
};
Runnable writer = () -> {
try {
for (int i = 0; i < 500; i++) {
rw.startWrite();
if (writers.incrementAndGet() != 1 || readers.get() != 0)
throw new IllegalStateException("writer not exclusive");
writers.decrementAndGet();
rw.endWrite();
}
} catch (InterruptedException e) { Thread.currentThread().interrupt(); }
};
Thread[] ts = { new Thread(reader), new Thread(reader), new Thread(reader),
new Thread(writer), new Thread(writer) };
for (Thread t : ts) t.start();
for (Thread t : ts) t.join();
System.out.println("ok");
}
}
RW Locks in Practice
Nobody hand-rolls these in production. They do, however, need to know which policy their library chose:
| Implementation | Policy | Gotchas |
|---|---|---|
glibc pthread_rwlock_t | Reader-preferring by default (PTHREAD_RWLOCK_PREFER_READER_NP), so writers can starve | Set PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP via pthread_rwlockattr_setkind_np to get writer preference. The plain PREFER_WRITER_NP value behaves like reader preference in glibc. |
Java ReentrantReadWriteLock (default, non-fair) | Barging allowed, but an arriving reader blocks if the thread at the head of the queue is a writer. This heuristic prevents writer starvation in practice. | No upgrade: a thread holding the read lock that calls writeLock().lock() deadlocks itself. Downgrade (write, then read, then release write) is allowed. |
Java ReentrantReadWriteLock(true) | Approximately FIFO (the third problem) | Lower throughput |
Java StampedLock | Optimistic reads: read without locking, then validate(stamp) | Not reentrant. Optimistic reads must tolerate inconsistent data until they validate. |
Go sync.RWMutex | Writer-preferring for new readers: once a goroutine is blocked in Lock(), new RLock() calls block. When the writer unlocks, the readers that were waiting are admitted before the next writer. Writers and readers alternate in batches, so neither starves. | Recursive read locking deadlocks: if goroutine A holds RLock, writer B calls Lock and blocks, and A calls RLock again, then A waits for B and B waits for A. The Go docs explicitly forbid it. |
Linux kernel rwlock_t / rw_semaphore | rwlock_t lets readers in interrupt context get in even when a writer is waiting, so writers can starve. rw_semaphore (sleeping, used for mmap_lock) queues fairly. | Kernel developers prefer RCU for read-mostly data |
The Go recursive-read deadlock as an interleaving:
sequenceDiagram
participant A as Goroutine A
participant L as RWMutex
participant B as Goroutine B
A->>L: RLock() ok
B->>L: Lock() blocks, waiting for readers to drain
Note over L: writer pending so new RLock calls must wait
A->>L: RLock() again (nested call) blocks behind B
Note over A,B: A waits for B, B waits for A to RUnlock
When an RW Lock Is Slower Than a Mutex
An RW lock is not free concurrency. Every RLock and RUnlock performs an atomic read-modify-write on the same shared counter. That cache line bounces between every core taking a read lock, so the readers serialize on cache coherence even though they are logically concurrent (see Cache Coherence and MESI). The RW lock loses when:
- The critical section is short (a map lookup, tens of nanoseconds). The cost of the lock dominates, and an RW lock's two atomics plus more complex state are slower than a mutex's single CAS.
- Writes are not actually rare. With more than roughly 10–20% writes, the bookkeeping buys nothing.
- There are many cores. Coherence traffic on the reader count grows with core count, so a 64-core box can show lower read throughput with an RW lock than with a mutex.
What to use instead, from cheapest to most work:
- Shard the data, with one mutex per shard (
ConcurrentHashMap's approach). - Copy-on-write snapshot: readers load an atomic pointer, and writers build a new copy and swap it in (Go
atomic.Pointer[T], JavaCopyOnWriteArrayList). - A seqlock or RCU, where readers write no shared memory at all (see Seqlocks and RCU).
- Per-CPU reader counts (Linux
percpu_rw_semaphore), which make reads cheap and writes expensive.
Always benchmark under realistic contention before choosing an RW lock over a mutex.
Where It Shows Up
- Databases: shared (S) and exclusive (X) locks in two-phase locking are readers–writers. Writer starvation in a reader-preferring lock manager shows up as a stuck
ALTER TABLEbehind a long-runningSELECT. MySQL's metadata locks queue writers to prevent this, which in turn blocks every newSELECTbehind the waitingALTER. That is writers-preference, and it is why online schema change tools exist. - Files:
flock(LOCK_SH)andflock(LOCK_EX), andfcntlbyte-range read and write locks. - Kernel:
mmap_lock(formerlymmap_sem), anrw_semaphoreand one of the most contended locks in Linux under page-fault-heavy, multithreaded workloads. - Applications: configuration and routing tables, in-process caches.
4. Dining Philosophers
Statement
Dijkstra, 1965; Hoare gave it the philosophers. Five philosophers sit at a round table. Between each pair of neighbours lies one fork (five forks in total). A philosopher alternates between thinking and eating, and needs both adjacent forks to eat: the left one (fork i) and the right one (fork (i+1) mod 5). Forks cannot be shared and cannot be taken from a philosopher who holds them.
flowchart LR
P0((P0)) --- F1[fork 1] --- P1((P1)) --- F2[fork 2] --- P2((P2))
P2 --- F3[fork 3] --- P3((P3)) --- F4[fork 4] --- P4((P4))
P4 --- F0[fork 0] --- P0
The forks are any resources that are each shared by exactly two parties, and the philosophers are threads that need two locks at once. Bank transfers that lock two accounts are dining philosophers.
Invariants
- Safety: a fork is held by at most one philosopher. Neighbours never eat at the same time.
- No deadlock: the system as a whole always makes progress.
- No starvation: every individual philosopher eventually eats. This is strictly stronger than no deadlock.
- Concurrency: up to ⌊5/2⌋ = 2 non-adjacent philosophers should be able to eat at the same time. A solution that lets only one eat at a time is correct but wasteful.
- No livelock: philosophers must not endlessly pick up and put down forks without anyone eating.
Naive Solution and the Circular Wait
semaphore fork[5] = {1, 1, 1, 1, 1}
philosopher i:
loop:
think()
P(fork[i]) // left
P(fork[(i + 1) % 5]) // right
eat()
V(fork[(i + 1) % 5])
V(fork[i])
If all five get hungry at the same moment and each picks up the left fork:
| Step | P0 | P1 | P2 | P3 | P4 |
|---|---|---|---|---|---|
| 1 | takes fork 0 | takes fork 1 | takes fork 2 | takes fork 3 | takes fork 4 |
| 2 | waits for fork 1 (P1 has it) | waits for fork 2 (P2) | waits for fork 3 (P3) | waits for fork 4 (P4) | waits for fork 0 (P0) |
| 3 | blocked forever | blocked forever | blocked forever | blocked forever | blocked forever |
The resource-allocation graph contains a cycle:
flowchart LR
P0((P0)) -- "holds" --> F0[fork 0]
P0 -. "waits" .-> F1[fork 1]
P1((P1)) -- "holds" --> F1
P1 -. "waits" .-> F2[fork 2]
P2((P2)) -- "holds" --> F2
P2 -. "waits" .-> F3[fork 3]
P3((P3)) -- "holds" --> F3
P3 -. "waits" .-> F4[fork 4]
P4((P4)) -- "holds" --> F4
P4 -. "waits" .-> F0
All four Coffman conditions hold: mutual exclusion (one philosopher per fork), hold and wait (holding the left fork while waiting for the right), no preemption (nobody can take a fork away), and circular wait (P0 → P1 → P2 → P3 → P4 → P0). Each solution below breaks exactly one of them.
A philosopher's life as a state machine (used by solution b):
stateDiagram-v2
[*] --> Thinking
Thinking --> Hungry: wants to eat
Hungry --> Eating: both forks available
Eating --> Thinking: puts both forks down
(a) Resource Hierarchy (Lock Ordering): Breaks Circular Wait
Number the forks and always pick up the lower-numbered fork first. For P0 through P3 that means left then right. For P4, whose forks are 4 and 0, it means fork 0 (the right one) first. P4 is the one philosopher who reaches the "other way".
philosopher i:
first = min(i, (i + 1) % 5)
second = max(i, (i + 1) % 5)
P(fork[first]); P(fork[second])
eat()
V(fork[second]); V(fork[first])
Why no deadlock: a cycle in the wait-for graph would need some philosopher holding a higher-numbered fork while waiting for a lower one. Nobody ever does that. Concretely, P0 and P4 now compete for fork 0 first, so at most one of them holds anything, and the five-way chain cannot close.
Starvation: possible with unfair locks. A fast neighbour can keep winning a contested fork. With FIFO locks, each fork has a bounded queue and every philosopher eventually eats.
// philosophers_ordered.go — go run philosophers_ordered.go
package main
import (
"fmt"
"sync"
"time"
)
const n = 5
func main() {
forks := make([]sync.Mutex, n) // slice of mutexes, never copied
meals := make([]int, n)
var wg sync.WaitGroup
for i := 0; i < n; i++ {
wg.Add(1)
go func(id int) {
defer wg.Done()
first, second := id, (id+1)%n
if first > second { // P4: take fork 0 before fork 4
first, second = second, first
}
for m := 0; m < 1000; m++ {
forks[first].Lock()
forks[second].Lock()
meals[id]++ // eat
forks[second].Unlock()
forks[first].Unlock()
time.Sleep(time.Microsecond) // think
}
}(i)
}
wg.Wait()
fmt.Println("meals:", meals) // [1000 1000 1000 1000 1000], never hangs
}
Delete the if first > second swap and the program will eventually print fatal error: all goroutines are asleep - deadlock!. Go's runtime detects the case where every goroutine is blocked.
This is the solution used in practice: transfer(a, b) locks the lower account ID first, the Linux kernel documents a lock order for every subsystem and checks it at runtime with lockdep, and Postgres takes locks in a fixed order where it can.
(b) The Waiter / Arbitrator: Breaks Hold-and-Wait
A philosopher asks a single arbitrator for both forks at once, and never holds one while waiting for the other. The textbook version (Dijkstra's, popularised by Tanenbaum) keeps a state[] array under one mutex. A philosopher may start eating only when neither neighbour is eating, and each philosopher has a private semaphore to sleep on.
enum { THINKING, HUNGRY, EATING } state[5]
semaphore mutex = 1
semaphore s[5] = {0, 0, 0, 0, 0} // one per philosopher, used as a signal
LEFT(i) = (i + 4) % 5
RIGHT(i) = (i + 1) % 5
take_forks(i):
P(mutex)
state[i] = HUNGRY
test(i) // try to get both forks
V(mutex)
P(s[i]) // block if test() did not grant them
put_forks(i):
P(mutex)
state[i] = THINKING
test(LEFT(i)) // maybe a neighbour can eat now
test(RIGHT(i))
V(mutex)
test(i):
if state[i] == HUNGRY and state[LEFT(i)] != EATING and state[RIGHT(i)] != EATING:
state[i] = EATING
V(s[i]) // remembered even if i has not reached P(s[i]) yet
Note the semaphore's memory at work: test(i) may V(s[i]) before philosopher i has reached P(s[i]), and the permit waits there. With a condition variable this would be a lost wakeup.
// philosophers_waiter.go — go run philosophers_waiter.go
package main
import (
"fmt"
"sync"
)
const n = 5
const (
thinking = iota
hungry
eating
)
type table struct {
mu sync.Mutex
state [n]int
s [n]chan struct{} // capacity-1 channel = binary semaphore initialised to 0
}
func newTable() *table {
t := &table{}
for i := range t.s {
t.s[i] = make(chan struct{}, 1)
}
return t
}
func left(i int) int { return (i + n - 1) % n }
func right(i int) int { return (i + 1) % n }
func (t *table) test(i int) { // caller holds t.mu
if t.state[i] == hungry && t.state[left(i)] != eating && t.state[right(i)] != eating {
t.state[i] = eating
t.s[i] <- struct{}{} // V(s[i])
}
}
func (t *table) takeForks(i int) {
t.mu.Lock()
t.state[i] = hungry
t.test(i)
t.mu.Unlock()
<-t.s[i] // P(s[i])
}
func (t *table) putForks(i int) {
t.mu.Lock()
t.state[i] = thinking
t.test(left(i))
t.test(right(i))
t.mu.Unlock()
}
func main() {
t := newTable()
meals := make([]int, n)
var wg sync.WaitGroup
for i := 0; i < n; i++ {
wg.Add(1)
go func(id int) {
defer wg.Done()
for m := 0; m < 1000; m++ {
t.takeForks(id)
t.mu.Lock()
if t.state[left(id)] == eating || t.state[right(id)] == eating {
panic("neighbours eating together")
}
t.mu.Unlock()
meals[id]++
t.putForks(id)
}
}(i)
}
wg.Wait()
fmt.Println("meals:", meals)
}
The channel send in test never blocks: s[i] gets at most one permit per hungry period, because state[i] becomes eating the moment the permit is sent, so test(i) cannot send a second one.
Why no deadlock: forks are only "taken" inside the critical section, atomically, and only if both are free. Nobody holds a fork while waiting.
Starvation: yes, this one can starve. If P1 and P3 alternate their meals so that at every moment at least one of them is eating, P2's test never succeeds:
sequenceDiagram
participant P1
participant P2
participant P3
P1->>P1: eating
P2->>P2: hungry, test fails (P1 eating)
P3->>P3: starts eating
P1->>P1: puts forks down, test(P2) fails (P3 eating)
P1->>P1: hungry again, starts eating
P3->>P3: puts forks down, test(P2) fails (P1 eating)
Note over P2: P2 starves although the system never deadlocks
You can fix it with aging (a hungry philosopher whose neighbour has been waiting longer defers to them) or with a FIFO ticket queue at the waiter. Both reduce concurrency.
A cruder waiter, a single sync.Mutex held while picking up both forks, is also deadlock-free, but a philosopher blocked on a fork while holding the waiter mutex stalls everybody behind it.
(c) Limit the Table to N − 1 Diners: Breaks Circular Wait
Let at most four philosophers sit down at once. A counting semaphore room = 4 does it:
semaphore room = 4
philosopher i:
P(room)
P(fork[i]); P(fork[(i + 1) % 5])
eat()
V(fork[(i + 1) % 5]); V(fork[i])
V(room)
Why no deadlock: by the pigeonhole principle, four philosophers sharing five forks means at least one of them can get both forks. They hold at most four forks between them in the worst case, and the fifth fork is free and adjacent to someone who already holds one. That philosopher eats, finishes, and releases forks. A full circular chain needs all five philosophers.
Starvation: none if room and the fork locks are FIFO. Each philosopher waits behind a bounded number of others at each step.
// Drop-in change to the naive version: a buffered channel as a counting semaphore.
room := make(chan struct{}, n-1)
// in each philosopher, around the naive left-then-right pickup:
room <- struct{}{} // P(room): blocks when 4 are already seated
forks[id].Lock()
forks[(id+1)%n].Lock()
meals[id]++
forks[(id+1)%n].Unlock()
forks[id].Unlock()
<-room // V(room)
This is the pattern behind admission control: connection-pool limits, bulkheads, and Kubernetes maxSurge all cap how many parties may be competing at once, which bounds contention and prevents some deadlocks. See Connection Pooling.
(d) Chandy–Misra (1984): Dirty and Clean Forks, Message Passing
Chandy and Misra generalised the problem to any number of philosophers on any conflict graph, with no shared memory: only messages between neighbours. That makes it a distributed algorithm, and it guarantees no starvation.
Rules.
- Every fork is held by exactly one of its two neighbours at any time, and is either dirty or clean.
- Initialisation: every fork starts dirty and is given to the neighbour with the lower ID. Define precedence: neighbour
ahas precedence overbifaholds their shared fork and it is clean, orbholds it and it is dirty. With the initial assignment, precedence simply follows ID order, so the precedence graph is acyclic. That is what breaks circular wait. - A hungry philosopher sends a request token to the neighbour for each fork it lacks.
- When a philosopher holding a fork receives a request:
- if the fork is clean, keep it and remember the request (defer it);
- if the fork is dirty, clean it and send it to the requester, even if you are hungry yourself.
- A philosopher eats when it holds both forks. After eating, both forks become dirty, and any deferred requests are honoured (each fork cleaned and sent).
philosopher i, for each neighbour j with shared fork f:
have[f], dirty[f], requested[f] // local state only
on becoming hungry:
for each fork f not held: send REQUEST(f) to neighbour
wait until holding all forks
eat()
for each fork f: dirty[f] = true
for each f with requested[f]: dirty[f] = false, send FORK(f), have[f] = false
on receiving REQUEST(f):
if dirty[f] and not eating:
dirty[f] = false, send FORK(f), have[f] = false
else:
requested[f] = true // defer: clean fork, or currently eating
on receiving FORK(f):
have[f] = true, dirty[f] = false
Why it works. "Dirty" means "I have eaten with this fork since I received it". A philosopher who has eaten must yield to a neighbour who asks, and a philosopher who received a fork (clean) keeps it until it has eaten. The precedence graph only changes when someone eats. Eating dirties all of the eater's forks, so every neighbour now has precedence over the eater, and the eater becomes a sink. Turning a node into a sink cannot create a cycle, since a cycle needs an edge leaving every node on it. So the graph stays acyclic, there is no deadlock, and every hungry philosopher rises in priority until it eats: no starvation.
Coffman mapping: the initial assignment breaks circular wait, and the "dirty forks must be surrendered" rule is a controlled form of preemption.
Costs: messages per meal are proportional to the node's degree. It needs neighbour-to-neighbour reliable channels and suits distributed resource allocation, where the forks are leases on shared resources between nodes. For distributed locks in practice, see Distributed Locking.
(e) Try-Lock with Timeout and Back-Off: Breaks Hold-and-Wait (and No-Preemption, Voluntarily)
Take the left fork. Try to take the right one. If it is busy, put the left one down, wait a while, and retry. The philosopher preempts itself.
# philosophers_trylock.py — python3 philosophers_trylock.py
import random, threading, time
N, MEALS = 5, 200
forks = [threading.Lock() for _ in range(N)]
meals = [0] * N
def philosopher(i):
left, right = forks[i], forks[(i + 1) % N]
backoff = 0.0001
while meals[i] < MEALS:
with left:
if right.acquire(timeout=0.001): # bounded wait, never forever
try:
meals[i] += 1 # eat
backoff = 0.0001
finally:
right.release()
continue
# could not get the right fork: left is already released by the with-block
time.sleep(random.uniform(0, backoff)) # RANDOMISED back-off
backoff = min(backoff * 2, 0.01) # exponential, capped
ts = [threading.Thread(target=philosopher, args=(i,)) for i in range(N)]
for t in ts: t.start()
for t in ts: t.join()
print("meals:", meals) # all 200, no hang
Why no deadlock: nobody waits indefinitely while holding a fork, so hold-and-wait never persists.
Livelock risk: if every philosopher uses the same fixed delay, they can move in lockstep (all pick up left, all fail right, all put down, all wait 1 ms, repeat). Everyone is busy and nobody eats. Randomised exponential back-off breaks the symmetry, the same trick Ethernet's CSMA/CD and TCP retransmission use. Progress then holds only with high probability, and an individual philosopher can still be unlucky for a long time. See Livelock.
In practice, the Linux kernel uses spin_trylock with back-off on paths that must take locks against the documented order. Databases and lock managers use lock timeouts (innodb_lock_wait_timeout, lock_timeout in Postgres), followed by an abort and retry. Go has sync.Mutex.TryLock (since 1.18), but its docs warn that correct uses are rare.
Summary: Five Solutions Against Four Conditions
| Solution | Coffman condition broken | Deadlock-free | Starvation-free | Max concurrent eaters | Practical use |
|---|---|---|---|---|---|
| (a) Resource ordering | Circular wait | Yes | With FIFO locks | 2 | Most common: lock ordering by ID or address, lockdep |
| (b) Waiter / state monitor | Hold and wait | Yes | No (neighbours can collude) | 2 | Central lock managers, "acquire all locks at once" APIs |
| (c) N − 1 at the table | Circular wait | Yes | With FIFO semaphores | 2 | Admission control, bulkheads, pool limits |
| (d) Chandy–Misra | Circular wait (acyclic priority) + preemption | Yes | Yes | 2 | Distributed resource allocation |
| (e) Try-lock + back-off | Hold and wait / no preemption | Yes | Probabilistic | 2 | Lock timeouts, optimistic retry, reverse-order kernel paths |
| Single global lock | Mutual exclusion is coarse | Yes | With a fair lock | 1 | Python's GIL, early Linux "Big Kernel Lock" |
Detection instead of prevention
Databases usually do not prevent deadlock at all. They let transactions lock rows in whatever order the queries dictate, maintain a wait-for graph, and when they find a cycle they abort one victim (ERROR: deadlock detected in Postgres). For the general workload this is cheaper than imposing an order. See Detecting Deadlocks.
Where It Shows Up
- Any code that takes two locks: account transfers, moving an item between two queues, renaming a file across two directories (the kernel's
lock_renameorders the two directory locks by ancestry). - Database row locks: two transactions updating rows A and B in opposite orders, which the DB resolves by detection.
- Distributed systems: services that each hold a lease and need a neighbour's. Chandy–Misra-style priority ordering is one way to resolve that without a central coordinator.
5. The Sleeping Barber
Statement
Dijkstra, 1965. A barbershop has one barber, one barber chair and a waiting room with N chairs.
- If there are no customers, the barber sleeps in the barber chair.
- An arriving customer who finds the barber asleep wakes him.
- An arriving customer who finds the barber busy sits in a free waiting chair. If every chair is taken, the customer leaves (the request is rejected).
- When the barber finishes a haircut he takes the next waiting customer, or goes back to sleep if there is none.
This is producer–consumer with two twists: the buffer rejects instead of blocking when full, and the consumer must sleep without missing a wakeup when the buffer is empty.
Invariants
- Safety: waiting customers never exceed
N, and no two customers take the same chair. The barber cuts at most one customer's hair at a time, and only a customer who is actually present. - No lost wakeups: the barber never sleeps while a customer is waiting, and a customer never waits while the barber sleeps.
- No busy waiting: the barber sleeps, and does not poll the waiting room.
The Naive Attempt and Its Race
"Barber: if the waiting room is empty, go to sleep. Customer: if the barber is asleep, wake him, else sit down."
sequenceDiagram
participant B as Barber
participant W as Waiting room
participant C as Customer
B->>W: looks, room is empty
Note over B: walking back to his chair
C->>B: looks, barber is not asleep (he is walking)
C->>W: sits down to wait
B->>B: falls asleep in the chair
Note over B,C: barber sleeps while a customer waits, forever
This is the same lost wakeup as in producer–consumer: each party decides based on a state that changes before it acts. There is a second race as well. Two customers arriving together can both see one free chair and both sit in it. Both races need the same fix: the "look" and the "act" must happen inside one critical section, and the wakeup must be remembered if it arrives early.
Semaphore Solution
semaphore customers = 0 // number of customers waiting; the barber sleeps on it
semaphore barber_ready = 0 // the barber signals "next, please"
semaphore seats_mutex = 1 // protects free_seats
int free_seats = N
barber:
loop:
P(customers) // sleep until someone is waiting
P(seats_mutex)
free_seats++ // one customer leaves the waiting room for the chair
V(barber_ready) // call that customer
V(seats_mutex)
cut_hair()
customer:
P(seats_mutex)
if free_seats > 0:
free_seats-- // take a seat
V(customers) // wake the barber (remembered if he is busy)
V(seats_mutex)
P(barber_ready) // wait to be called
get_haircut()
else:
V(seats_mutex)
leave() // shop full: reject
Why the race is gone. The customer's check (free_seats > 0) and action (free_seats--, V(customers)) happen under seats_mutex, so two customers cannot claim one seat. More importantly, the barber does not look at the room and then decide to sleep. He does P(customers), which sleeps only if the count is zero. If a customer arrived during the haircut, customers is already 1, and the barber's P returns immediately. The V is a stored fact, not a fleeting event.
Deadlock and starvation. Every waiting customer has performed V(customers) exactly once, and the barber does V(barber_ready) exactly once per P(customers), so the counts always match. The mutex is never held across a blocking P. With weak semaphores the barber may call a later arrival before an earlier one: barber_ready does not promise FIFO, so an individual customer can in principle be overtaken repeatedly. A FIFO semaphore, or a queue of per-customer semaphores, gives first-come-first-served order.
# sleeping_barber.py — python3 sleeping_barber.py
import random, threading, time
N_CHAIRS = 3
customers = threading.Semaphore(0)
barber_ready = threading.Semaphore(0)
seats_mutex = threading.Lock()
free_seats = N_CHAIRS
served, turned_away = [], []
def barber():
global free_seats
while True:
customers.acquire() # sleeps when nobody is waiting
with seats_mutex:
free_seats += 1
barber_ready.release()
time.sleep(random.uniform(0.001, 0.004)) # cut hair
def customer(i):
global free_seats
with seats_mutex:
if free_seats == 0:
turned_away.append(i) # shop full: leave
return
free_seats -= 1
customers.release()
barber_ready.acquire()
served.append(i) # in the chair
threading.Thread(target=barber, daemon=True).start()
cs = []
for i in range(200):
t = threading.Thread(target=customer, args=(i,))
cs.append(t)
t.start()
time.sleep(random.uniform(0, 0.003)) # random arrivals
for t in cs: t.join()
assert len(served) + len(turned_away) == 200
assert len(set(served)) == len(served)
print(f"served {len(served)}, turned away {len(turned_away)}")
Extension: make the customer wait until the haircut is finished
The version above lets the customer leave as soon as they sit in the chair. To make each side wait for the other at the end of the haircut, add a rendezvous: customer_done = 0, barber_done = 0. The customer does V(customer_done); P(barber_done) and the barber does P(customer_done); V(barber_done). Neither proceeds until both have arrived. Because there is only one barber chair, at most one customer is ever inside this rendezvous, so the semaphores cannot be "stolen" by the next customer. With several barbers you need per-customer semaphores (the Hilzer's barbershop variant).
Go: The Waiting Room Is a Buffered Channel
// sleepingbarber.go — go run sleepingbarber.go
package main
import (
"fmt"
"math/rand"
"sync"
"time"
)
func main() {
const chairs, total = 3, 200
waiting := make(chan int, chairs) // the waiting room
var served, turnedAway int
done := make(chan struct{})
go func() { // barber: blocking receive = sleeping when the room is empty
for range waiting {
time.Sleep(time.Duration(1+rand.Intn(3)) * time.Millisecond)
served++
}
close(done)
}()
var wg sync.WaitGroup
var mu sync.Mutex
for i := 0; i < total; i++ {
wg.Add(1)
go func(id int) {
defer wg.Done()
select {
case waiting <- id: // a free chair: sit down (wakes the barber if asleep)
default: // every chair taken: leave
mu.Lock()
turnedAway++
mu.Unlock()
}
}(i)
time.Sleep(time.Duration(rand.Intn(3)) * time.Millisecond)
}
wg.Wait()
close(waiting) // no more customers
<-done
fmt.Println("served", served, "turned away", turnedAway, "total", served+turnedAway)
}
select with default is a non-blocking send: an atomic "check for a free chair and take it". The channel's internal lock does what seats_mutex did, and a blocking receive does what P(customers) did. served is written only by the barber goroutine and read after <-done, and closing done creates the necessary happens-before edge.
Trade-offs and Where It Shows Up
The sleeping barber models a bounded queue with load shedding: reject at the door rather than queueing without limit.
ThreadPoolExecutorwith a boundedArrayBlockingQueueandAbortPolicy: when the pool and the queue are full,submitthrowsRejectedExecutionException.- A server returning HTTP 503 or 429 when its accept queue is full, which keeps latency bounded under overload (see Backpressure Patterns).
- The kernel's listen backlog: connections beyond the
listen()backlog are dropped, or answered with SYN cookies. - Any worker that sleeps on a futex,
epoll_waitor a condition variable and must not miss the event that arrives between "nothing to do" and "go to sleep".
With B barbers and N chairs this is an M/M/B/B+N queue in queueing theory. Little's Law and the Erlang formulas tell you how many customers are turned away for a given arrival rate.
6. The Cigarette Smokers Problem
Statement
Suhas Patil, 1971. Making a cigarette takes three ingredients: tobacco, paper and matches. There are three smokers, each with an infinite supply of one ingredient. An agent has an infinite supply of all three. In a loop, the agent places two different ingredients on the table at random. The smoker who has the third ingredient should pick up both, make a cigarette, signal the agent, and smoke. The agent then puts out the next pair.
The catch is that the agent's code is fixed and you cannot change it:
semaphore agent_sem = 1
semaphore tobacco = 0, paper = 0, match = 0
agent A: P(agent_sem); V(tobacco); V(paper)
agent B: P(agent_sem); V(paper); V(match)
agent C: P(agent_sem); V(tobacco); V(match)
// one of the three runs on each round (randomly), in a loop
The agent signals ingredients, not smokers. You write the smokers (and any helper threads).
Invariants
- Safety: only the smoker who has the missing ingredient takes the two on the table. No ingredient is taken by two parties.
- No deadlock: every round ends with one cigarette smoked and the agent signalled.
- Constraint: the agent may not be modified, so the agent's interface (two independent
Vs) is the whole difficulty.
The Obvious Attempt and the Deadlock
Each smoker waits for its two missing ingredients:
smoker with matches: P(tobacco); P(paper); smoke(); V(agent_sem)
smoker with tobacco: P(paper); P(match); smoke(); V(agent_sem)
smoker with paper: P(tobacco); P(match); smoke(); V(agent_sem)
The agent puts out tobacco and paper, so the smoker with matches should get them:
| Step | Agent | Smoker-with-paper | Smoker-with-matches | tobacco | paper |
|---|---|---|---|---|---|
| 1 | V(tobacco) | 1 | 0 | ||
| 2 | P(tobacco) succeeds (it wanted tobacco and matches) | 0 | 0 | ||
| 3 | V(paper) | 0 | 1 | ||
| 4 | P(match) blocks | P(tobacco) blocks | 0 | 1 | |
| 5 | P(agent_sem) blocks | waiting for matches | waiting for tobacco | deadlock |
The wrong smoker grabbed half of the pair. This is hold-and-wait again: a smoker holds one resource while waiting for a second one that will never come.
Patil's Argument
Patil used the problem to argue that Dijkstra's P and V are not expressive enough. He showed that under his rules (the agent is fixed, and the smokers may use only P and V on semaphores, with no conditional statements) no solution exists. The obstacle is that a smoker must wait for "tobacco AND paper", and a sequence of single P operations always commits to one ingredient before seeing the other. He proposed a primitive that acquires several semaphores atomically (a simultaneous P on a set).
David Parnas replied (1975) that the restriction on conditionals is artificial: allow ordinary if statements and shared variables, and the problem becomes solvable. It is now taught as an exercise in dispatching on combinations of events rather than as an impossibility result. Real systems did add atomic multi-semaphore operations. System V semop() applies an array of operations to a semaphore set all-or-nothing, and Windows WaitForMultipleObjects(..., bWaitAll=TRUE) waits for all handles at once.
The Pusher Solution
From Allen Downey's The Little Book of Semaphores. Add three pusher threads, one per ingredient. A pusher wakes when its ingredient appears, records it on a shared blackboard, and if it sees the other ingredient already recorded, it knows exactly which smoker to wake.
bool is_tobacco = false, is_paper = false, is_match = false
semaphore mutex = 1
semaphore tobacco_smoker = 0, paper_smoker = 0, match_smoker = 0 // named by what the smoker HAS
pusher_tobacco:
loop:
P(tobacco)
P(mutex)
if is_paper: is_paper = false; V(match_smoker) // tobacco + paper → matches smoker
else if is_match: is_match = false; V(paper_smoker) // tobacco + match → paper smoker
else: is_tobacco = true
V(mutex)
// pusher_paper and pusher_match are symmetric
smoker_with_tobacco:
loop:
P(tobacco_smoker)
make_cigarette()
V(agent_sem)
smoke()
Runnable Python, with the three pushers and three smokers generated from one function each:
# smokers.py — python3 smokers.py
import random, threading
ING = ("tobacco", "paper", "match")
agent_sem = threading.Semaphore(1)
on_table_sem = {k: threading.Semaphore(0) for k in ING} # the agent's semaphores
smoker_sem = {k: threading.Semaphore(0) for k in ING} # keyed by the ingredient the smoker HAS
mutex = threading.Lock()
seen = {k: False for k in ING} # the pushers' blackboard
smoked = {k: 0 for k in ING}
ROUNDS = 300
def agent(): # unmodified logic: P(agent_sem), then V two ingredients
for _ in range(ROUNDS):
agent_sem.acquire()
a, b = random.sample(ING, 2)
on_table_sem[a].release()
on_table_sem[b].release()
def pusher(mine):
while True:
on_table_sem[mine].acquire()
with mutex:
other = next((k for k in ING if k != mine and seen[k]), None)
if other is None:
seen[mine] = True # first of the pair: record it
else:
seen[other] = False # second of the pair: dispatch
missing = next(k for k in ING if k not in (mine, other))
smoker_sem[missing].release()
def smoker(has):
while True:
smoker_sem[has].acquire()
smoked[has] += 1 # make cigarette
agent_sem.release() # tell the agent
# smoke() would go here, outside any lock
for k in ING:
threading.Thread(target=pusher, args=(k,), daemon=True).start()
threading.Thread(target=smoker, args=(k,), daemon=True).start()
a = threading.Thread(target=agent)
a.start(); a.join()
agent_sem.acquire() # wait for the final round's smoker
assert sum(smoked.values()) == ROUNDS
print(smoked)
Correctness Argument
- Safety: the blackboard is read and written only under
mutex. In each round exactly two ingredient semaphores are posted, so exactly two pushers wake. Whichever runs first finds the blackboard empty and records its ingredient. The second finds it, clears it, and wakes the one smoker whose ingredient is missing. No smoker ever holds a partial pair, because smokers only ever wait on their own semaphore. - No deadlock: the blackboard is empty again before
V(agent_sem)can happen (the second pusher clears it before waking the smoker, and the smoker signals the agent). So every round starts from a clean state. - No starvation: there is nothing to starve. The agent's random choice decides which smoker smokes, and each pair maps to exactly one smoker.
The general lesson
When a thread needs a combination of events and the events arrive separately, do not have consumers grab pieces. Put a dispatcher in between that collects the pieces under one lock and hands the complete set to the right consumer. Go's select, actor mailboxes, and join patterns are all versions of this idea. In the generalised version, where the agent does not wait for the smoker, replace the booleans with counters (num_tobacco, ...) so that several pending ingredients can accumulate.
Where It Shows Up
- Dataflow and join scheduling: a task that runs when all of its inputs are ready (Airflow and Spark DAG schedulers, CompletableFuture's
allOf, make). - Matching engines and pairing: matching a buyer to a seller, or a ride request to a driver. A coordinator with a book of pending items avoids partial grabs.
- Resource managers that allocate atomically: a scheduler that must place a job only when CPU, memory and GPU are free on one node gang-allocates, instead of letting the job hold the CPU while waiting for the GPU.
7. The Santa Claus Problem
Statement
John Trono, 1994. Santa sleeps in his shop at the North Pole. He can be woken in two ways:
- All nine reindeer have returned from their vacation in the South Pacific. Santa harnesses them to the sleigh and they deliver toys. The reindeer then go back on vacation.
- Three elves need help making toys. Santa helps all three together. Further elves who need help must wait until those three have been helped. Elves never wake Santa one or two at a time.
If both conditions hold when Santa wakes, the reindeer have priority: the elves will wait until after Christmas.
Invariants
- Safety: Santa helps elves only in groups of exactly three. He delivers only when all nine reindeer are back. A fourth elf never joins a group that is being helped.
- Priority: if nine reindeer and three elves are both waiting, the reindeer go first.
- No deadlock and no lost wakeups: Santa must be woken exactly when a condition becomes true, and every waiting party must eventually be served.
- No busy waiting: Santa sleeps on a semaphore, not in a polling loop.
Naive Attempt: Santa Polls Two Counters
"Santa loops: if reindeer == 9 deliver, else if elves >= 3 help." This is busy waiting, and it is also wrong without a lock: two elves can both read elves == 2, both increment and both conclude they are the third, or a fourth elf can slip into the group after Santa started helping. If you add sleeping, you are back to the lost wakeup problem from producer–consumer: Santa checks both counters, finds neither ready, and while he is "lying down" the ninth reindeer arrives and signals nobody.
Semaphore Solution
Based on Downey's solution, with one correction (the reindeer barrier) explained below:
int elves = 0, reindeer = 0
semaphore mutex = 1 // protects both counters
semaphore santa_sem = 0 // wakes Santa; posted by the 9th reindeer or the 3rd elf
semaphore reindeer_sem = 0 // reindeer wait to be hitched
semaphore hitched = 0 // each reindeer reports "I am hitched"
semaphore elf_sem = 0 // elves wait for Santa's help
semaphore elf_tex = 1 // admits one group of 3 elves at a time
santa:
loop:
P(santa_sem)
P(mutex)
if reindeer == 9: // checked FIRST: reindeer have priority
reindeer = 0
prepare_sleigh()
V(reindeer_sem) × 9
P(hitched) × 9 // all nine hitched before anyone can re-count
else if elves == 3:
help_elves()
V(elf_sem) × 3
V(mutex)
reindeer:
loop:
vacation()
P(mutex)
reindeer++
if reindeer == 9: V(santa_sem)
V(mutex)
P(reindeer_sem)
get_hitched(); V(hitched)
deliver_toys()
elf:
loop:
work() // until stuck
P(elf_tex) // only 3 elves past here at a time
P(mutex)
elves++
if elves == 3: V(santa_sem) // third elf wakes Santa, keeps elf_tex closed
else: V(elf_tex) // first and second let the next elf in
V(mutex)
P(elf_sem)
get_help()
P(mutex)
elves--
if elves == 0: V(elf_tex) // last of the group reopens the door
V(mutex)
How the pieces fit.
elf_texis a turnstile that closes after three. The first two elves pass it and reopen it. The third keeps it closed, so a fourth elf waits outside until the whole group has been helped and the last helped elf reopens it. This is the "further elves must wait" rule.santa_semis posted once per event (a full set of reindeer, or a group of elves). If both happen before Santa wakes, it has count 2. Santa handles the reindeer first because he checks them first, then loops, takes the second permit, and findselves == 3.- The counters are read and written under
mutex, so "am I the 9th reindeer?" and "am I the 3rd elf?" are each true for exactly one thread.
The re-counting bug, and why `hitched` is there
Downey's published version releases reindeer_sem nine times and moves on. Consider a fast reindeer A that takes a permit, gets hitched, delivers, finishes a very short vacation, increments reindeer again, and calls P(reindeer_sem), all before a slow reindeer B has taken its permit from the previous round. A takes B's permit. B is now waiting for a permit that no longer exists, and B is not counted in the new round. The new round can then never reach nine. The P(hitched) × 9 loop, done while Santa still holds mutex, guarantees that all nine permits are consumed by the nine reindeer of this round before any of them can increment the counter again. (In the story vacations last a year, so it never happens. In code, "it would have to be slow" is not a correctness argument.)
The elves do not need this fix: a helped elf cannot reach P(elf_sem) again without first passing elf_tex, which stays closed until all three members of the group have decremented elves, which they do only after taking their permits.
// SantaClaus.java — javac SantaClaus.java && java SantaClaus
import java.util.concurrent.Semaphore;
import java.util.concurrent.ThreadLocalRandom;
public class SantaClaus {
static final Semaphore mutex = new Semaphore(1), santaSem = new Semaphore(0),
reindeerSem = new Semaphore(0), hitched = new Semaphore(0),
elfSem = new Semaphore(0), elfTex = new Semaphore(1);
static int elves = 0, reindeer = 0; // guarded by mutex
static void pause(int maxMs) throws InterruptedException {
Thread.sleep(ThreadLocalRandom.current().nextInt(maxMs + 1));
}
public static void main(String[] args) throws InterruptedException {
Thread santa = new Thread(() -> {
try {
int deliveries = 0;
while (deliveries < 3) {
santaSem.acquire();
mutex.acquire();
if (reindeer == 9) {
reindeer = 0;
System.out.println("Santa: sleigh ready, delivery " + (++deliveries));
reindeerSem.release(9);
hitched.acquire(9); // see the warning above
} else if (elves == 3) {
System.out.println("Santa: helping three elves");
elfSem.release(3);
}
mutex.release();
}
} catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
for (int r = 0; r < 9; r++) {
Thread t = new Thread(() -> {
try {
while (true) {
pause(20); // vacation
mutex.acquire();
if (++reindeer == 9) santaSem.release();
mutex.release();
reindeerSem.acquire();
hitched.release(); // get hitched
pause(2); // deliver toys
}
} catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
t.setDaemon(true);
t.start();
}
for (int e = 0; e < 10; e++) {
final int id = e;
Thread t = new Thread(() -> {
try {
while (true) {
pause(10); // work until stuck
elfTex.acquire();
mutex.acquire();
if (++elves == 3) santaSem.release();
else elfTex.release();
mutex.release();
elfSem.acquire();
System.out.println(" elf " + id + " got help");
mutex.acquire();
if (--elves == 0) elfTex.release();
mutex.release();
}
} catch (InterruptedException ex) { Thread.currentThread().interrupt(); }
});
t.setDaemon(true);
t.start();
}
santa.start();
santa.join(); // daemon threads die with the JVM
}
}
Correctness Argument
- Groups of exactly three: at most three elves can be between
P(elf_tex)and the finalelves--, since the door is reopened only atelves == 0and the first two each reopen it only for one more elf. Santa'selves == 3test is made undermutex. - Priority: whenever Santa wakes, he tests
reindeer == 9first. The reindeer cannot lose to the elves while both are pending. - No lost wakeup: the ninth reindeer and the third elf post
santa_semunder the same mutex that protects the counters. If Santa is busy, the permit waits. Santa'sP(santa_sem)count always equals the number of pending events. - No deadlock:
mutexis held by Santa while he waits onhitched, but the reindeer posthitchedwithout needingmutex. Nobody else blocks on anything while holdingmutex. - Starvation: elves can be delayed indefinitely if the reindeer were always ready, but that is the specified priority, not a bug. Within the elves,
elf_texis a weak semaphore in this code, so a particular elf could keep losing the race for a place in a group.new Semaphore(1, true)makes it FIFO.
Where It Shows Up
- Priority between two classes of work sharing one server: interactive requests ahead of batch jobs, and a GC's stop-the-world phase ahead of allocation requests.
- Batching into fixed-size groups: database group commit (flush the log once for several transactions), batching GPU kernels, and forming a quorum of three before proceeding.
- The
elf_texdoor that closes afterkentrants is a building block of its own, used whenever exactlykthreads must form a group (the companion page's LeetCode-style variants use the same idea).
8. Barriers and the Reusable Two-Phase Barrier
Statement
n threads each run phase 1 of a computation, and none may start phase 2 until all have finished phase 1. For iterative algorithms, the same barrier is used every round (a reusable or cyclic barrier). Barriers are the building block hidden in several of the problems above: Santa's hitched loop is a barrier between Santa and the reindeer, and the barber's rendezvous is a two-thread barrier.
Invariants
- Safety: no thread passes the barrier for round
runtil allnthreads have arrived at it for roundr. With reuse, no thread may get into roundr + 1's barrier and pass it while others are still leaving roundr's. - No deadlock: once the
nth thread arrives, everyone gets through. - No busy waiting.
Step 1: A One-Shot Barrier (Rendezvous plus Turnstile)
int count = 0
semaphore mutex = 1
semaphore barrier = 0
P(mutex); count++; V(mutex)
if count == n: V(barrier)
P(barrier) // turnstile: pass through ...
V(barrier) // ... and let the next one through
// critical point
The turnstile pattern P(barrier); V(barrier) lets threads pass one at a time once it has been opened. The last arrival opens it, and each thread passing through reopens it for the next. (Reading count outside the mutex is harmless here only because it only grows. Two threads may both see n and post twice, which leaves one extra permit, and that matters as soon as you reuse the barrier.)
Step 2: The Naive Reusable Barrier, and How a Fast Thread Laps the Others
The obvious way to reuse it is to count back down and close the turnstile:
P(mutex); count++; V(mutex)
if count == n: V(turnstile)
P(turnstile); V(turnstile)
// critical point
P(mutex); count--; V(mutex)
if count == 0: P(turnstile) // close it again
With n = 2:
| Step | T1 | T2 | count | turnstile |
|---|---|---|---|---|
| 1 | count = 1 | 1 | 0 | |
| 2 | count = 2, sees 2, V(turnstile) | 2 | 1 | |
| 3 | P and V the turnstile, passes | 2 | 1 | |
| 4 | count = 1 (leaving) | 1 | 1 | |
| 5 | loops to the next round: count = 2, sees 2, V(turnstile) | 2 | 2 | |
| 6 | passes round 2's turnstile while T2 is still in round 1 |
The turnstile is still open from round 1 when T1 comes round again, so T1 laps T2. The checks of count outside the mutex add further bugs (double V, or two threads both thinking they are last). The fix is two turnstiles: one that is open while threads enter and closed while they leave, and one that does the opposite. The barrier then works like an airlock.
Step 3: The Two-Phase Barrier
int count = 0
semaphore mutex = 1
semaphore turnstile = 0 // phase 1 gate: closed at start
semaphore turnstile2 = 0 // phase 2 gate: closed at start
wait():
// phase 1: arrive
P(mutex)
count++
if count == n: V(turnstile) × n // last arrival lets all n through
V(mutex)
P(turnstile)
// critical point: all n have arrived
// phase 2: depart
P(mutex)
count--
if count == 0: V(turnstile2) × n // last to leave lets all n out
V(mutex)
P(turnstile2)
This variant from Downey preloads n permits instead of chaining turnstile passes, which is simpler to reason about and avoids a chain of n context switches.
Correctness argument.
- Phase 1 safety:
turnstilestarts at 0 and receives exactlynpermits, posted only by thenth arrival. So nobody passes before everyone has arrived, and exactlynthreads pass. - No lapping: a fast thread that finishes phase 1 must take a
turnstile2permit before it can start the next round. Those are posted only whencountreturns to 0, which means allnthreads have passedturnstile. So all of roundr'sturnstilepermits are used up by roundr's threads before anyone can arrive for roundr + 1. The same argument, applied toturnstile2andturnstilethe other way round, covers phase 2. - No deadlock: every thread blocks only on a turnstile, and the last thread in each phase always opens it, while holding nothing else.
# reusable_barrier.py — python3 reusable_barrier.py
import threading
from collections import Counter
class ReusableBarrier:
def __init__(self, n):
self.n, self.count = n, 0
self.mutex = threading.Semaphore(1)
self.turnstile = threading.Semaphore(0)
self.turnstile2 = threading.Semaphore(0)
def wait(self):
with self.mutex:
self.count += 1
if self.count == self.n:
self.turnstile.release(self.n) # Python 3.9+: release n permits
self.turnstile.acquire()
with self.mutex:
self.count -= 1
if self.count == 0:
self.turnstile2.release(self.n)
self.turnstile2.acquire()
N, ROUNDS = 8, 500
barrier = ReusableBarrier(N)
arrived = Counter()
lock = threading.Lock()
def worker():
for r in range(ROUNDS):
with lock:
arrived[r] += 1 # phase 1 of round r
barrier.wait()
with lock:
assert arrived[r] == N, f"passed round {r} with only {arrived[r]} arrived"
ts = [threading.Thread(target=worker) for _ in range(N)]
for t in ts: t.start()
for t in ts: t.join()
print("ok:", ROUNDS, "rounds")
The assertion checks the barrier's safety property directly: after passing round r, all N threads must have arrived for round r. Do not also assert that nobody has arrived for round r + 1 yet. A fast thread may legitimately pass round r, do its phase-1 work for round r + 1, and arrive there before a slow thread runs its post-barrier check, and that is allowed. What the barrier forbids is passing round r + 1 early. Replace ReusableBarrier with the naive single-turnstile version and the assertion fails within a few runs.
Building Barriers in Practice
| Platform | Barrier | Notes |
|---|---|---|
| POSIX | pthread_barrier_wait | One thread gets PTHREAD_BARRIER_SERIAL_THREAD, useful for per-round bookkeeping |
| Java | CyclicBarrier(n, action), Phaser | CyclicBarrier uses a lock, a condition and a generation object instead of two turnstiles. Phaser supports a changing number of parties. |
| Python | threading.Barrier(n) | Reusable, has abort() to break waiters out |
| Go | No stdlib barrier | Use one sync.WaitGroup per phase, or errgroup for fork/join. For cyclic use, a mutex plus sync.Cond with a generation counter. |
| GPU (CUDA) | __syncthreads() | Block-level barrier. A barrier inside divergent control flow deadlocks the block. |
| MPI / OpenMP | MPI_Barrier, #pragma omp barrier | Bulk-synchronous parallel supersteps |
The generation counter used by CyclicBarrier is the monitor-style answer to the lapping problem: each waiter records the generation it arrived in and waits while (gen == myGen). The last arrival increments gen and calls signalAll(). A thread that laps into the next round has a different myGen, so it cannot be released by the old round's broadcast.
Where It Shows Up
- Parallel numeric code: each iteration of a stencil or matrix computation is a phase. MapReduce and Spark stage boundaries are barriers (no reduce task starts before every map finishes).
- Graph processing: Pregel and BSP supersteps.
- Garbage collectors: "all mutator threads have reached a safepoint" is a barrier.
- Tests and benchmarks: start all
nworkers at exactly the same moment to maximise contention. - Tail latency: a barrier runs at the speed of the slowest participant, so one straggler stalls everyone. This is why Spark has speculative execution.
Summary
| Problem | Core hazard | Standard solution | Real-world analogue |
|---|---|---|---|
| Critical section | Check-then-act on the lock itself; memory reordering | Peterson/Bakery in theory. TAS/CAS, ticket, MCS and futex locks in practice | Every mutex, spinlock and synchronized block |
| Producer–consumer | Lost wakeup; deadlock from blocking while holding the mutex | empty/full counting semaphores plus mutex (P on the counter first), or a monitor with two conditions and while | Pipes, BlockingQueue, Go channels, TCP windows, Kafka |
| Readers–writers | Starvation of writers (first) or readers (second) | Lightswitch. Writer gate. FIFO turnstile for fairness | pthread_rwlock, RWMutex, DB S/X locks, mmap_lock |
| Dining philosophers | Circular wait (deadlock), starvation, livelock | Lock ordering. Waiter. N − 1 seats. Chandy–Misra. Try-lock with randomised back-off | Two-account transfers, lockdep, DB deadlock detection |
| Sleeping barber | Lost wakeup on a sleeping server; two clients take one slot | Counting semaphore for waiting customers; seat counter under a mutex; reject when full | Bounded thread-pool queues, HTTP 503, listen backlog |
| Cigarette smokers | Partial grabs of a combination (hold and wait) | Dispatcher (pushers) with a blackboard under one lock; or atomic multi-acquire | DAG schedulers, matching engines, gang scheduling |
| Santa Claus | Group formation, priority between classes, lost wakeups | Counters under a mutex; one wake semaphore; elf_tex door; priority by test order | Group commit, priority queues, quorum assembly |
| Barrier | A fast thread laps the others on reuse | Two turnstiles (two-phase), or generation counter | CyclicBarrier, pthread_barrier, Spark stages, GC safepoints |
How to Approach Any New Synchronization Problem
- Write the invariants first. State the safety property as a predicate over shared state (
0 ≤ count ≤ N, "readers > 0 implies writers = 0"). Then state which liveness properties you need: deadlock-freedom only, or starvation-freedom per thread, and with what priority. - List the waits. For every point where a thread may have to wait, write down the condition it waits for and who makes that condition true. Each condition becomes a semaphore or a condition variable. Each piece of shared state gets a mutex.
- Choose the primitive by what has to be remembered. If a signal can arrive before the wait, use a semaphore (it counts) or a condition variable with a state predicate re-checked in a
whileloop. Never use a bare notify. - Check every blocking call made while holding a lock. For each, ask: does the thread that would wake me need this lock? If yes, you have the producer–consumer deadlock. Acquire counters before mutexes.
- Impose a global lock order whenever a thread holds more than one lock at a time, and write it down. If you cannot, use try-lock with back-off, or take all locks at once through an arbiter.
- Look for the patterns: mutex, signal, rendezvous (two signals), lightswitch (first in locks, last out unlocks), turnstile (
P; V), door that closes afterk, two-phase barrier, dispatcher. Most new problems are two or three of these combined. - Ask who can starve. For each class of thread, construct the adversarial schedule (a stream of readers, neighbours alternating, a fast thread lapping). Decide whether that is acceptable, and if not add a FIFO turnstile or a generation counter.
- Check the semantics you depend on. Is the semaphore FIFO? Is
signalMesa-style (it is, almost everywhere)? Are spurious wakeups allowed (yes)? Is your custom spin-based code protected by the right memory ordering? - Test adversarially. Add random sleeps at every preemption point, run thousands of iterations with assertions on the invariants, and use the race detector (
go run -race, ThreadSanitizer,jcstressfor the JVM). For a real proof, model the protocol in TLA+ or check it with a model checker such as SPIN. - Prefer the library. Once you understand the problem, use
BlockingQueue,RWMutex, channels,CyclicBarrierorSemaphore. Hand-built synchronization belongs in code you are prepared to prove correct.
Interview Questions
"State the three requirements for a solution to the critical-section problem."
Answer
Mutual exclusion (at most one process in the critical section), progress (if nobody is in it, a process wanting to enter cannot be blocked indefinitely, and processes in their remainder section do not take part in the decision), and bounded waiting (once a process requests entry, there is a bound on how many times others enter first). The first is safety, the other two are liveness. A simple flag violates mutual exclusion, strict alternation violates progress, and a test-and-set spinlock violates bounded waiting.
"Prove that Peterson's algorithm gives mutual exclusion. Why does it fail on a modern x86 CPU?"
Answer
If both processes were in the critical section, both flags would be true, so P0 must have seen turn == 0 and P1 must have seen turn == 1. Whichever wrote turn last would then have read a value other than the one it wrote, with no intervening write, which is impossible. On x86 the store to flag[i] can sit in the store buffer while the load of flag[j] completes. Both processes read the other's flag as false and both enter. A full fence (MFENCE) between the stores and the loop, or sequentially consistent atomics, fixes it.
"Why does the Bakery algorithm need the choosing array?"
Answer
A process may be between reading the maximum ticket and writing its own ticket. During that window its number is still 0, so another process scanning it would treat it as not interested and enter. When the first process then writes a ticket equal to the other's, and has a lower ID, it enters too. choosing[j] makes the scanner wait until j's ticket is written.
"In the bounded-buffer solution, what happens if the producer does P(mutex) before P(empty)?"
Answer
When the buffer is full, the producer acquires the mutex and blocks on empty while holding it. The consumer, which would free a slot, blocks on the mutex. Deadlock. The general rule: never block on a condition while holding a lock that the thread able to change that condition needs. The order of the V operations does not matter, since V never blocks.
"Why must a condition-variable wait be in a while loop?"
Answer
Under Mesa semantics (Java, POSIX, Go's sync.Cond), signal only makes the waiter runnable. Another thread can acquire the lock first and invalidate the condition, for example by taking the item. Spurious wakeups are also explicitly permitted. Re-checking the predicate in a loop handles both cases. if is only correct under Hoare semantics, which almost no real system implements.
"Readers-preference vs writers-preference: who starves, and how do you get a fair RW lock?"
Answer
Under readers-preference, writers starve while readers keep overlapping, because the reader count never reaches zero. Under writers-preference, readers starve under a steady stream of writers. For fairness, put a FIFO turnstile in front of both: every thread passes through it in arrival order, and a waiting writer blocks later arrivals until the readers already inside drain. Java's ReentrantReadWriteLock(true) does roughly this.
"Can Go's sync.RWMutex deadlock a single goroutine that only takes read locks?"
Answer
Yes, if it takes RLock recursively while a writer is waiting. RWMutex blocks new readers once a writer is pending, so the second RLock waits for the writer, and the writer waits for the first RLock to be released. The documentation forbids recursive read locking for this reason.
"When is an RW lock slower than a plain mutex?"
Answer
When critical sections are short, writes are not rare, or many cores take the read lock. Every read acquire and release is an atomic update to one shared counter, so the cache line bounces between cores and readers serialize on coherence traffic. Sharded locks, copy-on-write snapshots, seqlocks or RCU scale better for read-mostly data. Measure before choosing.
"Give four ways to prevent deadlock in dining philosophers and say which Coffman condition each breaks."
Answer
Resource ordering, where everyone takes the lower-numbered fork first, breaks circular wait. A waiter that grants both forks atomically breaks hold-and-wait. Allowing only N − 1 philosophers at the table breaks circular wait, by pigeonhole. Try-lock with back-off (release the first fork if the second is busy) breaks hold-and-wait by voluntary preemption. Chandy–Misra breaks circular wait through an acyclic precedence graph and adds preemption of dirty forks. Only Chandy–Misra (and ordering or N − 1 with FIFO locks) is starvation-free. The state-based waiter lets two neighbours starve the philosopher between them.
"Which dining-philosophers solution would you use in production?"
Answer
Lock ordering. Give every lock a total order (account ID, memory address, a documented hierarchy) and always acquire in that order. It is cheap, needs no coordinator, and is checkable at runtime (Linux lockdep). Where the order cannot be known in advance, as with database rows, systems use detection (a wait-for graph and victim abort) or lock timeouts.
"What race does the sleeping-barber solution avoid?"
Answer
The lost wakeup: the barber sees an empty waiting room and, before he falls asleep, a customer arrives, sees him awake, and sits down. The barber then sleeps with a customer waiting. The semaphore customers counts arrivals, so a customer's V before the barber's P is remembered. A mutex around the seat counter also prevents two customers from taking the last chair.
"Why can't the cigarette smokers problem be solved with each smoker simply waiting for its two ingredients?"
Answer
Single P operations commit to one ingredient before seeing the other. A smoker that wanted tobacco-and-matches can grab the tobacco intended for the matches smoker, and both wait forever: hold-and-wait. Patil showed that with P/V only and no conditionals it cannot be solved at all. Allowing conditionals, helper "pusher" threads record each ingredient on a shared blackboard under a mutex and wake exactly the right smoker once both have arrived. Atomic multi-semaphore operations (System V semop) would also solve it.
"In the Santa Claus problem, how are elves limited to groups of three, and how do reindeer get priority?"
Answer
A door semaphore elf_tex admits elves one at a time. The first and second elves reopen it, but the third keeps it closed and wakes Santa, and the last elf of the group to be helped reopens it. Priority comes from Santa checking reindeer == 9 before elves == 3 every time he wakes. Both wakeup sources post the same santa_sem, so pending events are never lost.
"Why does a reusable barrier need two turnstiles?"
Answer
With one turnstile, the gate is still open when a fast thread loops into the next round, so it passes round r + 1's barrier while others are still leaving round r. Two gates work like an airlock: the first opens only when all n have arrived, and the second opens only when all n have passed the first, so no thread can re-enter until everyone has left. A generation counter achieves the same with a monitor.
"What is the difference between deadlock, livelock and starvation? Give an example of each from this page."
Answer
Deadlock: threads are blocked forever in a cycle, as in five philosophers each holding a left fork. Livelock: threads are active but make no progress, as when philosophers using try-lock with an identical fixed back-off retry in lockstep. Starvation: the system makes progress but one thread never does, as with writers under a readers-preference lock or P2 between two alternating neighbours under the state-based waiter.
Further Reading
- Allen B. Downey, The Little Book of Semaphores: free, and the source of most of the pattern names used here (turnstile, lightswitch, two-phase barrier, pushers).
- E. W. Dijkstra, Cooperating Sequential Processes (1965): the original producer–consumer, sleeping barber and dining philosophers.
- P. J. Courtois, F. Heymans, D. L. Parnas, Concurrent Control with "Readers" and "Writers" (CACM, 1971).
- L. Lamport, A New Solution of Dijkstra's Concurrent Programming Problem (CACM, 1974): the Bakery algorithm.
- K. M. Chandy, J. Misra, The Drinking Philosophers Problem (TOPLAS, 1984).
- J. A. Trono, A New Exercise in Concurrency (SIGCSE Bulletin, 1994): the Santa Claus problem.
Related pages: Mutex, Semaphore & Monitor · Deadlocks, Livelocks & Starvation · Race Conditions · Concurrency Patterns · Lock-Free Programming · Actor Model · Kernel Synchronization · Go Concurrency · Concurrency Interview Problems