LeetCode 1226 - The Dining Philosophers
This problem asks us to implement a concurrent synchronization mechanism for the classic Dining Philosophers problem. We have five philosophers sitting around a circular table, and between every pair of neighboring philosophers lies a single fork.
Difficulty: 🟡 Medium
Topics: Concurrency
Solution
Problem Understanding
This problem asks us to implement a concurrent synchronization mechanism for the classic Dining Philosophers problem. We have five philosophers sitting around a circular table, and between every pair of neighboring philosophers lies a single fork. To eat, a philosopher must acquire both their left and right forks. Since forks are shared resources, two neighboring philosophers cannot use the same fork simultaneously.
The challenge is not simply to allow philosophers to eat, but to design a correct synchronization discipline that avoids common concurrency failures such as deadlock and starvation.
A deadlock occurs when every philosopher picks up one fork and waits forever for the second fork. For example, if all philosophers simultaneously pick up their left fork, no philosopher can acquire their right fork, causing the system to freeze permanently.
Starvation occurs when one philosopher is indefinitely prevented from eating because neighboring philosophers repeatedly obtain forks first.
The method we must implement is:
wantsToEat(
philosopher,
pickLeftFork,
pickRightFork,
eat,
putLeftFork,
putRightFork
)
The philosopher parameter identifies which philosopher wants to eat, numbered from 0 to 4 in clockwise order.
The callback functions represent actions:
pickLeftFork()picks up the philosopher's left fork.pickRightFork()picks up the philosopher's right fork.eat()allows the philosopher to eat.putLeftFork()releases the left fork.putRightFork()releases the right fork.
The expected output is implicit. We are not returning values. Instead, the correctness of the solution is determined by whether the actions occur in a valid order under concurrent execution.
The constraints are relatively small:
1 <= n <= 60
However, the difficulty does not come from input size. This is a concurrency problem, meaning correctness depends on synchronization rather than algorithmic scaling. Even with only five philosophers, naive implementations can easily deadlock.
An important detail is that the same philosopher's wantsToEat() method may be called again before the previous call finishes. This means we cannot assume sequential execution per philosopher, and our synchronization must be thread safe.
Several edge cases matter:
A naive solution where every philosopher picks up the left fork first can deadlock immediately if all five philosophers act simultaneously.
Multiple requests from the same philosopher may overlap, meaning fork access must remain safe even for repeated calls.
Heavy contention can happen when all philosophers repeatedly try to eat simultaneously. A correct solution must still guarantee progress.
The problem guarantees exactly five philosophers and valid philosopher IDs from 0 to 4.
Approaches
Brute Force Approach
A naive implementation would simply let each philosopher pick up their left fork first, then their right fork.
In this design, each fork is represented by a mutex. When a philosopher wants to eat, they lock the left fork mutex, then lock the right fork mutex, eat, and finally release both forks.
This appears correct because mutual exclusion is enforced, meaning no two philosophers can hold the same fork simultaneously.
However, this approach suffers from deadlock.
Imagine all five philosophers executing simultaneously:
- Philosopher 0 picks left fork.
- Philosopher 1 picks left fork.
- Philosopher 2 picks left fork.
- Philosopher 3 picks left fork.
- Philosopher 4 picks left fork.
Now every philosopher waits forever for the right fork, which is already held by a neighbor. Since nobody can progress, the system deadlocks permanently.
Although the implementation is simple, it is fundamentally unsafe for concurrent execution.
Optimal Approach
The key observation is that deadlock happens because all philosophers may attempt to acquire forks in the same order simultaneously, creating a circular dependency.
To prevent deadlock, we must break the cycle.
A standard and elegant solution is to use a global semaphore (or mutex limit) that allows at most four philosophers to compete for forks at the same time.
Since only four philosophers can attempt to eat simultaneously, at least one philosopher will always remain thinking. This guarantees at least one pair of forks remains available, preventing circular waiting and ensuring progress.
We still use a mutex for each fork to preserve exclusive access. The semaphore only limits contention.
The process becomes:
- Acquire permission from the semaphore.
- Lock the left fork.
- Lock the right fork.
- Eat.
- Release both forks.
- Release semaphore permission.
This avoids deadlock while maintaining correctness.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(1) | O(1) | Simple fork locking, but can deadlock |
| Optimal | O(1) | O(1) | Uses fork locks plus admission control to prevent deadlock |
Algorithm Walkthrough
Optimal Algorithm
- Create five mutexes, one for each fork.
Since forks are shared resources, only one philosopher may hold a fork at a time. A mutex is the natural synchronization primitive for exclusive ownership.
2. Create a semaphore with capacity 4.
The semaphore acts as a gatekeeper. At most four philosophers are allowed to attempt eating simultaneously. This prevents the circular wait condition that causes deadlock. 3. When a philosopher wants to eat, first acquire the semaphore.
If four philosophers are already competing for forks, the philosopher waits. This ensures one philosopher always remains outside the competition. 4. Determine fork indices.
For philosopher p:
- Left fork =
p - Right fork =
(p + 1) % 5
Since philosophers sit in a circle, modulo arithmetic naturally wraps around. 5. Lock the left fork mutex.
Once acquired, invoke pickLeftFork().
6. Lock the right fork mutex.
After acquiring it, invoke pickRightFork().
7. Execute eat().
Since both forks are guaranteed to be held exclusively, the philosopher can safely eat. 8. Release forks in reverse order.
Invoke putRightFork(), unlock the right fork, then invoke putLeftFork(), unlock the left fork.
9. Release semaphore access.
Another philosopher may now attempt to eat.
Why it works
The critical invariant is that at most four philosophers can compete for forks simultaneously.
Deadlock requires a circular waiting chain involving all five philosophers. By preventing all five from entering the fork acquisition phase at once, we eliminate the possibility of a full circular dependency.
Fork mutexes guarantee exclusive access, while the semaphore guarantees progress. Therefore, philosophers can continue alternating between eating and thinking indefinitely without deadlock.
Python Solution
from threading import Lock, Semaphore
from typing import Callable
class DiningPhilosophers:
def __init__(self):
self.forks = [Lock() for _ in range(5)]
self.semaphore = Semaphore(4)
def wantsToEat(
self,
philosopher: int,
pickLeftFork: 'Callable[[], None]',
pickRightFork: 'Callable[[], None]',
eat: 'Callable[[], None]',
putLeftFork: 'Callable[[], None]',
putRightFork: 'Callable[[], None]'
) -> None:
left_fork = philosopher
right_fork = (philosopher + 1) % 5
self.semaphore.acquire()
self.forks[left_fork].acquire()
pickLeftFork()
self.forks[right_fork].acquire()
pickRightFork()
eat()
putRightFork()
self.forks[right_fork].release()
putLeftFork()
self.forks[left_fork].release()
self.semaphore.release()
The implementation starts by initializing five locks, one for each fork. Since forks are shared resources, mutual exclusion is necessary to avoid multiple philosophers using the same fork simultaneously.
A semaphore of size four is also created. This is the crucial deadlock prevention mechanism.
Inside wantsToEat(), we compute fork indices using the philosopher ID. The philosopher first obtains permission from the semaphore before attempting to lock forks.
Once access is granted, the philosopher locks the left fork, executes pickLeftFork(), then locks the right fork and executes pickRightFork().
Only after both forks are secured can eat() be called.
Finally, the philosopher puts down the right fork and left fork, releasing their locks. The semaphore slot is also released, allowing another philosopher to enter.
The ordering ensures exclusive fork access and prevents deadlock.
Go Solution
package main
import "sync"
type DiningPhilosophers struct {
forks [5]sync.Mutex
limit chan struct{}
}
func Constructor() DiningPhilosophers {
return DiningPhilosophers{
limit: make(chan struct{}, 4),
}
}
func (this *DiningPhilosophers) wantsToEat(
philosopher int,
pickLeftFork func(),
pickRightFork func(),
eat func(),
putLeftFork func(),
putRightFork func(),
) {
leftFork := philosopher
rightFork := (philosopher + 1) % 5
this.limit <- struct{}{}
this.forks[leftFork].Lock()
pickLeftFork()
this.forks[rightFork].Lock()
pickRightFork()
eat()
putRightFork()
this.forks[rightFork].Unlock()
putLeftFork()
this.forks[leftFork].Unlock()
<-this.limit
}
The Go implementation follows the same design as the Python version but uses Go concurrency primitives.
Instead of a semaphore object, Go uses a buffered channel with capacity 4. Sending into the channel acquires permission, while receiving releases it.
Forks are implemented using sync.Mutex.
Unlike Python, Go requires explicit struct initialization. The Constructor() method initializes the channel.
There are no concerns about integer overflow because philosopher IDs are limited to 0 through 4.
Worked Examples
Example 1
Input:
n = 1
Suppose philosophers attempt to eat in order 0, 1, 2, 3, 4.
Initial state:
| Resource | State |
|---|---|
| Semaphore | 4 slots available |
| Forks | All unlocked |
Step 1: Philosopher 0
- Acquires semaphore.
- Locks fork
0. - Locks fork
1. - Eats.
- Releases forks.
| Fork | Owner |
|---|---|
| 0 | Philosopher 0 |
| 1 | Philosopher 0 |
| 2 | Free |
| 3 | Free |
| 4 | Free |
Step 2: Philosopher 1
Philosopher 1 needs forks 1 and 2.
If philosopher 0 already released fork 1, philosopher 1 proceeds immediately.
| Fork | Owner |
|---|---|
| 0 | Free |
| 1 | Philosopher 1 |
| 2 | Philosopher 1 |
| 3 | Free |
| 4 | Free |
Step 3: Remaining Philosophers
Philosophers 2, 3, and 4 proceed similarly.
At no point can all five philosophers become blocked simultaneously because the semaphore restricts concurrency to four active contenders.
Therefore, deadlock never occurs.
The exact execution order in the output may differ because thread scheduling is nondeterministic.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(1) | Each philosopher performs a constant number of lock and unlock operations |
| Space | O(1) | Only five fork locks and one semaphore are stored |
The time complexity is constant because the number of philosophers is fixed at five. Regardless of how many times wantsToEat() is called, each invocation performs only a fixed number of synchronization operations.
The space complexity is also constant because we store exactly five locks and one semaphore, independent of input size.
Test Cases
from threading import Thread
def test_dining_philosophers():
dp = DiningPhilosophers()
results = []
def create_callbacks(philosopher):
return (
lambda: results.append((philosopher, "pick_left")),
lambda: results.append((philosopher, "pick_right")),
lambda: results.append((philosopher, "eat")),
lambda: results.append((philosopher, "put_left")),
lambda: results.append((philosopher, "put_right")),
)
# Test 1: Single philosopher request
callbacks = create_callbacks(0)
dp.wantsToEat(0, *callbacks)
assert ("eat" in [x[1] for x in results]) # basic execution
results.clear()
# Test 2: All philosophers eat once concurrently
threads = []
for i in range(5):
callbacks = create_callbacks(i)
thread = Thread(
target=dp.wantsToEat,
args=(i, *callbacks)
)
threads.append(thread)
thread.start()
for thread in threads:
thread.join(timeout=2)
assert len(results) > 0 # ensures no deadlock
results.clear()
# Test 3: Repeated requests from same philosopher
threads = []
for _ in range(10):
callbacks = create_callbacks(0)
thread = Thread(
target=dp.wantsToEat,
args=(0, *callbacks)
)
threads.append(thread)
thread.start()
for thread in threads:
thread.join(timeout=2)
assert results.count((0, "eat")) == 10 # repeated calls
results.clear()
# Test 4: Stress concurrency
threads = []
for _ in range(20):
for philosopher in range(5):
callbacks = create_callbacks(philosopher)
thread = Thread(
target=dp.wantsToEat,
args=(philosopher, *callbacks)
)
threads.append(thread)
thread.start()
for thread in threads:
thread.join(timeout=5)
eat_count = sum(
1 for action in results if action[1] == "eat"
)
assert eat_count == 100 # high contention stress
| Test | Why |
|---|---|
| Single philosopher request | Validates baseline execution |
| All philosophers concurrent | Ensures deadlock prevention |
| Repeated same philosopher | Verifies overlapping calls are safe |
| High contention stress | Confirms robustness under concurrency |
Edge Cases
One important edge case is when all five philosophers attempt to eat simultaneously. This is the classic deadlock scenario for naive solutions. Without coordination, every philosopher could pick up one fork and wait forever. The semaphore prevents this because only four philosophers may compete at once, ensuring at least one philosopher can always complete eating and release resources.
Another important case is multiple overlapping requests from the same philosopher. The problem explicitly allows wantsToEat() to be called again for the same philosopher before the previous invocation finishes. A buggy implementation might assume philosophers execute sequentially. Since fork access is protected using mutexes, overlapping calls remain safe and properly synchronized.
A third edge case is maximum contention with repeated eating requests. Since n can be as high as 60, threads may repeatedly compete for forks. The implementation handles this correctly because every operation is protected through locking and admission control, preventing deadlock while maintaining safe resource sharing.
A final subtle case involves philosopher 4, whose right fork wraps around to fork 0. Incorrect index calculations could cause out-of-range access or incorrect fork ownership. Using:
(philosopher + 1) % 5
correctly models the circular table structure and ensures philosopher 4 shares a fork with philosopher 0.