CSE Roadmap

Common tier · about 5 hours · 7 parts

Part 5 of 7 · 2 min read

Request step

When thread P asks for a set of units, the banker's algorithm takes three steps:

  1. If the request is more than P's Need, refuse it: the thread has broken its own declared claim.
  2. If the request is more than Available, make P wait: the units are not free.
  3. Otherwise pretend to grant it: subtract the request from Available, add it to P's Allocation, and subtract it from P's Need. Run the safety algorithm on this pretended state. If it is safe, grant the request for real. If it is unsafe, put the numbers back, and make P wait.

Starting each time from the state of section 3, six requests gave these decisions:

Request Available after the pretend grant Result
P1 asks (1, 0) (1, 2) Granted: safe sequence P1, P0, P2, P3 still exists
P3 asks (1, 0) (1, 2) Refused: Needs are (4,2), (2,1), (2,1), (1,3), and none fits (1, 2)
P0 asks (1, 1) (1, 1) Refused: Needs are (3,1), (2,1), (2,1), (2,3), and none fits (1, 1)
P2 asks (2, 0) (0, 2) Granted: P2 needs only (0, 1), so it can finish first
P3 asks (0, 1) (2, 1) Granted: P1 needs (2, 1) and fits
P2 asks (1, 1) (1, 1) Granted: P2 then needs (1, 0) and fits

In plain words: Look at the second line. At that moment, 2 units of type 1 are free, and P3 asks for only 1. A plain system would grant it. The banker's algorithm refuses, because afterwards no thread could be sure to finish. P3 waits, and the other threads go on. When any of them finishes and returns units, P3's request is tried again.

Pretend grant

A pretend grant is the step in which the system changes its tables as if a request had been granted, tests the new state for safety, and keeps the change only if the state is safe.

Example: P3 asks for (1, 0); the pretend state has Available (1, 2), no thread fits, so the change is undone.

Check yourself: 1. In which of the three steps is a request refused for exceeding the declared claim? 2. Why does the system pretend to grant first and not simply grant? 3. What happens to a thread whose request was refused as unsafe?