Introduction

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.

Run It Yourself

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">Five philosophers, five forks. To eat, a philosopher needs both neighboring forks. Run the naive protocol (everyone grabs left first) and watch them deadlock — then pick a fix and see everyone eat.</p>
<div class="modes">
  <label><input type="radio" name="mode" value="naive" checked> Naive (left then right)</label>
  <label><input type="radio" name="mode" value="order"> Resource ordering</label>
  <label><input type="radio" name="mode" value="waiter"> Waiter (max 4 seated)</label>
</div>
<div class="stage"><svg id="table" viewBox="0 0 320 320" aria-label="round table"></svg></div>
<div class="status" id="status">Pick a mode, then press Run.</div>
<div class="counters">
  <span>Meals served: <b id="meals">0</b></span>
  <span>Ticks: <b id="ticks">0</b></span>
</div>
<div class="btns">
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dining philosophers (Dijkstra, 1965). N philosophers, N forks on a ring.
// Fork i sits between philosopher i and philosopher (i+1)%N.
// Philosopher i's LEFT fork = i, RIGHT fork = (i-1+N)%N (depends on seating; here we just need a fixed, distinct pair per philosopher).
const N = 5;
const leftFork  = i => i;                 // fork on the left of philosopher i
const rightFork = i => (i + 1) % N;       // fork on the right of philosopher i
// forkOwner[f] = philosopher index holding fork f, or -1 if free.
let forkOwner, state, meals, ticks, timer, mode;

function reset() {
  forkOwner = Array(N).fill(-1);
  state = Array(N).fill('thinking'); // thinking | hungry | eating
  meals = 0; ticks = 0;
  if (timer) { clearInterval(timer); timer = null; }
  setStatus('Pick a mode, then press Run.', '');
  draw();
}

// Which two forks philosopher i reaches for, in pickup order. Under "resource
// ordering" she always takes the LOWER-numbered fork first, which breaks the cycle.
function order2(i) {
  let a = leftFork(i), b = rightFork(i);
  if (mode === 'order' && a > b) return [b, a];
  return [a, b];
}

// One tick models a simultaneous round in two phases, so the naive policy can
// reach the classic deadlock: everyone grabs a first fork before anyone grabs a second.
function tick() {
  ticks++;
  let progressed = false;
  const seated = () => state.filter(s => s !== 'thinking').length;

  // Phase A: finish meals, wake thinkers, grab FIRST fork (all at once).
  for (let i = 0; i < N; i++) {
    if (state[i] === 'eating') {
      forkOwner[leftFork(i)] = -1; forkOwner[rightFork(i)] = -1;
      state[i] = 'thinking'; meals++; progressed = true; continue;
    }
    if (state[i] === 'thinking') {
      if (mode === 'waiter' && seated() >= N - 1) continue; // waiter blocks a 5th diner
      state[i] = 'hungry'; progressed = true;
    }
    if (state[i] === 'hungry') {
      const [a] = order2(i);
      if (forkOwner[a] === -1) { forkOwner[a] = i; progressed = true; }
    }
  }
  // Phase B: grab SECOND fork if free; if both are held, eat.
  for (let i = 0; i < N; i++) {
    if (state[i] !== 'hungry') continue;
    const [a, b] = order2(i);
    if (forkOwner[a] === i && forkOwner[b] === -1) { forkOwner[b] = i; progressed = true; }
    if (forkOwner[a] === i && forkOwner[b] === i) { state[i] = 'eating'; progressed = true; }
  }

  const blocked = state.every(s => s === 'hungry') &&
                  forkOwner.every(o => o !== -1);
  if (blocked) {
    for (let i = 0; i < N; i++) state[i] = 'hungry';
    draw(true);
    setStatus('☠ DEADLOCK: every philosopher holds one fork and waits forever.', 'bad');
    clearInterval(timer); timer = null; return;
  }
  draw();
  if (meals >= 8) {
    setStatus(fmt('✓ Everyone keeps eating — no deadlock, %meals% meals served.', { meals: meals }), 'ok');
    clearInterval(timer); timer = null; return;
  }
  if (!progressed) {
    setStatus('Stuck: no philosopher can make progress.', 'bad');
    clearInterval(timer); timer = null;
  }
}

function run() {
  reset();
  mode = document.querySelector('input[name=mode]:checked').value;
  setStatus(fmt('Running "%mode%"…', { mode: mode }), '');
  timer = setInterval(tick, 420);
}

// ---- drawing ----
const cx = 160, cy = 160, R = 95, fr = 70;
function pos(angle, r) { return [cx + r * Math.cos(angle), cy + r * Math.sin(angle)]; }
function draw(deadlock) {
  const svg = document.getElementById('table');
  let s = '<circle cx="160" cy="160" r="118" fill="none" stroke="#e3e7ec" stroke-width="2"/>';
  // forks sit between philosophers, at angle offset by half a slot
  for (let f = 0; f < N; f++) {
    const ang = (f + 0.5) * (2 * Math.PI / N) - Math.PI / 2;
    const [x, y] = pos(ang, fr);
    const held = forkOwner[f] !== -1;
    s += '<line class="fork' + (held ? ' held' : '') + '" x1="' + (x - 9) +
         '" y1="' + (y - 9) + '" x2="' + (x + 9) + '" y2="' + (y + 9) + '"/>';
    s += '<text x="' + x + '" y="' + (y + 18) + '" font-size="9" fill="#888" text-anchor="middle">f' + f + '</text>';
  }
  for (let i = 0; i < N; i++) {
    const ang = i * (2 * Math.PI / N) - Math.PI / 2;
    const [x, y] = pos(ang, R);
    let cls = 'phil ' + (state[i] === 'eating' ? 'eating' :
              state[i] === 'hungry' ? (deadlock ? 'blocked' : 'hungry') : '');
    s += '<circle class="' + cls.trim() + '" cx="' + x + '" cy="' + y + '" r="22"/>';
    s += '<text class="plabel" x="' + x + '" y="' + (y + 5) + '">P' + i + '</text>';
  }
  svg.innerHTML = s;
}
function setStatus(t, cls) { const e = document.getElementById('status'); e.textContent = t; e.className = 'status ' + cls;
  document.getElementById('meals').textContent = meals; document.getElementById('ticks').textContent = ticks; }

document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', reset);
document.querySelectorAll('input[name=mode]').forEach(r => r.addEventListener('change', reset));
reset();
Result
Console

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 Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dining-philosophers/Content licensed under CC BY-NC 4.0.