The Deadlock Dinner
The Deadlock Dinner
Can you spot who'll starve before they ever eat?
In the last post we talked about RAII — and how a mutex that never gets unlocked can freeze an entire multithreaded system into silence. But that story assumed the bug was accidental: a forgotten unlock on an early return path.
Today's puzzle is about something more insidious. A deadlock that happens even when every programmer did exactly what they were supposed to. Every thread locks a mutex. Every thread eventually unlocks it. The code looks correct. And yet, the system still seizes.
To see why, we go to dinner.
The Setup
Edsger Dijkstra's Dining Philosophers is one of the most famous thought experiments in computer science. Five philosophers sit at a round table. Between each adjacent pair of philosophers lies a single fork. A philosopher needs both the fork to their left and the fork to their right in order to eat. When they're not eating, they're thinking.
Now here's the rule that every philosopher follows — perfectly, every time:
- Pick up the left fork first.
- Then pick up the right fork.
- Eat.
- Put down both forks.
Sounds reasonable. Now imagine all five philosophers get hungry at exactly the same moment. Each one reaches left and picks up their fork. Now each philosopher holds one fork and is waiting for the fork to their right — which the philosopher to their right is already holding.
Nobody eats. Nobody ever will. Classic deadlock.
The Resource Allocation Graph
Computer scientists visualise deadlock with a Resource Allocation Graph (RAG). The idea is simple:
- Circles represent threads / processes (the philosophers).
- Rectangles represent resources (the forks, mutexes, file handles).
- An arrow from a thread to a resource means "this thread is waiting for this resource."
- An arrow from a resource to a thread means "this resource is currently held by this thread."
The killer insight: if you can find a cycle in this graph, you have a deadlock. No cycle, no deadlock. It's that clean.
Now, the puzzle.
The Puzzle — Three Scenarios
Below are three different table configurations — three different ways the philosophers have grabbed forks. Study the resource allocation graph for each scenario and decide: is this a deadlock, a safe state, or something in between? Then click your answer and see if you were right.
All five philosophers became hungry simultaneously and each grabbed the fork to their left. Now each holds one fork and waits for the one on their right. Study the graph — does a cycle exist?
P1 holds F1 and F5 and is eating. P2 holds F2 and is waiting for F1. P3, P4, P5 are still thinking — they haven't touched any forks yet. Is the system safe?
P1 holds F5 and waits for F1. P2 holds F1 and waits for F2. P3 holds F2 and waits for F5. Meanwhile P4 is eating (holds F3 and F4), and P5 is still thinking. How many philosophers are deadlocked?
Breaking the Deadlock
The puzzle reveals a key insight: a deadlock requires all four Coffman conditions to hold at once. Break any one and it evaporates. Here's how each solution maps to a real C++ pattern:
| Strategy | Condition broken | Real C++ mechanism |
|---|---|---|
| Resource hierarchy | Circular wait | Always lock mutexes in the same global order. std::scoped_lock does this automatically. |
| Try-and-back-off | Hold and wait | std::try_lock() — if you can't get both, release the one you hold and retry. |
| Timeout | No preemption | std::unique_lock with try_lock_for(). After a deadline, give up and retry. |
| Asymmetric philosopher | Circular wait | One thread grabs forks right-then-left. Classic textbook fix for the dining philosophers specifically. |
The scoped_lock Solution
In the real RAII world, the cleanest answer to the lock-ordering problem is std::scoped_lock, introduced in C++17. Pass it multiple mutexes and it locks them all atomically using a deadlock-avoidance algorithm — no matter what order you call it in different threads, you won't deadlock.
// Dangerous — lock order can differ between threads
std::mutex fork_left, fork_right;
void eat_unsafe() {
fork_left.lock(); // Thread A grabs left
fork_right.lock(); // Thread B may grab right first → deadlock
// ... eat ...
fork_right.unlock();
fork_left.unlock();
}
// Safe — scoped_lock uses deadlock-avoidance internally
void eat_safe() {
std::scoped_lock lk(fork_left, fork_right); // both or neither
// ... eat ...
} // both forks released here. always.
Notice: scoped_lock is RAII. The two concepts aren't separate tools — they're the same tool. RAII is what gives scoped_lock its guarantee, and the deadlock-avoidance algorithm is what makes locking multiple mutexes safe. The dining philosophers' problem is solved by combining both.
What Makes a Cycle Dangerous?
Scenario C in the puzzle is the sneakiest. P4 is eating happily, P5 is thinking peacefully — only P1, P2, and P3 are stuck. A partial deadlock is still a deadlock. The system as a whole will not progress normally, because whenever P4 eventually finishes and puts down F3 and F4, and P5 wakes up and tries to eat — they may complete their work, but P1, P2, and P3 are never going to get F1, F2, and F5. They will wait forever, even while the rest of the system continues.
This is exactly the kind of bug that survives unit tests and staging environments. Under low load, maybe P2 always releases F1 before P3 even gets hungry. Under production load with 48 threads hammering the subsystem, you hit the cycle. The logs go quiet. The system still responds to heartbeats. Only one subsystem is frozen — the one nobody checks on a Friday night.
std::scoped_lock, and let the compiler guarantee the answer for you.
The philosophers at our dinner table never solved the problem by trying harder. They solved it by changing the protocol. That's the lesson that outlasts the puzzle.
Did you get all three scenarios right? Drop your score in the comments. And if you've encountered a partial deadlock in production that looked suspiciously like Scenario C, I'd love to hear the story.
Coming up next: can you topologically sort this dependency graph? Another visual puzzle — this time with a build system that has a hidden cycle baked in.
Comments
Post a Comment