Dining Philosophers

The puzzle, and why it freezes

Five philosophers sit around a circular table. Between each pair of neighbors lies a single fork — five forks for five seats. A philosopher does only two things: think, and eat. To eat, they need both the fork on their left and the fork on their right. When done, they put both forks down and go back to thinking. That's the whole world.

It sounds harmless until you write the obvious code. Every philosopher runs the same loop: pick up the left fork, pick up the right fork, eat, put both down. Run all five threads, and on the very first round they each grab their left fork simultaneously. Now every fork is held, and every philosopher is blocked waiting for the right fork — which their neighbor is clutching and will never release, because that neighbor is also waiting. The table is frozen forever. This is deadlock, and the dining philosophers problem is the cleanest model of it ever devised.

Edsger Dijkstra introduced it in 1965, originally framed as five computers fighting over shared tape drives; Tony Hoare gave it the philosophers-and-forks dressing that stuck. The reason it endures is that it's not really about cutlery — it's about any thread that must acquire two or more locks to do its job, which is most non-trivial concurrent code.

The four conditions for deadlock

Deadlock isn't bad luck; it requires four conditions to hold simultaneously, identified by Coffman, Elphick, and Shoshani in 1971. Break any one and deadlock becomes impossible:

1. Mutual exclusion. A fork can be held by only one philosopher at a time. (Can't relax — forks aren't shareable.)
2. Hold and wait. A philosopher holds the left fork while waiting for the right one. (Relax by grabbing both atomically, or neither.)
3. No preemption. You can't yank a fork out of a neighbor's hand. (Relax by letting blocked philosophers put a held fork back down.)
4. Circular wait. The wait-for graph contains a cycle: P0→P1→P2→P3→P4→P0. (Relax by imposing a global ordering on resources.)

Every fix below is just an attack on one of these four. The famous "always grab the lower-numbered fork" trick attacks condition 4. The "put the fork back if you can't get the second one" trick attacks condition 2. There is no fifth idea — once you see deadlock as these four conditions, every solution is a corollary.

The resource-ordering fix

The most-used solution in real systems is dead simple: number the forks 0…4 and require every philosopher to pick up the lower-numbered fork first.

Walk the table. Philosopher 0 sits between fork 4 (left) and fork 0 (right), so they reach for fork 0 first. Every other philosopher i sits between fork i−1 and fork i, and reaches for the lower one. The crucial effect: philosopher 0 is now asymmetric — they grab their right fork first while everyone else grabs their left. That single broken symmetry makes a circular wait impossible. You can't have all five edges of the cycle pointing the same way around the table if one philosopher reaches the other direction.

This generalizes to the universal rule for real code: if every thread acquires locks in a single global order, deadlock cannot occur. Databases, kernels, and allocators all lean on this. The cost is zero runtime overhead — it's purely a discipline on the order of lock() calls — which is why it's the default advice.

Choosing a solution

• Resource ordering — when you can name and totally order all the locks ahead of time. Zero overhead, deadlock-free. The go-to.
• Arbitrator (waiter / footman) — when ordering is awkward; a central semaphore lets at most N−1 philosophers sit down, guaranteeing at least one can always finish. Simple, but the arbitrator is a contention point.
• Try-lock with backoff — when locks are dynamic and unorderable; grab the first fork, attempt the second, and if it fails, drop the first and retry after a randomized pause. Deadlock-free but can livelock without the random backoff.
• Chandy-Misra — when philosophers are distributed nodes with no shared memory; forks carry clean/dirty state and are passed on request. Fully decentralized and starvation-free, at the cost of message passing.

Comparing the classic solutions

	Resource ordering	Arbitrator (semaphore)	Try-lock + backoff	Chandy-Misra	Odd/even asymmetry
