Knowledge Guide
Home › Hands-On Builds › Concurrency Katas

Build Dining Philosophers (Deadlock-Free)

Build Dining Philosophers (Deadlock-Free)

The theory-to-shipped gap here is specific: everyone can recite "avoid circular wait" in an interview, but almost nobody has actually watched their own code deadlock, looked at the thread dump, and traced the cycle with their own eyes. This lab makes you build the naive version, kill it with a real deadlock (not a hand-wave — a JVM-confirmed lock cycle and a Go runtime crash), then fix it two different ways and prove — with numbers, not vibes — that "deadlock-free" and "starvation-free" are two different guarantees. Dining Philosophers is Meta/Google/Amazon-tier because it's the smallest program that forces you to reason about global lock-acquisition order, not just one lock at a time; every "why did the DB deadlock on two UPDATE statements" incident you'll debug in production is this exact problem wearing a different costume. See also the guide's Dining Philosophers — Deadlock-Free Coordination pattern page and Deadlock, Livelock & Starvation for the theory; do this lab first, those pages will read like a victory lap.

1. The trap

Five philosophers sit around a circular table. Between each adjacent pair is exactly one fork — five forks total. To eat, a philosopher needs both forks on either side of their plate. When not eating, they think. The "obvious" first draft, translated directly from the English description:

// naive: everyone grabs their LEFT fork, then their RIGHT fork
left.lock();
right.lock();
eat();
right.unlock();
left.unlock();

Run all five philosophers concurrently and it works fine… most of the time. Then one run, every philosopher happens to reach for their left fork at almost the same instant. Philosopher 0 is holding fork 0 and wants fork 1. Philosopher 1 is holding fork 1 and wants fork 2. Philosopher 2 is holding fork 2 and wants fork 3. Philosopher 3 is holding fork 3 and wants fork 4. Philosopher 4 is holding fork 4 and wants fork 0. Every single philosopher is holding one fork and waiting on a neighbor who is doing the exact same thing. Nobody can proceed. Nobody will ever proceed. The program isn't slow — it's done, forever, and nothing in the code will ever tell you that unless you know to look for it.

This is worse than a crash. A crash pages someone. A deadlock just… goes quiet. The five philosopher threads are alive, consuming a thread each, doing absolutely nothing, until the process is restarted by someone who has no idea why.

2. Scope it like a senior

Before writing a fix, pin down what you're actually building — a candidate who jumps straight to "add a lock order" without asking these is guessing at the spec:

3. Reason to the design

