The idea: never enter an unsafe state
A deadlock needs processes that hold some resources while they wait for more. The Banker's algorithm (Dijkstra, 1965) avoids it the way a careful banker lends money: every customer states its credit limit up front, and the banker hands out a loan only if, afterwards, it can still serve every customer to the end in some order. A state where that is possible is safe. The OS grants a request only if the state after it is still safe.
The four tables
The page uses the classic example from Silberschatz's Operating System Concepts: five processes P0–P4 and three resource types A, B and C, with 10, 5 and 7 instances.
- Max: the most of each type a process will ever hold at once. It declares this when it starts.
- Allocation: what it holds now.
- Need = Max − Allocation: the most it may still ask for.
- Available = Total − all Allocation: what the OS has left. At the start it is (3, 3, 2).
| Process | Allocation | Max | Need |
|---|---|---|---|
| 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 |
The safety algorithm
The state is safe if there is a safe sequence: an order in which each process can get its whole Need from what is free plus what the processes before it return.
Work = Available; Finish[i] = false for all i
repeat:
find i with Finish[i] == false and Need[i] <= Work
if none: break
Work = Work + Allocation[i] // Pi finishes and gives everything back
Finish[i] = true
safe if Finish[i] == true for all i
The page scans the processes round the circle: after a process passes, it goes on with the next one. On the starting state (Demo: safety check, starting state) Work grows like this:
| Test | Need ≤ Work? | Work after |
|---|---|---|
| P0 | (7, 4, 3) ≤ (3, 3, 2)? no ✗ | (3, 3, 2) |
| P1 | (1, 2, 2) ≤ (3, 3, 2)? yes ✓ | (5, 3, 2) |
| P2 | (6, 0, 0) ≤ (5, 3, 2)? no ✗ | (5, 3, 2) |
| P3 | (0, 1, 1) ≤ (5, 3, 2)? yes ✓ | (7, 4, 3) |
| P4 | (4, 3, 1) ≤ (7, 4, 3)? yes ✓ | (7, 4, 5) |
| P0 | (7, 4, 3) ≤ (7, 4, 5)? yes ✓ | (7, 5, 5) |
| P2 | (6, 0, 0) ≤ (7, 5, 5)? yes ✓ | (10, 5, 7) |
So ⟨P1, P3, P4, P0, P2⟩ is a safe sequence and the state is safe. Work always ends at the Total when the state is safe, since every process has given its resources back. Other scan orders can find other safe sequences; any one is enough.
Handling a request
When Pi asks for a vector Request, the banker checks three things:
- Request ≤ Need, or the process broke its promise: an error.
- Request ≤ Available, or the resources are not there: the process waits. Demo: P4 requests (3,3,0): only (2, 3, 0) is free, so P4 waits.
- Pretend to grant it (Available −= Request, Allocation += Request, Need −= Request) and run the safety algorithm. Safe: the grant stands. Unsafe: roll back, and the process waits.
Demo: P1 requests (1,0,2): the pretend state has Available = (2, 3, 0), and ⟨P1, P3, P4, P0, P2⟩ is still safe, so P1 gets it. Demo: P0 requests (0,2,0) starts from that state. The resources are free, but afterwards Available = (2, 1, 0) and no process's Need fits: unsafe. The banker rolls back and P0 waits, even though it could have been served.
Unsafe is not deadlock
In an unsafe state nobody is blocked yet. Max is only a worst case: a process may finish without asking for all of it. In Demo: unsafe is not deadlock, if P3 finishes early and returns (2, 1, 1), Work becomes (4, 2, 1) and everyone else can finish. But if every process does ask for its whole Need, nobody can be served and all of them block. Unsafe means the OS can no longer promise that this won't happen, so the banker never goes there.
Why real systems rarely use it
The safety check costs O(m × n²) for n processes and m resource types, on every request. Worse, processes must know their Max in advance, and the number of processes and resources must stay fixed. Real kernels prefer prevention (a lock order, as in Dining Philosophers), or they detect deadlocks and recover. The algorithm still shows up where claims are known, such as admission control for jobs with declared memory or GPU limits. See also Mutex for what blocking on a lock looks like, and CPU Scheduling for how the processes share the CPU while they hold their resources.
What the page leaves out
Processes that come and go, and resources that are added or removed. Releasing part of an allocation before finishing. The deadlock detection algorithm, which runs the same Work/Finish loop on current requests instead of Need. And Dijkstra's original version for a single resource type, where Work is one number (Habermann extended it to several types).