Coffman condition broken	Circular wait	Hold & wait (limits seating)	Hold & wait	Circular wait	Circular wait
Deadlock-free	Yes	Yes	Yes	Yes	Yes
Starvation-free	No (greedy neighbor)	No (without fairness)	No (unlucky thread)	Yes	No
Max concurrency	⌊N/2⌋	⌊N/2⌋	⌊N/2⌋	⌊N/2⌋	⌊N/2⌋
Central bottleneck	None	The arbitrator	None	None	None
Needs shared memory	Yes	Yes	Yes	No (messages)	Yes
Runtime overhead	~0	1 extra semaphore	Spins + sleeps on conflict	Token messages	~0
Best for	Orderable locks	Quick correctness	Unorderable locks	Distributed systems	Teaching the symmetry break

The headline trade-off: resource ordering is cheapest and most popular, but it can starve a philosopher whose neighbors are gluttons. Chandy-Misra is the only solution here that's both deadlock-free and starvation-free out of the box, which is why distributed-systems folks reach for it — but it pays in message traffic.

What the numbers actually say

• Maximum concurrency is ⌊N/2⌋. Each diner needs two adjacent forks; with N forks for N seats, at most ⌊N/2⌋ eat at once. For the classic N=5 that's two philosophers eating while three think — a 40% table utilization ceiling, not 100%.
• The naive solution deadlocks with probability that approaches 1. If all N threads grab their left fork before any grabs a right fork — the worst interleaving — deadlock is certain. Under a fair scheduler the odds per round are lower, but over a long run the probability of hitting the bad interleaving converges to 1, which is why "it worked on my laptop" is not a defense.
• The arbitrator caps seating at N−1. Allowing at most 4 of 5 philosophers to sit guarantees at least one has both neighbors free, so at least one can always eat — that single freed seat is what mathematically forbids the cycle.
• Resource ordering costs nothing at runtime. It reorders two lock() calls; there's no extra object, no extra syscall, no contention point. The entire fix is compile-time discipline.

JavaScript implementation

JavaScript is single-threaded, so we model concurrency with async functions and a tiny mutex. Each fork is a lock; a philosopher awaits both. The resource-ordering fix is the one line that sorts the two fork indices so every philosopher locks the lower-numbered fork first — which flips the acquisition order for exactly the one philosopher whose two forks straddle the 4→0 wrap, breaking the symmetry.

// Minimal async mutex — resolves the queue in FIFO order.
class Mutex {
  constructor() { this._busy = false; this._q = []; }
  async lock() {
    if (!this._busy) { this._busy = true; return; }
    await new Promise(res => this._q.push(res));
  }
  unlock() {
    const next = this._q.shift();
    if (next) next();           // hand the lock straight to the waiter
    else this._busy = false;
  }
}

const N = 5;
const forks = Array.from({ length: N }, () => new Mutex());
const sleep = ms => new Promise(r => setTimeout(r, ms));

async function philosopher(i, rounds = 3) {
  for (let r = 0; r < rounds; r++) {
    await sleep(Math.random() * 50);            // think

    // RESOURCE ORDERING: always lock the lower-numbered fork first.
    const left = i, right = (i + 1) % N;
    const [first, second] = left < right ? [left, right] : [right, left];

    await forks[first].lock();
    await forks[second].lock();
    // --- eat ---
    await sleep(Math.random() * 30);
    forks[second].unlock();
    forks[first].unlock();
  }
}

await Promise.all(Array.from({ length: N }, (_, i) => philosopher(i)));
// Without the [first, second] swap, every philosopher locks `left`
// then awaits `right` — and the program never resolves.

Python implementation

Python has real OS threads, so deadlock here is a genuine hang, not a metaphor. Below are two solutions side by side: resource ordering, and the arbitrator (a counting semaphore that seats at most N−1).

import threading, random, time

N = 5
forks = [threading.Lock() for _ in range(N)]

# --- Solution 1: resource ordering ---------------------------------
def philosopher_ordered(i, rounds=3):
    left, right = i, (i + 1) % N
    lo, hi = min(left, right), max(left, right)   # global lock order
    for _ in range(rounds):
        time.sleep(random.random() * 0.05)        # think
        with forks[lo]:
            with forks[hi]:
                time.sleep(random.random() * 0.03)  # eat

