CSE Roadmap

Common tier · about 5 hours · 8 parts

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.