On this page

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:

  1. Statement: the story and what the code has to do.
  2. Invariants: the safety property that must always hold, and the liveness failures to rule out (deadlock, starvation, busy waiting).
  3. A naive attempt and the exact interleaving that breaks it.
  4. Correct solution(s): semaphore pseudocode first, then real code in Java, Python or Go.
  5. Correctness argument: why it cannot deadlock, and whether it can starve anyone.
  6. Trade-offs: complexity, fairness, throughput.
  7. 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:

PseudocodeMeaningPythonJavaGo (buffered-channel semaphore)
P(s) / wait(s)If s > 0 decrement and continue, else blocks.acquire()s.acquire()s <- struct{}{}
V(s) / signal(s)Increment s, waking one blocked waiter if anys.release()s.release()<-s
semaphore s = kInitial count kthreading.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.Semaphore makes no FIFO promise. java.util.concurrent.Semaphore(n, true) is FIFO. POSIX sem_t wakes 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:

RequirementKindMeaning
Mutual exclusionSafetyAt most one process is in its critical section at any instant.
ProgressLiveness (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 waitingLiveness (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:

StepP0P1locked
1reads locked → falsefalse
2preemptedreads locked → falsefalse
3sets locked = true, enters CStrue
4sets locked = true, enters CStrue
5in CSin CSmutual 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:

StepP0P1
1flag[0] = true
2flag[1] = true
3spins: flag[1] is truespins: flag[0] is true
4spins foreverspins 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] = true throughout. P0 passed its loop, so it saw flag[1] == false or turn == 0. P1 passed, so it saw flag[0] == false or turn == 1. The flags are both true, so P0 saw turn == 0 and P1 saw turn == 1. turn is one variable, so the writes and reads must be ordered. Say P1 wrote turn = 0 last. After that, turn stays 0 until somebody exits. P1 then read turn == 1 after 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, turn is 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:

StepP1P2number
1reads max = 0[0, 0]
2reads max = 0, writes number[2] = 1[0, 1]
3scans: number[1] == 0, so passes it, enters CS[0, 1]
4writes number[1] = 1in CS[1, 1]
5scans: (1, 2) < (1, 1) is false, so passes, enters CSin CSboth 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 exit serving++. 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

SolutionProcessesNeeds atomics?Bounded waitingUncontended costNotes
Disable interruptsany (uniprocessor)non/a2 instructionsKernel-only, single CPU only
Peterson / Dekker2SC loads/stores + fenceyes (1)a few stores + fenceTeaching tool; generalises poorly
Bakerynno (safe registers suffice)yes, FCFSO(n) readsUnbounded tickets
TAS / CAS spinlocknyesno1 atomicCache-line ping-pong under contention
Ticket locknfetch-and-addyes, FIFO1 atomicAll waiters spin on one line
MCS / queued locknswap/CASyes, FIFO1 atomicEach waiter spins locally; Linux qspinlock
Futex mutexnCAS + syscalldepends on wake policy1 atomic, no syscallWhat 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 ≤ N at 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:

StepProducerConsumermutexemptyfull
010N
1P(mutex) succeeds00N
2P(empty) blocks, still holding mutex00N
3P(full) succeeds00N−1
4P(mutex) blocks00N−1
5waits 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:

StepC1C2Pcount
1locks, sees count == 0, awaits (releases lock)0
2locks, inserts, signal(), unlocks1
3woken, waiting to reacquire locklocks first, sees count == 1, takes the item0
4reacquires 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's V(full) and every P(empty) by a consumer's V(empty). The mutex is never held while waiting on a counting semaphore. So if the buffer has an item, some consumer can complete P(full) and then P(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

VariantWhenNotes
SPSC ring buffer, no lockExactly one producer and one consumerProducer writes only in, consumer only out. Needs only acquire/release atomics. See Lock-Free Programming.
Two locks (head and tail)Linked queue, MPMCLinkedBlockingQueue uses putLock and takeLock, so producers and consumers do not contend with each other
One lock, two conditionsArray queue, MPMCArrayBlockingQueue. Simpler, but one cache line under contention
Unbounded queueNever in productionNo backpressure, so memory grows until the OOM killer arrives
DisruptorUltra-low latencyPre-allocated ring, sequence counters, batching, no locks

Where It Shows Up

  • Unix pipes: the kernel pipe buffer (64 KiB by default on Linux). write blocks when it is full and read blocks 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 full count.

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.
VariantPriorityWho can starve
First readers–writersReaders. A new reader joins as long as any reader is activeWriters
Second readers–writersWriters. Once a writer is waiting, no new reader may startReaders
Third readers–writersArrival 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 on service_queue behind W. Readers already inside eventually finish (reads are finite), read_count reaches 0, W gets resource, then releases service_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 needs service_queue to 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:

ImplementationPolicyGotchas
glibc pthread_rwlock_tReader-preferring by default (PTHREAD_RWLOCK_PREFER_READER_NP), so writers can starveSet 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 StampedLockOptimistic reads: read without locking, then validate(stamp)Not reentrant. Optimistic reads must tolerate inconsistent data until they validate.
Go sync.RWMutexWriter-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_semaphorerwlock_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:

  1. Shard the data, with one mutex per shard (ConcurrentHashMap's approach).
  2. Copy-on-write snapshot: readers load an atomic pointer, and writers build a new copy and swap it in (Go atomic.Pointer[T], Java CopyOnWriteArrayList).
  3. A seqlock or RCU, where readers write no shared memory at all (see Seqlocks and RCU).
  4. 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 TABLE behind a long-running SELECT. MySQL's metadata locks queue writers to prevent this, which in turn blocks every new SELECT behind the waiting ALTER. That is writers-preference, and it is why online schema change tools exist.
  • Files: flock(LOCK_SH) and flock(LOCK_EX), and fcntl byte-range read and write locks.
  • Kernel: mmap_lock (formerly mmap_sem), an rw_semaphore and 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:

StepP0P1P2P3P4
1takes fork 0takes fork 1takes fork 2takes fork 3takes fork 4
2waits 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)
3blocked foreverblocked foreverblocked foreverblocked foreverblocked 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.

  1. Every fork is held by exactly one of its two neighbours at any time, and is either dirty or clean.
  2. Initialisation: every fork starts dirty and is given to the neighbour with the lower ID. Define precedence: neighbour a has precedence over b if a holds their shared fork and it is clean, or b holds 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.
  3. A hungry philosopher sends a request token to the neighbour for each fork it lacks.
  4. 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.
  5. 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

SolutionCoffman condition brokenDeadlock-freeStarvation-freeMax concurrent eatersPractical use
(a) Resource orderingCircular waitYesWith FIFO locks2Most common: lock ordering by ID or address, lockdep
(b) Waiter / state monitorHold and waitYesNo (neighbours can collude)2Central lock managers, "acquire all locks at once" APIs
(c) N − 1 at the tableCircular waitYesWith FIFO semaphores2Admission control, bulkheads, pool limits
(d) Chandy–MisraCircular wait (acyclic priority) + preemptionYesYes2Distributed resource allocation
(e) Try-lock + back-offHold and wait / no preemptionYesProbabilistic2Lock timeouts, optimistic retry, reverse-order kernel paths
Single global lockMutual exclusion is coarseYesWith a fair lock1Python'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_rename orders 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.

  • ThreadPoolExecutor with a bounded ArrayBlockingQueue and AbortPolicy: when the pool and the queue are full, submit throws RejectedExecutionException.
  • 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_wait or 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:

StepAgentSmoker-with-paperSmoker-with-matchestobaccopaper
1V(tobacco)10
2P(tobacco) succeeds (it wanted tobacco and matches)00
3V(paper)01
4P(match) blocksP(tobacco) blocks01
5P(agent_sem) blockswaiting for matcheswaiting for tobaccodeadlock

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:

  1. 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.
  2. 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_tex is 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_sem is 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 finds elves == 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 final elves--, since the door is reopened only at elves == 0 and the first two each reopen it only for one more elf. Santa's elves == 3 test is made under mutex.
  • Priority: whenever Santa wakes, he tests reindeer == 9 first. The reindeer cannot lose to the elves while both are pending.
  • No lost wakeup: the ninth reindeer and the third elf post santa_sem under the same mutex that protects the counters. If Santa is busy, the permit waits. Santa's P(santa_sem) count always equals the number of pending events.
  • No deadlock: mutex is held by Santa while he waits on hitched, but the reindeer post hitched without needing mutex. Nobody else blocks on anything while holding mutex.
  • 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_tex is 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_tex door that closes after k entrants is a building block of its own, used whenever exactly k threads 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 r until all n threads have arrived at it for round r. With reuse, no thread may get into round r + 1's barrier and pass it while others are still leaving round r'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:

StepT1T2countturnstile
1count = 110
2count = 2, sees 2, V(turnstile)21
3P and V the turnstile, passes21
4count = 1 (leaving)11
5loops to the next round: count = 2, sees 2, V(turnstile)22
6passes 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: turnstile starts at 0 and receives exactly n permits, posted only by the nth arrival. So nobody passes before everyone has arrived, and exactly n threads pass.
  • No lapping: a fast thread that finishes phase 1 must take a turnstile2 permit before it can start the next round. Those are posted only when count returns to 0, which means all n threads have passed turnstile. So all of round r's turnstile permits are used up by round r's threads before anyone can arrive for round r + 1. The same argument, applied to turnstile2 and turnstile the 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

PlatformBarrierNotes
POSIXpthread_barrier_waitOne thread gets PTHREAD_BARRIER_SERIAL_THREAD, useful for per-round bookkeeping
JavaCyclicBarrier(n, action), PhaserCyclicBarrier uses a lock, a condition and a generation object instead of two turnstiles. Phaser supports a changing number of parties.
Pythonthreading.Barrier(n)Reusable, has abort() to break waiters out
GoNo stdlib barrierUse 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 / OpenMPMPI_Barrier, #pragma omp barrierBulk-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 n workers 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

ProblemCore hazardStandard solutionReal-world analogue
Critical sectionCheck-then-act on the lock itself; memory reorderingPeterson/Bakery in theory. TAS/CAS, ticket, MCS and futex locks in practiceEvery mutex, spinlock and synchronized block
Producer–consumerLost wakeup; deadlock from blocking while holding the mutexempty/full counting semaphores plus mutex (P on the counter first), or a monitor with two conditions and whilePipes, BlockingQueue, Go channels, TCP windows, Kafka
Readers–writersStarvation of writers (first) or readers (second)Lightswitch. Writer gate. FIFO turnstile for fairnesspthread_rwlock, RWMutex, DB S/X locks, mmap_lock
Dining philosophersCircular wait (deadlock), starvation, livelockLock ordering. Waiter. N − 1 seats. Chandy–Misra. Try-lock with randomised back-offTwo-account transfers, lockdep, DB deadlock detection
Sleeping barberLost wakeup on a sleeping server; two clients take one slotCounting semaphore for waiting customers; seat counter under a mutex; reject when fullBounded thread-pool queues, HTTP 503, listen backlog
Cigarette smokersPartial grabs of a combination (hold and wait)Dispatcher (pushers) with a blackboard under one lock; or atomic multi-acquireDAG schedulers, matching engines, gang scheduling
Santa ClausGroup formation, priority between classes, lost wakeupsCounters under a mutex; one wake semaphore; elf_tex door; priority by test orderGroup commit, priority queues, quorum assembly
BarrierA fast thread laps the others on reuseTwo turnstiles (two-phase), or generation counterCyclicBarrier, pthread_barrier, Spark stages, GC safepoints

How to Approach Any New Synchronization Problem

  1. 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.
  2. 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.
  3. 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 while loop. Never use a bare notify.
  4. 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.
  5. 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.
  6. Look for the patterns: mutex, signal, rendezvous (two signals), lightswitch (first in locks, last out unlocks), turnstile (P; V), door that closes after k, two-phase barrier, dispatcher. Most new problems are two or three of these combined.
  7. 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.
  8. Check the semantics you depend on. Is the semaphore FIFO? Is signal Mesa-style (it is, almost everywhere)? Are spurious wakeups allowed (yes)? Is your custom spin-based code protected by the right memory ordering?
  9. 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, jcstress for the JVM). For a real proof, model the protocol in TLA+ or check it with a model checker such as SPIN.
  10. Prefer the library. Once you understand the problem, use BlockingQueue, RWMutex, channels, CyclicBarrier or Semaphore. 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