Detection Algorithms

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

# Conceptual representation of a wait-for graph
 
class WaitForGraph:
    """
    Wait-For Graph for deadlock detection.
    
    Nodes: Processes (identified by process IDs)
    Edges: P_i -> P_j means "P_i is waiting for P_j"
    
    Deadlock exists iff there is a cycle in this graph.
    """
    
    def __init__(self, num_processes: int):
        self.num_processes = num_processes
        # adjacency list: process -> set of processes it waits for
        self.waits_for: dict[int, set[int]] = {
            i: set() for i in range(num_processes)
        }
    
    def add_wait_edge(self, waiting: int, holding: int):
        """
        Record that 'waiting' is waiting for a resource held by 'holding'.
        This creates an edge: waiting -> holding
        """
        self.waits_for[waiting].add(holding)
    
    def remove_wait_edge(self, waiting: int, holding: int):
        """Remove a wait edge (e.g., when resource is granted)."""
        self.waits_for[waiting].discard(holding)
    
    def clear_edges_for(self, process: int):
        """Process completed or terminated - remove all its edges."""
        self.waits_for[process].clear()
        for p in self.waits_for:
            self.waits_for[p].discard(process)
    
    def has_cycle(self) -> bool:
        """
        Detect if there's a cycle in the graph.
        If a cycle exists, deadlock is present.
        """
        # Standard DFS-based cycle detection
        WHITE, GRAY, BLACK = 0, 1, 2
        color = {p: WHITE for p in range(self.num_processes)}
        
        def dfs(node: int) -> bool:
            color[node] = GRAY  # Currently exploring
            
            for neighbor in self.waits_for[node]:
                if color[neighbor] == GRAY:
                    # Back edge! We found a cycle
                    return True
                if color[neighbor] == WHITE:
                    if dfs(neighbor):
                        return True
            
            color[node] = BLACK  # Fully explored
            return False
        
        # Check from each node
        for process in range(self.num_processes):
            if color[process] == WHITE:
                if dfs(process):
                    return True
        
        return False

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
86
87
88
89
90
91
92
93
94

#include <stdint.h>
#include <stdbool.h>
#include <string.h>
 
#define MAX_PROCESSES 256
#define MAX_RESOURCE_TYPES 64
 
/**
 * Resource allocation tracking for deadlock detection.
 * 
 * The kernel maintains these structures and updates them
 * on every resource allocation/deallocation/request.
 */
 
// Total instances of each resource type in the system
uint32_t total_resources[MAX_RESOURCE_TYPES];
 
// Currently available (unallocated) instances of each type
uint32_t available[MAX_RESOURCE_TYPES];
 
// Allocation matrix: allocation[p][r] = instances of r held by p
uint32_t allocation[MAX_PROCESSES][MAX_RESOURCE_TYPES];
 
// Request matrix: request[p][r] = instances of r that p is waiting for
// (Zero means not waiting for that resource type)
uint32_t request[MAX_PROCESSES][MAX_RESOURCE_TYPES];
 
// Number of active processes and resource types
int num_processes;
int num_resource_types;
 
/**
 * Record a resource allocation.
 * Called when a resource request is granted.
 */
void record_allocation(int process, int resource_type, uint32_t count) {
    allocation[process][resource_type] += count;
    available[resource_type] -= count;
    
    // If this was a pending request, clear it
    if (request[process][resource_type] >= count) {
        request[process][resource_type] -= count;
    } else {
        request[process][resource_type] = 0;
    }
}
 
/**
 * Record a resource release.
 * Called when a process releases resources.
 */
void record_release(int process, int resource_type, uint32_t count) {
    if (allocation[process][resource_type] >= count) {
        allocation[process][resource_type] -= count;
        available[resource_type] += count;
    }
}
 
/**
 * Record a blocked request.
 * Called when a resource request cannot be immediately satisfied.
 */
void record_pending_request(int process, int resource_type, uint32_t count) {
    request[process][resource_type] = count;
}
 
/**
 * Construct the wait-for graph from allocation and request matrices.
 * 
 * wait_for[i][j] = true iff process i is waiting for process j
 * 
 * This is O(P^2 * R) where P = processes, R = resource types.
 */
void build_wait_for_graph(bool wait_for[MAX_PROCESSES][MAX_PROCESSES]) {
    // Clear the graph
    memset(wait_for, 0, sizeof(bool) * MAX_PROCESSES * MAX_PROCESSES);
    
    // For each process that's waiting for something
    for (int i = 0; i < num_processes; i++) {
        for (int r = 0; r < num_resource_types; r++) {
            if (request[i][r] > 0) {
                // Process i is waiting for resource type r
                // Find all processes j that hold instances of r
                for (int j = 0; j < num_processes; j++) {
                    if (j != i && allocation[j][r] > 0) {
                        // Process j holds resource r, process i waits for r
                        // Therefore: i waits for j
                        wait_for[i][j] = true;
                    }
                }
            }
        }
    }
}

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
86
87
88
89

