Deadlock Handling and Prevention

DSA, Database System & Operating System — Transaction Processing, Concurrency Control & Recovery, NEC licence examination syllabus (Nepal Engineering Council).

Deadlock Handling and Prevention

When transactions wait for each other in a cycle — detection, prevention, and the retry loop you must write.

🌍 Where this lives: deadlocks are not a bug to be eliminated; they are a normal outcome of concurrency that your application must handle. Postgres and MySQL both detect them and kill one transaction with a specific error code (40P01 / 1213), and any serious application catches that code and retries. The most common avoidable cause is inconsistent ordering: one code path updates account A then B, another updates B then A. Fixing that by always locking in primary-key order eliminates the majority of production deadlocks. Search "deadlock retry pattern exponential backoff".

The four conditions

A deadlock requires ALL FOUR simultaneously (Coffman conditions): 1. MUTUAL EXCLUSION a resource is held exclusively 2. HOLD AND WAIT a transaction holds one resource and waits for another 3. NO PREEMPTION a resource cannot be forcibly taken 4. CIRCULAR WAIT a cycle of transactions each waiting for the next Break any ONE and deadlock becomes impossible. Every prevention scheme below targets a specific condition. THE SIMPLEST DEADLOCK — two transactions, opposite order: T1: lock-X(A) T2: lock-X(B) T1: ... wants B ──waits──► held by T2 T2: ... wants A ──waits──► held by T1 → circular wait. Neither can proceed. Ever. WAIT-FOR GRAPH — the detection structure: · one node per active transaction · edge Ti → Tj if Ti is WAITING for a lock held by Tj · a DEADLOCK exists iff the graph has a CYCLE Note the difference from the precedence graph of the previous topic: that one describes conflicts in a completed schedule; this one describes who is blocked RIGHT NOW.

Deadlock, reproduced

deadlock.sql

-- Two real sessions on PostgreSQL 18, updating the same two
-- rows in OPPOSITE order.

-- SESSION 1                        SESSION 2
BEGIN;
UPDATE account SET balance=balance-1
  WHERE id=1;              -- takes X lock on row 1
                           -- BEGIN;
                           -- UPDATE account
                           --   SET balance=balance-1
                           --   WHERE id=2;   ← X lock row 2
UPDATE account SET balance=balance-1
  WHERE id=2;              -- ← BLOCKS on row 2
                           -- UPDATE account
                           --   SET balance=balance-1
                           --   WHERE id=1;  ← BLOCKS on row 1
                           -- → CIRCULAR WAIT

-- MEASURED RESULT (session 1 was chosen as the victim):
-- ERROR:  deadlock detected
-- DETAIL: Process 66697 waits for ShareLock on transaction
--         19816; blocked by process 66699.
--         Process 66699 waits for ShareLock on transaction
--         19815; blocked by process 66697.
-- HINT:   See server log for query details.
--
-- Note the DETAIL: it names BOTH sides of the cycle. That is
-- the wait-for graph, printed. PostgreSQL ran its detector,
-- found the cycle, and aborted one transaction so the other
-- could proceed.
--
-- The surviving transaction completed normally. The victim
-- must be RETRIED by the application.

-- ===== THE FIX: consistent lock ordering =====
-- If BOTH sessions always touch the lower id first, no cycle
-- can form:
BEGIN;
UPDATE account SET balance=balance-1 WHERE id=1;  -- lower
UPDATE account SET balance=balance-1 WHERE id=2;  -- higher
COMMIT;
-- Session 2 doing the same order simply WAITS for session 1
-- and then proceeds. A wait is not a deadlock.

-- Or lock everything up front, in a deterministic order: 
BEGIN;
SELECT id FROM account WHERE id IN (1,2)
  ORDER BY id FOR UPDATE;      -- ORDER BY is the point
UPDATE account SET balance=balance-1 WHERE id IN (1,2);
COMMIT;

