How does the Banker's algorithm decide whether a resource request is safe?
It pretends to grant the request, then checks whether some order exists in which every process can still finish with the resources left. If such a safe sequence exists, the request is granted; otherwise it waits.
Explain it simply
A bank never lends so much that it cannot satisfy its customers' maximum credit lines. The OS acts the same way: it grants a resource only if the system stays in a safe state, meaning a sequence exists in which every process can get its maximum need and finish.
Example with 12 identical tape drives:
| Process | Max need | Held | Still needs |
|---|---|---|---|
| P0 | 10 | 5 | 5 |
| P1 | 4 | 2 | 2 |
| P2 | 9 | 2 | 7 |
Available = 12 - (5 + 2 + 2) = 3.
Example
Is this state safe?
- P1 needs 2 and 3 are free, so P1 runs and finishes, returning 4. Available = 3 - 2 + 4 = 5.
- P0 needs 5 and 5 are free, so P0 finishes, returning 10. Available = 10.
- P2 needs 7 and 10 are free, so it finishes.
Safe sequence: <P1, P0, P2>. The state is safe.
Now P2 requests 1 more drive. Pretend to grant it: P2 holds 3 and needs 6; available = 2.
- P1 needs 2, available is 2, so P1 finishes and returns 4. Available = 4.
- P0 needs 5 but only 4 are free. P2 needs 6 but only 4 are free.
No process can finish, so the state is unsafe. The request is denied, even though a drive is physically available.
An unsafe state does not mean deadlock has happened, only that it might.
What to say in the interview
"Banker's algorithm tentatively allocates, then looks for a safe sequence: repeatedly find a process whose remaining need fits in the available resources, let it finish and reclaim its holdings. If all can finish, the request is granted. It avoids deadlock but needs maximum needs declared upfront."
Common mistakes
- Confusing unsafe state with deadlock. Unsafe only means deadlock is possible.
- Forgetting to add back the finished process's full holdings.