Watch 5 video solutions for The Dining Philosophers, a medium level problem involving Concurrency. This walkthrough by Light Of Truth has 4,286 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.
Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.
Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.
Design a discipline of behaviour (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.
The problem statement and the image above are taken from wikipedia.org
The philosophers' ids are numbered from 0 to 4 in a clockwise order. Implement the function void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) where:
philosopher is the id of the philosopher who wants to eat.pickLeftFork and pickRightFork are functions you can call to pick the corresponding forks of that philosopher.eat is a function you can call to let the philosopher eat once he has picked both forks.putLeftFork and putRightFork are functions you can call to put down the corresponding forks of that philosopher.Five threads, each representing a philosopher, will simultaneously use one object of your class to simulate the process. The function may be called for the same philosopher more than once, even before the last call ends.
Example 1:
Input: n = 1
Output: [[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
Explanation:
n is the number of times each philosopher will call the function.
The output array describes the calls you made to the functions controlling the forks and the eat function, its format is:
output[i] = [a, b, c] (three integers)
- a is the id of a philosopher.
- b specifies the fork: {1 : left, 2 : right}.
- c specifies the operation: {1 : pick, 2 : put, 3 : eat}.
Constraints:
1 <= n <= 60Problem Overview: Five philosophers sit around a circular table with one fork between each pair. A philosopher must pick up both left and right forks before eating. Multiple threads run concurrently, so the challenge is coordinating fork access without causing deadlock or starvation.
Approach 1: Using Locks with a Fork Hierarchy (O(1) time per operation, O(n) space)
Represent each fork as a mutex or lock. Philosophers must acquire the two fork locks before eating and release them afterward. The deadlock problem appears when every philosopher picks up their left fork simultaneously and waits for the right fork. A fork hierarchy prevents this by enforcing a strict order: always lock the lower-numbered fork first, then the higher-numbered one. This removes circular wait, which is a required condition for deadlock. Each eating attempt performs constant-time lock and unlock operations, so the runtime per action is O(1), while storing fork locks requires O(n) space for n forks. This approach relies on classic concurrency control using locks to guarantee safe resource access.
Approach 2: Asymmetric Philosophers (O(1) time per operation, O(n) space)
Break the symmetry in how philosophers acquire forks. Instead of everyone picking the same fork first, alternate the order: even-numbered philosophers pick up the left fork first, while odd-numbered philosophers pick up the right fork first. Because not all threads compete for the same resource order, the circular dependency disappears. Deadlock becomes impossible while still allowing parallel eating whenever forks are available. Each philosopher performs a constant number of lock acquisitions and releases, so the operational cost remains O(1) with O(n) space for fork locks. This strategy is widely used in systems programming to prevent synchronization issues without introducing complex coordination logic.
Recommended for interviews: The fork hierarchy approach is the safest explanation during interviews because it directly addresses the deadlock condition using a deterministic ordering rule. Interviewers expect you to mention the four deadlock conditions and show how ordering removes circular wait. The asymmetric strategy is also valid and demonstrates deeper understanding of concurrency design trade‑offs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Locks with Fork Hierarchy | O(1) per operation | O(n) | Best general solution. Prevents deadlock by enforcing a global lock order. |
| Asymmetric Philosophers | O(1) per operation | O(n) | Good when you want a simple deadlock prevention technique without ordering all resources. |