Operating System - Banker’s Algorithm
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:
-
Pretend it finishes:
Work += Allocation[i]
-
Finish[i] = true
-
Repeat Step 3
-
-
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] ✅
-
Work becomes:
Work = Work + Allocation[P1] = [5, 3, 2]
-
Finish[1] =
true
-
-
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
-
Avoids entering deadlocks by pre-checking every request
-
Guarantees system safety
Limitations
-
Requires advance knowledge of maximum resource needs
-
Complex and expensive to implement in large systems