Part 4 of 7 · 2 min read
The tables
In plain words: With several resource types, the same idea needs tables. The banker's algorithm (first published by Dijkstra in 1965, and named for the bank analogy) keeps four pieces of data for n threads and m resource types:
| Name | Shape | Meaning |
|---|---|---|
| Available | m numbers |
Free units of each type |
| Max | n × m |
The most each thread may ever hold |
| Allocation | n × m |
What each thread holds now |
| Need | n × m |
Max − Allocation: what each thread may still ask for |
Here is a made-up state with two resource types. The system has 10 units of type 1 and 6 units of type 2, and four threads, P0 to P3:
| Thread | Allocation | Max | Need |
|---|---|---|---|
| P0 | (2, 1) | (6, 3) | (4, 2) |
| P1 | (3, 2) | (5, 3) | (2, 1) |
| P2 | (2, 1) | (4, 2) | (2, 1) |
| P3 | (1, 0) | (3, 3) | (2, 3) |
The units held in total are (8, 4), so Available = (10 − 8, 6 − 4) = (2, 2).
The safety algorithm finds out whether the state is safe. Start with a work vector equal to Available. Repeat: find a thread whose Need is at most the work vector in every type, pretend it runs to the end, and add its Allocation to the work vector. If all threads can be taken in this way, the state is safe, and the order is a safe sequence. If at some point no thread fits, the state is unsafe.
Trace, computed by running the code of section 5:
| Step | Work | Thread chosen | Its Need | Work after it returns its Allocation |
|---|---|---|---|---|
| 1 | (2, 2) | P1 | (2, 1) ≤ (2, 2) | (2, 2) + (3, 2) = (5, 4) |
| 2 | (5, 4) | P0 | (4, 2) ≤ (5, 4) | (5, 4) + (2, 1) = (7, 5) |
| 3 | (7, 5) | P2 | (2, 1) ≤ (7, 5) | (7, 5) + (2, 1) = (9, 6) |
| 4 | (9, 6) | P3 | (2, 3) ≤ (9, 6) | (9, 6) + (1, 0) = (10, 6) |
The state is safe, with the safe sequence P1, P0, P2, P3. A machine count of all orders found 12 safe sequences in this state. The work vector ends at (10, 6), equal to the totals, as it must when everything is returned.
Banker's algorithm
The banker's algorithm is a deadlock-avoidance method that keeps the tables Available, Max, Allocation and Need, runs the safety algorithm on a pretended state, and grants a request only if that state is safe.
Example: in the table, the safety algorithm finds the order P1, P0, P2, P3, so the starting state is safe.
Check yourself:
1. How is the Need table calculated from the other tables?
2. In step 1, why can P1 be chosen but P3 cannot?
3. What does the safety algorithm do when no thread fits the work vector?