Banker's Algorithm

The Banker's Algorithm is a deadlock-*avoidance* strategy. Before granting any resource request, it checks whether doing so would still leave the system in a safe state — one where every process can run to completion in *some* order. If granting the request might leave no such order, the request waits, even though the resources are physically free. The name comes from a cautious banker who lends cash only if every customer could still be paid off.

The four tables it tracks

1. 1Allocation — how much of each resource each process is holding right now.
2. 2Max — the most of each resource each process declared, up front, that it could ever need.
3. 3Need — what each process might still request: Need = Max - Allocation.
4. 4Available — the free resources still in the pool (also called the *Work* vector).

The safety check

A state is safe if there's an order in which every process can finish. The check simulates that: repeatedly find a process whose remaining Need fits within the resources currently available, then pretend it finishes and returns everything it held.

Work = Available
Finish[i] = false for every process i

repeat:
  find an i with Finish[i] == false AND Need[i] <= Work
  if found:
    Work = Work + Allocation[i]   // i finishes, returns its resources
    Finish[i] = true
  else:
    stop

safe  if  Finish[i] == true for every i

Worked example

Five processes, three resource types, totals (10, 5, 7):

Available = (3, 3, 2)

      Allocation   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

Start with Work = (3,3,2). P1's Need (1,2,2) fits, so run P1 and reclaim its Allocation -> Work = (5,3,2). Now P3's Need (0,1,1) fits -> Work = (7,4,3). Then P4 -> (7,4,5), P0 -> (7,5,5), and finally P2 -> (10,5,7). Every process finished, so the state is safe, with safe sequence P1 -> P3 -> P4 -> P0 -> P2.