Part 7 of 8 · 3 min read
The choice
Choosing among the methods
The four approaches to deadlock suit different systems:
| Approach | Cost in normal running | When it fits |
|---|---|---|
| Prevention (page 3) | Rules for every programmer, small run-time cost | Programs where the code can be controlled, most of all lock ordering |
| Avoidance (page 4) | Claims in advance, much computing | Rare: closed systems with known needs |
| Detection and recovery (this page) | Bookkeeping, a check from time to time, lost work at recovery | Databases and systems where users choose the order |
| Ignore | None | Rare events, and cases where a reboot is cheap |
In plain words: Real systems mix them. A database prevents deadlocks within its own internal locks by ordering, and detects them among user transactions. The Linux kernel uses lock ordering with the lockdep checker (page 2) for its internal locks, and detection with EDEADLK for user record locks. A normal application prevents by ordering, and adds a timeout alarm as a safety net.
Two things limit all recovery methods. Some work cannot be undone: a thread that has sent an email or moved a robot arm cannot be rolled back by releasing locks. And recovery is a repair: it costs work every time it runs, so it is only good when deadlocks are rare.
Checkpoint
A checkpoint is a saved copy of a thread's state at a known good moment, kept so that the thread can later be returned to that point after a rollback.
Example: a database transaction records its starting state, so that an abort can undo every row it changed.
Interview angle
"How would you recover from a deadlock?" Say: detect it (a cycle or a timeout), choose a victim by the cost of restarting it, roll it back or stop it, and make sure no thread is chosen forever. Then name a real example, such as a database aborting a transaction, and add that the application must be ready to retry.
Check yourself: 1. Why can recovery not undo a thread's effect on the outside world? 2. Which approach does the Linux kernel use for user-level file record locks? 3. Why is detection less suitable when deadlocks are common?
Words you will meet
| Word | Meaning |
|---|---|
| Detection | Running an algorithm to find deadlocked threads |
| Request matrix | What each thread is waiting for now |
| Recovery | Breaking a deadlock that has been found |
| Victim | The thread chosen to be stopped, rolled back or robbed |
| Rollback | Undoing partial work and releasing the resources |
| Checkpoint | A saved state to return to |
| Deadlock timeout | A delay before the deadlock check is run |
EDEADLK |
The error code a call returns when it would deadlock |
| Starvation | A thread that is never served; here, a victim picked again and again |
Quick notes
- Deadlock detection and recovery is a method in which the system places no restriction on how threads request resources, periodically runs an algorithm to find deadlocked threads, and breaks each.
- The request matrix is a table that holds, for each thread, the number of units of each resource type it is waiting for at this moment; detection uses it in place of the maximum claim used by avoidance.
- A deadlock timeout is a delay that a system waits, after a thread has blocked, before it runs the deadlock check, so that the check is skipped when the wait ends by itself.
- A victim is the thread that the system stops, rolls back, or robs of a resource in order to break a deadlock, chosen so that the cost of recovery is.
- A rollback is the undoing of a thread's partial work and the release of the resources it holds, so that it can be restarted from a state in which it holds nothing.
- A checkpoint is a saved copy of a thread's state at a known good moment, kept so that the thread can later be returned to that point after a rollback.