Why Do Philosophers Keep Getting Hungry?
The Dining Philosophers Problem is a classic computer science thought experiment that illustrates common concurrency challenges. Five philosophers sit at a round table. Each philosopher alternates between thinking and eating. Between each pair of philosophers lies a single fork. A philosopher needs both forks to eat.
If every philosopher picks up the left fork at the same time, no one can pick up the right fork. Everyone starves. This is a deadlock.
Key sources: "Concurrency in Go" by Katherine Cox-Buday, Dijkstra's original paper (1965), and "Operating Systems: Three Easy Pieces" by Remzi and Andrea Arpaci-Dusseau.
The Core Problem
The setup is simple: - 5 philosophers - 5 forks (one between each pair) - Each philosopher needs 2 forks to eat - Each philosopher picks up the left fork, then the right fork
The naive solution creates deadlock. All five philosophers pick up their left fork simultaneously. No one can pick up the right fork. Everyone holds one fork and waits forever.
Philosopher 0: picks up fork 0, waits for fork 1
Philosopher 1: picks up fork 1, waits for fork 2
Philosopher 2: picks up fork 2, waits for fork 3
Philosopher 3: picks up fork 3, waits for fork 4
Philosopher 4: picks up fork 4, waits for fork 0
Circular wait. Deadlock.
Solutions
Solution 1: Global Mutex
Protect all forks with a single mutex. Only one philosopher eats at a time. Simple but limits concurrency.
Solution 2: Resource Hierarchy
Number the forks 0 through 4. Each philosopher picks up the lower-numbered fork first. This breaks the circular wait condition because philosopher 4 picks up fork 0 first instead of fork 4.
Solution 3: Limit Philosophers
Allow at most 4 philosophers at the table. With 4 philosophers and 5 forks, at least one philosopher can always get both forks. No deadlock.
Solution 4: TryLock
If a philosopher cannot pick up the second fork within a timeout, put down the first fork and try again later. This avoids deadlock but can cause livelock if everyone keeps trying simultaneously.
Real-World Applications
This problem appears in real systems:
- Database deadlocks: Transaction A holds lock on row 1 and waits for row 2. Transaction B holds lock on row 2 and waits for row 1.
- Resource allocation: Multiple processes competing for limited resources.
- Network protocols: Two devices waiting for each other to send a signal.
Key Takeaways
- Deadlock requires four conditions: mutual exclusion, hold and wait, no preemption, and circular wait.
- Breaking any one condition prevents deadlock.
- The Dining Philosophers Problem teaches resource allocation in concurrent systems.
- Real-world deadlocks happen in databases, file systems, and network protocols.
Rule of thumb: When multiple resources are involved in concurrent systems, always acquire them in the same order.