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)
}

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.

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.