Banker's algorithm: safe state and worked example

Difficulty: Advanced

Question

Explain the Banker's algorithm. Given 5 processes and 3 resource types, find a safe sequence and decide whether P1's request (1,0,2) can be granted.

Answer

The Banker's algorithm, by Dijkstra, is the standard deadlock avoidance technique, and it is named after a banker who never lends out so much money that they could not satisfy all customers' maximum credit lines eventually. Each process must declare its maximum resource need in advance. On every request, the system pretends to grant it and then checks whether the new state is still safe. A state is safe if there exists at least one ordering of the processes, a safe sequence, such that each one can obtain its remaining needs from the resources currently available plus those freed by earlier processes in the sequence. An unsafe state is not a deadlock yet, but it carries a risk of one; the algorithm simply refuses to enter it.

The data structures are matrices. Available is a vector of free instances per resource type. Max is the maximum demand of each process. Allocation is what each process holds now. Need = Max - Allocation. The safety algorithm sets Work = Available and marks all processes unfinished. It then repeatedly finds an unfinished process whose Need is less than or equal to Work component-wise. If found, it pretends that process finishes, adds its Allocation to Work, marks it finished, and continues. If all processes finish, the state is safe, and the order found is a safe sequence.

Let's do the classic example. Total resources are A=10, B=5, C=7. Allocation is P0 (0,1,0), P1 (2,0,0), P2 (3,0,2), P3 (2,1,1), P4 (0,0,2). Max is P0 (7,5,3), P1 (3,2,2), P2 (9,0,2), P3 (2,2,2), P4 (4,3,3). Summing allocations gives (7,2,5), so Available = (10,5,7) - (7,2,5) = (3,3,2). The Need matrix is P0 (7,4,3), P1 (1,2,2), P2 (6,0,0), P3 (0,1,1), P4 (4,3,1).

Safety check with Work = (3,3,2). P0 needs (7,4,3), too big. P1 needs (1,2,2), fits, so P1 finishes and Work becomes (5,3,2). P3 needs (0,1,1), fits, Work becomes (7,4,3). P4 needs (4,3,1), fits, Work becomes (7,4,5). P0 needs (7,4,3), fits now, Work becomes (7,5,5). P2 needs (6,0,0), fits, Work becomes (10,5,7), which equals the total, a good sanity check. The safe sequence is P1, P3, P4, P0, P2. Other valid sequences exist; any one suffices.

Now the resource request: P1 requests (1,0,2). Step one, is Request <= Need? (1,0,2) <= (1,2,2) yes. Step two, is Request <= Available? (1,0,2) <= (3,3,2) yes. Step three, pretend to allocate: Available becomes (2,3,0), P1's Allocation becomes (3,0,2), P1's Need becomes (0,2,0). Run the safety algorithm with Work = (2,3,0): P1 fits (0,2,0), Work becomes (5,3,2); P3 fits, (7,4,3); P4 fits, (7,4,5); P0 fits, (7,5,5); P2 fits, (10,5,7). Safe, so the request is granted.

Try two more requests on the new state to see denials. P4 requests (3,3,0): it is within its need (4,3,1) but Available is (2,3,0), so 3 > 2 in A and P4 must wait. P0 requests (0,2,0): within need and within available, but pretending to grant leaves Available (2,1,0), and no process's need fits (P0 needs (7,2,3), P1 needs (0,2,0) but B=1 is short, P3 needs C=1 but C=0), so the state is unsafe and the request is denied.

Limitations to mention: it requires knowing maximum needs in advance, assumes a fixed number of processes and resources, and costs O(m times n squared) per check, so real operating systems rarely use it, although the concept underlies safe resource management in databases and embedded systems.

Code examples

Banker's algorithm worked tables

Total = (10,5,7)
        Alloc    Max      Need = Max-Alloc
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
Available = (10,5,7) - (7,2,5) = (3,3,2)

Safety run (Work starts at 3 3 2)
 P1 need 1 2 2 <= Work -> Work = 5 3 2
 P3 need 0 1 1 <= Work -> Work = 7 4 3
 P4 need 4 3 1 <= Work -> Work = 7 4 5
 P0 need 7 4 3 <= Work -> Work = 7 5 5
 P2 need 6 0 0 <= Work -> Work = 10 5 7
Safe sequence: <P1, P3, P4, P0, P2>

Request P1 = (1,0,2): <= Need (1,2,2), <= Available (3,3,2)
 Pretend: Available = 2 3 0, P1 Alloc = 3 0 2, P1 Need = 0 2 0
 Safety re-run gives P1, P3, P4, P0, P2 -> SAFE -> GRANT

Then P4 = (3,3,0): Available (2,3,0) is too small in A -> WAIT
Then P0 = (0,2,0): pretend Available = (2,1,0) -> no process can finish -> UNSAFE -> DENY

Each step checks Need <= Work and adds the finished process's allocation back to Work.

Key points

• Need = Max - Allocation; Available = Total - sum of Allocations.
• Safe state means at least one safe sequence exists; unsafe does not mean deadlocked.
• A request is granted only if it is within Need, within Available, and leaves a safe state.
• Final Work equals the total resources when all processes finish, a useful sanity check.
• Banker's needs maximum demands upfront, which limits practical use.

Concepts covered

Banker's algorithm, safe state, deadlock avoidance, need matrix, safe sequence