Skills101

AdvancedOperating Systems · Lesson 11 of 12 · Updated ·

Banker's Algorithm in Practice — Safety Check, Resource Requests and Deadlock Detection (with Python)

Lesson 5 introduced deadlocks and found one safe sequence by hand. Exams go further: "Can this request be granted immediately?", "Is the system deadlocked right now?", "How many resources guarantee no deadlock?" This lesson answers all three — and gives you a short Python program that does the checking, so you can verify any answer you work out on paper.

1. The four tables

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

TableSizeMeaning
Availablemfree instances of each resource right now
Maxn × mthe most each process may ever ask for (declared in advance)
Allocationn × mwhat each process holds now
Needn × mMax − Allocation: what it may still ask for

Think of a bank. Each customer has a credit limit (Max) and has already borrowed some money (Allocation). The bank lends more only if, even in the worst case, it can still let every customer finish and repay.

Our example: 4 processes, resources A, B, C with 6, 4, 4 instances in total.

ProcessAllocation (A B C)Max (A B C)Need (A B C)
P01 0 13 2 22 2 1
P12 1 04 2 12 1 1
P21 1 13 3 22 2 1
P30 1 11 1 21 0 1

Allocated in total = (4, 3, 3), so Available = (6, 4, 4) − (4, 3, 3) = (2, 1, 1).

2. The safety algorithm

  1. Set Work = Available, and mark every process as not finished.
  2. Find an unfinished process whose Need ≤ Work (every component).
  3. Pretend it runs to the end and returns everything: Work = Work + Allocation. Mark it finished.
  4. Repeat. If all processes finish, the state is safe; the order you used is a safe sequence.

Safety check table: P1 needs (2,1,1) with Work (2,1,1) and Work becomes (4,2,1); P2 then (5,3,2); P3 then (5,4,3); P0 then (6,4,4); safe sequence P1, P2, P3, P0

Scanning P0, P1, P2, P3 in order: P0 needs (2, 2, 1) but Work has only 1 B, so skip it. P1's need (2, 1, 1) fits exactly. After P1 returns its allocation, P2, P3 and finally P0 can finish. Safe sequence: ⟨P1, P2, P3, P0⟩. Other safe sequences may exist — any one is enough to prove safety.

At the end Work equals the total (6, 4, 4). That is a useful self-check: if your final Work is not the total, you added something wrong.

3. The resource-request algorithm

When process Pi asks for a vector Request:

Flowchart: if Request is more than Need it is an error; if Request is more than Available the process waits; otherwise pretend to grant it and run the safety check — grant if safe, undo and make the process wait if unsafe

  1. If Request > Need → error (it asked for more than it declared).
  2. If Request > Available → wait (the resources simply are not free).
  3. Pretend to grant: Available −= Request, Allocation += Request, Need −= Request.
  4. Run the safety algorithm. Safe → grant. Unsafe → undo the pretend step; Pi waits.

Step 4 is the heart of avoidance: a request can be refused even when the resources are free right now.

4. The program

def is_safe(available, alloc, need):
    work = list(available)
    finished = [False] * len(alloc)
    order = []
    progress = True
    while progress:
        progress = False
        for i in range(len(alloc)):
            if not finished[i] and all(n <= w for n, w in zip(need[i], work)):
                work = [w + a for w, a in zip(work, alloc[i])]
                finished[i] = True
                order.append(f"P{i}")
                progress = True
    return all(finished), order

def request(i, req, available, alloc, need):
    if any(r > n for r, n in zip(req, need[i])):
        return "error: more than its declared maximum"
    if any(r > a for r, a in zip(req, available)):
        return "wait: resources not free"
    new_avail = [a - r for a, r in zip(available, req)]
    new_alloc = [row[:] for row in alloc]
    new_need = [row[:] for row in need]
    new_alloc[i] = [a + r for a, r in zip(alloc[i], req)]
    new_need[i] = [n - r for n, r in zip(need[i], req)]
    safe, order = is_safe(new_avail, new_alloc, new_need)
    return f"GRANT, safe sequence {order}" if safe else "wait: granting would be unsafe"

