What is the dining philosophers problem and how can it be solved?
Five philosophers sit round a table with five forks, and each needs two adjacent forks to eat. If all pick up their left fork together, everyone waits forever. Solutions include a fork ordering, a limit of four seated, or an asymmetric pickup.
Explain it simply
Five friends share a plate of noodles with only five chopsticks, one between each pair. To eat, a person needs the chopstick on each side. If everyone grabs the left one at the same moment, each holds one and waits for the right one, which their neighbour holds. Nobody eats.
That is a deadlock caused by circular wait, and it models any set of processes that each need several shared resources.
Example
Fixes, each breaking one deadlock condition:
- Allow at most four philosophers at the table. With four people and five forks, at least one can get two forks. This removes the circular wait.
- Asymmetric pickup. Odd-numbered philosophers pick left first, even-numbered pick right first. This breaks the circle.
- Number the forks and always pick the lower number first. Philosopher 4 (between forks 4 and 0) picks fork 0 before fork 4. A resource ordering makes a cycle impossible.
- Pick up both forks atomically (inside a monitor or under a mutex), or put them back if the second is unavailable.
// resource ordering version
lock(min(left, right))
lock(max(left, right))
eat()
unlock(both)Fix 4's "put them back" variant can cause livelock if everyone retries in step, so add a random delay.
What to say in the interview
"It is a model of deadlock and starvation with shared resources. Five philosophers each need two forks; if all take the left one, nobody proceeds. I'd fix it with a resource ordering on forks, limit four at the table, or an asymmetric pickup, since each breaks the circular wait."
Common mistakes
- Claiming a lock on each fork is enough on its own. Without an ordering it can still deadlock.