Definition
Dining Philosophers Problem
The dining philosophers problem is a classic synchronisation exercise illustrating challenges in avoiding deadlock and starvation.
Five philosophers sit around a circular table. Between each pair sits a single fork. To eat, a philosopher must acquire two adjacent forks.
Problems
Deadlock
If every philosopher picks up their left fork simultaneously, no right fork is available. All wait indefinitely.
Starvation
A philosopher may never eat if neighbours alternate such that at least one fork is always held.
Solutions
Limit Concurrency
Allow at most four philosophers simultaneously using a counting semaphore (init to 4). At least one philosopher can always acquire two forks.
Asymmetric Acquisition
Odd philosophers pick up left fork first; even philosophers pick up right fork first. Breaks circular wait.
Atomic Multiple Acquisition
Use M-Semaphores to acquire both forks atomically.
wait(S1, S2)proceeds only if both are available; otherwise block without releasing any.
Monitor Solution
monitor DiningPhilosophers
enum State { THINKING, HUNGRY, EATING }
State state[5]
condition self[5]
Void pickup(int i)
state[i] = HUNGRY
test(i)
if (state[i] != EATING)
self[i].wait()
Void putdown(int i)
state[i] = THINKING
test((i + 4) % 5) // left neighbour
test((i + 1) % 5) // right neighbour
Void test(int i)
if (state[(i + 4) % 5] != EATING &&
state[i] == HUNGRY &&
state[(i + 1) % 5] != EATING) {
state[i] = EATING
self[i].signal()
}