The measured DETAIL line is worth reading closely: Process 66697 waits for ... blocked by process 66699. Process 66699 waits for ... blocked by process 66697. That is a two-node cycle, stated explicitly. PostgreSQL's detector runs when a lock wait exceeds deadlock_timeout (default 1 second) — it does not check on every lock request, because building the wait-for graph is not free and the vast majority of waits resolve on their own. deadlock_timeout = 1s wait this long before checking That default is a deliberate trade: a real deadlock costs you one second of waiting before it is broken, in exchange for not paying detection cost on every ordinary lock wait. VICTIM SELECTION — which transaction dies? Criteria used by real systems: · the one with the LEAST work done (fewest log records) · the one holding the FEWEST locks · the YOUNGEST transaction · the one that has been rolled back fewest times (to avoid starvation) PostgreSQL aborts the transaction whose lock request COMPLETED the cycle — simple, and it means the transaction that arrived last usually loses.

The fix is not cleverness, it is ordering. A deadlock needs a cycle; a cycle needs two transactions acquiring the same resources in different orders. Impose a global order — primary key, table name, anything total and consistent — and condition 4 cannot be satisfied. This is the single most effective concurrency rule in application code.

The three strategies

STRATEGY 1 — DETECTION AND RECOVERY (what real systems do) Let deadlocks happen, detect the cycle, kill a victim. · build the wait-for graph periodically or on timeout · if a cycle exists, choose a victim and roll it back · release its locks so the others proceed WHEN TO RUN THE DETECTOR: every k seconds — simple, may delay detection on every lock wait — immediate, expensive after a timeout — PostgreSQL's approach, 1s default ✔ no overhead when there are no deadlocks ✔ no unnecessary aborts ✗ wasted work when a victim is killed ✗ the application MUST retry STRATEGY 2 — PREVENTION (make deadlock impossible) (a) CONSERVATIVE 2PL — acquire all locks before starting. Breaks HOLD AND WAIT. ✗ needs the lock set known in advance (b) ORDERED LOCKING — impose a total order on data items and always lock in that order. Breaks CIRCULAR WAIT. ✔ practical, and the standard application-level fix (c) TIMESTAMP-BASED SCHEMES — use transaction age to decide who waits and who dies. Breaks CIRCULAR WAIT because waiting only ever goes one way in timestamp order. WAIT-DIE (non-preemptive) Ti requests a lock held by Tj: if TS(Ti) < TS(Tj) → Ti is OLDER → Ti WAITS else → Ti is younger → Ti DIES (rolls back, retries with the SAME timestamp) older transactions wait; younger ones die. WOUND-WAIT (preemptive) Ti requests a lock held by Tj: if TS(Ti) < TS(Tj) → Ti is OLDER → Ti WOUNDS Tj (Tj rolls back) else → Ti WAITS older transactions kill younger ones; younger wait. BOTH are deadlock-free because waiting is always in one timestamp direction, so no cycle can form. KEY PROPERTY — no starvation: a rolled-back transaction keeps its ORIGINAL timestamp, so it grows older relative to everyone else and eventually becomes the oldest, at which point it can no longer be killed. STRATEGY 3 — TIMEOUT If a transaction waits longer than T, abort it. ✔ trivial to implement, no graph needed ✗ cannot distinguish a deadlock from mere slowness ✗ choosing T is guesswork: too short kills healthy transactions, too long lets deadlocks persist SET lock_timeout = '5s'; -- PostgreSQL, per session

Worked example — tracing wait-die and wound-wait

Three transactions with timestamps (smaller = older): TS(T1) = 10, TS(T2) = 20, TS(T3) = 30 SEQUENCE OF EVENTS: 1. T2 locks A 2. T1 requests A (held by T2) 3. T3 requests A (held by T2) UNDER WAIT-DIE: event 2: T1 requests, held by T2. TS(T1)=10 < TS(T2)=20 → T1 is OLDER → T1 WAITS event 3: T3 requests, held by T2. TS(T3)=30 > TS(T2)=20 → T3 is younger → T3 DIES, rolls back, retries later with timestamp 30 still Result: T2 proceeds, T1 queued, T3 restarted. UNDER WOUND-WAIT: event 2: T1 requests, held by T2. TS(T1)=10 < TS(T2)=20 → T1 is OLDER → T1 WOUNDS T2: T2 rolls back and T1 takes the lock event 3: T3 requests, held by T1. TS(T3)=30 > TS(T1)=10 → T3 is younger → T3 WAITS Result: T1 proceeds immediately, T2 restarted, T3 queued. COMPARING THE OUTCOMES: wait-die wound-wait who was rolled back T3 (youngest) T2 (the holder) who ran first T2 T1 (the oldest) rollbacks 1 1 WHICH IS BETTER? Wound-wait generally causes FEWER rollbacks overall, because a wounded transaction is killed early (it was only holding a lock) whereas under wait-die a young transaction may be repeatedly killed just as it is about to finish. But wound-wait requires preemption — the ability to force a rollback on a transaction that is running normally. NEITHER STARVES: a rolled-back transaction retains its timestamp, so with each restart it is relatively older, and an older transaction is progressively safer under both schemes. Eventually it is the oldest and cannot be killed at all. That timestamp-retention detail is the part most often missed in exam answers, and it is what makes both schemes fair.

