Loading AI tools
Algorithm used for program correctness From Wikipedia, the free encyclopedia
Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes an "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.
The algorithm was developed in the design process for the THE operating system and originally described (in Dutch) in EWD108.[1] When a new process enters a system, it must declare the maximum number of instances of each resource type that it may ever claim; clearly, that number may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.
For the Banker's algorithm to work, it needs to know three things:
Resources may be allocated to a process only if the amount of resources requested is less than or equal to the amount available; otherwise, the process waits until resources are available.
Some of the resources that are tracked in real systems are memory, semaphores and interface access.
The Banker's algorithm derives its name from the fact that this algorithm could be used in a banking system to ensure that the bank does not run out of resources, because the bank would never allocate its money in such a way that it can no longer satisfy the needs of all its customers.[2] By using the Banker's algorithm, the bank ensures that when customers request money the bank never leaves a safe state. If the customer's request does not cause the bank to leave a safe state, the cash will be allocated, otherwise the customer must wait until some other customer deposits enough.
Basic data structures to be maintained to implement the Banker's algorithm:
Let n be the number of processes in the system and m be the number of resource types. Then we need the following data structures:
Note: Need[i,j] = Max[i,j] - Allocation[i,j]. n=m-a.
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.
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.
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.
On the other hand, assume process 3 requests 1 unit of resource C.
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
Final example: from the state we started at, assume that process 2 requests 1 unit of resource B.
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
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")
Like the other algorithms, the Banker's algorithm has some limitations when implemented. Specifically, it needs to know how much of each resource a process could possibly request. In most systems, this information is unavailable, making it impossible to implement the Banker's algorithm. Also, it is unrealistic to assume that the number of processes is static since in most systems the number of processes varies dynamically. Moreover, the requirement that a process will eventually release all its resources (when the process terminates) is sufficient for the correctness of the algorithm, however it is not sufficient for a practical system. Waiting for hours (or even days) for resources to be released is usually not acceptable.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.