The problem

Five philosophers sit at a round table. Between each pair lies one fork, so there are as many forks as philosophers. A philosopher alternates between thinking and eating, and to eat it needs both forks next to it: the one on its left and the one on its right. Dijkstra posed the problem in 1965 as an exam exercise (with computers and tape drives); Hoare gave it the philosophers. The question is how each philosopher should pick up its forks so that nobody gets stuck and everyone gets to eat.

Round table with philosophers P0 to P4 numbered counter-clockwise and forks F0 to F4 between them. Pi's left fork is Fi and its right fork is F(i+1) mod 5, so P0 needs F0 and F1 and P4 needs F4 and F0.
Each fork lies between two philosophers, and each philosopher needs both of its forks to eat.

It is the standard model for any operation that needs several locks at once: a bank transfer locks two accounts, a database transaction locks several rows, a kernel function takes a lock on a directory and one on a file. Whatever goes wrong at the table goes wrong there.

How to use the animation

Philosopher Pi's left fork is Fi and its right fork is F(i+1) (mod N); the column next to the listing shows what left, right, low and high mean for each philosopher. The philosophers are numbered counter-clockwise, so each one's left fork really is on its left hand. Every philosopher runs the listing in an endless loop, and a coloured marker shows the line it will run next. Every step runs exactly one line, atomically. Step a philosopher by hand, or let the round-robin or random scheduler choose. A fork takes the colour of the philosopher holding it and slides towards it. A blocked philosopher stays in its seat, turns red and says what it waits for; an arrow from it to the holder of that fork means waits for. The arrows are grey, and turn red when they close a cycle. The panel under the table re-checks the four conditions for deadlock after every step, and the table at the bottom counts each philosopher's meals and how long it has been hungry.

The naive program deadlocks

philosopher i:
    think()
    lock(left)      // fork i
    lock(right)     // fork i+1
    eat()
    unlock(right)
    unlock(left)

Each philosopher takes its left fork and then its right one. Most schedules work, but if all of them take their left fork before any takes a right one, every right fork is already somebody's left fork: P0 waits for P1, P1 for P2, …, P4 for P0, and nobody will ever let go. Run Naive tab, Demo: deadlock: round-robin reaches this state at step 15, and the wait-for arrows form the red cycle P0 → P1 → P2 → P3 → P4 → P0. Demo: lucky schedule runs the same program without trouble. That is what makes deadlocks hard to find: a test can pass a thousand times.

The four conditions (Coffman, 1971)

A deadlock can happen only if all four of these hold at once:

  1. Mutual exclusion. A resource is held by one thread at a time. A fork cannot be shared: two philosophers cannot eat with the same fork.
  2. Hold and wait. A thread holds some resources while it waits for more. A philosopher keeps its left fork while it waits for the right one.
  3. No preemption. A resource cannot be taken away; its holder must release it. Nobody snatches a fork out of a philosopher's hand.
  4. Circular wait. There is a cycle of threads, each waiting for a resource the next one holds: P0 → P1 → … → P4 → P0.

So to prevent deadlock it is enough to break one of them. Mutual exclusion is the one condition that cannot go (a fork cannot be shared), and preemption is rarely possible for locks (you cannot take a lock away from a thread in the middle of its update). That leaves hold and wait and circular wait, and each variant in the animation breaks one of them.

The fixes

Resource ordering (breaks circular wait). Number the forks and let everyone take the lower-numbered fork first. P0…P3 still take left then right, but for P4 the lower fork is F0, its right one, so P4 reaches the other way round. Along any chain of waits the fork numbers go up, so the chain cannot come back to where it started. Resource ordering tab, Demo: chain, no cycle: P4 blocks on F0 holding nothing, and P3 eats at step 15. This is the fix used in real code: a lock hierarchy, or "always lock the account with the lower id first".

Two tables. Naive: every philosopher holds its left fork and waits for its right one, and the red wait-for arrows form the cycle P0 to P1 to P2 to P3 to P4 to P0: deadlock. Resource ordering: P4 reaches for the lower fork F0 first and waits holding nothing, so P3 gets F3 and F4 and eats; the wait-for arrows form a chain P4, P0, P1, P2, P3 with no cycle.
When everyone takes the left fork the waits form a cycle; taking the lower-numbered fork first turns the cycle into a chain that ends at someone who eats.

The waiter (breaks circular wait). A counting semaphore room = N − 1 lets at most N − 1 philosophers reach for forks at once. N − 1 philosophers and N forks: one of them always gets two. Waiter tab, Demo: P4 turned away: P4 is turned away at wait(room), and P3 eats at step 19. It costs a global bottleneck: a central arbiter.

