Transaction Problems - Learning Module

Loading content...

0/241

Deadlock Detection

The Deadlock Problem

Deadlocks are the nemesis of lock-based concurrency control. Two or more transactions become permanently stuck, each waiting for the other to release locks. Without intervention, the system grinds to a halt.

Deadlock problems are interview favorites because they test your understanding of concurrency, graph algorithms, and system design trade-offs. You'll be asked to detect deadlocks, explain prevention strategies, and reason about which transaction to abort.

This page gives you complete mastery of deadlock theory and practice, preparing you to handle any deadlock-related interview question with confidence.

What You Will Master

By completing this page, you will be able to: (1) Understand the four necessary conditions for deadlock; (2) Construct wait-for graphs and detect cycles; (3) Apply deadlock prevention techniques (wound-wait, wait-die); (4) Analyze deadlock avoidance strategies; (5) Choose optimal victim transactions for deadlock resolution.

Understanding Deadlock

What is Deadlock?

A deadlock is a situation where a set of transactions are blocked forever, each waiting for a lock held by another transaction in the set. No transaction can proceed, and without intervention, they will wait indefinitely.

The Classic Deadlock Scenario

T₁: holds X(A), waiting for X(B)
T₂: holds X(B), waiting for X(A)

T₁ cannot proceed until T₂ releases B. T₂ cannot proceed until T₁ releases A. Neither can make progress—they're deadlocked.

The Four Necessary Conditions (Coffman Conditions)

For a deadlock to occur, ALL four conditions must hold simultaneously:

Coffman Conditions for Deadlock

•Mutual Exclusion: Resources (locks) cannot be shared—if one transaction holds an exclusive lock, others cannot access the resource.
•Hold and Wait: A transaction holds at least one resource while waiting for additional resources held by other transactions.
•No Preemption: Resources cannot be forcibly taken from a transaction—they must be released voluntarily.
•Circular Wait: A circular chain of transactions exists, where each transaction waits for a resource held by the next transaction in the chain.

Breaking any one condition prevents deadlock. Different strategies target different conditions:

Lock ordering prevents circular wait
Lock timeouts break hold-and-wait
Transaction abort enables preemption
Predeclaration of all locks eliminates hold-and-wait

Deadlock vs. Livelock

In a deadlock, transactions are blocked and do nothing. In a livelock, transactions keep running (aborting and retrying) but make no progress. Both are problematic, but they require different solutions.

Wait-For Graphs

The wait-for graph is the standard tool for deadlock detection. It's analogous to the precedence graph for serializability—if there's a cycle, there's a problem.

Construction Algorithm

Step 1: Create Nodes

One node for each active transaction (transactions that hold locks or are waiting for locks)

Step 2: Create Edges

For each lock request where T_i is waiting for a lock held by T_j:
Add a directed edge from T_i to T_j
(T_i → T_j means "T_i is waiting for T_j")

Step 3: Detect Cycles

If the graph contains a cycle → Deadlock exists
The transactions in the cycle are the deadlocked set

Wait-For Graph ConstructionBuild the wait-for graph for the following scenario and determine if there's a deadlock.

Input

Current state:
• T₁ holds X(A), waiting for X(B)
• T₂ holds X(B), X(C), waiting for X(D)
• T₃ holds X(D), waiting for X(A)
• T₄ holds X(E), waiting for X(C)

Output

Wait-For Graph Edges:
• T₁ → T₂ (T₁ waits for B, held by T₂)
• T₂ → T₃ (T₂ waits for D, held by T₃)
• T₃ → T₁ (T₃ waits for A, held by T₁)
• T₄ → T₂ (T₄ waits for C, held by T₂)

Graph:
T₁ → T₂ → T₃ → T₁ (CYCLE!)
T₄ → T₂

✓ Deadlock detected: T₁, T₂, T₃ are in a deadlock cycle
✓ T₄ is only blocked, not deadlocked (will proceed once T₂ releases C)

