Part 4 of 7 · 3 min read
Philosophers
In plain words: Five philosophers sit at a round table. Between each pair of neighbours lies one fork, five forks in all. A philosopher thinks, then becomes hungry and needs both the left fork and the right fork to eat. When done, the philosopher puts both down. Neighbours share a fork, so two neighbours cannot eat at the same time. The analogy stops in one place: the philosophers do not talk, and the threads are not allowed to either.
Dijkstra posed this dining philosophers problem in 1965. Each philosopher is a thread, each fork is a mutex, and "eating" is the use of two shared resources together. A solution must let the philosophers eat, never get all stuck (no deadlock), and not let one starve.
The natural program is:
pthread_mutex_lock(&fork[left]); /* pick up the left fork */
pthread_mutex_lock(&fork[right]); /* then the right fork */
eat();
pthread_mutex_unlock(&fork[right]);
pthread_mutex_unlock(&fork[left]);
It looks right, and it can deadlock. If all five philosophers become hungry and each picks up the left fork at the same time, every fork is taken, and each philosopher waits for the right fork, which is the left fork of the neighbour, who holds it and waits for the next. Nobody can eat or let go.
| Step | P0 | P1 | P2 | P3 | P4 |
|---|---|---|---|---|---|
| 1 | takes fork 0 | takes fork 1 | takes fork 2 | takes fork 3 | takes fork 4 |
| 2 | wants fork 1 (held by P1) | wants fork 2 | wants fork 3 | wants fork 4 | wants fork 0 (held by P0) |
| Result | waits | waits | waits | waits | waits for ever |
The program was run with a 1 ms pause between the two pick-ups, to make the unlucky timing likely:
everyone takes the left fork first: 0 meals in 2 s, 0 more in the next second (STUCK)
It stuck at once, in both runs, and made no meals. With no pause, it would work for a long time and then hang one day, which is worse: the bug appears under load.
Behind the problem there is a general pattern: threads that each hold one resource and wait for another that is held by the next thread in a circle. Level 5 names the four conditions that must all hold for a deadlock, and shows how to break them.
Dining philosophers problem
The dining philosophers problem is a synchronisation problem in which five threads sit round a table with one shared resource, a fork, between each neighbouring pair, each thread needs both neighbouring forks to proceed, and the task is to share them without deadlock or starvation.
Example: if every philosopher picks up the left fork first and waits for the right one, all five wait for ever.
Check yourself: 1. Why can two neighbours not eat together? 2. Draw the wait-for circle in the stuck state. 3. Why is a pause between the two pick-ups useful in a test?