The Dining Philosophers Problem: Deadlock, Starvation and How to Avoid Both

A deliberately minimal deadlock

Edsger Dijkstra posed the dining philosophers problem in 1965 (originally about tape drives; the philosophers framing came later, popularised by Tony Hoare) to illustrate deadlock and starvation with the smallest possible setup: five philosophers sit around a circular table, a single fork lies between each adjacent pair, and each philosopher needs both neighbouring forks to eat. Every philosopher alternates between thinking and eating, and a fork can only be held by one philosopher at a time — it's a resource with mutual exclusion, exactly like a lock, a database row or a shared memory buffer in a real concurrent system.

The naive deadlock

The obvious implementation has each philosopher pick up their left fork, then their right fork, eat, and put both down. If every philosopher picks up their left fork at the same instant, all five forks are now held and every philosopher is stuck waiting forever for a right fork that will never be released — a deadlock. This is the textbook illustration of the four Coffman conditions that must all hold simultaneously for deadlock: mutual exclusion (a fork serves one philosopher), hold-and-wait (holding the left fork while waiting for the right), no preemption (no one can force a fork away from a philosopher), and circular wait (each philosopher waits on the neighbour to their right, forming a cycle).

// naive: deadlocks if every philosopher grabs left simultaneously
pickUp(leftFork);
pickUp(rightFork);   // blocks forever if right fork's holder is
                      // itself waiting on ITS right fork (a cycle)
eat();
putDown(leftFork);
putDown(rightFork);

Breaking any one of the four conditions prevents deadlock, and each classical solution breaks a different one.

Resource ordering breaks the cycle

The cheapest fix breaks circular wait directly: number the forks 0 through 4, and require every philosopher to pick up the lower-numbered fork first regardless of which side it's on. Now the philosopher between forks 4 and 0 picks up fork 0 first, not fork 4 — the one asymmetry needed to make a cyclic wait pattern impossible. This is exactly the technique used in real database engines and lock managers: always acquire locks in a fixed global order, and circular wait cannot arise no matter how many threads compete.

// resource (fork) ordering — breaks circular wait
const [first, second] = leftFork.id < rightFork.id
  ? [leftFork, rightFork] : [rightFork, leftFork];
pickUp(first);
pickUp(second);
eat();
putDown(second);
putDown(first);

The arbitrator and limiting concurrency

A second classical fix breaks hold-and-wait: introduce an arbitrator (a waiter, in the story) that a philosopher must ask permission from before picking up either fork, and the arbitrator only grants permission if both forks are actually free, handing them out atomically. Because no philosopher ever holds one fork while waiting for the other, deadlock is structurally impossible — at the cost of a single global synchronisation point that can become a bottleneck under heavy contention, which is the classic centralised-lock trade-off.

A third fix limits concurrency directly: allow at most four of the five philosophers to sit down at once. With only four candidates for five forks, at least one philosopher is guaranteed to have both neighbouring forks free, which breaks the deadlock without needing a central arbitrator or a fork ordering — it's the concurrency-theory analogue of admission control.

Deadlock vs. starvation vs. livelock

These are three distinct failure modes worth keeping separate. Deadlock is a set of processes each permanently waiting on the others in a cycle — nothing ever progresses. Starvation is when a process is perpetually denied a resource it needs even though the system as a whole keeps making progress, for instance if a scheduling policy always favours a philosopher's neighbours. Livelock is when processes actively change state in response to each other but still make no real progress — two philosophers repeatedly picking up and putting down a fork to be polite to one another, forever. A correct solution to dining philosophers should rule out all three, not just deadlock; resource ordering and the arbitrator both do, but a naive priority scheme can eliminate deadlock while still allowing one unlucky philosopher to starve.

Frequently asked questions

Try it live

Everything above runs in your browser — open Dining Philosophers and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.