What is the Banker’s Algorithm?
The Banker’s Algorithm helps the system decide whether to grant or deny resource requests in a way that avoids entering an unsafe state, which could lead to deadlock.Named after a bank that lends money to customers (processes), only if it’s sure it can fulfill all obligations safely in the worst-case scenario.
Data Structures
For n processes and m resource types, we use:
-
Available[ ] – Resources available of each type
-
Max[ ][ ] – Maximum resources each process may need
-
Allocation[ ][ ] – Resources currently allocated
-
Need[ ][ ] – Remaining need = Max - Allocation
Safe State Check (Simplified Algorithm Steps)
-
Work = Available (temporary copy of available resources)
-
Finish[i] = false for all processes
-
Find a process i such that:
-
Finish[i] == false
-
Need[i] <= Work
-
If found:
-
If all processes can finish (Finish[i] = true for all), the system is in a safe state
Example
System:
-
Processes: P0, P1, P2
-
Resources: A, B, C (3 types)
-
Available: A = 3, B = 3, C = 2
Given Tables:
Max Matrix
| Process |
A |
B |
C |
| P0 |
7 |
5 |
3 |
| P1 |
3 |
2 |
2 |
| P2 |
9 |
0 |
2 |
Allocation Matrix
| Process |
A |
B |
C |
| P0 |
0 |
1 |
0 |
| P1 |
2 |
0 |
0 |
| P2 |
3 |
0 |
2 |
Need Matrix (Max - Allocation)
| Process |
A |
B |
C |
| P0 |
7 |
4 |
3 |
| P1 |
1 |
2 |
2 |
| P2 |
6 |
0 |
0 |
Step-by-Step Safe State Check
Start with: Work = [3, 3, 2]
Finish = [false, false, false]
-
Check P1: Need = [1, 2, 2] <= Work [3,3,2] ✅
-
Check P0: Need = [7,4,3] > Work = [5,3,2] ❌
-
Check P2: Need = [6,0,0] > Work = [5,3,2] ❌
→ Only P1 can finish at this point
-
No other process can finish → System is not in a safe state
Unsafe State → Deny Request
If a resource request would lead to this situation, the system denies the request to avoid potential deadlock.
Benefits
Limitations
