Skip to content

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

AttackHowCost
Mutual exclusionmake resources shareablerarely possible
Hold and waittake everything at once, or nothingpoor utilisation
No preemptionallow taking resources backnot always safe
Circular waita global ordering on resourceseasy, 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.

StrategyUsed by
Prevention by lock orderingapplication code, and this is your job
Avoidancealmost nothing, in practice
Detection and recoverydatabases
IgnoringLinux, Windows, macOS