4.3Prevention and avoidance: safe states and Banker's algorithm
The idea
A state is safe if some order exists in which every process can finish. Banker's algorithm grants a request only if the state stays safe.
Think of it like this: A banker who lends only if, after the loan, he can still satisfy every customer's maximum credit in some order.
Why it exists
It avoids deadlock without banning any of the four conditions, at the price of knowing each process's maximum need in advance.
How it works
- Compute Need = Max − Allocation.
- Work = Available. Find any process with Need ≤ Work.
- Pretend it finishes: Work += its Allocation. Repeat.
- If all processes finish, the order found is a safe sequence. For a request: check ≤ Need, ≤ Available, pretend to grant, then run the safety test.
Worked example: Textbook 5-process example, Available (3, 3, 2)
Needs: P0 (7,4,3), P1 (1,2,2), P2 (6,0,0), P3 (0,1,1), P4 (4,3,1). P1 fits → work (5,3,2); P3 → (7,4,3); P0 → (7,5,3); P2 → (10,5,5); P4 → (10,5,7). Safe sequence P1, P3, P0, P2, P4.
Now play with it
- →Press nothing: the lab already shows the safe sequence.
- →Try the "2 processes: unsafe" preset, and ask for a request with the request box.
| Process | Allocation | Max | Need = Max − Alloc |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
GRANT: Granting it leaves a safe state. Safe sequence afterwards: P1 → P3 → P0 → P2 → P4
Safe means at least one order exists in which every process can finish. Unsafe does not mean deadlocked yet, it means deadlock is possible. A request is granted only if it is within Need, within Available, and leaves the state safe.
Check yourself
An unsafe state
Exam notes (the dense version)
A state is safe if some order of finishing exists in which every process can obtain its maximum need. Safe ⇒ no deadlock; unsafe does not mean deadlocked, only that deadlock is possible. Need = Max − Allocation. Safety algorithm: Work = Available; repeatedly pick a process with Need ≤ Work, let it finish and add its Allocation to Work. A request is granted only if Request ≤ Need, Request ≤ Available, and the state after a trial grant is still safe.
Previous year questions: Deadlock (9)
PYQs are grouped by topic, so this is the full set for Deadlock; try the ones that match this subtopic. Open all 9 on the topic page.