Deadlock Avoidance: Banker’s Algorithm Implementation and Examples

Introduction to Deadlock Avoidance

Deadlock avoidance is a crucial concept in operating systems that prevents the system from entering an unsafe state that could lead to deadlock. Unlike deadlock prevention, which imposes strict conditions on resource allocation, deadlock avoidance allows more flexible resource allocation while ensuring system safety through careful analysis.

The Banker’s Algorithm, developed by Edsger Dijkstra, is the most widely used deadlock avoidance algorithm. It’s named after the banking system analogy where a banker ensures they never allocate money in a way that prevents all customers from eventually completing their transactions.

Understanding the Banking Analogy

Imagine a bank with a limited amount of money to lend. Each customer requests a loan with a maximum credit limit. The banker must ensure that:

• Current loans plus available money can satisfy at least one customer’s maximum needs
• When that customer repays, the bank has enough to satisfy another customer
• This continues until all customers are satisfied

Core Concepts and Data Structures

Key Variables

The Banker’s Algorithm uses several important data structures:

• Available[]: Number of available instances of each resource type
• Max[][]: Maximum demand of each process for each resource
• Allocation[][]: Resources currently allocated to each process
• Need[][]: Remaining resource need (Max – Allocation)

Safety Algorithm

The safety algorithm determines if the system is in a safe state by finding a safe sequence of process execution.

