Session 3.5: Deadlock Prevention and Avoidance

System: 3 resource types (A, B, C)
Total instances: A=10, B=5, C=7

Current state:
Process | Allocation | Max | Need
        | A  B  C    | A B C | A B C
--------|-----------|-------|-------
P0      | 0  1  0    | 7 5 3 | 7 4 3
P1      | 2  0  0    | 3 2 2 | 1 2 2  
P2      | 3  0  2    | 9 0 2 | 6 0 0
P3      | 2  1  1    | 2 2 2 | 0 1 1
P4      | 0  0  2    | 4 3 3 | 4 3 1

Available: A=3, B=3, C=2

Question: Is this a safe state?
Answer: Need to check if there exists a safe sequence...

Let n = number of processes, m = number of resource types

Available[m]: Available instances of each resource type
Max[n][m]: Maximum demand of each process for each resource type  
Allocation[n][m]: Currently allocated instances to each process
Need[n][m]: Remaining need of each process
             Need[i][j] = Max[i][j] - Allocation[i][j]

Work[m]: Working copy of Available (used in algorithm)
Finish[n]: Boolean array to track completed processes

function bankers_algorithm(processes, resources, available, max, allocation):
    n = len(processes)  # number of processes
    m = len(resources)  # number of resource types
    
    # Calculate need matrix
    need = [[max[i][j] - allocation[i][j] for j in range(m)] for i in range(n)]
    
    # Check if current state is safe
    def is_safe():
        work = available[:]
        finish = [False] * n
        safe_sequence = []
        
        for _ in range(n):
            found = False
            for i in range(n):
                if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
                    # Process i can finish
                    for j in range(m):
                        work[j] += allocation[i][j]
                    finish[i] = True
                    safe_sequence.append(i)
                    found = True
                    break
            
            if not found:
                return False, []
        
        return True, safe_sequence
    
    return is_safe()

# Example usage:
processes = ['P0', 'P1', 'P2', 'P3', 'P4']
resources = ['A', 'B', 'C']
available = [3, 3, 2]
max = [[7,5,3], [3,2,2], [9,0,2], [2,2,2], [4,3,3]]
allocation = [[0,1,0], [2,0,0], [3,0,2], [2,1,1], [0,0,2]]

safe, sequence = bankers_algorithm(processes, resources, available, max, allocation)
print(f"Safe: {safe}, Sequence: {sequence}")

Current State:
Process | Allocation | Need     | Max
        | A  B  C    | A  B  C  | A  B  C
--------|-----------|----------|--------
P0      | 0  1  0    | 7  4  3  | 7  5  3
P1      | 2  0  0    | 1  2  2  | 3  2  2
P2      | 3  0  2    | 6  0  0  | 9  0  2
P3      | 2  1  1    | 0  1  1  | 2  2  2
P4      | 0  0  2    | 4  3  1  | 4  3  3

Available: A=3, B=3, C=2

Request: P1 requests (1,0,2)

Step 1: Check Request ≤ Need
(1,0,2) ≤ (1,2,2) ✓ Valid

Step 2: Check Request ≤ Available  
(1,0,2) ≤ (3,3,2) ✓ Sufficient resources

Step 3: Simulate allocation
New Available: (3,3,2) - (1,0,2) = (2,3,0)
New Allocation[P1]: (2,0,0) + (1,0,2) = (3,0,2)
New Need[P1]: (1,2,2) - (1,0,2) = (0,2,0)

Step 4: Check if new state is safe
Try to find safe sequence with Available=(2,3,0)...
- P1 needs (0,2,0) ≤ (2,3,0) ✓ Can finish
- After P1: Available = (2,3,0) + (3,0,2) = (5,3,2)
- Continue checking other processes...

If safe sequence found: Grant request
If no safe sequence: Deny request, restore original state

def process_request(process_id, request, available, allocation, need, max_claim):
    n = len(allocation)
    m = len(available)
    
    # Step 1: Check if request is valid
    if not all(request[j] <= need[process_id][j] for j in range(m)):
        return False, "Request exceeds maximum claim"
    
    # Step 2: Check if resources are available
    if not all(request[j] <= available[j] for j in range(m)):
        return False, "Insufficient resources available"
    
    # Step 3: Simulate allocation
    # Save current state
    old_available = available[:]
    old_allocation = [row[:] for row in allocation]
    old_need = [row[:] for row in need]
    
    # Modify state
    for j in range(m):
        available[j] -= request[j]
        allocation[process_id][j] += request[j]
        need[process_id][j] -= request[j]
    
    # Step 4: Check safety
    safe, sequence = is_safe_state(available, allocation, need)
    
    if safe:
        return True, f"Request granted. Safe sequence: {sequence}"
    else:
        # Restore original state
        available[:] = old_available
        allocation[:] = old_allocation
        need[:] = old_need
        return False, "Request denied - would lead to unsafe state"