Cairn
algorithms · concurrency · O(1) time per fork pickup, O(n) space, n-process deadlock avoidance

↩ back to Concurrency

Dining Philosophers Problem

This site's other three Concurrency entries — Peterson's algorithm, Lamport's bakery algorithm, and Dekker's algorithm — all answer the same question: can two or more processes ever be inside the same critical section at once? This page asks a different one. Dijkstra posed it in 1965 (the same year as Dekker's algorithm, in a note about computers competing for tape-drive peripherals), and Tony Hoare later gave it the framing that stuck: n philosophers sit at a circular table, alternating between thinking and eating. Between each adjacent pair sits one fork — n forks total — and eating requires picking up both of the forks on either side, one at a time, not atomically. A philosopher who can't get both forks just waits. Nothing here needs mutual exclusion over a single shared resource; it needs n processes to each acquire two of n shared resources arranged in a cycle without ever getting permanently stuck.

"Stuck" is the operative word, and it's a different failure mode than anything on this site's other eight Concurrency pages. A fork is only ever held by one philosopher at a time, by construction — picking one up always checks it's free first, so there's no safety violation to even look for here. The only real question is liveness: does every philosopher who wants to eat eventually get to, or can the table reach a state where everyone is holding one fork, waiting for a neighbor who is never going to let go? Same measure-don't-assume discipline as this site's other Concurrency pages: every claim below comes from exhaustively searching every reachable interleaving of a small state machine, not a hand-picked trace.

Try it

Pick a table size, how many times each philosopher tries to eat, and a pickup rule, then either step through by hand — each Step Pi button runs that philosopher's next pending action, or reports that they're blocked — or press Explore all schedules to search every reachable interleaving at once. Try Naive at the default 5 philosophers, 1 attempt each, and explore: guaranteed deadlock, every philosopher holding exactly one fork. Then switch to Resource hierarchy with the same settings: zero. Then try Alternate by parity at table sizes 3 through 7 — it looks like a trick that should only work when the table size is even; see what the search actually finds.

Pick a table size, attempt count, and pickup rule, then step each philosopher by hand.

Why it works

Number the philosophers and forks 0 through n-1 around the table. Philosopher i's left fork is fork i; their right fork is fork (i+1) mod n — which is exactly philosopher (i+1) mod n's left fork. Every fork is shared between exactly two neighbors this way, and the table forms one unbroken cycle.

A full deadlock needs all four of the classic conditions at once: each fork can only be held by one philosopher (true here by construction), a philosopher holds a fork while waiting for the other (hold-and-wait — nobody puts a fork back down just because the second one isn't free yet), nobody can be forced to surrender a fork they're holding (no preemption), and a chain of philosophers each waiting on the next one's fork closes back on itself (circular wait). Break any one of the four and deadlock becomes impossible. The Naive rule — everyone picks up their left fork first, then their right — leaves all four intact: if every philosopher picks up their left fork before any of them tries for a right one, philosopher i is left wanting fork (i+1) mod n, which is already sitting in philosopher (i+1) mod n's hand as their own left fork. Everyone is one fork away from eating, and everyone's missing fork is held by the next philosopher around the circle. That's circular wait, named exactly.

Resource hierarchy (Dijkstra's own fix) targets circular wait directly: every philosopher picks up the lower-numbered of their two forks first, whichever hand that happens to be. For every philosopher except one, the lower-numbered fork already is the left one (fork i < fork i+1 for every i from 0 to n-2) — so this changes nothing about n-1 of the n philosophers' behavior. The only philosopher it changes is the last one, n-1, whose forks are n-1 and the wraparound fork 0 — the lower-numbered one is 0, their right hand, not their left. Flipping a single philosopher's order is enough: every philosopher now always reaches for a strictly higher fork number second. Follow any chain of "is waiting on the philosopher holding fork k" and the fork number such a chain names strictly increases at every link — a strictly increasing sequence can never loop back to revisit a number it already used, so no cycle, and therefore no circular wait, can ever form. That argument holds for any n; it doesn't need the demo to confirm it, though the demo still runs the exhaustive search rather than asking you to take it on faith.

Alternate by parity — even-numbered philosophers reach for their left fork first, odd-numbered philosophers reach for their right fork first — is the tempting third option: it also sounds like "break the symmetry," the same move the hierarchy fix makes. Work out which fork each philosopher's first move targets and a real structural reason it resists deadlock falls out: an even philosopher i's first fork is i (even); an odd philosopher i's first fork is (i+1) mod n (also even, since odd+1 is even before the wraparound, and the one wraparound case, the largest odd index, lands back on fork 0). Every philosopher's first move, whoever they are, targets an even-numbered fork. Odd-numbered forks are never anyone's first request. With only the even-numbered forks ever in play for a first pickup, strictly fewer than n philosophers can ever be simultaneously holding a first fork at once — someone is always still waiting on a free even-numbered fork before they can even start, which rules out the exact all-n-first-forks-claimed-at-once precondition the naive rule's deadlock depends on. That argument rules out that specific pattern for any table size; see Pitfalls for what the full exhaustive search (which checks every pattern, not just that one) actually finds across several table sizes.

Reference implementation

Same ground rules as five of this site's other ten Concurrency pages (the Treiber Stack, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List are the exceptions, built on hardware compare-and-swap instead): ordinary reads and writes to shared memory (here, an array of fork owners), interleaved arbitrarily by the scheduler. fork[k] is null when free, or the index of whoever holds it.

function order(rule, i, n) {
  const left = i, right = (i + 1) % n;
  if (rule === 'naive') return [left, right];
  if (rule === 'hierarchy') return left < right ? [left, right] : [right, left];
  if (rule === 'parity') return (i % 2 === 0) ? [left, right] : [right, left];
}

function pickUpFirst(fork, i, rule, n) {
  const [first] = order(rule, i, n);
  if (fork[first] !== null) return false;   // blocked — try again later
  fork[first] = i;
  return true;
}

function pickUpSecond(fork, i, rule, n) {
  const [, second] = order(rule, i, n);
  if (fork[second] !== null) return false;  // blocked — try again later
  fork[second] = i;
  return true;                              // both forks held — eat
}

function putDown(fork, i, rule, n) {
  const [first, second] = order(rule, i, n);
  fork[first] = null;
  fork[second] = null;
}

The demo above runs this exact shape as a step-by-step state machine — picking up the first fork, picking up the second, and putting both down together are each their own click, independently interleavable across every philosopher — not a simplified stand-in for it.

Pitfalls

Naive deadlocks every single table size tested, in exactly n moves — no second fork ever needs to move. Every philosopher picking up their own left fork, in any order, is already enough: table sizes 3 through 7 at 1 attempt each each have exactly 1 reachable deadlocked state, reached by the shortest possible path of exactly n clicks (one left-fork pickup per philosopher, nothing else). Give every philosopher more than one attempt and the deadlock count climbs fast — and it isn't random growth, it's exact: at 2 attempts each the count is 2n (8, 16, 32, 64, 128 at n=3 through 7), and at 3 attempts each on the two smallest tables it's 3n (27 at n=3, 81 at n=4) — matching attemptsn exactly in every one of the 13 configurations checked (the demo above caps attempts at 2, and at 1 once n reaches 7, purely so a click stays instant; the n=7 2-attempts configuration and every 3-attempts configuration above were checked the same exhaustive way, in a plain Node script extracted from this page's own reference implementation, just outside the live widget's own input range). Each philosopher independently gets to choose which of their own attempt-rounds is the one that joins the final simultaneous grab, and that choice is free of every other philosopher's — which is exactly the shape an attemptsn count comes from.

Alternate by parity looks like it should need an even table to work, and the exhaustive search disagrees. The usual intuition: alternating directions around a circle is a 2-coloring, and a circle with an odd number of seats can't be properly 2-colored — so the fix should break down exactly where the coloring can't close cleanly, at odd n. Checked directly against table sizes 3 through 7 (the range the demo above supports), at 1 and 2 attempts each: zero deadlocks at every single one, odd and even n alike. The "Why it works" section above has the real mechanism — every philosopher's first move targets an even-numbered fork regardless of parity, which caps how many philosophers can simultaneously clear the first hurdle below n either way — but this page is making the narrower, honest claim the search actually supports: deadlock-free for every table size and attempt count checked here, not a proof that no table size anywhere could ever fail.

rulephilosophersattempts eachreachable statesdeadlocked states
Resource hierarchy515340
Resource hierarchy527,0350
Resource hierarchy716,7740
Alternate by parity514920
Alternate by parity526,2550
Alternate by parity715,7360
Naive515731
Naive717,2691
Naive527,77532
Naive435,04181

Complexity

Time: O(1) per fork pickup under any of the three rules above — picking up the lower-numbered fork first costs one comparison more than picking up the left fork unconditionally, not an asymptotically different amount of work. That's a cheaper per-operation cost than Lamport's bakery algorithm's O(n) ticket scan, but the two solve different problems: bakery guarantees only one of n processes is ever in one shared critical section; resource hierarchy guarantees n processes each acquiring two of n shared resources never deadlock, which says nothing about how long any one philosopher might wait its turn (a second philosopher could, in principle, keep winning a contested fork indefinitely with no violation of anything proven here — the fix here is a liveness-from-deadlock guarantee, not a bounded-waiting one). Space: O(n) — one shared "who's holding this" slot per fork, plus a per-philosopher state, both of which scale with the table size rather than staying fixed the way Peterson's and Dekker's two-process O(1) footprint does.

See Choosing a Mutual Exclusion Algorithm for Peterson's, Dekker's, and Lamport's bakery algorithm side by side — that guide's comparison axis (process count, operational cost) doesn't extend to this page, because this page was never trying to solve mutual exclusion over a single resource in the first place.