CSE Roadmap

Common tier · about 5 hours · 7 parts

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?