Deadlock Avoidance: Banker's Algorithm

By the end of this lesson you will be able to build the Need matrix, run the safety algorithm by hand and in Python, and decide whether a resource request should be granted or made to wait.

Prevention breaks one of the four deadlock conditions for ever, which is often wasteful. Avoidance is smarter: it allows all four conditions but checks every request before granting it, and refuses any request that could lead to trouble. The best-known avoidance method is Dijkstra's Banker's algorithm.

The banker's idea

Imagine a small cooperative bank in a village near Rohtak with ₹10 lakh to lend. Each farmer has a declared credit limit, the most they will ever borrow this season. A farmer repays only after receiving their full limit, because only then can they finish planting and sell the crop.

The careful banker never lends money if, after lending, there is no order in which every farmer could still get their full limit and repay. The banker does not need every farmer to finish at once, just a sequence that works: first Kabir, whose repayment then lets Meera finish, and so on.

Replace farmers with processes and money with resources, and you have the algorithm.

The data structures

For n processes and m resource types, the algorithm keeps:

A system with three resource types A, B and C (8, 6 and 5 instances in total) and five processes is in this state:

Step 1: compute Available by hand. The Allocation columns add up to 6, 4 and 3. So Available is (8 - 6, 6 - 4, 5 - 3) = (2, 2, 2).

Step 2: compute Need for P0: (4 - 1, 3 - 1, 1 - 0) = (3, 2, 1). Do the other four yourself before running the code.

Safe and unsafe states

A state is safe if there is at least one order of all processes, called a safe sequence, in which each process can get everything it still needs from what is free plus what earlier processes in the sequence have released.

• A safe state can never deadlock if the system keeps it safe.
• An unsafe state is not yet a deadlock, but it might become one, depending on what processes request next. The banker refuses to enter unsafe states at all.

The safety algorithm

1. Let Work = Available. Mark every process as not finished.
2. Find a process that is not finished and whose Need <= Work (every component).
3. Pretend it runs to the end and returns everything: Work = Work + Allocation for that process. Mark it finished.
4. Repeat from step 2. If every process gets marked, the state is safe; if you get stuck, it is unsafe.

total      = [8, 6, 5]                       # instances of A, B, C
allocation = {"P0": [1, 1, 0], "P1": [2, 0, 1], "P2": [0, 2, 1], "P3": [1, 0, 1], "P4": [2, 1, 0]}
maximum    = {"P0": [4, 3, 1], "P1": [3, 2, 2], "P2": [2, 4, 3], "P3": [1, 3, 2], "P4": [5, 2, 1]}

need = {p: [m - a for m, a in zip(maximum[p], allocation[p])] for p in maximum}
available = [t - sum(col) for t, col in zip(total, zip(*allocation.values()))]
print("Available:", available)
for p in need:
    print(f"{p} need {need[p]}")

def is_safe(available, allocation, need):
    work, finished, order = list(available), set(), []
    progress = True
    while progress:
        progress = False
        for p in need:
            if p not in finished and all(n <= w for n, w in zip(need[p], work)):
                work = [w + a for w, a in zip(work, allocation[p])]   # p finishes, returns all
                finished.add(p); order.append(p); progress = True
                print(f"  {p} can finish -> work = {work}")
    return len(finished) == len(need), order

safe, order = is_safe(available, allocation, need)
print("SAFE, sequence:" if safe else "UNSAFE", " ".join(order))

Available: [2, 2, 2]
P0 need [3, 2, 1]
P1 need [1, 2, 1]
P2 need [2, 2, 2]
P3 need [0, 3, 1]
P4 need [3, 1, 1]
  P1 can finish -> work = [4, 2, 3]
  P2 can finish -> work = [4, 4, 4]
  P3 can finish -> work = [5, 4, 5]
  P4 can finish -> work = [7, 5, 5]
  P0 can finish -> work = [8, 6, 5]
SAFE, sequence: P1 P2 P3 P4 P0

Step 3: check one step by hand. With Work = (2, 2, 2), P0 needs (3, 2, 1), and 3 > 2, so P0 must wait. P1 needs (1, 2, 1), which fits. P1 finishes and returns its allocation (2, 0, 1), so Work becomes (4, 2, 3). Carry on in the same way.

Notice that the final Work equals the total (8, 6, 5): once everyone has finished, everything is free again. That is a handy check on your arithmetic. There can be more than one safe sequence; exams usually accept any correct one, or ask you to scan processes in order as the code does.

