Deadlock Detection (Wait-For Graph)

Deadlock in a database

Transaction T1 locks row A and then asks for row B. Meanwhile T2 holds B and asks for A. Each waits for the other forever: a deadlock. Locking is required for isolation, so deadlocks must be handled rather than ignored.

The wait-for graph

Make one node per transaction. Draw an arrow Ti → Tj when Ti is waiting for a lock that Tj holds.

There is a deadlock if and only if the graph contains a cycle.

Detection

for each transaction T not yet visited:
    DFS(T), remembering the current path
    if DFS reaches a transaction already on the path:
        cycle found → deadlock

Databases run this check periodically or whenever a lock request has to wait. The cost is O(V + E).

Recovery: pick a victim

Break the cycle by aborting one transaction in it. Common victim choices:

• the youngest transaction (least work lost),
• the one that has done the least work,
• the one holding the fewest locks.

The victim is rolled back, its locks are released, the others continue, and the victim is restarted. To avoid starving the same transaction, systems count how often it was chosen.

Prevention instead of detection

Timestamp-based rules never allow a cycle:

Code

def find_cycle(waits_for):
    state, path = {}, []
    def dfs(u):
        state[u] = 'on-path'
        path.append(u)
        for v in waits_for.get(u, []):
            if state.get(v) == 'on-path':
                return path[path.index(v):]
            if v not in state:
                cycle = dfs(v)
                if cycle:
                    return cycle
        path.pop()
        state[u] = 'done'
        return None
    for t in list(waits_for):
        if t not in state:
            cycle = dfs(t)
            if cycle:
                return cycle
    return None

print(find_cycle({'T1': ['T2'], 'T2': ['T3'], 'T3': ['T1'], 'T4': ['T1']}))  # ['T1', 'T2', 'T3']

Common mistakes

• Thinking that waiting means deadlock. A chain of waits without a cycle ends when the first transaction commits.
• Aborting a transaction outside the cycle, which does not help.
• Forgetting to remove the victim’s edges and re-check. Several cycles can exist.
• Confusing this with the Banker’s algorithm: detection finds a deadlock after it happens, while the Banker’s algorithm avoids it.