Operating System - Deadlock Avoidance
What is Deadlock Avoidance?
Deadlock avoidance is a strategy where the system dynamically examines every resource request and decides whether it is safe to grant it, avoiding unsafe states that could lead to deadlock.
Key Concept: Safe and Unsafe States
-
Safe State: There is at least one sequence of process execution where each process can finish, even if all request their maximum resources.
-
Unsafe State: No such sequence exists. It doesn’t mean deadlock has occurred yet, but it could happen.
Banker’s Algorithm (Safe State Algorithm)
Named because it's like a banker who only loans money if they’re sure they can fulfill all future demands of their clients without going bankrupt.
For n processes and m resource types, we use:
-
Available[]
: How many instances of each resource are currently available. -
Max[][]
: Maximum resources each process may need. -
Allocation[][]
: Resources currently allocated to each process. -
Need[][]
: What each process still needs (Need = Max - Allocation
).
Safe State Check Algorithm
-
Initialize:
-
Work = Available
(copy of available resources). -
Finish[i] = false
for all processes.
-
-
Find a process
i
such that:-
Finish[i] == false
-
Need[i] <= Work
(i.e., all needed resources can be satisfied now).
-
-
If found:
-
Pretend to allocate resources:
Work = Work + Allocation[i]
. -
Set
Finish[i] = true
. -
Go back to step 2.
-
-
If no such process is found, and some
Finish[i] == false
, the system is not in a safe state. -
If all
Finish[i] == true
, the system is in a safe state.
Example: 3 Processes, 3 Resources
Available = [3, 3, 2]
Process | Max | Allocation | Need (Max - Allocation) |
---|---|---|---|
P0 | [7,5,3] | [0,1,0] | [7,4,3] |
P1 | [3,2,2] | [2,0,0] | [1,2,2] |
P2 | [9,0,2] | [3,0,2] | [6,0,0] |
Step-by-Step Safe Sequence Check:
Start with Work = [3,3,2]
-
Check P1:
Need = [1,2,2] <= Work = [3,3,2]
→ ✅
→ Allocate and release:Work = Work + Allocation[1] = [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 could complete so far.
Next:
-
Still can't do P0 or P2 → No other process can proceed → Not a safe state ❌
So this is not a safe state.