# --- Solution 2: arbitrator (footman) ------------------------------
footman = threading.Semaphore(N - 1)              # seat at most N-1
def philosopher_footman(i, rounds=3):
    left, right = i, (i + 1) % N
    for _ in range(rounds):
        time.sleep(random.random() * 0.05)
        with footman:                             # ask to sit down
            with forks[left]:
                with forks[right]:
                    time.sleep(random.random() * 0.03)

def run(target):
    ts = [threading.Thread(target=target, args=(i,)) for i in range(N)]
    for t in ts: t.start()
    for t in ts: t.join()

run(philosopher_ordered)   # deadlock-free
run(philosopher_footman)   # deadlock-free, different mechanism

# The naive version — DON'T ship this — hangs forever:
# def naive(i):
#     with forks[i]:                 # left fork
#         with forks[(i + 1) % N]:   # right fork  ← circular wait
#             pass

Note the asymmetry between the two correct solutions. Resource ordering rewrites which fork each philosopher grabs first and adds no shared object. The footman keeps the natural left-then-right order but adds a single semaphore that throttles how many philosophers may sit at all — a different Coffman condition (hold-and-wait) attacked from a different angle, same correct result.

Variants worth knowing

The odd/even asymmetry rule. Odd-numbered philosophers grab left-then-right; even-numbered grab right-then-left. Like resource ordering, this breaks the symmetry that creates the cycle, and it's the easiest to explain on a whiteboard, though it can still starve a diner. (Dijkstra's own 1965 solution was the fork-numbering hierarchy above — take the lower-numbered fork first; the odd/even split is a folklore variant on the same symmetry-breaking idea.)

The footman / arbitrator. A butler admits at most N−1 philosophers to the table at once. With one seat always empty, at least one philosopher has both forks free — so someone can always eat. Correct, but the footman serializes seating and becomes a contention point at scale.

Chandy-Misra (1984). Designed for distributed nodes with no shared memory. Each fork is dirty or clean; a hungry philosopher requests a fork from a neighbor, who hands it over only if it's dirty (already used), cleaning it on the way. Priorities encoded in fork ownership form an acyclic precedence graph, guaranteeing both no deadlock and no starvation — the gold standard for distributed mutual exclusion.

Try-lock with backoff. Grab the left fork, then attempt the right with a non-blocking try_lock. On failure, release the left fork and sleep a random interval before retrying. Deadlock-free because no philosopher holds a fork while blocked — but without the randomized backoff, all five can release-and-retry in lockstep forever: that failure mode is livelock, deadlock's busier cousin.

Tanenbaum's solution. A per-philosopher state machine (THINKING / HUNGRY / EATING) plus a per-philosopher semaphore and a single mutex. A philosopher eats only when neither neighbor is eating, and on finishing it explicitly wakes a hungry, eligible neighbor — making it both deadlock-free and starvation-free with shared memory.

Common bugs and edge cases

• Off-by-one on the wrap-around philosopher. The whole resource-ordering fix lives in one seat: the philosopher between fork N−1 and fork 0. Forget to swap their order and you've changed nothing — the cycle survives.
• Fixing deadlock but ignoring starvation. Resource ordering and odd/even are deadlock-free yet let a philosopher with greedy neighbors never eat. "It doesn't hang" is not the same as "everyone eats."
• Livelock from synchronized retries. The try-lock solution without randomized backoff: all philosophers drop and retry in perfect lockstep, busy forever while making no progress. Add jitter.
• Releasing forks in the wrong order or not at all. An exception between the two lock() calls can leave one fork held — in real code use RAII / with / try…finally so a held fork is always released on unwind.
• Assuming a fair scheduler saves you. Fairness reduces the odds of the bad interleaving per round but doesn't eliminate it; over a long run the deadlock interleaving will eventually be hit. Correctness must not depend on the scheduler.
• Modeling forks as a single global lock. Wrapping the whole eat phase in one mutex is trivially deadlock-free but destroys all parallelism — you've serialized the table down to one diner at a time, abandoning the ⌊N/2⌋ concurrency the problem is about.