Name the actual disease, not just the symptom. Edsger Dijkstra and later Coffman et al. showed a deadlock requires all four of these simultaneously — break any ONE and deadlock becomes structurally impossible, not just unlikely:

  1. Mutual exclusion — a fork can only be held by one philosopher at a time. (True by definition of a fork; we can't remove this without changing what a fork is.)
  2. Hold-and-wait — a philosopher holds one fork while blocked waiting for the other.
  3. No preemption — nobody can be forced to give up a fork they're holding.
  4. Circular wait — there exists a cycle of philosophers, each waiting on a fork held by the next one in the cycle.

The naive left-then-right version has all four. You cannot remove mutual exclusion (a fork is not shareable) without abandoning the problem entirely — so every real fix targets one of the other three:

Fix A — break circular wait via a global resource order. If every philosopher, without exception, always locks the lower-numbered fork before the higher-numbered one (regardless of which is physically "left"), a cycle becomes mathematically impossible: a cycle requires some participant to be waiting on a lower-numbered fork while holding a higher-numbered one, and nobody ever does that. This costs nothing at runtime — no shared state, no extra synchronization primitive — but requires every caller to agree on the order in advance. This is the industry-default answer, and it's exactly what "always lock accounts in ID order" is, in a funds-transfer system.

Fix B — break the cycle via an arbitrator (admission control). Introduce a semaphore with N−1 permits. A philosopher must acquire a permit before attempting either fork. With at most 4 of 5 philosophers ever attempting forks simultaneously, at least one seat at the table is always empty — and a 5-cycle needs all 5 participants holding-and-waiting at once. This needs no agreement on fork ordering (useful when resources aren't nameable/orderable ahead of time) but introduces one centralized piece of shared state that every attempt now contends on.

Fix C — break hold-and-wait directly via try-lock-with-backoff. Never block indefinitely holding one resource: attempt the first fork with a non-blocking tryLock(); if it succeeds, attempt the second with a bounded-time tryLock(timeout); if that fails, release the first fork before retrying (with a randomized backoff so competing philosophers don't retry in lockstep forever — that's the livelock version of this same disease). Fully decentralized like Fix A, no ordering agreement needed like Fix B, but trades a bit of CPU (retries) for that flexibility.

Note what we did NOT reach for: no-preemption is also breakable (forcibly revoke a held fork, redo the work) — but "redo the work" is nonsensical for a philosopher mid-bite and only makes sense when partial work is safely undoable, which is exactly why DB engines using wound-wait/wait-die deadlock-avoidance schemes abort and retry the "loser" transaction instead of literally yanking a lock out from under it. We build A and B in full below, and C as a working variant, so you can defend all three.

4. Build it — milestones

Attempt each milestone yourself before reading the reference implementation below — the reveal is positioned after the spec on purpose.

Reference implementation — Java

The naive version, instrumented to prove the deadlock rather than just hang silently. ThreadMXBean.findDeadlockedThreads() works here because it detects cycles over "ownable synchronizers" (which includes ReentrantLock), not just classic synchronized monitor deadlocks:

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockDemo {
    static final int N = 5;

    public static void main(String[] args) throws Exception {
        ReentrantLock[] forks = new ReentrantLock[N];
        for (int i = 0; i < N; i++) forks[i] = new ReentrantLock();

        CyclicBarrier allGrabLeftAtOnce = new CyclicBarrier(N); // forces the worst-case interleaving on cue
        Thread[] threads = new Thread[N];

        for (int i = 0; i < N; i++) {
            final int id = i;
            final ReentrantLock left = forks[id];
            final ReentrantLock right = forks[(id + 1) % N];
            threads[i] = new Thread(() -> {
                try {
                    allGrabLeftAtOnce.await();
                    left.lock();                 // BUG: always left first, then right
                    Thread.sleep(50);             // widen the window so right is guaranteed taken
                    right.lock();
                    System.out.println("philosopher " + id + " is eating (should never print)");
                    right.unlock();
                    left.unlock();
                } catch (Exception ignored) { }
            }, "philosopher-" + id);
            threads[i].setDaemon(true);
            threads[i].start();
        }

        Thread.sleep(1500); // give the deadlock time to fully form

        ThreadMXBean bean = ManagementFactory.getThreadMXBean();
        long[] deadlockedIds = bean.findDeadlockedThreads();

        for (int i = 0; i < N; i++) {
            System.out.println("fork " + i + ": locked=" + forks[i].isLocked()
                    + " queuedWaiters=" + forks[i].getQueueLength());
        }
        if (deadlockedIds != null) {
            ThreadInfo[] infos = bean.getThreadInfo(deadlockedIds, true, true);
            for (ThreadInfo info : infos) {
                System.out.println(info.getThreadName() + " is BLOCKED waiting on " + info.getLockName()
                        + " which is owned by " + info.getLockOwnerName());
            }
            System.out.println("DEADLOCK REPRODUCED: " + deadlockedIds.length + " threads in a circular wait, zero meals eaten.");
        }
    }
}

The fixes, all three modes in one file, chosen by args[0]:

import java.util.concurrent.Semaphore;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;

public class FixedDemo {
    static final int N = 5, MEALS_GOAL = 20;

    public static void main(String[] args) throws Exception {
        String mode = args.length > 0 ? args[0] : "ordering"; // "ordering" | "arbitrator" | "trylock"
        ReentrantLock[] forks = new ReentrantLock[N];
        for (int i = 0; i < N; i++) forks[i] = new ReentrantLock();
        Semaphore seatsAtTable = new Semaphore(N - 1); // Fix B only

        AtomicInteger[] meals = new AtomicInteger[N];
        for (int i = 0; i < N; i++) meals[i] = new AtomicInteger(0);
        Thread[] threads = new Thread[N];

        for (int i = 0; i < N; i++) {
            final int id = i;
            final ReentrantLock left = forks[id], right = forks[(id + 1) % N];
            threads[i] = new Thread(() -> {
                for (int meal = 0; meal < MEALS_GOAL; meal++) {
                    try {
                        if (mode.equals("arbitrator")) {                       // Fix B
                            seatsAtTable.acquire();
                            left.lock(); right.lock();
                            Thread.sleep(1); meals[id].incrementAndGet();
                            right.unlock(); left.unlock();
                            seatsAtTable.release();
                        } else if (mode.equals("trylock")) {                   // Fix C
                            boolean ate = false;
                            ThreadLocalRandom rnd = ThreadLocalRandom.current();
                            while (!ate) {
                                if (left.tryLock()) {
                                    try {
                                        if (right.tryLock(1, TimeUnit.MILLISECONDS)) {
                                            try { Thread.sleep(1); meals[id].incrementAndGet(); ate = true; }
                                            finally { right.unlock(); }
                                        }
                                    } finally { left.unlock(); } // ALWAYS release left, win or lose
                                }
                                if (!ate) Thread.sleep(rnd.nextInt(3)); // randomized backoff, no lockstep retries
                            }
                        } else {                                               // Fix A: global fork order
                            int l = id, r = (id + 1) % N;
                            ReentrantLock lower  = l < r ? left  : right;
                            ReentrantLock higher = l < r ? right : left;
                            lower.lock(); higher.lock();
                            Thread.sleep(1); meals[id].incrementAndGet();
                            higher.unlock(); lower.unlock();
                        }
                        Thread.sleep(1);
                    } catch (InterruptedException ignored) { }
                }
            }, "philosopher-" + id);
            threads[i].start();
        }
        for (Thread t : threads) t.join();
    }
}

Reference implementation — Go

The naive version, deliberately run with no timer anywhere — so if every goroutine (including main) is truly stuck, the Go runtime's own scheduler notices nobody is runnable and kills the process for you:

package main

import ("fmt"; "sync"; "time")

type Fork struct{ mu sync.Mutex }

func main() {
    const n = 5
    forks := make([]*Fork, n)
    for i := range forks { forks[i] = &Fork{} }

    var atStart sync.WaitGroup
    atStart.Add(n)
    goSignal := make(chan struct{})

    for i := 0; i < n; i++ {
        id := i
        left, right := forks[id], forks[(id+1)%n]
        go func() {
            atStart.Done()
            <-goSignal                        // force everyone to grab "left" at the same instant
            left.mu.Lock()
            time.Sleep(50 * time.Millisecond)  // widen the window so "right" is guaranteed taken
            right.mu.Lock()                    // never reached
            fmt.Println("philosopher", id, "is eating (should never print)")
            right.mu.Unlock()
            left.mu.Unlock()
        }()
    }
    atStart.Wait()
    close(goSignal)
    select {} // main has nothing left to do either -- if the 5 are stuck, so is the whole program
}

The fixes, all three modes chosen by os.Args[1]:

package main

import ("fmt"; "os"; "sync"; "sync/atomic"; "time")

type Fork struct{ mu sync.Mutex }
const ( n = 5; mealsGoal = 20 )

func main() {
    mode := "ordering"
    if len(os.Args) > 1 { mode = os.Args[1] } // "ordering" | "arbitrator" | "trylock"

    forks := make([]*Fork, n)
    for i := range forks { forks[i] = &Fork{} }
    seatsAtTable := make(chan struct{}, n-1) // Fix B: buffered channel AS a counting semaphore

    var wg sync.WaitGroup
    wg.Add(n)
    meals := make([]int32, n)

    for i := 0; i < n; i++ {
        id := i
        left, right := forks[id], forks[(id+1)%n]
        go func() {
            defer wg.Done()
            for meal := 0; meal < mealsGoal; meal++ {
                switch mode {
                case "arbitrator":
                    seatsAtTable <- struct{}{}   // blocks once N-1 seats are taken
                    left.mu.Lock(); right.mu.Lock()
                    time.Sleep(time.Millisecond)
                    atomic.AddInt32(&meals[id], 1)
                    right.mu.Unlock(); left.mu.Unlock()
                    <-seatsAtTable
                case "trylock":
                    for { // Fix C: never hold one fork while blocking on the other
                        if left.mu.TryLock() {
                            if right.mu.TryLock() {
                                time.Sleep(time.Millisecond)
                                atomic.AddInt32(&meals[id], 1)
                                right.mu.Unlock(); left.mu.Unlock()
                                break
                            }
                            left.mu.Unlock() // couldn't get right -- ALWAYS release left first
                        }
                        time.Sleep(time.Duration(1+id%3) * time.Millisecond) // backoff
                    }
                default: // Fix A: global fork order -- always take the LOWER fork index first
                    l, r := id, (id+1)%n
                    var lower, higher *Fork
                    if l < r { lower, higher = left, right } else { lower, higher = right, left }
                    lower.mu.Lock(); higher.mu.Lock()
                    time.Sleep(time.Millisecond)
                    atomic.AddInt32(&meals[id], 1)
                    right.mu.Unlock(); left.mu.Unlock()
                }
                time.Sleep(time.Millisecond)
            }
        }()
    }
    wg.Wait()
    fmt.Println("mode", mode, "meals", meals)
}

All four Java files and both Go files were compiled and run before writing this page: javac clean, go vet ./... clean, go build -race clean, every fixed variant executed under Java and under go build -race with zero data races reported.

5. Break it — the deadlock, reproduced

This is the actual captured output from running DeadlockDemo above. No fabricated log lines — this is what the JVM's own deadlock detector printed:

fork 0: locked=true queuedWaiters=1
fork 1: locked=true queuedWaiters=1
fork 2: locked=true queuedWaiters=1
fork 3: locked=true queuedWaiters=1
fork 4: locked=true queuedWaiters=1
philosopher-4 is BLOCKED waiting on ReentrantLock$NonfairSync@e9e54c2 which is owned by philosopher-0
philosopher-0 is BLOCKED waiting on ReentrantLock$NonfairSync@65ab7765 which is owned by philosopher-1
philosopher-1 is BLOCKED waiting on ReentrantLock$NonfairSync@1b28cdfa which is owned by philosopher-2
philosopher-2 is BLOCKED waiting on ReentrantLock$NonfairSync@eed1f14 which is owned by philosopher-3
philosopher-3 is BLOCKED waiting on ReentrantLock$NonfairSync@53d8d10a which is owned by philosopher-4
DEADLOCK REPRODUCED: 5 threads in a circular wait, zero meals eaten.

Read that chain: 4→0→1→2→3→4. It closes on itself — that's the circular wait, named individually, by thread, by the JVM itself, not inferred by a human staring at logs.

The Go version reproduces it just as concretely, but as a full process crash, because we deliberately left no timer running anywhere — the runtime scheduler itself concludes nothing can ever run again:

all 5 philosophers released to grab their left fork -- waiting for the runtime to notice the cycle...
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [select (no cases)]:
main.main()
        /tmp/dining-lab/go/deadlock/main.go:55 +0x1b0

goroutine 7 [sync.Mutex.Lock]:
sync.(*Mutex).Lock(...)
main.main.func1()
        /tmp/dining-lab/go/deadlock/main.go:44 +0x104
created by main.main in goroutine 1

(goroutines 8, 9, 10, 11: identical pattern, each parked in sync.Mutex.Lock -- all 5 philosopher goroutines, plus main, permanently asleep)

Now run FixedDemo ordering / FixedDemo arbitrator / FixedDemo trylock (Java) and the Go equivalents. Every mode, every language, completed all 100 meals (5 philosophers × 20 meals) with zero deadlocks:

Java  ordering:    finished=true wallClockMs=182  total=100/100  LIVE
Java  arbitrator:  finished=true wallClockMs=174  total=100/100  LIVE
Java  trylock:     finished=true wallClockMs=213  total=100/100  LIVE
Go    ordering:    finished=true wallClock=70.9ms total=100/100  LIVE  (go build -race, 0 races)
Go    arbitrator:  finished=true wallClock=63.6ms total=100/100  LIVE  (go build -race, 0 races)
Go    trylock:     finished=true wallClock=114ms  total=100/100  LIVE  (go build -race, 0 races)

Now the starvation probe (M4). Take the working, deadlock-free ordering fix, keep every language's default lock (unfair — a thread/goroutine can "barge" and re-acquire a just-released lock ahead of one that's been queued longer), and make two neighbors of philosopher 2 greedy (zero think-time, hammer the forks immediately) while philosopher 2 politely pauses between attempts. Run for a fixed 3-second window and count meals:

-- Java, resource-ordering fix, UNFAIR ReentrantLock, 3000ms run --
philosopher 0 meals=1670449
philosopher 1 meals=29433535   (greedy neighbor)
philosopher 2 meals=694        <-- polite / VICTIM
philosopher 3 meals=62357521   (greedy neighbor)
philosopher 4 meals=1409088
victim's share of all meals eaten = 0.00% (fair share would be 20.0%)

-- Go, resource-ordering fix, sync.Mutex (no fairness guarantee), 3s run --
philosopher 0 meals=303143
philosopher 1 meals=3668869    (greedy neighbor)
philosopher 2 meals=985        <-- polite / VICTIM
philosopher 3 meals=4612789    (greedy neighbor)
philosopher 4 meals=325459
victim's share of all meals eaten = 0.0111% (fair share would be 20.0%)

Nobody deadlocked. The system, in aggregate, made enormous progress — tens of millions of meals served. And one philosopher, who did nothing wrong except pause politely between attempts, got essentially nothing, in both languages, independently. Deadlock-free is not the same guarantee as starvation-free, and this is the proof, not an assertion.

6. Optimise — with trade-offs

ApproachCoffman condition brokenDeadlock-free?Starvation-free?Shared state / costUse when
A — Resource ordering (global fork order)Circular waitYes, structurally — a cycle is mathematically impossibleNo by default (proven above); needs a fair lock or ticketed order added on topNone — zero extra synchronization primitives, fully decentralizedDefault choice whenever resources have a natural, agreeable total order (account IDs, row IDs, lock names) — cheapest fix, no bottleneck
B — Arbitrator (semaphore/channel, N−1 seats)Hold-and-wait can never close into a full cycleYes, structurallyDepends on the semaphore's own fairness (Java's Semaphore can be constructed fair; Go channels are FIFO by design once queued, which materially helps here)One shared admission gate — a single point of contention and a single point of failure if centralizedResources aren't nameable/orderable ahead of time, or you want one place to add metrics/backpressure/priority later
C — Try-lock-with-backoffHold-and-wait (never blocks indefinitely while holding a resource)Yes, in practice; needs randomized backoff or it degrades to livelock (everyone retries in lockstep, forever, correctly avoiding deadlock but making zero progress)Weak — no ordering guarantee at all; whoever wins the race wins, same unfairness risk as A without even a resource-order tiebreakNone extra, but burns CPU on retries under contentionYou cannot get agreement on a global order AND can't afford a centralized gate — fully decentralized, at the cost of wasted retry work
Channels (Go idiom for B)Same as BYesBetter than a raw semaphore in practice — Go's channel send/receive queuing is closer to FIFO than a bare sync.Mutex/unfair lockOne shared channel; simplest correct Go idiom, the runtime owns the wait/notify protocolAny Go program needing B — prefer the channel-as-semaphore over hand-rolling one with a raw counter and a mutex