def detect_deadlock_reduction(
    num_processes: int,
    num_resource_types: int,
    available: list[int],          # available[r] = free instances of r
    allocation: list[list[int]],  # allocation[p][r] = held by p
    request: list[list[int]]      # request[p][r] = waiting for by p
) -> list[int]:
    """
    Deadlock detection via simulation/reduction algorithm.
    
    Returns: List of deadlocked process IDs, or empty list if no deadlock.
    
    Algorithm:
    1. Start with a "work" vector = available resources
    2. Find processes whose requests can be satisfied with "work"
    3. Simulate their completion: add their held resources to "work"
    4. Repeat until no more processes can complete
    5. Any remaining unfinished processes are deadlocked
    """
    
    # Work vector: simulates currently available resources
    work = available.copy()
    
    # Track which processes have "finished" in our simulation
    finished = [False] * num_processes
    
    # Repeatedly find processes that can complete
    made_progress = True
    while made_progress:
        made_progress = False
        
        for p in range(num_processes):
            if finished[p]:
                continue  # Already simulated completion
            
            # Can process p's request be satisfied?
            can_satisfy = True
            for r in range(num_resource_types):
                if request[p][r] > work[r]:
                    can_satisfy = False
                    break
            
            if can_satisfy:
                # Simulate process p completing:
                # It releases all resources it holds
                for r in range(num_resource_types):
                    work[r] += allocation[p][r]
                
                finished[p] = True
                made_progress = True
                # Note: don't break, check all processes each round
    
    # Any process not "finished" is deadlocked
    deadlocked = [p for p in range(num_processes) if not finished[p]]
    
    return deadlocked
 
 
# Example scenario
if __name__ == "__main__":
    # 5 processes, 3 resource types
    # Resource totals: [7, 2, 6]
    
    available = [0, 0, 0]  # All resources currently allocated
    
    allocation = [
        [0, 1, 0],  # P0 holds: 0 of R0, 1 of R1, 0 of R2
        [2, 0, 0],  # P1 holds: 2 of R0, 0 of R1, 0 of R2
        [3, 0, 3],  # P2 holds: 3R0, 0R1, 3R2
        [2, 1, 1],  # P3 holds: 2R0, 1R1, 1R2
        [0, 0, 2],  # P4 holds: 0R0, 0R1, 2R2
    ]
    
    request = [
        [0, 0, 0],  # P0 not waiting
        [2, 0, 2],  # P1 waiting for: 2R0, 0R1, 2R2
        [0, 0, 0],  # P2 not waiting
        [1, 0, 0],  # P3 waiting for: 1R0
        [0, 0, 2],  # P4 waiting for: 2R2
    ]
    
    deadlocked = detect_deadlock_reduction(
        5, 3, available, allocation, request
    )
    
    if deadlocked:
        print(f"DEADLOCK DETECTED! Processes: {deadlocked}")
    else:
        print("No deadlock - system can make progress")

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
86

#include <vector>
#include <queue>
#include <algorithm>
 
struct DeadlockDetector {
    int num_processes;
    int num_resources;
    
    std::vector<std::vector<int>> allocation;  // allocation[p][r]
    std::vector<std::vector<int>> request;     // request[p][r]
    std::vector<int> available;
    
    /**
     * Optimized detection using a work queue.
     * 
     * Time: O(n * m) in best case, O(n^2 * m) worst case
     *       where n = processes, m = resource types
     * Space: O(n)
     */
    std::vector<int> detect_deadlock() {
        std::vector<int> work = available;
        std::vector<bool> finished(num_processes, false);
        
        // Queue of processes that *might* be able to complete
        // (processes whose requests are potentially satisfiable)
        std::queue<int> candidates;
        
        // Initially, any process with all-zero requests can complete
        // (they can't be waiting for anything)
        for (int p = 0; p < num_processes; p++) {
            if (request_is_zero(p) || can_satisfy(p, work)) {
                candidates.push(p);
            }
        }
        
        while (!candidates.empty()) {
            int p = candidates.front();
            candidates.pop();
            
            if (finished[p]) continue;  // Already processed
            
            // Recheck if we can satisfy (work may have changed)
            if (!can_satisfy(p, work)) continue;
            
            // Process p completes: release its resources
            finished[p] = true;
            for (int r = 0; r < num_resources; r++) {
                work[r] += allocation[p][r];
            }
            
            // Resources released - some waiting processes might now be able to proceed
            // Note: In a sophisticated implementation, we'd track which processes
            // wait for which resources to efficiently wake only relevant ones.
            for (int q = 0; q < num_processes; q++) {
                if (!finished[q] && can_satisfy(q, work)) {
                    candidates.push(q);
                }
            }
        }
        
        // Collect deadlocked processes
        std::vector<int> deadlocked;
        for (int p = 0; p < num_processes; p++) {
            if (!finished[p]) {
                deadlocked.push_back(p);
            }
        }
        
        return deadlocked;
    }
    
private:
    bool can_satisfy(int p, const std::vector<int>& work) {
        for (int r = 0; r < num_resources; r++) {
            if (request[p][r] > work[r]) return false;
        }
        return true;
    }
    
