Problem 15 The Dining Philosophers

Why the naive solution deadlocks, and the one-line idea that fixes it

Five philosophers sit in a circle; a fork lies between each pair. To eat, a philosopher needs both adjacent forks. The textbook deadlock appears the instant every philosopher picks up their left fork at the same time: each now holds one fork and waits forever for the right one. That is a circular wait — one of the four Coffman conditions for deadlock — and it is exactly what the earlier version of this page shipped (its tryLock attempt also leaked the first fork when the second acquisition failed, then falsely claimed to be deadlock-free).

The fix is resource ordering: number the forks and require every philosopher to acquire the lower-numbered fork first. With a global order on lock acquisition, a cycle in the wait-for graph is impossible, so deadlock cannot occur. (No timeouts, no central waiter needed.)

Correct Java

import java.util.concurrent.locks.ReentrantLock;

class DiningPhilosophers {
    private final ReentrantLock[] forks = new ReentrantLock[5];
    DiningPhilosophers() { for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock(); }

    // philosopher id in 0..4; left fork = id, right fork = (id+1)%5
    public void dine(int id) throws InterruptedException {
        int left = id, right = (id + 1) % 5;
        int first = Math.min(left, right), second = Math.max(left, right); // GLOBAL ORDER

        forks[first].lock();
        try {
            forks[second].lock();
            try {
                eat(id);                 // both forks held -> safe to eat
            } finally { forks[second].unlock(); }
        } finally { forks[first].unlock(); }   // unlock in finally: no leak on exception
    }
}

The two finally blocks are not decoration — they guarantee a fork is released even if eat throws, which is precisely the leak the buggy tryLock version had.

Correct Go

Go models each fork as a sync.Mutex and applies the same ordering. (Idiomatically you can also model a fork as a buffered channel of capacity 1 — send = pick up, receive = put down — but a mutex with ordering is the clearest mapping.)

var forks [5]sync.Mutex

func dine(id int) {
    first, second := id, (id+1)%5
    if first > second {
        first, second = second, first   // always lock the lower index first
    }
    forks[first].Lock()
    defer forks[first].Unlock()
    forks[second].Lock()
    defer forks[second].Unlock()
    eat(id)
}

Deadlock interleaving (5 philosophers, all left-first)

#	Event	State
1	P0 picks left fork 0	P0 holds 0
2	P1 picks left fork 1	P0:0, P1:1
3	P2 picks left fork 2	+P2:2
4	P3 picks left fork 3	+P3:3
5	P4 picks left fork 4	all hold left
6	Each blocks on right (held by neighbour)	P0→1, P1→2, P2→3, P3→4, P4→0
7	Circular wait complete	deadlock

Resource ordering (always acquire min(left,right) first) makes step 5 impossible for the whole ring: at least one philosopher reaches for a fork already contested in the opposite order, breaking the cycle.

Pitfalls

• Leaking a lock on the failure path (the original bug): if you try-lock fork 2 and it fails, you must release fork 1 before retrying, or you've created the deadlock you were avoiding.
• Other valid remedies: an arbitrator/waiter lock, or limiting the table to 4 seated philosophers via a Semaphore(4) (at most 4 compete for 5 forks → someone always finishes). Resource ordering is the cheapest — no extra coordination object.

Three fixes, three different Coffman conditions broken

Deadlock needs all four Coffman conditions at once — mutual exclusion, hold-and-wait, no-preemption, and circular wait — so any remedy works by killing exactly one of them. Knowing which one each fix removes is the difference between memorizing three tricks and understanding the problem:

Fix	Coffman condition it breaks	How
Resource ordering (take min(left,right) first)	Circular wait	A cycle in the wait-for graph needs someone holding a high-numbered fork while waiting on a low-numbered one; but everyone acquires low-then-high, so that edge can't exist and the ring can't close.
Arbitrator / waiter (a central lock granting both forks)	Hold-and-wait	A philosopher acquires both forks atomically under the waiter, or neither — they never hold one fork while blocked waiting for the second, so there is nothing to wait on while holding.
Limited seating (Semaphore(4) for 5 seats)	Circular wait	With at most 4 philosophers ever competing for 5 forks, all 5 can never simultaneously hold their left fork; by pigeonhole at least one philosopher can always obtain both, so no full cycle forms.

(Breaking mutual exclusion — sharing a fork — is nonsensical here, and breaking no-preemption — yanking a fork back — means tryLock-with-backoff, which is deadlock-free but livelock-prone if everyone backs off in lockstep. Those are why the three above are the practical choices.)

Which to pick — throughput vs fairness

In a 5-seat ring the physical ceiling is 2 philosophers eating at once (the maximum set of non-adjacent seats in a 5-cycle is 2 — e.g. P0 and P2), so a fix's quality is how close it gets to that 2 and how evenly it shares.

• Resource ordering — reaches the full concurrency of 2, adds no coordination object, and is the cheapest. Weakness: it is not fair — the two philosophers who contend for the shared lowest-numbered fork can be starved by luckier neighbours; there is no queue guaranteeing turns.
• Arbitrator — most fair (the central waiter can hand out turns FIFO), but the waiter is a serialization point: if it is held across the whole pick-up-both step it throttles concurrency toward 1 eater at a time, halving throughput. Choose it when fairness/starvation-freedom matters more than raw throughput, or when you need one place to reason about the whole intersection of forks.
• Limited seating — also reaches concurrency 2 and gives good starvation resistance (the semaphore bounds contention so no one waits indefinitely), at the price of one extra semaphore object and a global admission gate. A solid middle ground when you want ordering's throughput but better fairness.

Takeaways

• Deadlock here is a circular wait; break it by imposing a global lock-acquisition order.
• Always release in finally (Java) / before every return (Go) so a failure can't leak a held fork.
• Semaphore(N-1) and an arbitrator are alternative fixes; ordering is the simplest and lock-free of extra objects.

---

Re-authored for correctness for this guide (the prior version leaked a fork and falsely claimed deadlock- freedom). Classic Dijkstra dining-philosophers; Coffman conditions for deadlock. See also: Mutex Lock, Deadlock.

I'm working on the problem **Problem 15 The Dining Philosophers** (Concurrency). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Problem 15 The Dining Philosophers** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Problem 15 The Dining Philosophers**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Problem 15 The Dining Philosophers**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.