Deadlock avoidance with the banker's algorithm
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.
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