16/32 · 5 min
Four ways to deal with it
Deadlock needs four conditions at once. Every strategy is an attack on one of them, or a decision to live with it.
The four conditions
Mutual exclusion: a resource cannot be shared. Hold and wait: a process holds one resource while waiting for another. No preemption: a resource cannot be taken away. Circular wait: a cycle of processes each waiting on the next.
Remove any one and deadlock is impossible.
Prevention: make it structurally impossible
| Attack | How | Cost |
|---|---|---|
| Mutual exclusion | make resources shareable | rarely possible |
| Hold and wait | take everything at once, or nothing | poor utilisation |
| No preemption | allow taking resources back | not always safe |
| Circular wait | a global ordering on resources | easy, and this is the one used |
The last row is the practical answer. Number every lock and require them to be taken in increasing order, and a cycle cannot form, because a cycle needs someone to take a lower number while holding a higher one.
Avoidance: check before granting
The system knows in advance what each process might request, and refuses any allocation that could lead to an unsafe state. Banker's algorithm is the standard example.
It works and is almost never used, because it requires knowing maximum requirements up front, which real programs cannot state.
Detection and recovery
Let it happen, notice, and break it. Periodically look for a cycle in the wait for graph, then abort a process or forcibly take a resource back.
This is what databases do. A deadlocked transaction is chosen as the victim and rolled back with an error, and the application retries. Aborting is cheap because a transaction is designed to be undoable, which is exactly why the strategy suits databases and not general programs.
Ignoring it
The ostrich approach, and what general purpose operating systems actually do.
The reasoning is a cost benefit one rather than laziness: deadlocks in an OS are rare, the prevention machinery would slow every allocation, and the recovery is a reboot which users already know how to do. Spending constant overhead to avoid a rare event is a bad trade.
| Strategy | Used by |
|---|---|
| Prevention by lock ordering | application code, and this is your job |
| Avoidance | almost nothing, in practice |
| Detection and recovery | databases |
| Ignoring | Linux, Windows, macOS |