The Dining Philosophers Problem

The Dining Philosophers Problem

The dining philosophers problem is a famous illustration of resource contention. Five philosophers sit around a table with one fork between each neighboring pair. A philosopher needs both the left and right fork to eat, then puts them down to think.

The naive solution has every philosopher pick up the left fork, then the right. This deadlocks. If all five grab their left fork at once, every philosopher holds one fork and waits forever for the right fork that a neighbor holds. This is a perfect circular wait.

Several fixes break the deadlock:

• Resource ordering Number the forks and always pick up the lower numbered fork first. This breaks the circular wait because someone must reach for a fork others already hold.
• An arbitrator A waiter or central authority grants permission to pick up forks, never allowing all five to hold one.
• Limit diners Allow at most four philosophers to sit and reach at once, so at least one pair of forks is always free.
• Try and back off Pick up one fork, and if the other is unavailable, release the first and retry, though this risks livelock or starvation.

The problem cleanly separates two failure modes. Deadlock is everyone stuck forever, while starvation is one philosopher who keeps losing the race and never eats even though others make progress. A good solution avoids both.

Key idea

Forcing a global order on shared resources breaks the circular wait that causes the dining philosophers to deadlock, while extra care is still needed to prevent starvation.