The real judgment call: resource ordering (A) is the right default — it's free and provably deadlock-free, and the trade-off you're accepting is "I need a total order over my resources," which is almost always available (IDs sort). Reach for the arbitrator (B) specifically when you want ONE place to also enforce fairness, rate-limit admission, or add observability — the centralization that looks like a downside for deadlock-avoidance becomes an asset for those other concerns. Try-lock-with-backoff (C) is the right call only when you genuinely can't get agreement on ordering AND can't afford a shared gate — e.g., fully peer-to-peer systems with no coordinator and no shared identity space. None of the three is starvation-free out of the box; if bounded waiting is a hard requirement, layer a fair lock (Java: new ReentrantLock(true), at a real throughput cost from FIFO handoff) or a ticket/round-robin scheme onto whichever deadlock-avoidance strategy you picked.

7. Defend under drilling

8. You can now defend

Re-authored/Deepened for this guide. Reference code compiled and executed before publishing (javac; go vet, go build -race) — the naive version's deadlock was reproduced via JVM ThreadMXBean cycle detection and, independently, via Go's native runtime deadlock detector; all three fixes completed 100/100 meals with zero data races in both languages; the starvation probe's numbers are real captured output, not illustrative estimates. See also: Dining Philosophers — Deadlock-Free Coordination and Deadlock, Livelock & Starvation.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build Dining Philosophers (Deadlock-Free)? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build Dining Philosophers (Deadlock-Free)** (Hands-On Builds) and want to truly understand it. Explain Build Dining Philosophers (Deadlock-Free) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build Dining Philosophers (Deadlock-Free)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build Dining Philosophers (Deadlock-Free)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build Dining Philosophers (Deadlock-Free)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Build a Semaphore from ScratchBuild a Future / Promise →