Dining Philosophers
Five philosophers, five forks, alternating thinking and eating. Each needs both adjacent forks to eat, so naively-acquired forks deadlock. Classic solutions: enforce odd/even acquisition order, limit to 4 eaters at once, or use a waiter (arbitrator).
The setup
Dijkstra came up with this in 1965. Picture five philosophers sitting around a round table. Between every pair of philosophers there is one fork, so there are five forks total. To eat, a philosopher needs the fork on their left and the fork on their right at the same time. They spend their day in two states: thinking, or eating. When they want to eat, they pick up both forks, eat for a while, then put both forks back and go back to thinking.
The catch is that each fork is shared between two neighbors. Only one of them can be holding it at any moment. So if the person on your left is eating, you can't pick up the fork between you. You have to wait for them to put it down.
The job is to write the philosopher's code so that the table keeps running. Nobody freezes forever waiting on a fork that never comes free. Ideally nobody is starved out either.
A picture of the table
Five philosophers, five forks between them, in a ring. Each philosopher needs the two forks they are connected to.
Why the obvious solution gets stuck
The first thing anyone tries: every philosopher picks up their left fork first, then their right fork. It looks reasonable. It also breaks immediately if everyone gets hungry at the same time.
Now every philosopher is holding one fork and waiting on the next one in the ring. Nobody is willing to put their fork down until they finish eating, but they cannot eat without two. Everyone waits forever. That is a deadlock.
The reason this happens is a circle. P0 is waiting on a fork held by P1, who is waiting on P2, who is waiting on P3, and so on, all the way back to P0. Everyone in the cycle is stuck.
Three ways to break the cycle
The fixes work by making sure that exact circle cannot form, or cannot last.
Fix 1: change the pick-up order for some philosophers
If everyone reaches for the left fork first, the cycle is built into the rules. Break the symmetry. Even-numbered philosophers (P0, P2, P4) reach for the right fork first; odd-numbered ones (P1, P3) reach for the left fork first.
Now picture the same "everyone hungry at once" moment. Two neighbors are no longer both reaching the same way around the table. At least one fork ends up unclaimed in that first round, so at least one philosopher gets their second fork and starts eating. That breaks the freeze.
Fix 2: cap the number of philosophers eating at once
Put a quota on how many philosophers may be in the "trying to eat" state at the same time. With five philosophers and five forks, allow at most four to be reaching for forks at once. The fifth one must wait its turn before even picking up a fork.
Why does that work? A full deadlock needs all five participants in the circle. If one of them is sitting out, the chain is broken, somebody in the ring can finish, put their forks down, and unblock the next person.
This is what Semaphore(4) does in the code above.
Fix 3: ask a waiter for permission
Add one more person, a waiter, who watches the whole table. Philosophers do not pick up forks on their own. They ask the waiter, "may I eat?" The waiter only says yes when both forks next to that philosopher are free. The waiter hands them out together, or refuses for now.
This avoids the deadlock by giving out the two forks as a single unit, never one at a time. There is no in-between state where a philosopher is holding one fork and waiting for the other.
If the waiter also keeps a fair queue of who has been waiting longest, no philosopher gets starved out either.
Why this problem still gets asked
The shape shows up everywhere Anytime two operations each need two shared resources and pick them up one at a time, you have a dining philosophers problem in disguise.
Examples from real systems:
- Transferring money between two accounts. Each transfer locks the "from" account and the "to" account. If two transfers go in opposite directions and lock in opposite orders, they deadlock. Fix: always lock the lower account ID first. That is the asymmetric pick-up order, applied to bank accounts.
- Row-level locks in databases. Two transactions touching the same two rows in opposite orders deadlock. Postgres and MySQL run deadlock detectors specifically because this pattern shows up so often in real schemas.
- Distributed lock services like etcd or Consul. Clients holding multiple named locks have to acquire them in a fixed order, otherwise the same circle forms across machines.
What separates strong answers from weak ones
The trap is to memorize one of the fixes and write it down. The interviewer is watching for whether you can explain why it works.
A weaker answer says: "I make even ones reach right first, that fixes it." A stronger answer says: "Without the change, all five philosophers can each grab one fork and then wait on the next, forming a circle of waiters that nobody can escape. Reaching different ways around the ring means at least one fork stays free in that first round, so the circle never closes."
Most fixes solve deadlock, not starvation The asymmetric order and the four-eaters cap both stop the table from freezing. They do not guarantee that any one philosopher actually gets to eat. A slow philosopher could keep losing the race to their faster neighbors and go hungry forever. Naming this gap, and offering the waiter-with-a-queue as the fix, is the part most candidates miss.
Implementations
Even-numbered philosophers grab right then left; odd grab left then right. The asymmetry breaks the circular-wait condition (Coffman). At most 4 philosophers can be holding their first fork simultaneously, so at least one can complete.
1 import java.util.concurrent.locks.ReentrantLock;
2
3 class DiningPhilosophers {
4 private final ReentrantLock[] forks = new ReentrantLock[5];
5
6 public DiningPhilosophers() {
7 for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
8 }
9
10 public void wantsToEat(int p, Runnable pickLeft, Runnable pickRight,
11 Runnable eat, Runnable putLeft, Runnable putRight) {
12 ReentrantLock left = forks[p];
13 ReentrantLock right = forks[(p + 1) % 5];
14 if (p % 2 == 0) {
15 right.lock(); pickRight.run();
16 left.lock(); pickLeft.run();
17 } else {
18 left.lock(); pickLeft.run();
19 right.lock(); pickRight.run();
20 }
21 eat.run();
22 putLeft.run(); left.unlock();
23 putRight.run(); right.unlock();
24 }
25 }A Semaphore(4) caps how many philosophers are eating concurrently. With at most 4 trying to eat, at least one always gets both forks. Simpler to reason about than asymmetry.
1 import java.util.concurrent.Semaphore;
2
3 class DiningPhilosophersV2 {
4 private final ReentrantLock[] forks = new ReentrantLock[5];
5 private final Semaphore eaters = new Semaphore(4); // ← cap
6
7 public DiningPhilosophersV2() {
8 for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
9 }
10
11 public void wantsToEat(int p, Runnable pickLeft, Runnable pickRight,
12 Runnable eat, Runnable putLeft, Runnable putRight)
13 throws InterruptedException {
14 eaters.acquire();
15 try {
16 forks[p].lock();
17 forks[(p + 1) % 5].lock();
18 pickLeft.run(); pickRight.run();
19 eat.run();
20 putLeft.run(); forks[p].unlock();
21 putRight.run(); forks[(p + 1) % 5].unlock();
22 } finally { eaters.release(); }
23 }
24 }Key points
- •Naive solution (each grabs left then right) deadlocks, circular wait
- •Solution 1: odd philosophers grab left first, even grab right first → asymmetry breaks cycle
- •Solution 2: a Semaphore(N-1) limits concurrent eaters → no full cycle possible
- •Solution 3: arbitrator (waiter) serializes fork pickups
- •Modern Go solution: channel-based fork ownership eliminates locks entirely