The Dining Philosophers
Problem
Five philosophers sit around a round table; between each pair lies a single fork. To eat, a philosopher needs both adjacent forks. Design a protocol that prevents deadlock when all five attempt to eat concurrently.
n = 5 philosophers, 5 forksno deadlock; each philosopher eats infinitely oftenimport threading
class DiningPhilosophers:
def __init__(self):
self.forks = [threading.Lock() for _ in range(5)]
def wantsToEat(self, p, pick_left, pick_right, eat, put_left, put_right):
left, right = p, (p + 4) % 5
# asymmetric: philosopher 0 grabs right first
first, second = (right, left) if p == 0 else (left, right)
with self.forks[first]:
with self.forks[second]:
pick_left() if first == left else pick_right()
pick_right() if second == right else pick_left()
eat()
put_left() if first == left else put_right()
put_right() if second == right else put_left()class DiningPhilosophers {
constructor() { this.forks = Array.from({ length: 5 }, () => ({ held: false })); }
async wantsToEat(p, pickLeft, pickRight, eat, putLeft, putRight) {
const left = p, right = (p + 4) % 5;
const [first, second] = p === 0 ? [right, left] : [left, right];
await this.acquire(first);
await this.acquire(second);
pickLeft(); pickRight(); eat(); putLeft(); putRight();
this.release(second); this.release(first);
}
}class DiningPhilosophers {
private final ReentrantLock[] forks = new ReentrantLock[5];
public DiningPhilosophers() {
for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
}
public void wantsToEat(int p,
Runnable pickLeft, Runnable pickRight, Runnable eat,
Runnable putLeft, Runnable putRight) throws InterruptedException {
int left = p, right = (p + 4) % 5;
int first = (p == 0) ? right : left;
int second = (p == 0) ? left : right;
forks[first].lock();
forks[second].lock();
pickLeft.run(); pickRight.run(); eat.run(); putLeft.run(); putRight.run();
forks[second].unlock();
forks[first].unlock();
}
}class DiningPhilosophers {
std::mutex forks[5];
public:
void wantsToEat(int p,
function<void()> pickLeft, function<void()> pickRight, function<void()> eat,
function<void()> putLeft, function<void()> putRight) {
int left = p, right = (p + 4) % 5;
int first = (p == 0) ? right : left;
int second = (p == 0) ? left : right;
std::lock_guard<std::mutex> a(forks[first]);
std::lock_guard<std::mutex> b(forks[second]);
pickLeft(); pickRight(); eat(); putLeft(); putRight();
}
};Explanation
Deadlock happens when all five philosophers grab their left fork first at the same moment — now everyone holds one fork and waits forever for the right one. The fix is to break the symmetry so this perfect circle of waiting can never close.
Each fork is a lock. Normally a philosopher locks left then right. But for one chosen philosopher (here p == 0) we reverse the order to right then left via first, second = (right, left).
With one philosopher picking up forks in the opposite order, there's always at least one fork that two neighbors compete for in a way that lets one win outright. That broken link means no cyclic chain of "everyone waits on everyone" can form, so the system is deadlock-free.
The locks also guarantee a fork is held by only one philosopher at a time, and releasing both after eating lets neighbors proceed.
Example: philosopher 1 takes its left then right and eats; meanwhile philosopher 0, by reaching for its right fork first, can't join a stalemate, so eventually everyone gets to eat.