Deadlock Definition

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

// Classic two-process deadlock scenario
// Process P1
pthread_mutex_lock(&mutex_A);     // P1 acquires A
// Context switch occurs here
pthread_mutex_lock(&mutex_B);     // P1 waits for B (held by P2)
// ... critical section ...
pthread_mutex_unlock(&mutex_B);
pthread_mutex_unlock(&mutex_A);
 
// Process P2
pthread_mutex_lock(&mutex_B);     // P2 acquires B
// Context switch occurs here  
pthread_mutex_lock(&mutex_A);     // P2 waits for A (held by P1)
// ... critical section ...
pthread_mutex_unlock(&mutex_A);
pthread_mutex_unlock(&mutex_B);
 
/*
 * DEADLOCK STATE:
 * ┌─────────┐         ┌─────────┐
 * │   P1    │ waiting │   P2    │
 * │ holds A ├────────►│ holds B │
 * └────▲────┘    B    └────┬────┘
 *      │                   │
 *      │     waiting A     │
 *      └───────────────────┘
 * 
 * Neither process can proceed.
 * This is a PERMANENT state unless external intervention.
 */

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

/*
 * SIMPLE BLOCKING - Will Eventually Resolve
 */
// Process A
pthread_mutex_lock(&mutex);    // A acquires mutex
// ... do work ...
pthread_mutex_unlock(&mutex);  // A will eventually release
 
// Process B
pthread_mutex_lock(&mutex);    // B waits, but A will release
// B eventually proceeds
 
/*
 * DEADLOCK - Will Never Resolve
 */
// Process A                       // Process B
pthread_mutex_lock(&m1);           pthread_mutex_lock(&m2);
pthread_mutex_lock(&m2);  // waits pthread_mutex_lock(&m1);  // waits
// A can only proceed if B         // B can only proceed if A
// releases m2, but B is           // releases m1, but A is
// waiting for m1 from A           // waiting for m2 from B
 
/*
 * Key insight: In simple blocking, the dependency is one-directional.
 * In deadlock, the dependency is circular/bidirectional.
 */

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

#include <stdbool.h>
#include <string.h>
 
#define MAX_PROCESSES 100
 
// Wait-for graph represented as adjacency matrix
// graph[i][j] = 1 means process i is waiting for process j
int graph[MAX_PROCESSES][MAX_PROCESSES];
int num_processes;
 
// DFS colors for cycle detection
typedef enum { WHITE, GRAY, BLACK } Color;
 
// Recursive DFS to detect cycle
bool dfs_detect_cycle(int vertex, Color* colors) {
    colors[vertex] = GRAY;  // Mark as being processed
    
    for (int neighbor = 0; neighbor < num_processes; neighbor++) {
        if (graph[vertex][neighbor]) {
            if (colors[neighbor] == GRAY) {
                // Back edge found - cycle exists!
                return true;
            }
            if (colors[neighbor] == WHITE) {
                if (dfs_detect_cycle(neighbor, colors)) {
                    return true;
                }
            }
        }
    }
    
    colors[vertex] = BLACK;  // Mark as fully processed
    return false;
}
 
// Main deadlock detection function
bool detect_deadlock() {
    Color colors[MAX_PROCESSES];
    memset(colors, WHITE, sizeof(colors));
    
    // Check from each unvisited vertex
    for (int i = 0; i < num_processes; i++) {
        if (colors[i] == WHITE) {
            if (dfs_detect_cycle(i, colors)) {
                return true;  // Deadlock detected
            }
        }
    }
    return false;  // No deadlock
}
 
/*
 * Time Complexity: O(V + E) where V = processes, E = wait edges
 * Space Complexity: O(V) for the color array
 * 
 * In practice, real OS deadlock detectors also track which
 * specific processes are in the cycle for recovery purposes.
 */

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

-- Transaction T1                    -- Transaction T2
BEGIN TRANSACTION;                   BEGIN TRANSACTION;
UPDATE accounts SET balance = 100    UPDATE accounts SET balance = 200
WHERE id = 'A';  -- Locks row A      WHERE id = 'B';  -- Locks row B
 
-- At this point, T1 holds lock on A, T2 holds lock on B
 
UPDATE accounts SET balance = 150    UPDATE accounts SET balance = 250
WHERE id = 'B';  -- Waits for T2     WHERE id = 'A';  -- Waits for T1
                                     
-- DEADLOCK! Neither can proceed
 
/*
 * Database Resolution:
 * 
 * DBMS detects cycle in lock wait-for graph.
 * Selects one transaction as "victim" based on:
 *   - Transaction age (younger preferred as victim)
 *   - Work done (less work = better victim)
 *   - Locks held (fewer locks = better victim)
 * 
 * Victim transaction is ROLLED BACK, releasing its locks.
 * Surviving transaction proceeds.
 * Application receives error and should retry.
 */

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

"""
Formal invariants for deadlock analysis.
 
These formalizations help reason about system correctness
and can be checked by model checkers like TLA+ or SPIN.
"""
 
class SystemState:
    """Represents a snapshot of process/resource state."""
    
    def __init__(self):
        self.holds = {}      # Process -> set of resources held
        self.waits = {}      # Process -> resource waiting for (or None)
        
    def is_safe_state(self):
        """
        A state is SAFE if there exists a sequence of process terminations
        (a safe sequence) that can complete all processes.
        
        Safe => No deadlock possible if we stay in safe states
        Unsafe => Deadlock might occur (not guaranteed)
        """
        # Simulate process completion to find if safe sequence exists
        available = self.compute_available_resources()
        work = available.copy()
        finish = {p: False for p in self.processes}
        
        changed = True
        while changed:
            changed = False
            for p in self.processes:
                if not finish[p]:
                    if self.can_complete(p, work):
                        # Process can complete, release its resources
                        for r in self.holds.get(p, []):
                            work[r] = work.get(r, 0) + 1
                        finish[p] = True
                        changed = True
        
        return all(finish.values())
    
    def has_deadlock(self):
        """
        Deadlock exists iff there is a cycle in the wait-for graph.
        
        Invariant: No cycle => No deadlock (always)
        Invariant: Has cycle + single instance resources => Deadlock
        Invariant: Has cycle + multiple instances => Maybe deadlock
        """
        # Build wait-for graph
        wait_for = {}
        for p, resource in self.waits.items():
            if resource:
                holder = self.find_holder(resource)
                if holder:
                    wait_for[p] = holder
        
        # Check for cycle using DFS
        return self._has_cycle(wait_for)
    
    def _has_cycle(self, graph):
        """DFS-based cycle detection."""
        visited = set()
        rec_stack = set()
        
        def dfs(node):
            visited.add(node)
            rec_stack.add(node)
            
            neighbor = graph.get(node)
            if neighbor:
                if neighbor in rec_stack:
                    return True  # Cycle found
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True
            
            rec_stack.remove(node)
            return False
        
        for node in graph:
            if node not in visited:
                if dfs(node):
                    return True
        return False