The problem
Five philosophers sit around a circular table. Between each adjacent pair sits a single fork — five forks total. Each philosopher alternates between thinking (needs no forks) and eating (needs both the fork to their left and the fork to their right, simultaneously). A fork can be held by only one philosopher at a time. Design a protocol so that:
- No deadlock — the philosophers don't all get permanently stuck.
- No starvation — every philosopher who wants to eat eventually does, even under an adversarial (but not literally impossible) scheduling.
Dijkstra posed this in 1965 as a teaching example, and it endures because it's the smallest possible instance of a problem that shows up constantly in real systems: N threads each need multiple shared resources out of a shared pool, and the naive acquisition strategy creates a circular wait. Database transactions locking multiple rows, distributed transactions locking multiple partitions, and a thread locking two mutexes in "the wrong" order are all the same shape as this problem.
Why the naive solution deadlocks
The obvious first attempt: model each fork as a binary semaphore/mutex initialized to 1, and have every philosopher pick up their left fork, then their right fork:
philosopher(i):
loop:
think()
wait(fork[i]) # pick up left fork
wait(fork[(i + 1) % N]) # pick up right fork
eat()
signal(fork[i])
signal(fork[(i + 1) % N])
This is a textbook circular wait, one of the four Coffman conditions for deadlock (alongside mutual exclusion, hold-and-wait, and no preemption — see Deadlock, Livelock & Starvation later in this roadmap). If all N philosophers simultaneously pick up their left fork, every single one is now holding one fork and waiting on a right-hand neighbor who is symmetrically holding their left fork and waiting too. Nobody ever releases anything. This isn't a rare edge case you can wave away — with N identical, simultaneously-scheduled threads running identical code, it's the likely outcome, not a corner case.
Note also that even without full deadlock, this naive version has zero fairness guarantee — a scheduler could let two non-adjacent philosophers eat forever while starving a third, so fixing deadlock alone doesn't automatically fix starvation.
Classic fix #1: Resource ordering (break the symmetry)
If every philosopher instead picks up the lower-numbered fork first, regardless of whether that's their "left" or "right," the circular wait becomes structurally impossible:
philosopher(i):
first = min(i, (i + 1) % N)
second = max(i, (i + 1) % N)
loop:
think()
wait(fork[first])
wait(fork[second])
eat()
signal(fork[second])
signal(fork[first])
The argument for why this works is worth being able to state precisely: fork N-1 (the highest-numbered fork) is never anyone's first fork to acquire except for the philosopher who owns it as their low fork — there's always at least one philosopher (the one adjacent to the highest-numbered fork) who requests both of their forks in an order that can't be blocked by every other philosopher simultaneously holding one fork each. More generally: a total ordering on resources, with every thread acquiring resources in that order, makes circular wait impossible — this is the general-purpose deadlock-prevention technique, and dining philosophers is just the cleanest place to first prove it to yourself. It generalizes directly to any "thread needs multiple locks" scenario, not just this problem.
Classic fix #2: The asymmetric philosopher
A variant of the same idea without needing to compare indices: make every odd-numbered philosopher pick up their right fork first, then their left, while every even-numbered philosopher picks up left-then-right as originally written. With an odd N (5, as in the classic statement), this also breaks the perfect symmetry that caused the all-pick-up-left-simultaneously deadlock — at least one adjacent pair is now competing for the same fork as their first choice instead of each reaching for a different one, which necessarily means one of them loses the race and blocks before acquiring anything, rather than after acquiring one fork and holding it hostage.
Classic fix #3: The arbitrator / waiter
Introduce a single additional mutex ("the waiter") that a philosopher must acquire before attempting to pick up either fork, and release after acquiring both:
philosopher(i):
loop:
think()
wait(waiter)
wait(fork[i])
wait(fork[(i + 1) % N])
signal(waiter)
eat()
signal(fork[i])
signal(fork[(i + 1) % N])
This serializes the fork-acquisition phase across all philosophers globally, which trivially prevents circular wait (only one philosopher can even be in the acquiring phase at a time) at the cost of destroying most of the concurrency the problem is trying to allow — with a naive single global waiter, only one philosopher can ever be acquiring forks at once, though already-eating philosophers can still eat concurrently once past that phase. It's correct, easy to justify, and it's the fallback answer when you're asked for "the simplest possible fix" rather than the most concurrent one.
Classic fix #4: Limit the room to N−1 diners
Introduce a counting semaphore room initialized to N - 1, and require a philosopher to acquire a permit from room before attempting to pick up any forks (releasing it after eating):
philosopher(i):
loop:
think()
wait(room) # at most N-1 philosophers may be "in the room"
wait(fork[i])
wait(fork[(i + 1) % N])
eat()
signal(fork[i])
signal(fork[(i + 1) % N])
signal(room)
The pigeonhole argument: with only N - 1 of N philosophers ever attempting to acquire forks simultaneously, at least one fork always has no more than one interested philosopher, so someone is always guaranteed to get both their forks and make progress. This is Dijkstra's own original resource-hierarchy-adjacent idea and is a favorite "prove it rigorously" interview follow-up — being able to state the pigeonhole argument out loud (not just "trust me, it works") is what separates a 3-difficulty answer from a 4-difficulty one here.
Deadlock-free is not the same as starvation-free
All four fixes above prevent deadlock. None of them, as stated, guarantee starvation-freedom under an adversarial scheduler — resource ordering and the N-1 room technique both still permit a pathological (if increasingly unlikely) interleaving where one specific philosopher's neighbors keep "cutting in line" indefinitely. A genuinely starvation-free solution needs an explicit fairness mechanism layered on top — e.g. a FIFO ticket per fork, or bounding how many times a neighbor may eat before yielding — which is meaningfully harder to argue rigorously and is where this problem edges into difficulty-5 territory. If you're asked for "the fully general, provably starvation-free solution," flag that it requires strictly more than the four classic fixes above, and sketch the FIFO/ticket idea rather than claiming any of the above already provides it.
Pitfalls and interview gotchas
- Presenting "just add a mutex around everything" as the fix. This is fix #3 above (the arbitrator) — it's a valid answer, but if you present it as the answer without acknowledging it collapses concurrency to nearly nothing, you've missed half the point of the problem, which is about maximizing safe concurrency, not just achieving correctness by any means.
- Confusing deadlock-freedom with starvation-freedom, as covered above — a very common conflation, and interviewers will often probe specifically for whether you know the difference.
- Getting the resource-ordering argument hand-wavy. "Just order the forks" is the right idea, but be ready to explain why a total order prevents circular wait in general (it means there is no fork that is "highest" for every philosopher simultaneously trying to acquire it, so the cycle of hold-and-wait can't close) — this generalizes directly to lock-ordering discipline in real multi-lock code, which is very likely the actual follow-up question.
- Forgetting this is explicitly the topic that owns the textbook problem — if an interviewer follows up with "now implement this as a LeetCode-style callback API" (
wantsToEat, pickLeftFork, etc.), that's the related-but-distinct coding-interview framing covered in this roadmap's Classic Concurrency Interview Patterns topic; the concepts transfer directly, but the API shape is different.