Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 79 ยท Concurrency Control

Deadlocks: Detection, Prevention and Recovery

Understand deadlocks in a DBMS: wait-for graphs, cycle detection, victim selection, wait-die and wound-wait prevention, timeouts, plus runnable Python demos.

Locking buys isolation at a price: transactions wait. Waiting is harmless until it forms a circle. Imagine T1 holds a lock on account A and now wants B, while T2 holds B and now wants A. Each is waiting for something only the other can release. Nothing will ever change on its own: this is a deadlock. Two-phase locking guarantees serializability but does nothing to prevent it, so every lock-based DBMS needs a plan for deadlocks.

A deadlock needs four things at once (the Coffman conditions): resources that cannot be shared (mutual exclusion), transactions that keep what they hold while asking for more (hold and wait), locks that cannot be taken away (no preemption), and a circular wait. Remove any one and deadlock is impossible. The three families of solutions below remove or break one of them.

Three ways to handle deadlock

Prevention Make circular waits impossible.
Detection Find cycles, then abort one victim.
Timeouts Give up after waiting too long.

Real engines mostly detect, or time out, and let the application retry.

1 / 2

The wait-for graph

The standard tool is the wait-for graph. It has one node per active transaction and an edge Ti โ†’ Tj whenever Ti is waiting for a lock that Tj holds. The system can read this straight from the lock manager's tables (the granted and waiting lists). The rule is simple: there is a deadlock if and only if the graph contains a cycle.

flowchart LR
  T1["T1<br/>holds A"] -->|"waits for B"| T2["T2<br/>holds B"]
  T2 -->|"waits for A"| T1

Two transactions waiting for each other: a cycle of length two.

When to run the check is a design choice. Checking at every blocked request finds deadlocks immediately but costs CPU on every wait. Checking periodically, or only after a request has waited for a while, is cheaper and adds a small delay. Cycles can also be long (T1 waits for T2 waits for T3 waits for T1), and they can involve several lockable items.

Detecting a deadlock and picking a victim

Once a cycle is found, at least one transaction in it must be aborted: it is rolled back, its locks are released, and the others can continue. The chosen transaction is the victim. A sensible policy is to pick the transaction that is cheapest to undo, for example the one that holds the fewest locks or has written the least log, and to break ties by choosing the youngest. A policy that always picks the same transaction can starve it, so many systems also count how often a transaction has been victimized and spare the ones that have suffered repeatedly. After the abort, the application is expected to retry the transaction, which will then usually succeed.

The program below builds the wait-for graph from a lock table, finds a cycle with a depth-first search, aborts the victim and checks again until the graph is clean. It runs three scenarios: a two-way deadlock, a three-way deadlock, and a long chain that is not a deadlock.

Python Wait-for graph and deadlock resolution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first scenario both transactions hold one lock, so the tie goes to the youngest, T2. In the second, the cycle is T1, T2, T3. Every member holds one lock, so the youngest, T3, is the victim. T2 also waits for T4 (a shared holder of C), but T4 is not waiting for anyone, so it is not on the cycle and is left alone. After T3 is rolled back, the remaining edges form no cycle. The third scenario is a queue: T4 waits for T1, which waits for T2, which waits for T3, which waits for nobody. T3 will finish and the whole chain unwinds. A long wait is not a deadlock; only a cycle is.

Deadlock prevention

Detection lets deadlocks happen and cleans up. Prevention arranges things so a cycle can never form. There are several strategies:

  • Lock ordering. If every transaction acquires locks in one global order (say, by account number), a cycle is impossible, because every wait edge points from a lower to a higher item. This is the most useful rule for application developers: when a transfer touches two accounts, always lock the lower id first.
  • Conservative 2PL. Acquire every lock before doing anything, all at once or not at all. No transaction ever waits while holding a lock, so no circular wait. It needs the access set in advance, which is rarely known.
  • Timestamp-based schemes. Each transaction gets a timestamp when it starts (older means smaller). When a requester finds the lock held, the timestamps decide who may wait.

Two classic timestamp schemes use the same idea in opposite ways:

  • Wait-die (non-preemptive): an older requester waits for a younger holder; a younger requester dies (aborts and restarts) rather than wait for an older holder.
  • Wound-wait (preemptive): an older requester wounds the younger holder (forces it to abort) and takes the lock; a younger requester waits for an older holder.

In both schemes a restarted transaction keeps its original timestamp, so it eventually becomes the oldest and cannot starve. And in both, waits only ever go in one direction (older to younger under wait-die, younger to older under wound-wait), so a cycle cannot form. The price is that some transactions are aborted that would never actually have deadlocked.

Python Wait-die versus wound-wait

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Under wait-die, T1 (older) is allowed to wait for T2, but when T2 (younger) asks for A, it dies instead of closing the circle. Under wound-wait, T1 simply wounds T2 as soon as it asks for B, so T2 never gets a chance to ask for A. Either way the deadlock is gone before it forms, at the cost of one restart.

No-wait, cautious waiting and starvation

Wait-die and wound-wait need timestamps to decide. Two simpler prevention schemes need no timestamps at all.

  • No-wait. A transaction that cannot get a lock never waits: it is aborted at once and restarted later. With no waiting there is no hold-and-wait, so no deadlock. The scheme is trivial to build, but it aborts many transactions that would only have waited a moment, and a transaction that is restarted immediately can collide again and again. Practical versions delay the restart by a random or growing back-off time.
  • Cautious waiting. A requester may wait only if the transaction holding the lock is not itself waiting. If the holder is blocked, the requester aborts. Because only running transactions are ever waited for, a chain of waits is at most one link long, so no cycle can form. It aborts fewer transactions than no-wait, and unlike wait-die it needs no timestamps.

