Deadlock Avoidance: The Banker's Algorithm
Among the various ways to handle deadlock, avoidance is arguably the most intelligent approach. Rather than placing hard restrictions on how processes use resources, it lets things run naturally but keeps a close eye on every resource request before approving it.
The most well known algorithm built around this idea is the Banker's Algorithm, developed by Edsger Dijkstra.
The Core Idea
Think about how a bank works. A bank has a fixed amount of money and multiple customers, each of whom might need loans at different points in time.
A responsible bank manager never hands out money blindly. Before approving any loan, the manager checks whether the remaining funds can still cover the worst-case needs of every other customer. If the math works out, the loan gets approved. If not, the customer waits.
Two Core Steps
The algorithm operates in two distinct phases:
Step 1: Safety Check
Before anything else, the system needs a way to determine whether its current state is safe. A safe state means there exists at least one ordering of processes such that each process can get all the resources it needs, finish its work, and return those resources.
- Create a working copy of the available resources. Mark all processes as unfinished.
- Look for any unfinished process whose remaining resource needs can be satisfied with what is currently available.
- If such a process is found, assume it runs to completion and returns all its allocated resources back to the available pool. Mark it as finished.
- Repeat steps 2 and 3 until either all processes are marked finished (SAFE state) or no eligible process can be found (UNSAFE state).
Step 2: Handling a Resource Request
When a process asks for resources, the system does not grant the request immediately. Instead:
- Check that the request does not exceed what the process said it would ever need (its declared Maximum).
- Check that the requested resources are actually available right now.
- Temporarily pretend the resources have been granted and update the matrices accordingly.
- Run the Safety Check (Step 1) on this hypothetical new state. If the system is still safe, make the allocation permanent. If not, undo the temporary allocation and make the process wait.
A Worked Example
Consider a system with 4 processes (P0 to P3) and 3 resource types: X, Y, and Z. The total resources originally in the system are X=9, Y=6, Z=8.
| Process | Max (X,Y,Z) | Allocated (X,Y,Z) | Need (X,Y,Z) |
|---|---|---|---|
| P0 | 6, 4, 5 | 1, 0, 2 | 5, 4, 3 |
| P1 | 2, 3, 3 | 2, 1, 0 | 0, 2, 3 |
| P2 | 5, 2, 4 | 3, 2, 2 | 2, 0, 2 |
| P3 | 3, 3, 2 | 1, 1, 1 | 2, 2, 1 |
First, we calculate the currently Available resources:
Total allocated = (1+2+3+1, 0+1+2+1, 2+0+2+1) = (7, 4, 5)
Available = Total - Allocated = (9, 6, 8) - (7, 4, 5) = (2, 2, 3)Running the Safety Check starting with Available = (2, 2, 3):
1. P1 needs (0, 2, 3). Available (2, 2, 3) covers it.
Run P1, release its resources.
New Available = (2, 2, 3) + (2, 1, 0) = (4, 3, 3)
2. P2 needs (2, 0, 2). Available (4, 3, 3) covers it.
Run P2, release its resources.
New Available = (4, 3, 3) + (3, 2, 2) = (7, 5, 5)
3. P3 needs (2, 2, 1). Available (7, 5, 5) covers it.
Run P3, release its resources.
New Available = (7, 5, 5) + (1, 1, 1) = (8, 6, 6)
4. P0 needs (5, 4, 3). Available (8, 6, 6) covers it.
Run P0, release its resources.
New Available = (8, 6, 6) + (1, 0, 2) = (9, 6, 8)
Result: All processes finished. Safe sequence: P1 -> P2 -> P3 -> P0C++ Implementation
#include <iostream>
using namespace std;
#define P 4 // Number of processes
#define R 3 // Number of resource types
int main() {
int i, j, k;
// Available resources
int available[R] = {2, 2, 3};
// Maximum resource demand
int maxDemand[P][R] = {
{6, 4, 5},
{2, 3, 3},
{5, 2, 4},
{3, 3, 2}
};
// Currently allocated resources
int allocation[P][R] = {
{1, 0, 2},
{2, 1, 0},
{3, 2, 2},
{1, 1, 1}
};
// Calculate Need matrix
int need[P][R];
for (i = 0; i < P; i++)
for (j = 0; j < R; j++)
need[i][j] = maxDemand[i][j] - allocation[i][j];
bool finish[P] = {false};
int safeSeq[P];
int count = 0;
// Safety Check Loop
while (count < P) {
bool found = false;
for (i = 0; i < P; i++) {
if (!finish[i]) {
bool canRun = true;
for (j = 0; j < R; j++) {
if (need[i][j] > available[j]) {
canRun = false;
break;
}
}
if (canRun) {
// Reclaim resources
for (k = 0; k < R; k++)
available[k] += allocation[i][k];
safeSeq[count++] = i;
finish[i] = true;
found = true;
}
}
}
if (!found) {
cout << "System is not in a safe state." << endl;
return 0;
}
}
cout << "System is in a safe state." << endl;
cout << "Safe sequence: ";
for (i = 0; i < P; i++) {
cout << "P" << safeSeq[i];
if (i != P - 1) cout << " -> ";
}
cout << endl;
return 0;
}Output:
System is in a safe state.
Safe sequence: P1 -> P2 -> P3 -> P0Limitations Worth Knowing
The Banker's Algorithm works perfectly in theory but comes with some practical drawbacks that make it hard to use in general-purpose operating systems like Windows or Linux:
- Every process must declare its maximum resource needs upfront, which is very difficult to predict in modern, dynamic applications.
- The safety check has to run every single time a resource is requested, adding significant computational overhead.
- It assumes a fixed number of processes and resources, which does not reflect how real systems constantly spawn new threads and attach/detach devices.
Summary
Despite its limitations, the Banker's Algorithm remains a foundational concept in OS design and a solid example of how careful resource management can keep a system out of trouble.
It gives the operating system a structured way to make resource allocation decisions without ever letting the system drift into a deadlock-prone state. By always verifying that a safe execution order exists before committing to any allocation, it trades a bit of computational overhead for a strong guarantee: as long as the algorithm is followed, deadlock simply cannot occur.
Understanding the Banker's Algorithm
Question 1 of 1Test your knowledge on the mechanics of the algorithm.