The resource-request algorithm

When process Pi asks for a vector Request, the banker:

1. Checks Request <= Need[i]. If not, it is an error: the process broke its own declared maximum.
2. Checks Request <= Available. If not, Pi must wait: the resources are simply not free.
3. Pretends to grant it: Available -= Request, Allocation[i] += Request, Need[i] -= Request.
4. Runs the safety algorithm on this pretend state. If it is safe, grant the request for real. If not, undo the pretend changes and make Pi wait.

Here four separate requests are each checked against the original state above.

total      = [8, 6, 5]
allocation = {"P0": [1, 1, 0], "P1": [2, 0, 1], "P2": [0, 2, 1], "P3": [1, 0, 1], "P4": [2, 1, 0]}
maximum    = {"P0": [4, 3, 1], "P1": [3, 2, 2], "P2": [2, 4, 3], "P3": [1, 3, 2], "P4": [5, 2, 1]}
need = {p: [m - a for m, a in zip(maximum[p], allocation[p])] for p in maximum}
available = [t - sum(col) for t, col in zip(total, zip(*allocation.values()))]

def is_safe(available, allocation, need):
    work, finished, order = list(available), set(), []
    progress = True
    while progress:
        progress = False
        for p in need:
            if p not in finished and all(n <= w for n, w in zip(need[p], work)):
                work = [w + a for w, a in zip(work, allocation[p])]
                finished.add(p); order.append(p); progress = True
    return len(finished) == len(need), order

def request(p, req):
    print(f"{p} requests {req}")
    if any(r > n for r, n in zip(req, need[p])):
        return print("  error: asks for more than its declared maximum")
    if any(r > a for r, a in zip(req, available)):
        return print("  must wait: not enough available")
    avail2 = [a - r for a, r in zip(available, req)]
    alloc2 = {**allocation, p: [a + r for a, r in zip(allocation[p], req)]}
    need2 = {**need, p: [n - r for n, r in zip(need[p], req)]}
    safe, order = is_safe(avail2, alloc2, need2)
    if safe:
        print("  GRANT, safe sequence:", " ".join(order))
    else:
        print("  DENY for now: the new state would be unsafe")

for p, r in [("P4", [1, 0, 1]), ("P0", [2, 1, 0]), ("P3", [0, 1, 0]), ("P2", [3, 0, 0])]:
    request(p, r)

P4 requests [1, 0, 1]
  GRANT, safe sequence: P1 P2 P3 P4 P0
P0 requests [2, 1, 0]
  DENY for now: the new state would be unsafe
P3 requests [0, 1, 0]
  DENY for now: the new state would be unsafe
P2 requests [3, 0, 0]
  error: asks for more than its declared maximum

The P3 result surprises most students. P3 asks for just one unit of B, and one is free. But after granting it, Available would be (2, 1, 2), and no process's Need fits inside that, so the banker refuses. Small requests can be dangerous too.

Strengths and limits

• The algorithm runs in about m x n x n steps for each request, which is fine for small systems but too slow to run on every lock in a modern OS.
• Every process must declare its maximum needs in advance, which real programs rarely know.
• The number of processes and resources must stay fixed while it runs.

These limits are why general-purpose kernels do not use it for application locks. The ideas still matter: safe states, careful admission and "check before you grant" appear in resource managers, cloud schedulers and exams. For single-instance resources, an avoidance variant uses the resource allocation graph with dashed claim edges and refuses any request that would create a cycle.

Common mistakes

• Using Max instead of Need in the comparison. The test is Need <= Work, not Max <= Work.
• Forgetting to add Allocation back. When a process finishes, Work grows by that process's Allocation, not by its Need.
• Calling an unsafe state a deadlock. Unsafe means deadlock may happen; it has not necessarily happened.

Key points

• Avoidance checks each request and grants it only if the resulting state is safe.
• Need = Max - Allocation and Available = Total - sum of Allocation.
• The safety algorithm repeatedly finds a process with Need <= Work, then adds its Allocation to Work.
• A safe sequence is an order in which every process can finish.
• A request must be within Need and Available, and must leave the system safe.
• Processes must declare maximum needs in advance, which limits real-world use.

request("P1", [1, 0, 1])

P1 requests [1, 0, 1]
  GRANT, safe sequence: P1 P2 P3 P4 P0