Dining Philosophers — Deadlock-Free Fork Ordering

Problem#

Five philosophers sit at a circular table. Between each adjacent pair is one fork — five philosophers, five forks. To eat, a philosopher needs both the fork to their left and the fork to their right. Each philosopher thinks, then tries to eat, then puts both forks down, and repeats.

The classic failure: every philosopher picks up their left fork simultaneously. All five hold one fork and wait forever for the fork to their right — a circular deadlock with no way out. The implementation must guarantee no deadlock, no starvation.

Think Before Coding#

Work through these before looking at the solution:

1. Where does the circular wait come from? Each philosopher holds fork[i] and waits for fork[(i+1)%5]. The last philosopher holds fork[4] and waits for fork[0], which philosopher 0 is holding — that closes the cycle and locks everyone in place.

2. Three standard fixes:

   • Limit concurrency: allow at most 4 of 5 philosophers to attempt eating at once (one fork is always free).
   • One odd one out: make one philosopher reach right-before-left; breaks the symmetry.
   • Global fork ordering: every philosopher always acquires the lower-indexed fork first — the fix used here.

3. Why does global ordering prevent cycles? A deadlock cycle requires at least one thread holding a higher-indexed resource while waiting for a lower-indexed one. If every thread always acquires the lower index first, that can never happen — the cycle has nowhere to close.

Implementation#

package DiningPhilosophers;

import java.util.concurrent.locks.ReentrantLock;

public class DiningPhilosophers {
    private final ReentrantLock[] forks = new ReentrantLock[5];

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

    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {

        int left  = philosopher;
        int right = (philosopher + 1) % 5;

        // Always lock the lower-indexed fork first — global ordering
        int first  = Math.min(left, right);
        int second = Math.max(left, right);

        forks[first].lock();    // acquire lower index first
        forks[second].lock();   // then higher index
        try {
            // Callbacks run in logical order for readable output;
            // mutual exclusion was already established above.
            pickLeftFork.run();
            pickRightFork.run();
            eat.run();
            putLeftFork.run();
            putRightFork.run();
        } finally {
            forks[second].unlock();  // release in reverse order
            forks[first].unlock();
        }
    }
}

Key Design Decisions#

Global fork ordering breaks the circular wait

For philosophers 0–3, left < right already, so first = left, second = right — they happen to match physical left-then-right. Philosopher 4 is the exception: left = 4, right = 0, so min/max flips it — philosopher 4 locks fork 0 first, then fork 4. This one reversal is what kills the cycle.

Without the flip, philosopher 4 would hold fork 4 and wait for fork 0, while philosopher 0 holds fork 0 and waits for fork 1, … closing a cycle of 5. With the flip, philosopher 4 competes for fork 0 before fork 4 — whoever wins fork 0 is the one that can proceed; no cycle can form.

Why this works in general

A deadlock cycle needs a thread holding a higher-indexed lock while blocked waiting for a lower-indexed one. Every philosopher here acquires the lower index first, so the only lock() call a thread can be blocked on is its second one — which is always the higher index. A thread can only be waiting on something bigger than what it holds. That's precisely what prevents the cycle from closing.

try/finally for unlock

Both forks are released in finally, in reverse acquisition order (second then first). If eat.run() or any callback throws, neither fork remains held permanently.

ReentrantLock over synchronized

ReentrantLock is explicit about what is locked, easier to reason about in arrays, and supports tryLock() if you later want timeout-based acquisition without changing the structure.

Demo#

package DiningPhilosophers;

public class Demo {
    public static void main(String[] args) throws InterruptedException {
        DiningPhilosophers table = new DiningPhilosophers();
        int rounds = 3;

        Thread[] philosophers = new Thread[5];
        for (int i = 0; i < 5; i++) {
            final int id = i;
            philosophers[i] = new Thread(() -> {
                try {
                    for (int r = 0; r < rounds; r++) {
                        table.wantsToEat(id,
                            () -> System.out.println("Philosopher " + id + " picks up LEFT fork"),
                            () -> System.out.println("Philosopher " + id + " picks up RIGHT fork"),
                            () -> System.out.println("Philosopher " + id + " is EATING"),
                            () -> System.out.println("Philosopher " + id + " puts down LEFT fork"),
                            () -> System.out.println("Philosopher " + id + " puts down RIGHT fork")
                        );
                        Thread.sleep((long)(Math.random() * 20));
                    }
                } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            }, "philosopher-" + id);
        }

        for (Thread p : philosophers) p.start();
        for (Thread p : philosophers) p.join();
        System.out.println("All philosophers finished — no deadlock.");
    }
}

What to observe#

All 5 philosophers complete 3 rounds each (15 eating events total) with no hang. The output shows pick-left / pick-right / eat / put-left / put-right in logical order per philosopher, but interleaved across philosophers. The program exits cleanly — proof of no deadlock.

Common Mistakes#