Deadlock Detection & Recovery

By the end of this lesson you will be able to detect a deadlock with a wait-for graph or the detection algorithm, pick a victim to break it, and recognise how databases and kernels handle deadlocks in practice.

Prevention and avoidance stop deadlocks before they happen, but both have a cost. Many systems take a third path: let processes run freely, check now and then whether a deadlock has formed, and break it if it has. It is like the traffic police clearing a gridlocked junction instead of banning cars from the road.

Single-instance resources: the wait-for graph

When every resource has exactly one instance (as with locks), you can simplify the resource allocation graph into a wait-for graph. Remove the resource nodes and draw an edge A -> B whenever process A waits for a resource held by process B.

The rule is simple: a deadlock exists exactly when the wait-for graph has a cycle.

Step 1: run this check. Four database transactions wait on each other's row locks.

# Wait-for graph: an edge A -> B means "A waits for a lock held by B"
waits_for = {"T1": ["T2"], "T2": ["T3"], "T3": ["T1"], "T4": ["T1"]}

def has_cycle(g):
    colour = {}
    def visit(n):
        colour[n] = "grey"
        for m in g.get(n, []):
            if colour.get(m) == "grey" or (m not in colour and visit(m)):
                return True
        colour[n] = "black"
        return False
    return any(n not in colour and visit(n) for n in list(g))

print("deadlock?", has_cycle(waits_for))
waits_for["T3"] = []          # T3 stops waiting (it got its lock)
print("after T3 is served:", has_cycle(waits_for))

deadlock? True
after T3 is served: False

Step 2: read it. T1, T2 and T3 form a circle, so they are deadlocked. T4 waits for T1, so it is stuck as well, but it is not in the cycle. Once T3 stops waiting, the circle breaks. The grey/black colouring is the standard depth-first way to find a cycle: grey means "on the current path".

Multiple instances: the detection algorithm

With several instances per resource type, a cycle is not enough proof. Instead we use an algorithm that looks very like the Banker's safety check, with one key difference: it uses what each process is requesting right now, not its declared maximum. It needs:

• Available: free instances of each type.
• Allocation: what each process holds.
• Request: what each process is currently waiting for.

Steps:

1. Let Work = Available. Mark any process that holds nothing as finished, because it cannot be part of a deadlock.
2. Find an unfinished process whose Request <= Work.
3. Assume it gets what it wants, finishes and releases everything: Work = Work + Allocation. Mark it finished.
4. Repeat. Any process still unfinished at the end is deadlocked.

The algorithm is optimistic: it assumes a process whose request can be met will finish without asking for more. If that turns out wrong, the next detection run will catch it.

Detecting and recovering in Python

This example has three resource types and four processes. After finding the deadlock, it recovers by aborting the process whose loss costs least, then checks again.

available  = [0, 1, 0]
allocation = {"P0": [1, 0, 1], "P1": [2, 0, 0], "P2": [0, 1, 1], "P3": [0, 0, 0]}
request    = {"P0": [0, 1, 0], "P1": [0, 0, 2], "P2": [2, 0, 0], "P3": [1, 0, 0]}

def detect(available, allocation, request):
    work = list(available)
    # a process holding nothing cannot be part of a deadlock
    finished = {p for p in allocation if not any(allocation[p])}
    progress = True
    while progress:
        progress = False
        for p in allocation:
            if p not in finished and all(r <= w for r, w in zip(request[p], work)):
                work = [w + a for w, a in zip(work, allocation[p])]
                finished.add(p); progress = True
    return [p for p in allocation if p not in finished]

stuck = detect(available, allocation, request)
print("Deadlocked:", stuck or "none")

# Recovery: abort the cheapest victim, release its resources, check again
cost = {"P0": 5, "P1": 8, "P2": 3, "P3": 1}       # e.g. minutes of work lost
while stuck:
    victim = min(stuck, key=cost.get)
    print(f"Abort {victim}, releasing {allocation[victim]}")
    available = [a + h for a, h in zip(available, allocation[victim])]
    allocation = {p: v for p, v in allocation.items() if p != victim}
    stuck = detect(available, allocation, request)
    print("Deadlocked now:", stuck or "none")

Deadlocked: ['P1', 'P2']
Abort P2, releasing [0, 1, 1]
Deadlocked now: none

Step 3: trace it by hand. Work starts at (0, 1, 0). P3 holds nothing, so it is marked finished at once. P0 requests (0, 1, 0), which fits; it finishes and Work becomes (1, 1, 1). P1 wants 2 of C and P2 wants 2 of A, but only 1 of each is free, so both are stuck. Aborting P2 releases (0, 1, 1). In the next check Work reaches (1, 2, 2) after P0, which is enough for P1 to finish.

When should detection run?

• On every request that cannot be granted immediately: finds deadlocks at once, but costs time on every wait.
• Periodically, for example every few minutes: cheaper, but a deadlock may sit unnoticed for a while.
• When CPU use drops suddenly: a group of deadlocked processes often shows up as an idle CPU with blocked work.

Ways to recover

Process termination.

• Abort all deadlocked processes: simple and sure, but a lot of work is lost.
• Abort one at a time and re-run detection after each, as the code does: less loss, more checking.

How to choose a victim: lowest priority, least work done so far, fewest resources held, closest to the start, or an interactive process last. Picking well is a judgement call, like deciding which car should reverse in a jammed lane.

Resource preemption. Take resources from some processes and give them to others:

• Select a victim to lose resources at the lowest cost.
• Roll back the victim to a safe earlier state (a checkpoint) or restart it, because it cannot continue from where it was.
• Prevent starvation: if the same process is always chosen, it never finishes. Count how many times a process has been rolled back and include that in the cost.

Where you meet this in real systems

• Databases detect deadlocks between transactions with wait-for graphs. MySQL's InnoDB engine picks a victim, rolls it back and returns error 1213: Deadlock found when trying to get lock; try restarting transaction. Applications are expected to retry.
• The Linux kernel has lockdep, a checker that developers enable to catch lock-order problems that could deadlock, before users ever see them. It also has a hung-task detector that logs a warning when a task stays in uninterruptible sleep too long (120 seconds by default).
• Windows offers Driver Verifier, which can check drivers for lock-order violations that may cause deadlocks.

-- Typical application pattern after MySQL reports a deadlock (error 1213):
-- roll back is already done by the server; the app simply retries the transaction
START TRANSACTION;
UPDATE accounts SET balance = balance - 500 WHERE id = 7;
UPDATE accounts SET balance = balance + 500 WHERE id = 3;
COMMIT;

Common mistakes

• Using Need instead of Request in detection. Detection uses current requests; avoidance uses declared maximum needs.
• Forgetting processes that hold nothing. They are marked finished at the start.
• Assuming the process outside a cycle is deadlocked. It may be blocked, but it recovers once the cycle is broken.

Key points

• With single-instance resources, a deadlock exists exactly when the wait-for graph has a cycle.
• The multi-instance detection algorithm uses Available, Allocation and Request; unfinished processes at the end are deadlocked.
• Detection can run on every blocked request, periodically, or when CPU use drops.
• Recovery means aborting processes (all or one at a time) or preempting resources with rollback.
• Victim selection weighs priority, work lost and resources held, and must avoid starving one process.
• Databases detect and roll back deadlocked transactions; Linux lockdep catches lock-order bugs early.

request["P1"] = [1, 0, 1]
print("Deadlocked:", detect([0, 1, 0], {"P0": [1, 0, 1], "P1": [2, 0, 0], "P2": [0, 1, 1], "P3": [0, 0, 0]}, request) or "none")

Deadlocked: none