bool isSafe(int processes, int resources, int available[], 
           int max[][resources], int allocation[][resources]) {
    int need[processes][resources];
    
    // Calculate need matrix
    for (int i = 0; i < processes; i++) {
        for (int j = 0; j < resources; j++) {
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }
    
    bool finish[processes] = {false};
    int safeSeq[processes];
    int work[resources];
    
    // Copy available resources to work
    for (int i = 0; i < resources; i++) {
        work[i] = available[i];
    }
    
    int count = 0;
    while (count < processes) {
        bool found = false;
        
        for (int p = 0; p < processes; p++) {
            if (!finish[p]) {
                int j;
                // Check if process p can be satisfied
                for (j = 0; j < resources; j++) {
                    if (need[p][j] > work[j]) break;
                }
                
                // If all resources can be satisfied
                if (j == resources) {
                    // Add allocated resources back to work
                    for (int k = 0; k < resources; k++) {
                        work[k] += allocation[p][k];
                    }
                    
                    safeSeq[count++] = p;
                    finish[p] = true;
                    found = true;
                }
            }
        }
        
        if (!found) {
            printf("System is not in safe state\n");
            return false;
        }
    }
    
    printf("System is in safe state.\nSafe sequence: ");
    for (int i = 0; i < processes; i++) {
        printf("%d ", safeSeq[i]);
    }
    printf("\n");
    
    return true;
}

Complete Banker’s Algorithm Implementation

Here’s a comprehensive implementation of the Banker’s Algorithm with resource request handling:

#include <stdio.h>
#include <stdbool.h>

#define MAX_PROCESSES 10
#define MAX_RESOURCES 10

int available[MAX_RESOURCES];
int max[MAX_PROCESSES][MAX_RESOURCES];
int allocation[MAX_PROCESSES][MAX_RESOURCES];
int need[MAX_PROCESSES][MAX_RESOURCES];
int processes, resources;

void calculateNeed() {
    for (int i = 0; i < processes; i++) {
        for (int j = 0; j < resources; j++) {
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }
}

bool isSafe() {
    int work[MAX_RESOURCES];
    bool finish[MAX_PROCESSES] = {false};
    
    // Initialize work with available resources
    for (int i = 0; i < resources; i++) {
        work[i] = available[i];
    }
    
    int safeSeq[MAX_PROCESSES];
    int count = 0;
    
    while (count < processes) {
        bool found = false;
        
        for (int p = 0; p < processes; p++) {
            if (!finish[p]) {
                int j;
                for (j = 0; j < resources; j++) {
                    if (need[p][j] > work[j]) break;
                }
                
                if (j == resources) {
                    // Process p can be satisfied
                    for (int k = 0; k < resources; k++) {
                        work[k] += allocation[p][k];
                    }
                    
                    safeSeq[count++] = p;
                    finish[p] = true;
                    found = true;
                    
                    printf("Process P%d can be satisfied. Work: [", p);
                    for (int k = 0; k < resources; k++) {
                        printf("%d", work[k]);
                        if (k < resources - 1) printf(", ");
                    }
                    printf("]\n");
                }
            }
        }
        
        if (!found) {
            printf("System is in UNSAFE state!\n");
            return false;
        }
    }
    
    printf("System is in SAFE state.\n");
    printf("Safe sequence: ");
    for (int i = 0; i < processes; i++) {
        printf("P%d", safeSeq[i]);
        if (i < processes - 1) printf(" -> ");
    }
    printf("\n\n");
    
    return true;
}

bool requestResources(int processId, int request[]) {
    printf("\nProcess P%d requesting resources: [", processId);
    for (int i = 0; i < resources; i++) {
        printf("%d", request[i]);
        if (i < resources - 1) printf(", ");
    }
    printf("]\n");
    
    // Check if request exceeds need
    for (int i = 0; i < resources; i++) {
        if (request[i] > need[processId][i]) {
            printf("Error: Request exceeds maximum need!\n");
            return false;
        }
    }
    
    // Check if request exceeds available
    for (int i = 0; i < resources; i++) {
        if (request[i] > available[i]) {
            printf("Process must wait - insufficient resources available.\n");
            return false;
        }
    }
    
    // Pretend to allocate resources
    for (int i = 0; i < resources; i++) {
        available[i] -= request[i];
        allocation[processId][i] += request[i];
        need[processId][i] -= request[i];
    }
    
    // Check if system remains safe
    if (isSafe()) {
        printf("Request granted successfully!\n");
        return true;
    } else {
        // Rollback allocation
        for (int i = 0; i < resources; i++) {
            available[i] += request[i];
            allocation[processId][i] -= request[i];
            need[processId][i] += request[i];
        }
        printf("Request denied - would lead to unsafe state!\n");
        return false;
    }
}

void displayState() {
    printf("\n=== CURRENT SYSTEM STATE ===\n");
    printf("Available: [");
    for (int i = 0; i < resources; i++) {
        printf("%d", available[i]);
        if (i < resources - 1) printf(", ");
    }
    printf("]\n\n");
    
    printf("Process | Max     | Allocation | Need\n");
    printf("--------|---------|------------|--------\n");
    for (int i = 0; i < processes; i++) {
        printf("P%d      | [", i);
        for (int j = 0; j < resources; j++) {
            printf("%d", max[i][j]);
            if (j < resources - 1) printf(",");
        }
        printf("] | [");
        for (int j = 0; j < resources; j++) {
            printf("%d", allocation[i][j]);
            if (j < resources - 1) printf(",");
        }
        printf("]      | [");
        for (int j = 0; j < resources; j++) {
            printf("%d", need[i][j]);
            if (j < resources - 1) printf(",");
        }
        printf("]\n");
    }
    printf("\n");
}

int main() {
    // Example scenario
    processes = 5;
    resources = 3;
    
    // Available resources [A, B, C]
    available[0] = 3; available[1] = 3; available[2] = 2;
    
    // Max demand matrix
    int maxMatrix[5][3] = {
        {7, 5, 3},  // P0
        {3, 2, 2},  // P1
        {9, 0, 2},  // P2
        {2, 2, 2},  // P3
        {4, 3, 3}   // P4
    };
    
    // Current allocation matrix
    int allocMatrix[5][3] = {
        {0, 1, 0},  // P0
        {2, 0, 0},  // P1
        {3, 0, 2},  // P2
        {2, 1, 1},  // P3
        {0, 0, 2}   // P4
    };
    
    // Copy matrices
    for (int i = 0; i < processes; i++) {
        for (int j = 0; j < resources; j++) {
            max[i][j] = maxMatrix[i][j];
            allocation[i][j] = allocMatrix[i][j];
        }
    }
    
    calculateNeed();
    displayState();
    
    printf("=== INITIAL SAFETY CHECK ===\n");
    isSafe();
    
    // Test resource request
    int request1[] = {1, 0, 2};  // P1 requests [1,0,2]
    requestResources(1, request1);
    
    displayState();
    
    int request2[] = {3, 3, 0};  // P4 requests [3,3,0] - should be denied
    requestResources(4, request2);
    
    return 0;
}

Step-by-Step Execution Example

Let’s trace through the algorithm with a concrete example:

Initial State

Available Resources: (3,3,2)

Safety Algorithm Execution

Initial Work = Available = [3, 3, 2]

Step 1: Check P1 (Need: [1,2,2])
   - Need[1] <= Work? [1,2,2] <= [3,3,2] ✓
   - Execute P1: Work = [3,3,2] + [2,0,0] = [5,3,2]
   - Safe sequence: [P1]

Step 2: Check P3 (Need: [0,1,1])
   - Need[3] <= Work? [0,1,1] <= [5,3,2] ✓
   - Execute P3: Work = [5,3,2] + [2,1,1] = [7,4,3]
   - Safe sequence: [P1, P3]

Step 3: Check P4 (Need: [4,3,1])
   - Need[4] <= Work? [4,3,1] <= [7,4,3] ✓
   - Execute P4: Work = [7,4,3] + [0,0,2] = [7,4,5]
   - Safe sequence: [P1, P3, P4]

Step 4: Check P0 (Need: [7,4,3])
   - Need[0] <= Work? [7,4,3] <= [7,4,5] ✓
   - Execute P0: Work = [7,4,5] + [0,1,0] = [7,5,5]
   - Safe sequence: [P1, P3, P4, P0]

Step 5: Check P2 (Need: [6,0,0])
   - Need[2] <= Work? [6,0,0] <= [7,5,5] ✓
   - Execute P2: Work = [7,5,5] + [3,0,2] = [10,5,7]
   - Safe sequence: [P1, P3, P4, P0, P2]

Result: System is SAFE
Safe sequence: P1 → P3 → P4 → P0 → P2

Resource Request Handling

When a process requests resources, the algorithm performs these steps:

1. Validity Check: Ensure request doesn’t exceed maximum need
2. Availability Check: Ensure sufficient resources are available
3. Tentative Allocation: Temporarily grant the request
4. Safety Check: Run safety algorithm on new state
5. Decision: Grant if safe, otherwise rollback and deny

Interactive Example Walkthrough

Let’s demonstrate how the algorithm handles a specific resource request:

Scenario: Process P1 Requests [1,0,2]

Current State:
- P1 Allocation: [2,0,0], Need: [1,2,2]
- Available: [3,3,2]

Step 1: Validity Check
   Request [1,0,2] ≤ Need [1,2,2]? 
   1≤1 ✓, 0≤2 ✓, 2≤2 ✓ → Valid

Step 2: Availability Check
   Request [1,0,2] ≤ Available [3,3,2]?
   1≤3 ✓, 0≤3 ✓, 2≤2 ✓ → Available

Step 3: Tentative Allocation
   New Allocation[P1] = [2,0,0] + [1,0,2] = [3,0,2]
   New Need[P1] = [1,2,2] - [1,0,2] = [0,2,0]
   New Available = [3,3,2] - [1,0,2] = [2,3,0]

Step 4: Safety Check with New State
   Available = [2,3,0]
   
   Check P1: Need [0,2,0] ≤ [2,3,0] ✓
   Execute P1: Work = [2,3,0] + [3,0,2] = [5,3,2]
   
   Check P3: Need [0,1,1] ≤ [5,3,2] ✗ (0≤5✓, 1≤3✓, 1≤2✗)
   
   System becomes UNSAFE!

Step 5: Decision
   Rollback allocation and DENY request

Advantages and Disadvantages

Advantages

• Deadlock Prevention: Guarantees no deadlock will occur
• High Resource Utilization: More flexible than prevention methods
• Predictable Behavior: Provides clear decision criteria
• Suitable for Real-time Systems: Bounded execution time

Disadvantages

• Prior Knowledge Required: Must know maximum resource requirements
• Conservative Approach: May deny requests unnecessarily
• Fixed Process Count: Assumes constant number of processes
• Overhead: Safety algorithm runs on every request

Real-World Applications

The Banker’s Algorithm finds applications in various scenarios:

• Database Management Systems: Managing locks on database records
• Memory Management: Allocating memory pages to processes
• Network Resource Management: Bandwidth allocation in communication systems
• Cloud Computing: Virtual machine resource allocation
• Embedded Systems: Managing limited hardware resources

Optimization Techniques

Several optimizations can improve the algorithm’s performance:

1. Early Termination

bool canSatisfyAnyProcess(int available[], int need[][MAX_RESOURCES], 
                         bool finished[], int processes, int resources) {
    for (int i = 0; i < processes; i++) {
        if (!finished[i]) {
            bool canSatisfy = true;
            for (int j = 0; j < resources; j++) {
                if (need[i][j] > available[j]) {
                    canSatisfy = false;
                    break;
                }
            }
            if (canSatisfy) return true;
        }
    }
    return false;
}

2. Incremental Safety Checking

Instead of recalculating the entire safety sequence, track changes incrementally when possible.

3. Lazy Evaluation

Only perform safety checks when resource availability changes significantly.

Conclusion

The Banker’s Algorithm provides a robust solution for deadlock avoidance in operating systems. While it requires prior knowledge of maximum resource requirements and can be conservative in resource allocation, it guarantees deadlock-free execution and maintains system safety.

Understanding this algorithm is crucial for system administrators, kernel developers, and anyone working with concurrent systems where resource contention is a concern. The implementation examples and interactive walkthrough provided here demonstrate both the theoretical foundations and practical applications of this important algorithm.

When implementing the Banker’s Algorithm in production systems, consider the trade-offs between safety and resource utilization, and evaluate whether the assumptions (known maximum requirements, fixed process count) align with your system’s characteristics.