wait_for_graph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def build_wait_for_graph(lock_state, wait_requests):
    """
    Build wait-for graph from current lock state and pending requests.
    
    Args:
        lock_state: Dict[item] -> transaction holding the lock
        wait_requests: List[(waiting_txn, requested_item)]
    
    Returns:
        Adjacency list of wait-for relationships
    """
    from collections import defaultdict
    
    graph = defaultdict(set)
    
    for waiting_txn, item in wait_requests:
        if item in lock_state:
            holding_txn = lock_state[item]
            if waiting_txn != holding_txn:
                graph[waiting_txn].add(holding_txn)
    
    return graph
 
def detect_deadlock(graph, transactions):
    """
    Detect if deadlock exists using DFS cycle detection.
    
    Returns:
        (has_deadlock, cycle_transactions)
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {t: WHITE for t in transactions}
    
    def dfs(node, path):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                # Found cycle - return transactions in cycle
                cycle_start = path.index(neighbor)
                return True, path[cycle_start:]
            if color[neighbor] == WHITE:
                result = dfs(neighbor, path + [neighbor])
                if result[0]:
                    return result
        color[node] = BLACK
        return False, []
    
    for t in transactions:
        if color[t] == WHITE:
            result = dfs(t, [t])
            if result[0]:
                return result
    
    return False, []
 
# Example usage
lock_state = {'A': 'T1', 'B': 'T2', 'C': 'T2', 'D': 'T3', 'E': 'T4'}
wait_requests = [('T1', 'B'), ('T2', 'D'), ('T3', 'A'), ('T4', 'C')]
transactions = {'T1', 'T2', 'T3', 'T4'}
 
graph = build_wait_for_graph(lock_state, wait_requests)
has_deadlock, cycle = detect_deadlock(graph, transactions)
 
print(f"Deadlock: {has_deadlock}")  # True
print(f"Cycle: {cycle}")  # ['T1', 'T2', 'T3'] or similar

Multiple Cycles

A wait-for graph can have multiple cycles. Standard DFS will find one cycle, but resolving it (by aborting a transaction) may reveal additional cycles that were hidden. Real systems run cycle detection iteratively until no cycles remain.

Deadlock Prevention Strategies

Prevention strategies ensure deadlocks never occur by breaking one of the four necessary conditions before any transaction enters a wait state.

Strategy 1: Lock Ordering

Idea: Define a global ordering on data items. Transactions must acquire locks in that order.

Example: If the ordering is A < B < C, then any transaction needing locks on A and C must request A first, then C. Never C before A.

Effect: Prevents circular wait—any waiting chain follows the total order, so cycles are impossible.

Limitation: Requires knowing all locks needed in advance; not always practical.

Strategy 2: Predeclaration

Idea: Each transaction declares all locks it will need before starting. System either grants all or none.

Effect: Prevents hold-and-wait—transactions never hold locks while waiting.

Limitation: Many applications don't know lock needs in advance.

Strategy 3: Timestamp-Based Prevention

These protocols use transaction timestamps to make consistent decisions about who waits and who aborts. They prevent deadlocks by ensuring wait relationships never form cycles.

Wait-Die Protocol (Non-preemptive)

Rule: "Older waits for younger; younger dies"

If T_i (requesting) is older than T_j (holding): T_i waits
If T_i (requesting) is younger than T_j (holding): T_i aborts (dies) and restarts with same timestamp

Result: Wait edges only go from older → younger, so no cycle possible.

Wound-Wait Protocol (Preemptive)

Rule: "Older wounds younger; younger waits"

If T_i (requesting) is older than T_j (holding): T_i wounds T_j (T_j is aborted)
If T_i (requesting) is younger than T_j (holding): T_i waits

Result: Wait edges only go from younger → older, so no cycle possible.

Wait-Die vs Wound-Wait Comparison
Scenario	Wait-Die	Wound-Wait
Older requests from younger	Older waits	Older wounds (aborts younger)
Younger requests from older	Younger dies (aborts)	Younger waits
Who gets aborted	Younger transactions	Younger transactions
Who waits	Older transactions	Younger transactions
Preemptive	No (requester may abort)	Yes (holder may be aborted)
Advantage	Less disruption (holder never aborted)	No starvation (older always wins)

Timestamp Preservation on Restart

When a transaction aborts and restarts under these protocols, it KEEPS its original timestamp. This prevents starvation—eventually, the transaction becomes 'old' enough to succeed without being aborted.

Deadlock Avoidance

Avoidance strategies allow deadlock conditions to exist but carefully choose which lock requests to grant to ensure a deadlock never actually forms.

The Banker's Algorithm (Conceptual)

Classic avoidance: Before granting a lock, simulate what happens. If granting could lead to a state where deadlock is inevitable, don't grant (force transaction to wait).

In database terms: Before T_i acquires lock on X, check if a safe sequence exists—a sequence in which all transactions can still complete.

Safe State Analysis

A state is safe if there exists some order to complete all current transactions, granting their remaining lock requests, without deadlock.

Example:

System resources: 10 units total
T₁: holds 5, needs max 8 → still needs 3
T₂: holds 3, needs max 9 → still needs 6
Available: 2 units

Can we complete?
- Give T₁ remaining 2 → T₁ has 7 (not enough for max 8) → Wait
- Actually: T₁ needs 3 more, we have 2 → If nothing else, unsafe?

Let's think differently:
- Available: 2, T₁ needs 3 more → Cannot complete T₁ first
- Available: 2, T₂ needs 6 more → Cannot complete T₂ first
→ UNSAFE STATE (potential deadlock)

Timeout-Based Avoidance

A simpler, practical approach used in most real systems:

Mechanism: If a transaction waits for a lock longer than a threshold (e.g., 5 seconds), assume potential deadlock and abort the transaction.

Advantages:

Simple to implement
No need for complex analysis
Works with any access pattern

Disadvantages:

May abort transactions that aren't actually deadlocked (false positives)
Threshold tuning is tricky:
- Too short → Unnecessary aborts
- Too long → Slow deadlock resolution

Most Systems Use Timeouts

Despite their theoretical elegance, sophisticated avoidance algorithms are rarely used in production databases. Simple timeouts combined with occasional wait-for graph checks are the norm. The overhead of perfect avoidance usually isn't worth it.

Deadlock Detection and Resolution

Detection strategies allow deadlocks to occur, then detect and break them. This is the most common approach in modern database systems.

Detection Timing

Continuous detection: Check for deadlocks every time a wait occurs.

Pro: Immediate detection
Con: High overhead

Periodic detection: Check at regular intervals (e.g., every 1 second).

Pro: Lower overhead
Con: Delayed detection, transactions wait longer

Triggered detection: Check only when symptoms appear (e.g., many transactions waiting).

Pro: Minimal overhead during normal operation
Con: May miss some deadlocks initially

Resolution: Victim Selection

Once a deadlock is detected, at least one transaction must be aborted (rolled back) to break the cycle. The aborted transaction is called the victim.

Victim Selection Criteria

•Minimum Work Lost: Choose the transaction that has done the least work (fewest writes, shortest runtime).
•Minimum Restart Cost: Choose the transaction cheapest to restart (e.g., already close to starting).
•Minimum Rollback Cascading: Choose the transaction whose abort causes the fewest cascading aborts.
•Resource Holding: Choose the transaction holding the most resources (releases the most locks).
•Fairness/Priority: Consider user priorities; don't always pick the same transaction.
•Number of Cycles: Choose the transaction appearing in the most cycles (breaks multiple deadlocks).

Rollback Types

Total Rollback: Abort the victim completely and restart from the beginning.

Simpler to implement
May lose more work

Partial Rollback: Roll back the victim just enough to release the lock causing the deadlock.

Preserves more work
Requires savepoints and more complex recovery
May cause repeated deadlocks if not careful

Starvation Prevention

If the same transaction is repeatedly chosen as victim, it may never complete (starvation).

Solution: Track how many times a transaction has been victimized. Include this count in victim selection—after N times, give the transaction priority immunity.

Interview Answer Structure

When asked about deadlock resolution, structure your answer: (1) Detect via wait-for graph (show cycle), (2) Explain victim selection heuristics, (3) Discuss total vs. partial rollback, (4) Mention starvation prevention. This demonstrates comprehensive understanding.

Comprehensive Worked Examples

Let's work through several complete deadlock analysis problems.

Problem: Given the following schedule, determine when/if a deadlock occurs.

Time    T₁         T₂         T₃
1       X(A)
2                  X(B)
3                             X(C)
4       req X(B)   
        [wait]
5                  req X(C)   
                   [wait]
6                             req X(A)
                              [wait]

Analysis:

After time 6:

T₁ holds X(A), waits for X(B) → T₁ → T₂
T₂ holds X(B), waits for X(C) → T₂ → T₃
T₃ holds X(C), waits for X(A) → T₃ → T₁

Wait-for graph: T₁ → T₂ → T₃ → T₁ (CYCLE)

Result: Deadlock detected at time 6 when T₃ requests X(A).

Resolution: Abort one transaction (e.g., T₃ as it has done least work if we choose that criterion), release X(C). T₂ gets X(C), completes, releases X(B). T₁ gets X(B), completes.

Interview Problem Patterns

Deadlock problems in interviews follow recognizable patterns. Here's how to approach each type systematically.

Type 1: Build Wait-For Graph

•Given lock state and wait queue
•Draw graph: node per transaction
•Edge: waiting → holding
•Report if cycle exists
•Time target: 2-3 minutes

Type 2: Apply Prevention Protocol

•Given timestamps and requests
•Apply Wait-Die or Wound-Wait
•Show who waits, who aborts
•Trace schedule to completion
•Time target: 4-5 minutes

Type 3: Victim Selection

•Given deadlock and transaction info
•Apply multiple selection criteria
•Justify your choice
•Discuss starvation prevention
•Time target: 3-4 minutes

Type 4: Comparison Questions

•'Compare Wait-Die vs Wound-Wait'
•'Prevention vs Detection trade-offs'
•'Why use timeouts in practice?'
•Conceptual, design-focused
•Time target: 2-3 minutes explanation

Common Gotchas

(1) In Wait-Die/Wound-Wait, transactions restart with the SAME timestamp. (2) Younger means higher timestamp (started later). (3) Wait-Die never aborts the holder; Wound-Wait can. (4) A long wait isn't deadlock if no cycle exists—it's just blocking.

Summary: Mastering Deadlock Detection

Deadlock handling is essential for any lock-based concurrency control system. Let's consolidate the essential skills:

Key Takeaways

•Deadlocks require four conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait. Break any one to prevent deadlock.
•Wait-for graphs detect deadlocks: build nodes for transactions, edges for wait relationships, check for cycles.
•Wait-Die (older waits, younger dies) and Wound-Wait (older wounds, younger waits) prevent deadlock via timestamps.
•Victim selection considers work done, restart cost, resources held, and starvation fairness.
•Practical systems typically use timeout-based detection combined with periodic wait-for graph checks.

What's Next:

With deadlock detection mastered, we'll tackle Recovery Scenarios—understanding how database systems recover from failures, the role of logging, ARIES recovery algorithm, and how to reason about recovery-related interview problems.

Page Complete

You now have comprehensive knowledge of deadlock theory and practice. You can construct wait-for graphs, apply prevention protocols, select optimal victims, and reason about the trade-offs between different deadlock handling strategies. This knowledge is directly applicable to system design interviews and real database implementation.