The banker's algorithm avoids deadlock by refusing any allocation that could leave the system unsafe: a state where there is no order in which every process can finish. Exam questions give the Allocation and Max matrices and the Available vector, then ask for the Need matrix, whether the state is safe, a safe sequence, and whether a request can be granted. This page works the classic textbook example (from Silberschatz's Operating System Concepts) all the way through.
The example
Five processes, three resource types: A (10 instances), B (5) and C (7).
| Process | Allocation (A B C) | Max (A B C) |
|---|---|---|
| P0 | 0 1 0 | 7 5 3 |
| P1 | 2 0 0 | 3 2 2 |
| P2 | 3 0 2 | 9 0 2 |
| P3 | 2 1 1 | 2 2 2 |
| P4 | 0 0 2 | 4 3 3 |
Available = (3, 3, 2). (10, 5, 7 minus the column totals of Allocation, 7, 2, 5.)
Step 1: the Need matrix
Need = Max − Allocation, row by row: what each process may still ask for.
| Process | Need (A B C) |
|---|---|
| P0 | 7 4 3 |
| P1 | 1 2 2 |
| P2 | 6 0 0 |
| P3 | 0 1 1 |
| P4 | 4 3 1 |
Step 2: the safety check
Start with Work = Available = (3, 3, 2) and every process unfinished. Repeatedly find an unfinished process whose Need ≤ Work in every column; pretend it runs to completion and releases its Allocation (Work += Allocation). Scanning from P0 each time:
| Step | Work before | Picked | Its Need | Work after (+ its Allocation) |
|---|---|---|---|---|
| 1 | (3, 3, 2) | P1 | (1, 2, 2) | (5, 3, 2) |
| 2 | (5, 3, 2) | P3 | (0, 1, 1) | (7, 4, 3) |
| 3 | (7, 4, 3) | P0 | (7, 4, 3) | (7, 5, 3) |
| 4 | (7, 5, 3) | P2 | (6, 0, 0) | (10, 5, 5) |
| 5 | (10, 5, 5) | P4 | (4, 3, 1) | (10, 5, 7) |
Every process finishes, so the state is safe, with safe sequence ⟨P1, P3, P0, P2, P4⟩. The final Work equals the total instances (10, 5, 7), a good check on your arithmetic.
More than one safe sequence
At step 3, both P0 and P4 fit (Work (7, 4, 3) covers P4's Need (4, 3, 1) too). Picking P4 first gives ⟨P1, P3, P4, P2, P0⟩, the sequence printed in the textbook. Both are correct: any order in which every process can finish is a safe sequence. If your answer differs from the key, check that each process's Need really fits the Work at its step.
Step 3: resource requests
When a process asks for resources, the algorithm checks three things in order:
- Request ≤ Need (it can't ask for more than it declared), otherwise it's an error.
- Request ≤ Available, otherwise it must wait.
- Pretend to grant it, then run the safety check on the new state. Safe → grant; unsafe → roll back and make it wait.
P1 requests (1, 0, 2). It is ≤ Need (1, 2, 2) and ≤ Available (3, 3, 2). Granting gives Available = (2, 3, 0), P1's Allocation (3, 0, 2) and Need (0, 2, 0). The safety check still finds ⟨P1, P3, P0, P2, P4⟩, so it is granted.
Now, in that new state:
P4 requests (3, 3, 0). Only (2, 3, 0) is available, so P4 must wait: the resources simply aren't there.
P0 requests (0, 2, 0). It fits Need and Available, so try it: Available would drop to (2, 1, 0). Now no process's Need fits: P1 needs (0, 2, 0) but only 1 B is free, P3 needs (0, 1, 1) but no C is free, and the others need more. The state would be unsafe, so the request is refused and P0 waits, even though the resources physically exist.
Common mistakes
- Comparing against Max instead of Need in the safety check.
- Forgetting to add the finished process's Allocation back to Work.
- Granting a request because Available covers it, without running the safety check on the new state.
- Thinking unsafe means deadlocked. Unsafe means deadlock is possible; the algorithm refuses to take that risk.
Check your own answers
The banker's algorithm calculator computes the Need matrix, runs the safety check with the Work vector at every step, finds a safe sequence, and tests resource requests, with the same three checks as above. For the rest of the OS course, see page replacement and round robin scheduling.
Use the CPU Scheduling Calculator to trace CPU scheduling as another operating systems exercise.