Banker's algorithm

Total system resources are:
A B C D
6 5 7 6

Available system resources are:
A B C D
3 1 1 2

Processes (currently allocated resources):
   A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

Processes (maximum resources):
   A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

Need = maximum resources - currently allocated resources
Processes (possibly needed resources):
   A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

A state (as in the above example) is considered safe if it is possible for all processes to finish executing (terminate). Since the system cannot know when a process will terminate, or how many resources it will have requested by then, the system assumes that all processes will eventually attempt to acquire their stated maximum resources and terminate soon afterward. This is a reasonable assumption in most cases since the system is not particularly concerned with how long each process runs (at least not from a deadlock avoidance perspective). Also, if a process terminates without acquiring its maximum resource it only makes it easier on the system. A safe state is considered to be the decision maker if it's going to process ready queue.

Given that assumption, the algorithm determines if a state is safe by trying to find a hypothetical set of requests by the processes that would allow each to acquire its maximum resources and then terminate (returning its resources to the system). Any state where no such set exists is an unsafe state.

We can show that the state given in the previous example is a safe state by showing that it is possible for each process to acquire its maximum resources and then terminate.

1. P1 needs 2 A, 1 B and 1 D more resources, achieving its maximum
   • [available resource: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
   • The system now still has 1 A, no B, 1 C and 1 D resource available
2. P1 terminates, returning 3 A, 3 B, 2 C and 2 D resources to the system
   • [available resource: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
   • The system now has 4 A, 3 B, 3 C and 3 D resources available
3. P2 acquires 2 B and 1 D extra resources, then terminates, returning all its resources
   • [available resource: <4 3 3 3> - <0 2 0 1> + <1 2 3 4> = <5 3 6 6>]
   • The system now has 5 A, 3 B, 6 C and 6 D resources
4. P3 acquires 1 B and 4 C resources and terminates.
   • [available resource: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
   • The system now has all resources: 6 A, 5 B, 7 C and 6 D
5. Because all processes were able to terminate, this state is safe

For an example of an unsafe state, consider what would happen if process 2 was holding 1 units of resource B at the beginning.

When the system receives a request for resources, it runs the Banker's algorithm to determine if it is safe to grant the request. The algorithm is fairly straightforward once the distinction between safe and unsafe states is understood.

1. Can the request be granted?
   • If not, the request is impossible and must either be denied or put on a waiting list
2. Assume that the request is granted
3. Is the new state safe?
   • If so grant the request
   • If not, either deny the request or put it on a waiting list

Whether the system denies or postpones an impossible or unsafe request is a decision specific to the operating system.

    Example 

Starting in the same state as the previous example started in, assume process 1 requests 2 units of resource C.

1. There is not enough of resource C available to grant the request
2. The request is denied

On the other hand, assume process 3 requests 1 unit of resource C.

1. There are enough resources to grant the request
2. Assume the request is granted
   • The new state of the system would be:

    Available system resources
     A B C D
Free 3 1 0 2

    Processes (currently allocated resources):
     A B C D
P1   1 2 2 1
P2   1 0 3 3
P3   1 2 2 0

    Processes (maximum resources):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0

1. Determine if this new state is safe
   1. P1 can acquire 2 A, 1 B and 1 D resources and terminate
   2. Then, P2 can acquire 2 B and 1 D resources and terminate
   3. Finally, P3 can acquire 1 B and 3 C resources and terminate
   4. Therefore, this new state is safe
2. Since the new state is safe, grant the request

Final example: from the state we started at, assume that process 2 requests 1 unit of resource B.

1. There are enough resources
2. Assuming the request is granted, the new state would be:

    Available system resources:
     A B C D
Free 3 0 1 2

    Processes (currently allocated resources):
     A B C D
P1   1 2 5 1
P2   1 1 3 3
P3   1 2 1 0

    Processes (maximum resources):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0

1. Is this state safe? Assuming P1, P2, and P3 request more of resource B and C.
   • P1 is unable to acquire enough B resources
   • P2 is unable to acquire enough B resources
   • P3 is unable to acquire enough B resources
   • No process can acquire enough resources to terminate, so this state is not safe
2. Since the state is unsafe, deny the request

import numpy as np

n_processes = int(input("Number of processes? "))
n_resources = int(input("Number of resources? "))

available_resources = [int(x) for x in input("Claim vector? ").split(" ")]

currently_allocated = np.array([
  [int(x) for x in input(f"Currently allocated for process {i + 1}? ").split(" ")]
  for i in range(n_processes)
])

max_demand = np.array([
  [int(x) for x in input(f"Maximum demand from process {i + 1}? ").split(" ")]
  for i in range(n_processes)
])

total_available = available_resources - np.sum(currently_allocated, axis=0)
running = np.ones(n_processes)  # An array with n_processes 1's to indicate if process is yet to run

while np.count_nonzero(running) > 0:
    at_least_one_allocated = False
    for p in range(n_processes):
        if running[p]:
            if all(i >= 0 for i in total_available - (max_demand[p] - currently_allocated[p])):
                at_least_one_allocated = True
                print(f"{p} is running")
                running[p] = 0
                total_available += currently_allocated[p]
    if not at_least_one_allocated:
        print("Unsafe")
        break  # exit
    else:
        print("Safe")