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

Source: https://skills101.in/learn/operating-systems/os-bankers-algorithm — Skills101 free tutorial (Operating Systems). Updated 2026-11-18.

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:

| Table | Size | Meaning |
|---|---|---|
| **Available** | m | free instances of each resource right now |
| **Max** | n × m | the most each process may ever ask for (declared in advance) |
| **Allocation** | n × m | what each process holds now |
| **Need** | n × m | **Max − 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.

| Process | Allocation (A B C) | Max (A B C) | Need (A B C) |
|---|---|---|---|
| P0 | 1 0 1 | 3 2 2 | 2 2 1 |
| P1 | 2 1 0 | 4 2 1 | 2 1 1 |
| P2 | 1 1 1 | 3 3 2 | 2 2 1 |
| P3 | 0 1 1 | 1 1 2 | 1 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](https://skills101.in/learn-img/operating-systems/bankers-trace.svg)

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](https://skills101.in/learn-img/operating-systems/request-flow.svg)

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

```python
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))
```

```text
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.

| Process | Allocation (A B C) | Request (A B C) |
|---|---|---|
| P0 | 0 1 0 | 0 0 0 |
| P1 | 2 0 0 | 2 0 2 |
| P2 | 3 0 3 | 0 0 0 |
| P3 | 2 1 1 | 1 0 0 |
| P4 | 0 0 2 | 0 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 n | Max need k | Minimum R |
|---|---|---|
| 3 | 2 | 4 |
| 3 | 4 | 10 |
| 5 | 3 | 11 |

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 quiz and free certificate: https://skills101.in/learn/operating-systems/os-bankers-algorithm