alloc = [[1, 0, 1], [2, 1, 0], [1, 1, 1], [0, 1, 1]]
maximum = [[3, 2, 2], [4, 2, 1], [3, 3, 2], [1, 1, 2]]
available = [2, 1, 1]
need = [[m - a for m, a in zip(mr, ar)] for mr, ar in zip(maximum, alloc)]

print("Need:", need)
print("Safe now?", is_safe(available, alloc, need))
print("P3 asks (1,0,1):", request(3, [1, 0, 1], available, alloc, need))
print("P0 asks (1,0,1):", request(0, [1, 0, 1], available, alloc, need))
print("P1 asks (3,0,0):", request(1, [3, 0, 0], available, alloc, need))
print("P2 asks (0,2,0):", request(2, [0, 2, 0], available, alloc, need))
Need: [[2, 2, 1], [2, 1, 1], [2, 2, 1], [1, 0, 1]]
Safe now? (True, ['P1', 'P2', 'P3', 'P0'])
P3 asks (1,0,1): GRANT, safe sequence ['P3', 'P0', 'P1', 'P2']
P0 asks (1,0,1): wait: granting would be unsafe
P1 asks (3,0,0): error: more than its declared maximum
P2 asks (0,2,0): wait: resources not free

Each request is tested on the original state, independently.

5. Why P0's request is refused

P0 asks for (1, 0, 1). It is within its Need (2, 2, 1) and the resources are free (Available (2, 1, 1)). Pretend to grant:

  • Available becomes (1, 1, 0).
  • Needs become: P0 (1, 2, 0), P1 (2, 1, 1), P2 (2, 2, 1), P3 (1, 0, 1).

Now check every process: P0 needs 2 B (only 1 free); P1 and P2 need 2 A (only 1 free); P3 needs 1 C (none free). Nobody can be guaranteed to finish → unsafe → P0 must wait.

Compare P3's request (1, 0, 1): after granting it, P3's Need is (0, 0, 0), so P3 can finish at once and return everything. That keeps the system safe.

6. Deadlock detection (no Max table)

Avoidance needs every process to declare its maximum in advance, which real programs rarely can. Detection instead lets requests happen and checks later. The algorithm is the safety check with Request (what each process is waiting for right now) in place of Need.

ProcessAllocation (A B C)Request (A B C)
P00 1 00 0 0
P12 0 02 0 2
P23 0 30 0 0
P32 1 11 0 0
P40 0 20 0 2

Available = (0, 0, 0). P0 and P2 request nothing, so they can finish and release: Work goes (0,1,0) → (3,1,3); then P3 → (5,2,4); P4 → (5,2,6); P1 → (7,2,6). No deadlock.

Now suppose P2 also requests one more C: Request(P2) = (0, 0, 1). Only P0 can finish (Work becomes (0, 1, 0)), and nobody else's request fits. P1, P2, P3 and P4 are deadlocked. The OS must now recover — for example by terminating one of them.

7. The "minimum resources" formula

n processes each need at most k instances of one resource type. What is the smallest number R of instances that makes deadlock impossible?

Worst case: every process holds k − 1 and waits for one more. If there is even one extra instance, some process can finish and release everything. So:

R = n(k − 1) + 1

Processes nMax need kMinimum R
324
3410
5311

The question is often reversed: "6 tape drives, each process needs 2 — what is the maximum number of processes without deadlock?" Solve n(2 − 1) + 1 ≤ 6 → n ≤ 5.

Common mistakes

  • Comparing Request with Max instead of with Need.
  • Granting a request just because the resources are free — always run the safety check after the pretend step.
  • Forgetting to undo the pretend allocation when the result is unsafe.
  • In detection, using Need instead of the current Request matrix.
  • Writing R = n(k − 1) and forgetting the + 1.

Quick recap

  • Need = Max − Allocation; Work starts as Available and grows by each finished process's Allocation.
  • Request check: ≤ Need, ≤ Available, then pretend and run the safety algorithm.
  • Free resources are not enough — the state after granting must be safe.
  • Detection = the same loop with the current Request matrix; processes that never finish are deadlocked.
  • Deadlock-free minimum: R = n(k − 1) + 1.

Practice what you learned

📝 Quiz: Banker's Algorithm in Practice5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →