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.
In this approach, we use a hierarchy for acquiring locks to avoid deadlock. By choosing an order in which the locks (forks) are acquired, we ensure that no circular wait occurs, thus preventing deadlock.
To implement this, a philosopher will first pick the fork with the lower index (among their left and right forks) before picking the one with the higher index. This breaks the circular dependency, allowing a safe locking mechanism.
This solution uses C's pthread library to handle concurrency with mutex locks. Each philosopher is represented by a separate thread. By locking the forks in a specific order determined by their index, the solution ensures that deadlock is avoided. The picking of forks and eating actions are simulated through function pointers provided to the wantsToEat function. After eating, the forks are released in reverse order of locking.
Time Complexity: O(1) for each pick and release operation since they handle constant locks.
Space Complexity: O(1) for storing the mutexes.
This approach relies on introducing asymmetry among philosophers. Instead of using a singular, uniform strategy for all philosophers to pick up the fork, we introduce a slight alteration in behavior. Specifically, we let some philosophers pick up the left fork first and others pick up the right fork first. This ensures that two neighboring philosophers don’t deadlock by waiting on each other's fork.
This approach adjusts the method by which philosophers grab the forks to further reduce potential conflict, leveraging the asymmetry to ensure progress without deadlock.
This C implementation uses an asymmetric approach where philosophers with an even index pick up their left fork first, while those with an odd index pick up their right fork first. The alternating pattern ensures no two neighbors are waiting indefinitely for each other's fork.
Time Complexity: O(1) due to constant mutex operations for each eating attempt.
Space Complexity: O(1), as each philosopher only handles fixed data and a set number of mutexes.
C++
| Approach | Complexity |
|---|---|
| Approach 1: Using Locks with a Fork Hierarchy | Time Complexity: O(1) for each pick and release operation since they handle constant locks. |
| Approach 2: Asymmetric Philosophers | Time Complexity: O(1) due to constant mutex operations for each eating attempt. |
| Default Approach | — |
| 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. |
LeetCode 1226 - The Dining Philosophers • Light Of Truth • 4,286 views views
Watch 4 more video solutions →Practice The Dining Philosophers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor