Before you start
- Mutexes, blocking and waking up (lesson Synchronization: mutexes and semaphores).
- The ready queue and the blocked state (lesson Processes and their states).
Theory
In this lesson each resource has a single instance: a lock, a file, a printer, a fork. A thread takes it (or blocks until its owner releases it), uses it and releases it. If someone is waiting when it is released, the first in line gets it.
The resource-allocation graph shows who holds what and who waits for what:
| Arrow | Means |
|---|---|
| Solid, from R to T | T holds R. |
| Dashed, from T to R | T waits for R. |
A deadlock is a set of threads where each one waits for a resource held by another one in the set. None can continue, so none will ever release what it holds. With single-instance resources, there is a deadlock if and only if the graph has a cycle.
The dining philosophers: n philosophers around a table and one fork between each pair. To eat, a philosopher needs the two forks beside it. Each one takes the fork on its left, then the one on its right, eats and puts both down. In the simulator, philosopher Ti’s left fork is Ri and its right fork is Ri+1 (R1 for the last one).
There is one CPU, each turn runs one operation and turns go around in a circle.
Example: T1 holds R1 and waits for R2; T2 holds R2. That is a chain, T1 → R2 → T2, not a cycle: when T2 releases R2, T1 will continue.
Predict
The board starts with Philosophers: five philosophers sit down at the same time. Each one takes the left fork, then the right one, eats once and puts both down.
Answer in the Your prediction panel before you run: does it end in a deadlock? and how many philosophers get to eat (to run work)?
Run
Scenario
With a global order, each thread asks for its resources from lowest to highest number (R1 before R2), without changing when it asks.
Delay before starting
Turns the thread spends doing something else before its program.
Your prediction
The board before the first turn
One CPU, one operation per turn, turns in a circle. Each resource has a single owner.
| Thread | State | Holds | Waits for | Program |
|---|---|---|---|---|
| Ready | nothing | – |
| |
| Ready | nothing | – |
| |
| Ready | nothing | – |
| |
| Ready | nothing | – |
| |
| Ready | nothing | – |
|
What happened this turn
Press Run or step through. Here you will see what each thread asks for and who holds it.
As it runs, watch three moments:
- At step 5, is any fork still free?
- Between steps 6 and 9 one dashed arrow appears per turn. Is it a cycle yet?
- At step 10, where does the last arrow lead?
The table below the graph shows what each thread holds, what it waits for and where it is in its program.
Explain
This stage opens when you run the simulation to the end.
Go to the simulationThe right answers were: yes, it deadlocks, and no philosopher eats.
Waiting does not fix a deadlock. In the first five turns each philosopher takes its left fork. In the next five each one asks for its right fork, which is its neighbor’s left fork. At step 10 the last request closes the cycle T5 → R1 → T1 → R2 → T2 → R3 → T3 → R4 → T4 → R5 → T5. To move on, someone would have to put a fork down, and nobody releases anything while waiting.
The four Coffman conditions. A deadlock needs all four at once:
| Condition | At the table |
|---|---|
| Mutual exclusion | A fork has one owner. |
| Hold and wait | Each keeps its left fork while asking for the right one. |
| No preemption | Nobody takes a fork away from another. |
| Circular wait | The cycle in the graph. |
Breaking any one of them makes deadlock impossible.
Prevention with a global order. Number the resources and always ask for them from lowest to highest. A cycle would need someone to hold a high resource while waiting for a lower one, and the order forbids it: circular wait is broken. At the table only one philosopher changes, T5, which now takes R1 before R5. The others already took the lower-numbered fork first.
Waiting is not being deadlocked. With the global order, after step 8 four philosophers are blocked at once, but their arrows form a chain that ends at T4, which holds R4 and finds R5 free: it takes it on its next turn, eats, releases, and the chain unwinds one at a time.
The rest of the system keeps going. In Two locks, T1 and T2 deadlock at step 8, but T3, which only uses R3, finishes normally. The system does not freeze: the threads in the cycle simply never come back.
Adjusting the timing is not a fix. If T2 starts 2 turns late, T1 takes both locks first and Two locks finishes. With a 1-turn delay the cycle forms anyway. A slower disk or a different load brings the bad timing back.
Four strategies:
- Prevent: break a Coffman condition by design. A global lock order, asking for everything at once, or trying the lock and, if it is taken, releasing what you hold and retrying.
- Avoid: grant a request only if the system stays in a safe state (Dijkstra’s banker’s algorithm). It requires knowing in advance the most each thread will ask for; rare in general-purpose systems.
- Detect and recover: look for cycles in the wait-for graph and abort a victim. Databases do this: PostgreSQL checks for a deadlock when a wait exceeds
deadlock_timeout(1 second by default) and aborts one transaction with an error. - Ignore the problem: general-purpose operating systems do not detect deadlocks between application locks. The program hangs and someone kills it.
Tools. In the Linux kernel, lockdep records the order in which locks are taken and warns the first time two of them are taken in opposite orders, before the deadlock ever happens.
Several instances. If a resource type has several instances, a cycle means a deadlock is possible, but not certain. Deciding it takes an algorithm like the banker’s safety check.
Experiment
This stage opens when you run the simulation to the end.
Go to the simulationUse the board to solve these challenges. Each one has a possible solution when you expand it.
1. Make all five philosophers eat, changing only the order in which they ask for forks.
Switch on Global order. Only T5 changes (it takes R1 before R5) and circular wait becomes impossible. They eat in this order: T4, T3, T2, T1, T5.
2. Find a moment when four threads wait at the same time without a deadlock.
With the global order, after step 8. The dashed arrows form a chain that ends at T4, which holds R4 and can still take R5, which is free.
3. Make Two locks finish without changing the lock order.
Set T2’s delay to 2 (or more). T1 takes R2 before T2 asks for it. With delay 1 the cycle forms anyway, at step 10: relying on timing is fragile.
4. Cause a deadlock with as few threads as possible.
Philosophers with 2 at the table: the cycle closes at step 4. Two threads and two locks taken in opposite orders are enough.
Check
This stage opens when you run the simulation to the end.
Go to the simulationGo deeper
- The banker’s algorithm, step by step: safe and unsafe states, and why an unsafe state does not always end in deadlock.
- Livelock. Philosophers who put their fork down and retry all at the same time: nobody is blocked, but nobody makes progress.
- Try and back off. Taking a lock with
trylockand, if it fails, releasing everything and waiting a random time breaks deadlock in exchange for possible livelock. - Deadlocks in databases. Wait-for graphs between transactions and how the victim is chosen.
Further reading:
- Coffman, Elphick and Shoshani, “System Deadlocks”, ACM Computing Surveys 3(2), 1971.
- Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces, ch. 32, section 32.3, and ch. 31, section 31.6. Free online.
- Silberschatz, Galvin and Gagne, Operating System Concepts, 10th ed., ch. 8.
- Linux kernel documentation, Runtime locking correctness validator: docs.kernel.org.
- PostgreSQL documentation,
deadlock_timeout: postgresql.org.