Deadlock & Banker's Algorithm

What is a deadlock?

A deadlock is a situation where a group of processes are all waiting for each other, so none can ever continue.

Example: P1 holds the printer and waits for the scanner. P2 holds the scanner and waits for the printer. Both wait forever.

The four Coffman conditions

A deadlock can happen only if all four hold at once:

1. Mutual exclusion — a resource can be used by only one process at a time.
2. Hold and wait — a process holds some resources while waiting for others.
3. No preemption — resources can’t be taken away forcibly.
4. Circular wait — a cycle of processes each waiting for the next.

Four ways to handle deadlocks

Strategy	Idea
Prevention	Design rules so one condition can never hold (e.g. request all resources at once, or number resources and request in order)
Avoidance	Check every request and only grant it if the system stays safe — the Banker’s algorithm
Detection & recovery	Let deadlocks happen, detect cycles, then kill or roll back a process
Ignore it	“Ostrich algorithm” — used by most desktop OSes because deadlocks are rare

The Banker’s algorithm

Named after a banker who only lends money if they can still satisfy every customer’s maximum needs. For n processes and m resource types the OS keeps:

• Available[m] — free units of each resource,
• Max[n][m] — the most each process may ever request,
• Allocation[n][m] — what each process holds now,
• Need = Max − Allocation — what each may still request.

Safety algorithm

Work ← Available;  Finish[i] ← false
repeat:
    find i with Finish[i] = false and Need[i] ≤ Work
    if found:  Work ← Work + Allocation[i];  Finish[i] ← true
until no such i
safe if every Finish[i] is true

The idea: if a process’s remaining need fits in what’s free, it can finish and return everything it holds — so Work grows. If every process can finish in some order (a safe sequence), the state is safe.

Resource-request algorithm

When process Pi asks for Request:

1. If Request > Need[i] → error.
2. If Request > Available → Pi waits.
3. Pretend to grant it and run the safety algorithm. Safe → grant; unsafe → undo and make Pi wait.

Worked example

Resources A = 10, B = 5, C = 7. Available = (3, 3, 2).

	Allocation	Max	Need
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

Safety: P1 fits → Work (5,3,2); P3 → (7,4,3); P4 → (7,4,5); P0 → (7,5,5); P2 → (10,5,7). Safe sequence P1 → P3 → P4 → P0 → P2. Watch exactly this happen in the 3D model.

Code

def is_safe(available, alloc, maxm):
    n, m = len(alloc), len(available)
    need = [[maxm[i][j] - alloc[i][j] for j in range(m)] for i in range(n)]
    work, finish, seq = available[:], [False] * n, []
    progress = True
    while progress:
        progress = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
                work = [work[j] + alloc[i][j] for j in range(m)]
                finish[i], progress = True, True
                seq.append(f"P{i}")
    return all(finish), seq

alloc = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
maxm  = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
print(is_safe([3, 3, 2], alloc, maxm))   # (True, ['P1', 'P3', 'P4', 'P0', 'P2'])

Limitations

The Banker’s algorithm needs to know each process’s maximum needs in advance and a fixed number of processes and resources — rarely true in general-purpose OSes. That’s why it’s mostly taught as a model, while real systems prefer prevention rules (like lock ordering) or detection.

Common mistakes

• Comparing Need with Available inside the loop instead of the growing Work.
• Thinking “unsafe” means “deadlocked” — unsafe only means a deadlock is possible.
• Forgetting to roll back the pretend allocation when the request is refused.