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.
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.
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.
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.
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.
| rule | philosophers | attempts each | reachable states | deadlocked states |
|---|---|---|---|---|
| Resource hierarchy | 5 | 1 | 534 | 0 |
| Resource hierarchy | 5 | 2 | 7,035 | 0 |
| Resource hierarchy | 7 | 1 | 6,774 | 0 |
| Alternate by parity | 5 | 1 | 492 | 0 |
| Alternate by parity | 5 | 2 | 6,255 | 0 |
| Alternate by parity | 7 | 1 | 5,736 | 0 |
| Naive | 5 | 1 | 573 | 1 |
| Naive | 7 | 1 | 7,269 | 1 |
| Naive | 5 | 2 | 7,775 | 32 |
| Naive | 4 | 3 | 5,041 | 81 |
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.