Trylock and back-off (breaks hold and wait). Take the left fork; if the right one is taken, put the left one back and try again later. Nobody ever waits while holding a fork, so there can be no deadlock. But run Trylock + back-off tab, Demo: livelock (back-off: none): with everyone in step, all take the left fork, all fail, all put it down, and all start again, every 25 steps, forever. After 50 steps without a meal the page reports a livelock: everybody is busy, nobody is blocked, and nobody makes progress. Demo: random back-off waits a random number of steps after a failure, which breaks the symmetry. Ethernet's exponential back-off after a collision solves the same problem the same way.

All or nothing (breaks hold and wait). Tanenbaum's solution: a monitor (one mutex) keeps each philosopher's state, THINKING, HUNGRY or EATING, and a semaphore s[i] per philosopher. A hungry philosopher may eat only when neither neighbour eats, and then gets both forks at once:

philosopher i:                          test(k):   // called with mutex held
    think()                                 if state[k] == HUNGRY and
    wait(mutex)                                state[LEFT(k)] != EATING and
    state[i] = HUNGRY                          state[RIGHT(k)] != EATING:
    test(i)                                     state[k] = EATING
    signal(mutex)                               signal(s[k])
    wait(s[i])      // sleep until allowed
    eat()
    wait(mutex)
    state[i] = THINKING
    test(LEFT(i)); test(RIGHT(i))       // maybe a neighbour can eat now
    signal(mutex)

No deadlock, and two neighbours never eat together. But it is not fair: in All or nothing tab, Demo: P1 starves, P0 and P2 take turns so that one of them is always eating, and test(P1) always finds a neighbour at the table. P1's hunger grows without bound while the others eat three meals each.

Handling deadlock in general

  • Prevention: make one of the four conditions impossible, as the variants here do.
  • Avoidance: grant a request only if the system stays in a safe state, one from which there is an order in which every thread can still get what it may need. Dijkstra's banker's algorithm does this, but it requires every thread to declare its maximum needs in advance, so general-purpose systems rarely use it.
  • Detection and recovery: let deadlocks happen, find the cycle in the wait-for graph, and break it by aborting a victim. Databases do exactly this: InnoDB checks the graph when a lock wait starts and rolls back one transaction with Deadlock found when trying to get lock; PostgreSQL waits deadlock_timeout (1 s by default) before it looks for a cycle. See MySQL and PostgreSQL.
  • Ignoring it (the "ostrich algorithm"): if deadlocks are rare and a restart is cheap, doing nothing is an engineering choice. Most operating systems ignore deadlocks between user processes.

The fixes in real code

  • Lock ordering. The Linux kernel documents the order in which its locks must be taken, and lockdep checks at run time that every path follows it: it reports a possible deadlock the first time two locks are taken in both orders, even if the bad interleaving never happened. When two objects of the same type must be locked, a common rule is to lock the one with the lower address or id first.
  • tryLock with back-off. Java's ReentrantLock.tryLock(timeout, unit) gives up after a timeout; the caller releases what it holds and retries after a random pause. Without the random part, two threads can livelock just like the philosophers.
  • A global arbiter. One lock (or a semaphore like the waiter's) around the whole acquisition: simple, but it serialises everyone.
  • All-or-nothing acquisition. C++ std::scoped_lock(a, b) and std::lock(a, b) lock several mutexes with a deadlock-avoidance algorithm; a transaction that locks all its rows up front does the same.

Chandy–Misra (1984)

A solution for philosophers who can only send messages to their neighbours, for any number of philosophers, with no deadlock and no starvation. Every fork is either dirty or clean. Initially each fork is given to the lower-numbered of its two philosophers, dirty. A philosopher who wants a fork it does not have sends a request token to its neighbour. A holder that receives a request keeps a clean fork, but hands over a dirty one, cleaning it on the way. After eating, all of a philosopher's forks are dirty, so it must give them up on request. Think of the forks as pointing to who has priority: the initial assignment makes this precedence graph acyclic, and every hand-over keeps it acyclic, so there is never a cycle of waits; and a philosopher that has just eaten always yields, so every hungry philosopher eventually eats. It is described here but not animated: its message passing does not fit the one-shared-memory-line-per-step model of this page.

Deadlock, livelock, starvation

DeadlockLivelockStarvation
Threads areblockedrunningsome running, one waiting
Progressnone, forevernone, while the pattern laststhe others progress
Demonaivetrylock, no back-offall or nothing
Typical fixlock orderingrandom back-offfair (FIFO) queues, ageing

A fourth liveness bug, priority inversion, happens when a high-priority thread waits for a lock held by a low-priority thread that a medium-priority thread keeps from running; priority inheritance fixes it. Starvation of a whole class of threads is the subject of readers–writers.

See also: Bounded buffer, whose waits swapped bug is the same hold-and-wait deadlock with two semaphores, and Readers–writers, where writers or readers can starve.