Dining Philosophers

Five philosophers sit around a circular table. Between each pair lies a single fork, so there are exactly five forks for five diners. A philosopher alternates between thinking and eating, and to eat she needs both the fork on her left and the one on her right.

The rule sounds civilized: pick up your left fork, then your right fork, eat, put them back. But picture the worst moment — everyone gets hungry at once. Each philosopher grabs her left fork simultaneously. Now every fork is held, every philosopher waits for the neighbor on her right to let go, and that neighbor is waiting too.

Nobody is doing anything wrong. Nobody will ever eat again. This frozen circle of polite waiting is deadlock, and the table is the cleanest picture computer science has of it.

Below is the round table. Each philosopher tries to pick up her left fork, then her right fork. Press Run (naive) and watch what happens when they all reach for the left fork together.

<p class="hint">{{hint}}</p>
<div class="modes">
  <label><input type="radio" name="mode" value="naive" checked> {{mode_naive}}</label>
  <label><input type="radio" name="mode" value="order"> {{mode_order}}</label>
  <label><input type="radio" name="mode" value="waiter"> {{mode_waiter}}</label>
</div>
<div class="stage"><svg id="table" viewBox="0 0 320 320" aria-label="{{aria_table}}"></svg></div>
<div class="status" id="status">{{pick_mode}}</div>
<div class="counters">
  <span>{{meals_served}} <b id="meals">0</b></span>
  <span>{{ticks_label}} <b id="ticks">0</b></span>
</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.modes { display: flex; flex-direction: column; gap: .25rem; font-size: .88rem; margin: 0 0 .6rem; }
.modes label { cursor: pointer; }
.stage { display: flex; justify-content: center; }
svg { width: 300px; height: 300px; max-width: 100%; }
.phil { fill: #e8eef3; stroke: #cdd9e3; stroke-width: 2; }
.phil.hungry { fill: #f2d27a; stroke: #d9ad3a; }
.phil.eating { fill: #6fcf7f; stroke: #3aa64f; }
.phil.blocked { fill: #e88c8c; stroke: #c64545; }
.plabel { font: 700 13px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; }
.fork { stroke: #adb1b8; stroke-width: 5; stroke-linecap: round; }
.fork.held { stroke: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0 .2rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.counters { display: flex; gap: 1.2rem; font-size: .9rem; color: #444; margin: .1rem 0 .6rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The naive run slides into deadlock: five forks held, five philosophers blocked, zero meals served. Now switch on a fix. Resource ordering numbers the forks and forces everyone to pick up the lower-numbered fork first — one philosopher ends up reaching the "wrong" way, breaks the circular wait, and dinner proceeds. A waiter instead admits at most four philosophers to the table at once, so there is always a free fork somewhere. Either way the freeze disappears.

The dining philosophers are not an unsolved problem — they are a solved one, and the value lies in why the solution works. Edsger Dijkstra posed the table in 1965 as an exam exercise; Tony Hoare later gave it its famous phrasing.

Deadlock isn't bad luck. In 1971 Edward Coffman showed it needs four conditions to hold at once:

• Mutual exclusion — a fork is held by at most one philosopher.
• Hold and wait — you keep your left fork while waiting for the right.
• No preemption — nobody can yank a fork from a neighbor.
• Circular wait — a closed loop of "I'm waiting for the one you hold."

Break any single condition and deadlock becomes impossible. Resource ordering numbers the forks and demands you always grab the lower number first; that kills the circular wait, because at least one philosopher now reaches right-then-left. A waiter (an arbitrator) caps the diners at four, which removes hold-and-wait at the table level. Both are proven deadlock-free.

The deeper lesson connects to scheduling and fairness: a fix that merely avoids deadlock can still let one philosopher starve forever. Guaranteeing liveness — everyone eventually eats — is the subtle part, and it echoes the trade-offs you meet in scheduling.

"Several workers each need several shared resources" is everywhere in real systems, and the dining philosophers are its training wheels:

• Operating systems: two processes each holding a lock the other needs is the textbook kernel deadlock — the OS uses lock ordering exactly like the numbered forks.
• Databases: transactions that each lock rows in a different order can deadlock; engines detect the cycle and abort one transaction to break it.
• Multithreaded code: acquiring mutexes in a consistent global order is the everyday programmer's "resource ordering" fix.
• Distributed systems: services waiting on each other's responses can form the same circular wait, which is why timeouts and arbitration matter.

Understand the five forks and you understand the core hazard of concurrency — the same circular wait that links this puzzle to fairness questions in scheduling and to the broader landscape mapped in P vs NP.

The dining philosophers turn an abstract failure mode into something you can watch happen: five courteous diners, each waiting for one fork, all frozen forever. The genius of the puzzle is that the freeze isn't a bug in anyone's logic — it emerges from the system, from four innocent conditions holding at the same time.

The cure is just as instructive. Number the forks, or seat one fewer diner, and the circle can never close. So the next time a program hangs with every thread "just waiting," remember the table: somewhere a circular wait has formed, and breaking even one link sets dinner moving again.