Multiple Instance Detection

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

from dataclasses import dataclass, field
from typing import List
import numpy as np
 
@dataclass
class MultiInstanceState:
    """
    Complete state for multiple-instance deadlock detection.
    
    Invariants maintained:
    1. Available + sum(Allocation across all processes) = Total resources
    2. Request[i][j] >= 0 for all i, j
    3. Allocation[i][j] >= 0 for all i, j
    4. Available[j] >= 0 for all j
    """
    num_processes: int
    num_resource_types: int
    
    # Total instances of each resource type (for validation)
    total: np.ndarray = field(default_factory=lambda: np.array([]))
    
    # Currently available (unallocated)
    available: np.ndarray = field(default_factory=lambda: np.array([]))
    
    # allocation[i][j] = instances of Rj held by Pi
    allocation: np.ndarray = field(default_factory=lambda: np.array([]))
    
    # request[i][j] = instances of Rj that Pi is waiting for
    request: np.ndarray = field(default_factory=lambda: np.array([]))
    
    def __post_init__(self):
        n, m = self.num_processes, self.num_resource_types
        if self.total.size == 0:
            self.total = np.zeros(m, dtype=np.int32)
        if self.available.size == 0:
            self.available = np.zeros(m, dtype=np.int32)
        if self.allocation.size == 0:
            self.allocation = np.zeros((n, m), dtype=np.int32)
        if self.request.size == 0:
            self.request = np.zeros((n, m), dtype=np.int32)
    
    def validate_invariants(self) -> List[str]:
        """Check that state invariants hold."""
        errors = []
        
        # Check non-negativity
        if np.any(self.available < 0):
            errors.append("Available has negative values")
        if np.any(self.allocation < 0):
            errors.append("Allocation has negative values")
        if np.any(self.request < 0):
            errors.append("Request has negative values")
        
        # Check resource totals
        total_allocated = np.sum(self.allocation, axis=0)
        expected_available = self.total - total_allocated
        if not np.array_equal(self.available, expected_available):
            errors.append(
                f"Available mismatch: have {self.available}, "
                f"expected {expected_available}"
            )
        
        return errors
    
    def print_state(self, title: str = "System State"):
        """Pretty-print the current state."""
        print(f"
{'='*50}")
        print(f"{title}")
        print(f"{'='*50}")
        print(f"Total resources:     {self.total}")
        print(f"Available resources: {self.available}")
        print(f"
Allocation matrix:")
        print(f"{'Process':<10}", end="")
        for j in range(self.num_resource_types):
            print(f"R{j:<4}", end="")
        print()
        for i in range(self.num_processes):
            print(f"P{i:<9}", end="")
            for j in range(self.num_resource_types):
                print(f"{self.allocation[i][j]:<5}", end="")
            print()
        
        print(f"
Request matrix:")
        print(f"{'Process':<10}", end="")
        for j in range(self.num_resource_types):
            print(f"R{j:<4}", end="")
        print()
        for i in range(self.num_processes):
            print(f"P{i:<9}", end="")
            for j in range(self.num_resource_types):
                print(f"{self.request[i][j]:<5}", end="")
            print()
 
 
def create_example_state() -> MultiInstanceState:
    """Create an example state for demonstration."""
    state = MultiInstanceState(
        num_processes=5,
        num_resource_types=3,
    )
    
    # Total resources: [7, 2, 6]
    state.total = np.array([7, 2, 6], dtype=np.int32)
    
    # Current allocation
    state.allocation = np.array([
        [0, 1, 0],  # P0
        [2, 0, 0],  # P1
        [3, 0, 3],  # P2
        [2, 1, 1],  # P3
        [0, 0, 2],  # P4
    ], dtype=np.int32)
    
    # Current requests
    state.request = np.array([
        [0, 0, 0],  # P0: not waiting
        [2, 0, 2],  # P1: waiting for 2 of R0, 2 of R2
        [0, 0, 0],  # P2: not waiting
        [1, 0, 0],  # P3: waiting for 1 of R0
        [0, 0, 2],  # P4: waiting for 2 of R2
    ], dtype=np.int32)
    
    # Calculate available
    state.available = state.total - np.sum(state.allocation, axis=0)
    
    return state
 
 
if __name__ == "__main__":
    state = create_example_state()
    errors = state.validate_invariants()
    if errors:
        print("Invariant violations:", errors)
    else:
        state.print_state("Example Multi-Instance State")

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

import numpy as np
from typing import List, Tuple, Set
from dataclasses import dataclass
 
@dataclass  
class DetectionResult:
    """Result of multiple-instance deadlock detection."""
    has_deadlock: bool
    deadlocked_processes: List[int]
    safe_sequence: List[int]  # Order in which safe processes can complete
    iterations: int           # Number of algorithm iterations
    
def detect_deadlock_multiple(
    num_processes: int,
    num_resources: int,
    available: np.ndarray,
    allocation: np.ndarray,
    request: np.ndarray,
    verbose: bool = False
) -> DetectionResult:
    """
    Detect deadlock in a system with multiple resource instances.
    
    Time Complexity: O(n^2 * m) where n = processes, m = resource types
    Space Complexity: O(n + m)
    
    Args:
        num_processes: Number of processes in the system
        num_resources: Number of resource types
        available: Vector of available instances per resource type
        allocation: Matrix of currently allocated resources
        request: Matrix of current resource requests (blocking)
        verbose: If True, print step-by-step execution
        
    Returns:
        DetectionResult with deadlock information and safe sequence
    """
    # Work vector: available resources we can use
    work = available.copy()
    
    # Finish array: which processes have "completed" in simulation
    # Initially, processes not requesting anything are considered finished
    finish = np.array([
        np.all(request[i] == 0) 
        for i in range(num_processes)
    ])
    
    if verbose:
        print(f"Initial state:")
        print(f"  Work = {work}")
        print(f"  Finish = {finish}")
        print(f"  (True = not waiting or already processed)")
    
    safe_sequence = []
    iterations = 0
    
    # Add already-finished processes to safe sequence
    for i in range(num_processes):
        if finish[i]:
            safe_sequence.append(i)
    
    # Repeat until no progress can be made
    made_progress = True
    while made_progress:
        made_progress = False
        iterations += 1
        
        for i in range(num_processes):
            if finish[i]:
                continue  # Already finished
            
            # Check if Request[i] <= Work (element-wise)
            if np.all(request[i] <= work):
                # This process can complete
                if verbose:
                    print(f"
Iteration {iterations}: Process P{i} can complete")
                    print(f"  Request[{i}] = {request[i]} <= Work = {work}")
                
                # Simulate completion: reclaim allocated resources
                work = work + allocation[i]
                finish[i] = True
                safe_sequence.append(i)
                made_progress = True
                
                if verbose:
                    print(f"  Reclaim Allocation[{i}] = {allocation[i]}")
                    print(f"  New Work = {work}")
    
    # Any process still not finished is deadlocked
    deadlocked = [i for i in range(num_processes) if not finish[i]]
    
    if verbose:
        print(f"
Final state after {iterations} iterations:")
        print(f"  Finish = {finish}")
        print(f"  Safe sequence = {safe_sequence}")
        print(f"  Deadlocked = {deadlocked}")
    
    return DetectionResult(
        has_deadlock=len(deadlocked) > 0,
        deadlocked_processes=deadlocked,
        safe_sequence=safe_sequence,
        iterations=iterations
    )
 
 
def demo_detection():
    """Demonstrate the detection algorithm with examples."""
    
    print("="*60)
    print("EXAMPLE 1: No Deadlock")
    print("="*60)
    
    # State from Silberschatz example
    available1 = np.array([0, 0, 0])
    allocation1 = np.array([
        [0, 1, 0],
        [2, 0, 0],
        [3, 0, 3],
        [2, 1, 1],
        [0, 0, 2],
    ])
    request1 = np.array([
        [0, 0, 0],  # P0: not waiting (can complete immediately)
        [2, 0, 2],  # P1: waiting
        [0, 0, 0],  # P2: not waiting (can complete immediately)
        [1, 0, 0],  # P3: waiting
        [0, 0, 2],  # P4: waiting
    ])
    
    result1 = detect_deadlock_multiple(
        5, 3, available1, allocation1, request1, verbose=True
    )
    
    print(f"
Result: {'DEADLOCK' if result1.has_deadlock else 'NO DEADLOCK'}")
    print(f"Safe sequence: {result1.safe_sequence}")
    
    print("
" + "="*60)
    print("EXAMPLE 2: Deadlock Present")
    print("="*60)
    
    # Modified state that creates deadlock
    request2 = np.array([
        [0, 0, 0],  # P0: not waiting
        [2, 0, 2],  # P1: waiting for 2 of R0, 2 of R2
        [0, 0, 1],  # P2: now waiting for 1 of R2 (changed!)
        [1, 0, 0],  # P3: waiting
        [0, 0, 2],  # P4: waiting
    ])
    
    result2 = detect_deadlock_multiple(
        5, 3, available1, allocation1, request2, verbose=True
    )
    
    print(f"
Result: {'DEADLOCK' if result2.has_deadlock else 'NO DEADLOCK'}")
    if result2.has_deadlock:
        print(f"Deadlocked processes: {result2.deadlocked_processes}")
 
 
if __name__ == "__main__":
    demo_detection()

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

#include <vector>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <immintrin.h>  // For SIMD
 
/**
 * Optimized multiple-instance deadlock detector.
 * 
 * Optimizations:
 * 1. Bitset for finish tracking (cache-friendly)
 * 2. Skip processes with zero requests upfront
 * 3. SIMD comparison for vector operations
 * 4. Track candidate processes to avoid full scans
 */
class OptimizedDetector {
public:
    static constexpr int MAX_PROCESSES = 4096;
    static constexpr int MAX_RESOURCES = 256;
    
    struct DetectionInput {
        int num_processes;
        int num_resources;
        int* available;           // [num_resources]
        int* allocation;          // [num_processes * num_resources]
        int* request;             // [num_processes * num_resources]
    };
    
    struct DetectionOutput {
        bool has_deadlock;
        int num_deadlocked;
        int deadlocked[MAX_PROCESSES];
        int num_safe;
        int safe_sequence[MAX_PROCESSES];
    };
    
    void detect(const DetectionInput& in, DetectionOutput& out) {
        // Local work vector
        alignas(64) int work[MAX_RESOURCES];
        std::memcpy(work, in.available, in.num_resources * sizeof(int));
        
        // Bitset for finished processes (very cache-efficient)
        std::bitset<MAX_PROCESSES> finished;
        
        // Pre-compute processes with zero requests (immediately "done")
        std::vector<int> candidates;
        candidates.reserve(in.num_processes);
        
        out.num_safe = 0;
        
        for (int i = 0; i < in.num_processes; i++) {
            bool zero_request = true;
            const int* req = &in.request[i * in.num_resources];
            
            for (int j = 0; j < in.num_resources; j++) {
                if (req[j] > 0) {
                    zero_request = false;
                    break;
                }
            }
            
            if (zero_request) {
                // Not waiting - add to safe sequence immediately
                finished.set(i);
                out.safe_sequence[out.num_safe++] = i;
                
                // Reclaim its resources
                const int* alloc = &in.allocation[i * in.num_resources];
                for (int j = 0; j < in.num_resources; j++) {
                    work[j] += alloc[j];
                }
            } else {
                // Potential candidate
                candidates.push_back(i);
            }
        }
        
        // Main detection loop
        bool progress = true;
        while (progress) {
            progress = false;
            
            for (auto it = candidates.begin(); it != candidates.end(); ) {
                int i = *it;
                
                // Compare Request[i] <= Work
                const int* req = &in.request[i * in.num_resources];
                bool can_satisfy = compare_le_vector(req, work, in.num_resources);
                
                if (can_satisfy) {
                    // Process can complete
                    finished.set(i);
                    out.safe_sequence[out.num_safe++] = i;
                    
                    // Reclaim resources
                    const int* alloc = &in.allocation[i * in.num_resources];
                    for (int j = 0; j < in.num_resources; j++) {
                        work[j] += alloc[j];
                    }
                    
                    // Remove from candidates
                    it = candidates.erase(it);
                    progress = true;
                } else {
                    ++it;
                }
            }
        }
        
        // Remaining candidates are deadlocked
        out.has_deadlock = !candidates.empty();
        out.num_deadlocked = 0;
        for (int i : candidates) {
            out.deadlocked[out.num_deadlocked++] = i;
        }
    }
    
private:
    // SIMD-optimized vector comparison: returns true if a[i] <= b[i] for all i
    inline bool compare_le_vector(const int* a, const int* b, int len) {
        // Simple version (compiler may auto-vectorize)
        for (int i = 0; i < len; i++) {
            if (a[i] > b[i]) return false;
        }
        return true;
        
        // For explicit SIMD with AVX2:
        // Process 8 ints at a time using _mm256_cmpgt_epi32
    }
};
 
/**
 * Further optimization: incremental detection.
 * 
 * Instead of re-running full detection, maintain a "potentially satisfiable"
 * set that updates as resources are allocated/released.
 */
class IncrementalDetector {
public:
    // When resources are released, check if any blocked process can now proceed
    void on_resource_release(int resource_type, int count) {
        // Only processes waiting for this resource type need rechecking
        for (int pid : processes_waiting_for[resource_type]) {
            if (can_satisfy(pid)) {
                mark_ready(pid);
            }
        }
    }
    
    // When a process blocks, check for immediate deadlock
    bool on_process_block(int pid, int resource_type) {
        add_to_waiting(pid, resource_type);
        
        // Quick check: is there an obvious cycle?
        // (Only for single-instance or as heuristic)
        // Full detection may be triggered if quick check fails
        return quick_deadlock_check(pid);
    }
    
private:
    std::vector<std::set<int>> processes_waiting_for; // [resource_type] -> pids
    
    bool can_satisfy(int pid) { /* ... */ return true; }
    void mark_ready(int pid) { /* ... */ }
    void add_to_waiting(int pid, int resource_type) { /* ... */ }
    bool quick_deadlock_check(int pid) { 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
95
96
97
98
99
100
101
102
103
104
105

def mixed_resource_detection(
    single_instance_resources: list,   # [(resource_id, holder_pid or None), ...]
    multi_instance_resources: list,    # [(resource_id, total_count), ...]
    allocations: dict,                 # pid -> {rid: count, ...}
    requests: dict,                    # pid -> [(rid, count), ...] (blocked on)
) -> dict:
    """
    Handle detection with mixed single and multiple instance resources.
    
    Strategy: Unify representation, then use matrix-based detection.
    """
    # Build unified resource representation
    # For single-instance: treat as multi with count=1
    all_resources = {}
    
    for rid, holder in single_instance_resources:
        all_resources[rid] = {
            'total': 1,
            'type': 'single'
        }
    
    for rid, count in multi_instance_resources:
        all_resources[rid] = {
            'total': count,
            'type': 'multi'
        }
    
    # Build matrices
    processes = list(set(allocations.keys()) | set(requests.keys()))
    process_idx = {pid: i for i, pid in enumerate(processes)}
    resource_idx = {rid: j for j, rid in enumerate(all_resources.keys())}
    
    n = len(processes)
    m = len(all_resources)
    
    import numpy as np
    
    allocation_matrix = np.zeros((n, m), dtype=np.int32)
    request_matrix = np.zeros((n, m), dtype=np.int32)
    total_vector = np.array([all_resources[rid]['total'] 
                              for rid in resource_idx.keys()], dtype=np.int32)
    
    # Fill allocation matrix
    for pid, resources in allocations.items():
        if pid not in process_idx:
            continue
        i = process_idx[pid]
        for rid, count in resources.items():
            if rid in resource_idx:
                j = resource_idx[rid]
                allocation_matrix[i, j] = count
    
    # Fill request matrix
    for pid, resource_requests in requests.items():
        if pid not in process_idx:
            continue
        i = process_idx[pid]
        for rid, count in resource_requests:
            if rid in resource_idx:
                j = resource_idx[rid]
                request_matrix[i, j] = count
    
    # Calculate available
    available_vector = total_vector - np.sum(allocation_matrix, axis=0)
    
    # Run standard detection algorithm
    result = detect_deadlock_multiple(
        n, m, available_vector, allocation_matrix, request_matrix
    )
    
    # Map back to process IDs
    deadlocked_pids = [processes[i] for i in result.deadlocked_processes]
    
    return {
        'has_deadlock': result.has_deadlock,
        'deadlocked_pids': deadlocked_pids,
        'safe_sequence_pids': [processes[i] for i in result.safe_sequence],
    }
 
 
# For even better performance, we can use a hybrid approach:
def hybrid_detection(state):
    """
    Hybrid approach:
    1. Quick check using wait-for graph (O(V+E))
    2. If no cycle, no deadlock (quick exit)
    3. If cycle found with only single-instance resources, deadlock confirmed
    4. If cycle found with multi-instance, run full matrix detection
    
    This optimizes for the common case where there's no cycle at all.
    """
    cycle = find_wait_for_cycle(state)
    
    if not cycle:
        return {'has_deadlock': False}
    
    # Check if cycle involves only single-instance resources
    if all_single_instance_in_cycle(cycle, state):
        return {
            'has_deadlock': True,
            'deadlocked_pids': list(cycle)
        }
    
    # Multi-instance involved: need full analysis
    return run_matrix_detection(state)

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

// Example: Database connection pool deadlock
// Pool size: 10 connections
 
public class ConnectionPoolDeadlock {
    private ConnectionPool pool = new ConnectionPool(10);
    
    // Transaction A needs 6 connections total
    public void transactionA() {
        List<Connection> conns = pool.acquire(4);  // Gets 4
        // ... do some work ...
        
        // Needs 2 more to complete, but...
        List<Connection> more = pool.acquire(2);  // BLOCKS
        // If pool is exhausted, we're stuck
        
        // ... release all ...
    }
    
    // Transaction B needs 6 connections total  
    public void transactionB() {
        List<Connection> conns = pool.acquire(4);  // Gets 4
        // ... do some work ...
        
        // Needs 2 more to complete
        List<Connection> more = pool.acquire(2);  // BLOCKS
        // ... release all ...
    }
    
    // If both run concurrently:
    // - A holds 4, needs 2 more (only 2 left)
    // - B holds 4, needs 2 more (only 2 left)
    // A waits for B's resources, B waits for A's -> DEADLOCK (if pool size 8, not 10)
    
    // Detection result:
    // Available: [2] (connections)
    // Allocation: A=[4], B=[4]
    // Request: A=[2], B=[2]
    // 
    // Try A: Request[A]=2, Work=2 -> A can complete!
    //        Work = 2 + 4 = 6
    // Try B: Request[B]=2, Work=6 -> B can complete!
    // 
    // No deadlock with pool size 10.
    // With pool size 8: Available=[0], instant deadlock!
}