Deadlock avoidance with the banker's algorithm

Grant a resource request only if the resulting state is safe: every process can still finish.

Python

def safe_sequence(available, allocation, maximum):
    need = [[m - a for m, a in zip(mx, al)] for mx, al in zip(maximum, allocation)]
    work = list(available)
    finished = [False] * len(allocation)
    order = []
    progress = True
    while progress:
        progress = False
        for i, row in enumerate(need):
            if not finished[i] and all(n <= w for n, w in zip(row, work)):
                work = [w + a for w, a in zip(work, allocation[i])]
                finished[i] = True
                order.append(f"P{i}")
                progress = True
    return order if all(finished) else None


def try_request(available, allocation, maximum, process, request):
    if any(r > a for r, a in zip(request, available)):
        return None
    new_available = [a - r for a, r in zip(available, request)]
    new_allocation = [row[:] for row in allocation]
    new_allocation[process] = [x + r for x, r in zip(new_allocation[process], request)]
    if safe_sequence(new_available, new_allocation, maximum) is None:
        return None
    return new_available, new_allocation


available = [3, 3, 2]
allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]]
maximum = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
print(safe_sequence(available, allocation, maximum))

state = (available, allocation)
for process, request in ((1, [1, 0, 2]), (4, [3, 3, 0]), (0, [0, 2, 0])):
    outcome = try_request(state[0], state[1], maximum, process, request)
    print(f"P{process} {request}:", "granted" if outcome else "denied")
    if outcome:
        state = outcome

Output

['P1', 'P3', 'P4', 'P0', 'P2']
P1 [1, 0, 2]: granted
P4 [3, 3, 0]: denied
P0 [0, 2, 0]: denied

Explanation

A deadlock is a set of processes each waiting for a resource held by another, so none can proceed. Four conditions must hold together (the Coffman conditions): mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any one of them prevents deadlock.

Deadlock avoidance lets the system grant a request only when the result is a safe state. A state is safe if there is some order, a safe sequence, in which every process can obtain its maximum remaining need and finish. Dijkstra's banker's algorithm checks this. It repeatedly looks for a process whose remaining need fits in the available resources, lets it finish, and returns its allocation to the pool. If every process can finish this way, the state is safe.

The program uses a standard textbook example with five processes and three resource types. Need is maximum minus allocation. To handle a request, the system pretends to grant it and runs the safety check on the new state. Process P1 asking for (1, 0, 2) is granted. P4 asking for (3, 3, 0) is denied because that exceeds what is available. P0 asking for (0, 2, 0) is denied because the resulting state has no safe sequence. An unsafe state does not mean deadlock has happened, only that it is possible.

Explore the dry run

Guided walkthroughReady

1def safe_sequence(available, allocation, maximum):

2 need = [[m - a for m, a in zip(mx, al)] for mx, al in zip(maximum, allocation)]

3 work = list(available)

4 finished = [False] * len(allocation)

5 order = []

6 progress = True

7 while progress:

8 progress = False

9 for i, row in enumerate(need):

10 if not finished[i] and all(n <= w for n, w in zip(row, work)):

11 work = [w + a for w, a in zip(work, allocation[i])]

12 finished[i] = True

13 order.append(f"P{i}")

14 progress = True

15 return order if all(finished) else None

18def try_request(available, allocation, maximum, process, request):

19 if any(r > a for r, a in zip(request, available)):

20 return None

21 new_available = [a - r for a, r in zip(available, request)]

22 new_allocation = [row[:] for row in allocation]

23 new_allocation[process] = [x + r for x, r in zip(new_allocation[process], request)]

24 if safe_sequence(new_available, new_allocation, maximum) is None:

25 return None

26 return new_available, new_allocation

29available = [3, 3, 2]

30allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]]

31maximum = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]

32print(safe_sequence(available, allocation, maximum))

34state = (available, allocation)

35for process, request in ((1, [1, 0, 2]), (4, [3, 3, 0]), (0, [0, 2, 0])):

36 outcome = try_request(state[0], state[1], maximum, process, request)

37 print(f"P{process} {request}:", "granted" if outcome else "denied")

38 if outcome:

39 state = outcome

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Remaining need is the maximum claim minus what the process already holds.	`P1 need = (1, 2, 2)`	—
A process can finish if its whole remaining need fits in the available resources.	`P1 need = (1, 2, 2)`	—
When a process finishes it returns everything it holds, enlarging the available pool.	`after P1: work = (5, 3, 2)`	—
All five processes can finish in the order P1, P3, P4, P0, P2, so the initial state is safe.	`after P1: work = (5, 3, 2)`	['P1', 'P3', 'P4', 'P0', 'P2']
A request larger than the available resources must wait: P4 asks for 3 of resource A but only 2 remain after P1's grant.	`after P1: work = (5, 3, 2)`	['P1', 'P3', 'P4', 'P0', 'P2']
P1's request keeps the state safe and is granted. P4's exceeds availability. P0's would leave no safe sequence, so it is denied.	`after P1: work = (5, 3, 2)`	['P1', 'P3', 'P4', 'P0', 'P2'] P1 [1, 0, 2]: granted P4 [3, 3, 0]: denied P0 [0, 2, 0]: denied

Cost and common mistakes

Safety checking is O(m·n²) for n processes and m resource types, because each pass scans every process and at most n passes finish a process.

A safe sequence is not unique. The order found depends on the scan order, but safety does not.
An unsafe state is not a deadlock. It means a deadlock is possible if processes request their maximum.
The banker's algorithm needs each process's maximum claim in advance, which makes it uncommon in general-purpose operating systems. Many systems rely on detection and recovery or lock ordering instead.

Try it yourself

Why must a process's whole remaining need fit in available resources before it can finish?

Reveal answer and reasoning

The process may request all of its remaining need at once. Only if that can be satisfied is it guaranteed to finish and release what it holds.

Deadlock avoidance with the banker's algorithm

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading