Every textbook that teaches concurrency eventually reaches the dining philosophers: a round table, five thinkers, five forks, and an evening that ends in gridlock. It is the field’s most famous story problem, and it has outlived the technology it was meant to explain. This site teaches algorithms, so the people who built them get to sit at the table. Here is the dining developers version, with actual contributors to computer science in the chairs.
If you’ve met the philosophers, you know the setup. Only the names change. If you haven’t, this article covers the table, the rules, the agreed plan, and the exact moment that plan fails. We stop there. The problem is the lesson; the solutions belong in a separate read.
The table is set
Five developers sit at a round table. Each has a plate of spaghetti. Exactly one fork sits between each pair of adjacent plates, giving five forks to five developers and one fewer decision than you might expect. The developers eat spaghetti the Italian way, with a fork in each hand, so each developer needs both the fork to their left and the fork to their right to take a bite. One fork is not enough to eat. With neither fork, a developer can only think.
The seating chart is deliberate. The five are:
- Edsger Dijkstra, who invented the whole affair - more on that below - and is now stuck at the table he designed.
- Tony Hoare, who gave the problem the name “the dining philosophers” and is repaid by being one of them.
-
Donald Knuth, mid-thought about whether the optimal fork-picking strategy
could be
O(log n). - Alan Turing, who has decided the forks are a decidable problem and is quietly disappointed.
- Grace Hopper, who would like to remind the table that the first compiler she ever wrote didn’t need a fork, and could everyone please just eat.
The table is just barely provisioned. Five forks cannot feed five people at once. At most two non-adjacent developers can hold two forks simultaneously, so eating requires sharing. Sharing requires coordination. Talking would make that easy, but the house forbids it.
The rules of the house
Two rules. That is the whole problem.
- Think, then eat, forever. Each developer alternates between thinking (no fork needed) and eating (two forks needed), indefinitely. There is no last meal. The simulation never ends.
- No talking. The developers may not discuss who gets the forks when. (Presumably they are too busy thinking.) All coordination must emerge from the forks themselves - from the only thing they can observe and touch.
That second rule makes this a concurrency problem, not a dinner-party plan. In a real system, processes competing for resources cannot reliably “just talk it out” either. They may be separate threads or machines, with the resource as their only shared ground. The forks are shared memory. The developers are processes. The mapping is direct.
The naive plan, and the exact moment it fails
Left alone, all five developers reach the same sensible-sounding plan:
- Think until the fork on your left is available, then pick it up.
- Think until the fork on your right is available, then pick it up.
- Eat until full.
- Put down the left fork.
- Put down the right fork.
- Think until hungry again, and repeat.
Every step looks reasonable. No developer is greedy: each holds a fork only while waiting for the second and releases both after eating. No developer is malicious. Nobody hogs a fork out of spite. This is the obvious plan for a well-meaning process.
Start the evening. The five developers are similar, so they get hungry together and reach for their left fork together. Every left fork is free. Every left fork is picked up. At that instant, the table’s state is fixed: every fork is in someone’s left hand, so every developer’s right fork is held by the neighbor on their right. Each developer has one fork and waits for a fork held by someone who is also waiting.
Nobody eats. Nobody can put down a fork first without breaking the plan. The evening ends before the spaghetti gets cold.
This is deadlock: a cycle of waiting in which every participant is blocked on a resource held by another participant in the cycle, so no participant can make progress and no resource can be released. Nothing went wrong at the individual level. Nobody made a mistake, panicked, or behaved badly. Each developer followed a locally sensible rule, but the arrangement of those rules produced deadlock. That is the lesson: deadlock is a property of the system, not of the people in it.
The problem is sharper because the table is exactly provisioned. Five forks cannot let everyone eat at once, so someone has to wait at any moment. Waiting alone is not a bug. The bug is that the naive plan makes everyone wait on everyone else, and the waiting sustains itself forever. Scarcity creates the need for coordination. Failed coordination creates deadlock.
What the problem is actually about
Remove the spaghetti and you have a bare model of the failure modes that make shared-memory programming hard:
- Shared resources. The forks are the resources, and they’re shared - each fork is adjacent to two developers. No resource belongs exclusively to one process.
- Mutual exclusion. A fork is either in use by exactly one developer or free. There is no “sharing a bite” - the fork can’t be split. This is the same constraint a lock or a mutex encodes.
- No out-of-band coordination. The developers can’t talk, so the only channel of coordination is the resource itself - exactly the situation threads find themselves in when their only shared ground is the memory or lock they’re fighting over.
A second failure mode appears just past deadlock. It has a name. Suppose the plan said, “if you’ve waited ten minutes for your right fork, put your left fork down and try again.” That breaks the deadlock, then recreates it immediately. All five developers would wait ten minutes, put down their forks together, reach for their left forks together, and return to the same state. That’s livelock: everyone is busy, nobody is blocked, and nothing gets done. The dinner stays uneaten either way.
The original version was more prosaic. In 1965, Edsger Dijkstra set an exam exercise for his students at the Eindhoven University of Technology about five computers competing for five tape-drive peripherals - a real, boring, administrative-sounding problem. He turned it into philosophers at a round table because starving philosophers stick in the mind better than deadlocked processes. Tony Hoare, who gave the problem its present form and its name a few years later, put the word dining in front of the philosophers. The costumes changed. The deadlock did not.
The solutions exist - and they’re not the point
The dinner is not doomed. The dining philosophers problem has been solved several ways, each with different trade-offs - an authority that doles out forks, a fixed order in which everyone must pick forks up, a dirty-fork handoff rule, randomized backoff. You will meet each technique again under its real name when you study concurrent programming.
This article stops at the diagnosis because that is the part people skip and the part that generalizes. Each solution matters only because you can see exactly how the naive plan fails: the waiting cycle, the exactly-provisioned table, and the silence. If you can narrate the failure, the fixes are a menu. If you cannot, they are spells. The problem is explained here. The solutions are deliberately not.
Where this leaves you on this site
The Dining Philosophers exercise is this table, grader-run: n philosophers, n forks, everyone must eat. The logical predecessor is still Print in Order, which asks the question that has to be answered before any synchronization can work: given a set of tasks and their prerequisites, is a valid order even possible? The runtime version is Print in Order (concurrent): three processes that must fire in sequence while the harness scrambles the calls. A mutex doesn’t create an order; it protects an order that must already exist. Topological sort decides whether the order exists; the deadlock is what you get when it doesn’t, and something keeps trying to enforce one anyway.
The mechanics of how real runtimes share a machine - the single event loop, the preemptive scheduler, the cost of each model - are the subject of the concurrency article. That article is about how threads and processes work; this one is about how they fail. Read both before you write your first genuinely concurrent program.
The honest summary
Five developers, five forks, a round table, and a rule against talking. Each developer can eat only with both adjacent forks; each follows a locally sensible plan; and because they all follow it in lockstep, every fork ends up in a left hand and everyone waits forever on the neighbor holding their right fork. No malice. No mistake. Individually reasonable rules have deadlocked the system.
The dining developers is the canonical demonstration that in concurrent systems, good behavior is not enough. You also need the system to guarantee that waiting terminates - and that guarantee has to be designed in, because nobody at the table is going to break the silence to ask for it.
Where to go next
- Dining Philosophers - this table, as an exercise: n philosophers, n forks, everyone must eat.
- Print in Order - ordering guarantees by design, the constructive answer to this article’s “the guarantee has to be designed in.”
- Print in Order (concurrent) - the same order enforced at runtime, not computed as a list.
- Process Ring - the same ring shape with the deadlock removed: a cycle of BEAM processes passing a token, where the message passing is the coordination.
-
Graphs: when the answer is a hop away
- deadlock, named properly: a cycle in the wait-for graph, the same shape as this article’s table drawn as a ring of waiting developers.