the dining philosophers problem
/ Dijkstra -> DYKE-struh /
Five philosophers sit around a round table. Between each pair of neighbors lies a single chopstick — five chopsticks for five philosophers. A philosopher only ever thinks or eats, and to eat a bowl of noodles they need both the chopstick on their left and the one on their right. The trouble is that each chopstick is shared with a neighbor, so two adjacent philosophers can never eat at the same time. This little dinner party, posed by Edsger Dijkstra in 1965, is the most famous illustration in all of computing of how a group sharing limited resources can grind to a halt.
Here is the disaster. Suppose every philosopher follows the same simple rule: pick up the left chopstick, then pick up the right one. Now imagine all five get hungry at the exact same moment. Each one picks up their left chopstick — and now every chopstick on the table is held. Each philosopher is waiting for their right chopstick, which is the left one of their neighbor, who will never put it down because they too are waiting. Nobody can eat, nobody will let go, and they all sit there forever. That is deadlock, and the four conditions for it are all present: each chopstick is exclusively held (mutual exclusion), each philosopher holds one while waiting for another (hold-and-wait), nobody can be forced to drop a chopstick (no preemption), and the wait forms a perfect circle around the table (circular wait).
The cures are the lessons, and each one breaks a different condition. Resource ordering: number the chopsticks and require everyone to pick up the lower-numbered one first — now one philosopher reaches for the same chopstick first as their neighbor, the circle is broken, and deadlock cannot form. An arbitrator (a waiter): a philosopher must ask the waiter's permission before picking up any chopstick, and the waiter simply never lets all five grab at once. Limited seating: allow at most four philosophers at the table at a time, so at least one chopstick is always free. Each is a real, transferable technique for keeping concurrent code from locking up.
Resource-ordering fix: number chopsticks 0–4. Philosopher i normally takes chopstick i then i+1, but philosopher 4 (between chopstick 4 and chopstick 0) must take chopstick 0 first. Now not everyone can grab their left stick simultaneously, so the cycle never closes.
Breaking circular wait by imposing a global order on resource acquisition — the most widely used deadlock-prevention trick.
The naive 'just pick up both at once' or random-retry fixes can replace deadlock with livelock: all five repeatedly grab a stick, see they can't get the second, put it back, and try again in perfect lockstep — busy forever, eating never.