The retry loop your application must have

retry.py

# A deadlock or serialization failure is a NORMAL, expected
# outcome. The database has done its job by detecting it; the
# application's job is to try again.
import psycopg
import time
import random

RETRYABLE = {'40001',   # serialization_failure
             '40P01'}   # deadlock_detected

def transfer(conn, src, dst, amount, max_attempts=5):
    for attempt in range(1, max_attempts + 1):
        try:
            with conn.transaction():
                cur = conn.cursor()
                # lock in a DETERMINISTIC order to make deadlock
                # unlikely in the first place
                lo, hi = sorted((src, dst))
                cur.execute(
                    "SELECT id FROM account WHERE id IN (%s,%s) "
                    "ORDER BY id FOR UPDATE", (lo, hi))
                cur.execute(
                    "UPDATE account SET balance = balance - %s "
                    "WHERE id = %s", (amount, src))
                cur.execute(
                    "UPDATE account SET balance = balance + %s "
                    "WHERE id = %s", (amount, dst))
            return True                     # committed

        except psycopg.errors.Error as e:
            if e.sqlstate not in RETRYABLE:
                raise                       # a real bug
            if attempt == max_attempts:
                raise                       # give up
            # EXPONENTIAL BACKOFF WITH JITTER.
            # Without jitter, two conflicting transactions
            # retry in lockstep and collide again.
            delay = (2 ** attempt) * 0.01 * (0.5 + random.random())
            time.sleep(delay)
    return False

THREE DETAILS THAT MATTER IN THAT CODE: 1. ONLY retry the retryable codes. A constraint violation (23505) or a syntax error will fail identically on every attempt — retrying it turns a fast failure into a slow one and hides the bug. 2. THE JITTER is not decoration. Without it, two transactions that deadlocked will both sleep exactly 20 ms and collide again, then both sleep 40 ms and collide again. The random factor decorrelates them. 3. LOCK IN A DETERMINISTIC ORDER inside the transaction. The retry loop handles deadlocks that still occur; the ORDER BY prevents most of them from occurring. Do both — prevention for the common case, retry for the rest. WHEN YOU MUST HAVE A RETRY LOOP: · always, if you use SERIALIZABLE isolation (40001 is routine there) · always, if any transaction touches more than one row · in practice: always. It is a dozen lines and it converts a user-visible error into an invisible retry.

🌍 Go further: the timestamp schemes above are the classical answer, but distributed databases revived them because a global wait-for graph is impractical across nodes. Google Spanner uses wound-wait precisely for this reason, and CockroachDB does too — with a distributed system you cannot cheaply ask "who is waiting for whom" everywhere at once, so a rule based only on local timestamp comparison becomes attractive again. Search "Spanner wound-wait distributed deadlock" and "CockroachDB transaction contention".

💡 Exam angle: state the four Coffman conditions and which one each strategy breaks. Draw a wait-for graph with a cycle. The highest-value item is wait-die versus wound-wait: get the direction right — in wait-die the older transaction waits and the younger requester dies; in wound-wait the older transaction kills the younger holder. Note that both are deadlock-free because waiting goes one way in timestamp order, and that neither starves because a restarted transaction keeps its original timestamp. Mention that real systems use detection plus an application retry loop.

Syllabus points

Detection & prevention
Wait-die / wound-wait

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.