The program replays one small scenario under both rules.

Python No-wait and cautious waiting, and why timestamps matter for starvation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Under no-wait, both requests are refused, even though T2's wait for the running T3 was harmless. Under cautious waiting, T2 may wait, because T3 is running. Then T1 asks for B, which T2 holds, and T2 is now blocked, so T1 aborts instead of joining a waiting chain.

Starvation

All of these schemes solve deadlock by aborting somebody. A different failure appears when the same transaction is aborted again and again: it makes no progress, even though the system as a whole does. This is starvation (or livelock when transactions keep restarting each other). The second half of the program shows the classic cause. If wait-die gives a restarted transaction a new, later timestamp, it is always the youngest and dies at every conflict. If it keeps its original timestamp, it grows older relative to new arrivals and eventually wins.

Common cures:

  • Keep the original timestamp on restart (wait-die and wound-wait do this by design).
  • Do not always choose the same victim. When detecting deadlocks, count how often each transaction has been a victim and favor it next time.
  • Queue lock requests fairly (first come, first served), so a writer is not overtaken forever by a stream of readers; see the lock manager.
  • Back off before restarting in no-wait style schemes, so colliding transactions do not retry in lockstep.

Timeouts and what real systems do

The crudest strategy is the timeout: if a transaction has waited longer than some limit, assume a deadlock and abort it. It needs no graph, is trivial to implement and works across distributed systems where a global wait-for graph is hard to build. The drawbacks are that a too-short limit aborts transactions that were only waiting behind a slow one, and a too-long limit leaves real deadlocks hanging.

Engines combine these ideas, and details vary by product and version. Many server databases run a deadlock detector (PostgreSQL does so after a transaction has waited about one second by default; MySQL's InnoDB checks as requests block) and abort one victim with a dedicated error code (SQLSTATE 40P01 in PostgreSQL, error 1213 in MySQL). The application is expected to catch it and retry the whole transaction:

Python
# Retry pattern (read-only sketch, any language works the same way)
for attempt in range(3):
    try:
        with database.transaction():
            transfer(a, b, amount)
        break
    except DeadlockDetected:
        continue           # the engine rolled the transaction back; start over

SQLite takes a simpler route. It allows one writer at a time, so true lock cycles between writers cannot arise. Instead a connection that cannot get the lock it needs receives a SQLITE_BUSY error ("database is locked"). The classic trap is two deferred transactions that both start by reading and then try to write: each holds a read lock that blocks the other's write, so one of them must receive SQLITE_BUSY at once, since waiting would never help. You can reduce busy errors by starting write transactions with BEGIN IMMEDIATE and by setting a wait budget. These statements concern a file shared by several connections, which the in-browser database does not have, so they are shown as code only:

SQL
PRAGMA busy_timeout = 5000;   -- wait up to 5 s for a lock before reporting SQLITE_BUSY
BEGIN IMMEDIATE;              -- take the write lock up front instead of upgrading later
UPDATE account SET balance = balance - 10 WHERE id = 1;
COMMIT;

Good habits cut deadlocks on every engine: keep transactions short, touch rows in a consistent order, avoid waiting for user input while holding locks, and always be ready to retry.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does an edge T1 -> T2 in a wait-for graph mean?

    Edges point from the waiting transaction to the one that holds the lock it needs. A cycle of such edges is a deadlock.
  2. 2. T1 waits for T2, T2 waits for T3, and T3 is running normally. Is this a deadlock?

    A deadlock requires a cycle in the wait-for graph. A chain ends at a transaction that can finish and release its locks.
  3. 3. Under wait-die, an older transaction requests a lock held by a younger one. What happens?

    In wait-die, only younger requesters die. Older requesters are allowed to wait, so every wait goes from older to younger and no cycle can form.
  4. 4. Why does a restarted transaction keep its original timestamp in wait-die and wound-wait?

    A fresh timestamp each time would let the same transaction be the youngest again and again. Keeping the original one guarantees it eventually gets priority.
  5. 5. Which application-level rule reduces deadlocks?

    With a global lock order every wait edge goes from a lower to a higher item, so a cycle cannot form.

Summary

  • A deadlock is a cycle of transactions each waiting for a lock another holds; it needs mutual exclusion, hold and wait, no preemption and circular wait.
  • Detection builds a wait-for graph and looks for cycles, then aborts a victim chosen by cost, age and past aborts; the application retries.
  • Prevention avoids cycles: a global lock order, conservative 2PL, or the timestamp schemes wait-die (young requesters die) and wound-wait (old requesters wound).
  • No-wait aborts any requester that would have to wait; cautious waiting lets a requester wait only for a holder that is running. Starvation is avoided by keeping timestamps on restart, varying victims and fair queues.
  • Timeouts are simple and robust but can abort innocent waiters or leave real deadlocks waiting too long.
  • SQLite avoids lock cycles by allowing one writer at a time and reports SQLITE_BUSY instead; server engines detect deadlocks and expect your code to retry.

Next: Timestamp-Based Protocols.