Home/Learn/Operating Systems/Deadlock Avoidance: Banker's Algorithm

Deadlock Avoidance: Banker's Algorithm

Advanced

Deadlocks

The Banker's Algorithm dynamically evaluates each resource request to ensure the system stays in a safe state — a state from which all processes can eventually complete.

Overview

Unlike prevention, avoidance does not impose blanket restrictions. Instead, when a process requests resources, the OS simulates granting the request and checks if the resulting state is 'safe'. A safe state guarantees a safe sequence — an ordering where each process can finish using currently available plus resources released by earlier processes. If safe, the request is granted; if unsafe, the process waits. The algorithm requires processes to declare their maximum resource needs upfront (the max matrix). While theoretically sound, the Banker's Algorithm is rarely used in general-purpose OS due to this requirement, but the concept underpins capacity planning and admission control in databases and cloud schedulers.

Safety Algorithm: Finding a Safe Sequence

Given allocation, max, need, and available vectors, find an ordering of all processes such that each can complete. Iteratively find a process whose need can be satisfied by current available resources, 'run' it (add its allocation back to available), and repeat until all processes are scheduled or none can proceed (unsafe).

Java — Banker's Algorithm safety check

// Banker's Algorithm — Safety Check
// 3 processes (P0, P1, P2), 3 resource types (A, B, C)

int[] available   = {3, 3, 2};             // free instances

int[][] allocation = {                      // currently allocated
    {0, 1, 0},  // P0
    {2, 0, 0},  // P1
    {3, 0, 2},  // P2
};

int[][] max = {                             // maximum demand
    {7, 5, 3},  // P0
    {3, 2, 2},  // P1
    {9, 0, 2},  // P2
};

int n = 3, r = 3;
int[][] need = new int[n][r];
for (int i = 0; i < n; i++)
    for (int j = 0; j < r; j++)
        need[i][j] = max[i][j] - allocation[i][j];

boolean[] finished = new boolean[n];
int[] safeSeq = new int[n];
int count = 0;

int[] work = available.clone();

while (count < n) {
    boolean found = false;
    for (int i = 0; i < n; i++) {
        if (!finished[i]) {
            boolean canRun = true;
            for (int j = 0; j < r; j++)
                if (need[i][j] > work[j]) { canRun = false; break; }

            if (canRun) {
                for (int j = 0; j < r; j++) work[j] += allocation[i][j];
                safeSeq[count++] = i;
                finished[i] = true;
                found = true;
            }
        }
    }
    if (!found) { System.out.println("UNSAFE STATE"); break; }
}
// Safe sequence: P1 → P2 → P0 (need[P1]≤avail, then P2, then P0)

Resource Request Algorithm

When process Pi requests resources, first check that request ≤ need[i] (no overclaiming), then check request ≤ available (resources exist). Tentatively grant: subtract from available, add to allocation, subtract from need. Run the safety algorithm — if safe, commit; if unsafe, roll back and make Pi wait.

Java — Banker's resource request algorithm

// Resource Request for process P1 requesting [1, 0, 2]
int[] request = {1, 0, 2};
int pid = 1; // P1

// Check 1: request ≤ need[pid]
for (int j = 0; j < r; j++) {
    if (request[j] > need[pid][j]) {
        throw new IllegalStateException("Process exceeded max claim!");
    }
}

// Check 2: request ≤ available
for (int j = 0; j < r; j++) {
    if (request[j] > available[j]) {
        System.out.println("P" + pid + " must wait — resources unavailable");
        return;
    }
}

// Tentatively grant
for (int j = 0; j < r; j++) {
    available[j]        -= request[j];
    allocation[pid][j]  += request[j];
    need[pid][j]        -= request[j];
}

// Run safety algorithm
if (isSafe(available, allocation, need)) {
    System.out.println("Request granted — system remains safe");
} else {
    // Rollback
    for (int j = 0; j < r; j++) {
        available[j]        += request[j];
        allocation[pid][j]  -= request[j];
        need[pid][j]        += request[j];
    }
    System.out.println("Request denied — would lead to unsafe state");
}

Key Points to Remember

1A safe state guarantees a safe sequence exists; an unsafe state may or may not lead to deadlock.
2The Banker's Algorithm requires processes to declare maximum resource needs upfront — impractical for general-purpose OS.
3Time complexity of the safety algorithm is O(n² × r) where n is processes and r is resource types.
4The algorithm prevents deadlock dynamically at runtime without imposing permanent structural restrictions.
5Cloud and database admission control systems use Banker's-style reasoning to avoid overcommitting resources.
6A process in an unsafe state is made to wait, not killed — the system may eventually become safe as others release resources.

Interview Questions

What is the difference between a safe state and a deadlock-free state in the Banker's Algorithm?

MediumGoogle

Walk me through the Banker's Algorithm with 3 processes and 2 resource types.

HardAmazon

Why is the Banker's Algorithm not used in general-purpose operating systems like Linux?

MediumMicrosoft

How does the concept of safe state apply to database connection pool sizing and admission control?

HardNetflix

Ask Aria about Deadlock Avoidance: Banker's Algorithm

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Deadlock Prevention

Deadlock Detection & Recovery