    bool request_is_zero(int p) {
        for (int r = 0; r < num_resources; r++) {
            if (request[p][r] > 0) return false;
        }
        return true;
    }
};

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

/*
 * Conceptual kernel deadlock detection architecture
 * (Simplified for educational purposes)
 */
 
#include <linux/spinlock.h>
#include <linux/workqueue.h>
#include <linux/timer.h>
 
/* Global lock protecting detection state */
static DEFINE_SPINLOCK(detection_lock);
 
/* Detection work - runs in process context */
static struct delayed_work detection_work;
 
/* Detection interval (jiffies) */
static unsigned long detection_interval = HZ * 30;  /* 30 seconds */
 
/* Resource tracking structures */
static struct {
    uint32_t allocation[NR_CPUS][MAX_RESOURCES];
    uint32_t request[NR_CPUS][MAX_RESOURCES];
    uint32_t available[MAX_RESOURCES];
    atomic_t sequence;  /* For snapshot consistency */
} resource_state;
 
/**
 * Called when a resource request blocks.
 * Updates the request matrix.
 */
void deadlock_record_block(struct task_struct *task, int resource, int count)
{
    unsigned long flags;
    
    spin_lock_irqsave(&detection_lock, flags);
    resource_state.request[task->pid % NR_CPUS][resource] = count;
    atomic_inc(&resource_state.sequence);
    spin_unlock_irqrestore(&detection_lock, flags);
    
    /* Optionally trigger immediate detection for this task */
    if (sysctl_deadlock_detect_on_block) {
        schedule_work(&detection_work.work);
    }
}
 
/**
 * Called when a resource is granted.
 * Updates allocation and clears request.
 */
void deadlock_record_grant(struct task_struct *task, int resource, int count)
{
    unsigned long flags;
    
    spin_lock_irqsave(&detection_lock, flags);
    resource_state.allocation[task->pid % NR_CPUS][resource] += count;
    resource_state.request[task->pid % NR_CPUS][resource] = 0;
    resource_state.available[resource] -= count;
    atomic_inc(&resource_state.sequence);
    spin_unlock_irqrestore(&detection_lock, flags);
}
 
/**
 * Called when a resource is released.
 */
void deadlock_record_release(struct task_struct *task, int resource, int count)
{
    unsigned long flags;
    
    spin_lock_irqsave(&detection_lock, flags);
    resource_state.allocation[task->pid % NR_CPUS][resource] -= count;
    resource_state.available[resource] += count;
    atomic_inc(&resource_state.sequence);
    spin_unlock_irqrestore(&detection_lock, flags);
}
 
/**
 * The detection worker function.
 * Runs periodically or on-demand.
 */
static void detection_worker(struct work_struct *work)
{
    unsigned long flags;
    int seq_before, seq_after;
    bool deadlock_found = false;
    
    /* Take a consistent snapshot */
    do {
        seq_before = atomic_read(&resource_state.sequence);
        
        spin_lock_irqsave(&detection_lock, flags);
        /* Copy state for analysis */
        memcpy(snapshot.allocation, resource_state.allocation, ...);
        memcpy(snapshot.request, resource_state.request, ...);
        memcpy(snapshot.available, resource_state.available, ...);
        spin_unlock_irqrestore(&detection_lock, flags);
        
        seq_after = atomic_read(&resource_state.sequence);
    } while (seq_before != seq_after);  /* Retry if state changed */
    
    /* Run detection on snapshot */
    deadlock_found = detect_deadlock(&snapshot);
    
    if (deadlock_found) {
        handle_detected_deadlock(&snapshot);
    }
    
    /* Schedule next detection */
    schedule_delayed_work(&detection_work, detection_interval);
}
 
/**
 * Initialize deadlock detection subsystem.
 */
void __init deadlock_detection_init(void)
{
    INIT_DELAYED_WORK(&detection_work, detection_worker);
    schedule_delayed_work(&detection_work, detection_interval);
    
    printk(KERN_INFO "Deadlock detection initialized, interval=%lu ms
",
           jiffies_to_msecs(detection_interval));
}