Banker’s algorithm in Python
In this tutorial, we will learn about the Banker’s algorithm also referred to as the deadlock algorithm. It simulates the allocation of the predetermined maximum possible amount of all resources and makes an S-state check the deadlock condition. Edsger Dijkstra developed this algorithm for computer operating systems.
Banker’s Algorithm – Deadlock Condition in Python
Let’s say there are P account holders in a bank. The sum of all their money in the bank is R. If an account holder wants a loan from the bank, the bank subtracts the loan amount from the total money of the bank. As a result, the loan is processed only when the difference is greater than R. Because the bank should have money even after all the P account holders withdraw all their money at once.
This algorithm works in a similar way in operating systems. When a new Process is created, The system must specify the maximum number of instances for each of the resources which it would ever request. The data structures used to implement this algorithm are:
- Maximum -> It’s a 2-dimensional NumPy array indicating the maximum demand of each process in a system.
- Allocated -> It’s a 2-dimensional Numpy array indicating the number of resources of each type allocated to each process.
- Available -> It’s a 1-dimensional Numpy array that defines the number of available resources of each type.
- Needed -> It’s a 2-dimensional Numpy array that indicates the resources needed for each process.
Python implementation of Banker’s Algorithm
- Needed = Maximum – Allocated.
- Available = Available + Allocated.
I assume that you have Numpy installed in your system. If not,
import numpy as np def check(i): for j in range(no_r): if(needed[i][j]>available[j]): return 0 return 1 no_p = 5 no_r = 4 Sequence = np.zeros((no_p,),dtype=int) visited = np.zeros((no_p,),dtype=int) allocated = np.array([[4,0,0,1],[1,1,0,0],[1,2,5,4],[0,6,3,3],[0,2,1,2]]) maximum = np.array([[6,0,1,2],[1,7,5,0],[2,3,5,6],[1,6,5,3],[1,6,5,6]]) needed = maximum - allocated available = np.array([3,2,1,1]) count = 0 while( count < no_p ): temp=0 for i in range( no_p ): if( visited[i] == 0 ): if(check(i)): Sequence[count]=i; count+=1 visited[i]=1 temp=1 for j in range(no_r): available[j] += allocated[i][j] if(temp == 0): break if(count < no_p): print('The system is Unsafe') else: print("The system is Safe") print("Safe Sequence: ",Sequence) print("Available Resource:",available)
The system is Safe Safe Sequence: [0 2 3 4 1] Available Resource: [ 9 13 10 11]
In the above example, the system will skip process 0 and move to process 1. Because each process holds some resource and if the resource is not enough, the process can’t be completed. Since the system doesn’t have enough resources for process 0, it can not complete that process. Hence the deadlock condition occurs. Once a process is completed, the system will regain the allocated resources. AS a result, there will be enough resources to allocate for upcoming processes and deadlock conditions can be avoided. Therefore the system allocates resources in the order P1, P2, P3, P4, P0.