//
Proposed by Edsger Dijkstra in 1965, the Dining Philosophers Problem is a classic illustration of the challenges of deadlock, starvation, and mutual exclusion in concurrent systems.
Five philosophers sit around a circular table. Between each pair of adjacent philosophers lies a single chopstick (5 total). A philosopher alternates between thinking and eating. To eat, a philosopher must pick up BOTH the chopstick to their left AND the chopstick to their right. After eating, they put both chopsticks down and resume thinking.
If every philosopher simultaneously picks up their left chopstick, all five chopsticks are taken. Now every philosopher waits for their right chopstick, which is held by the philosopher to their right. No philosopher can eat. No philosopher will put down their left chopstick (they're waiting for the right one). Deadlock!
Number the chopsticks 0 through 4. Every philosopher always picks up the lower-numbered chopstick first, then the higher-numbered one.
Allow at most 4 philosophers (out of 5) to attempt eating simultaneously. Use a counting semaphore initialized to 4. This guarantees that at least one philosopher can always acquire both chopsticks.
Use a monitor where each philosopher checks if BOTH chopsticks are available before picking up either one. If both are available, pick up both atomically. If not, wait on a condition variable.
Even without deadlock, Starvation can occur. A philosopher might always find one of their chopsticks taken by a fast-eating neighbor and never get to eat. Solutions must ensure fairness so every philosopher eventually gets to eat.
The Dining Philosophers problem models any scenario where multiple processes compete for a limited set of shared resources. Database systems with multiple transactions competing for row locks, or multi-threaded applications sharing files, face exactly this problem.