Banker Algorithm

Banker algorithm is a famous deadlock avoidance algorithm , The idea is ： Think of the operating system as a banker , The resources managed by the operating system are equivalent to the funds managed by bankers , A process requests the operating system to allocate resources, which is equivalent to a user lending to a banker . The operating system allocates resources to processes according to the rules set by the banker . Declare the maximum demand for various resources before the process runs , When the process continues to request resources during execution , First, test whether the sum of the number of resources occupied by the process and the number of resources applied for this time exceeds the declared maximum demand of the process . If more than, refuse to allocate resources , If not, retest whether the existing resources of the system can meet the maximum resources required by the process , If it can be met, the resources will be allocated according to the current application amount , Otherwise, we have to postpone the distribution .

Problem description

Design program to simulate the working process of banker algorithm to avoid deadlock . Assume that there are n A process ： P 1 , P 2 , … , P n P_1,P_2,\dots,P_n P1​,P2​,…,Pn​, Yes m Class allocatable resources R 1 , … , R m R_1,\dots,R_m R1​,…,Rm​, At some point , process P i P_i Pi​ Assigned j Class resources are A l l o c a t i o n [ i ] [ j ] Allocation[i][j] Allocation[i][j] individual , It also needs to be j Class resources n e e d [ i ] [ j ] need[i][j] need[i][j] individual , At present, the system remains j Class resources A v a i l a b l e [ j ] Available[j] Available[j] individual .

The experimental requirements

1. Judge whether the current state is safe . If safe , Give the safety sequence ; If it's not safe , Give reasons .
2. For the next moment , A process makes a resource request Request(R1,…,Rm), Use banker's algorithm as the decision basis to judge whether it should respond to the request .
3. Input the resource allocation table and process request information at a certain time , Output safety sequence analysis , Give the decision plan .

Data structure description

• System available resource vector A v a i l a b l e [ m ] Available[m] Available[m]
• Maximum demand matrix M a x [ n ] [ m ] Max[n][m] Max[n][m]
• Distribution matrix A l l o c a t i o n [ n ] [ m ] Allocation[n][m] Allocation[n][m]
• Demand matrix N e e d [ n ] [ m ] Need[n][m] Need[n][m]

among ,n Is the number of processes ,m Is the number of resource types .

Algorithm description

• Input ：T0 Time resource allocation table
• Output ：Pi After a resource request is made , Safety sequence analysis table and safety sequence . If it's not safe , Then give the cause of insecurity .

1. process Pi Request R e q u e s t i Request_i Requesti​, First check its legitimacy , if R e q u e s t i ≤ N e e d [ i ] Request_i\le Need[i] Requesti​≤Need[i] I'm going to continue , Otherwise, the report will be wrong ;
2. if R e q u e s t i ≤ A v a i l a b l e Request_i\le Available Requesti​≤Available, I'm going to continue , Otherwise, it is considered that the current resources are insufficient , Do not respond to the current request ;
3. The system tentatively allocates resources to processes Pi：
   A v a i l a b l e − = R e q u e s t i Available-=Request_i Available−=Requesti​
   A l l o c a t i o n [ i ] + = R e q u e s t i Allocation[i]+=Request_i Allocation[i]+=Requesti​
   N e e d [ i ] − = R e q u e s t i Need[i]-=Request_i Need[i]−=Requesti​
4. Use banker algorithm for security check , After checking this resource allocation , Whether the system is in a safe state , Only when it is safe can resources be formally allocated to the process Pi; Otherwise, this trial is invalid ,Pi Continue to wait for . The security check algorithm is as follows ：
   1. Set the workload W o r k [ m ] Work[m] Work[m], Indicates the number of available resources remaining in the system . At the beginning of the security check , Set up Work=Available;
   2. Initially, the security sequence is empty ;
   3. Traverse Need Matrix row , Find a line k, This line corresponds to Pk Not in the safe sequence , And N e e d [ k ] ≤ W o r k Need[k]\le Work Need[k]≤Work, To the corresponding Pk Insert safe sequence , If it cannot be found, skip the next step ;
   4. to update W o r k = W o r k + A l l o c a t i o n [ k ] Work=Work+Allocation[k] Work=Work+Allocation[k], characterization Pk After obtaining resources and running , The process of releasing resources . Return to the previous step , Continue to find the next process that can allocate resources ;
   5. here , If there are all processes in the security sequence , Then the system is in a safe state , Otherwise, the system is unsafe .

algorithm flow chart

Result analysis

Set up n=5;m=3
T0 Time resource allocation table
Available: [3 3 2]
P Allocation Need
0 [0 1 0] [7 4 3]
1 [2 0 0] [1 2 2]
2 [3 0 2] [6 0 0]
3 [2 1 1] [0 1 1]
4 [0 0 2] [4 3 1]

（1）P1 Request resources ,Request1 = [1, 0, 2]
VALID CHECK PASSED!
RESOURCE CHECK PASSED!
Through legitimacy and resource checks , Is assumed to be P1 Allocate resources , Then conduct a security check ：
P Work Need Allocation Work+Allocation
1 [2 3 0] [0 2 0] [3 0 2] [5 3 2]
3 [5 3 2] [0 1 1] [2 1 1] [7 4 3]
0 [7 4 3] [7 4 3] [0 1 0] [7 5 3]
2 [7 5 3] [6 0 0] [3 0 2] [10 5 5]
4 [10 5 5] [4 3 1] [0 0 2] [10 5 7]
SAFE CHECK PASSED!
Secured Sequence is [1, 3, 0, 2, 4].
Pass the safety check , by P1 Allocate resources , Output current resource allocation information ：
Available: [2 3 0]
P Allocation Need
0 [0 1 0] [7 4 3]
1 [3 0 2] [0 2 0]
2 [3 0 2] [6 0 0]
3 [2 1 1] [0 1 1]
4 [0 0 2] [4 3 1]

（2）T1 moment ,P4 Continue to request resources ：
Request4 = [3, 3, 0]
VALID CHECK PASSED!
️REQUEST EXCEEDS AVAILABLE!
Request4<=Need[4], but Request4>Available, Resource check failed ,P4 Waiting to allocate resources

（3）T2 moment ,P0 Request resources ：
Request0 = [0, 2, 0]
VALID CHECK PASSED!
RESOURCE CHECK PASSED!
️SAFE CHECK FAILED!
Pass the legitimacy and resource test , Assuming that P0 Allocate resources , here Available Does not satisfy the banker's Algorithm , Security check failed , if P0 Allocating resources can lead to deadlocks , So return to the original state .

（4）T3 moment ,P3 Request resources ：
Request3 = [0, 2, 1]
️Exception: ERROR!P3 REQUEST EXCEEDS ITS NEED!
Report errors , Because the requested resources are greater than the demand ！

appendix ： Code

# @Sylvan Ding 2022.05.31
import numpy as np
def err(P):
raise Exception("ERROR!P{} REQUEST EXCEEDS ITS NEED!".format(P))
def valid_check(P, Request, Need):
if np.sum(Request > Need[P, :]):
err(P)
print("\033[0;32mVALID CHECK PASSED!\033[0m")
def resource_check(Request, Available):
if np.sum(Request > Available):
print("\033[0;31mREQUEST EXCEEDS AVAILABLE!\033[0m")
return False
else:
print("\033[0;32mRESOURCE CHECK PASSED!\033[0m")
return True
def safe_check(Work, Need, Allocation, n):
Q = []
while True:
i = 0
while i < n:
if i not in Q and not np.sum(Need[i, :] > Work):
Q.append(i)
temp = Work.copy()
Work = Work + Allocation[i, :]
print_safe_check(i, temp, Need, Allocation, Work)
break
i = i + 1
if i == n:
break
if len(Q) < n:
print("\033[0;31mSAFE CHECK FAILED!\033[0m")
return False
else:
print("\033[0;32mSAFE CHECK PASSED!\nSecured Sequence is {}.\033[0m".format(Q))
return True
def try_allocate(Available, Allocation, Need, Request, P):
Available = Available - Request
Allocation[P, :] = Allocation[P, :] + Request
Need[P, :] = Need[P, :] - Request
return Available, Need, Allocation
def print_safe_check(k, Work, Need, Allocation, Work_Allocation):
print("{}\t {}\t {}\t {}\t {}".format(k,
Work,
Need[k, :],
Allocation[k, :],
Work_Allocation))
def print_resource(Available, Need, Allocation, n):
print("Current resource information: ")
print("Available: {}".format(Available))
print("P\t Allocation\t Need")
for i in range(n):
print("{}\t {}\t {}".format(i, Allocation[i, :], Need[i, :]))
def print_request_info(P, Request):
print("\033[0;33mP{} requests {}.\033[0m".format(P, Request))
def Banker(n, Available, Max, Allocation, P, Request):
""" :param n: int :param Available: array[n][m] :param Max: array[n][m] :param Allocation: array[n][m] :param P: index of process to request :param Request: array[m] :return: Available, Need, Allocation """
print_request_info(P, Request)
Available = np.asarray(Available)
Max = np.asarray(Max)
Allocation = np.asarray(Allocation)
Request = np.asarray(Request)
Need = Max - Allocation
print_resource(Available, Need, Allocation, n)
valid_check(P, Request, Need)
if (resource_check(Request, Available) and
safe_check(*try_allocate(Available.copy(),
Allocation.copy(),
Need.copy(),
Request, P), n)):
Available, Need, Allocation = try_allocate(Available.copy(),
Allocation.copy(),
Need.copy(),
Request, P)
print_resource(Available, Need, Allocation, n)
return Available, Need, Allocation
def BankerAlgorithm():
n = 5
# m = 3
Available = [3, 3, 2]
Max = [[7, 5, 3],
[3, 2, 2],
[9, 0, 2],
[2, 2, 2],
[4, 3, 3]]
Allocation = [[0, 1, 0],
[2, 0, 0],
[3, 0, 2],
[2, 1, 1],
[0, 0, 2]]
P1 = 1
Request1 = [1, 0, 2]
Available, Need, Allocation = Banker(n, Available, Max, Allocation, P1, Request1)
P4 = 4
Request4 = [3, 3, 0]
Available, Need, Allocation = Banker(n, Available, Max, Allocation, P4, Request4)
P0 = 0
Request0 = [0, 2, 0]
Available, Need, Allocation = Banker(n, Available, Max, Allocation, P0, Request0)
P3 = 3
Request3 = [0, 2, 1]
Banker(n, Available, Max, Allocation, P3, Request3)
if __name__ == '__main__':
BankerAlgorithm()

Original article ： Reprint please indicate the source ️ Sylvan Ding

reference

1. 2023 Operating system postgraduate entrance examination review guidance / Wangdao forum postgraduate entrance examination group editor .—— Beijing ： Electronic industry press ,2021.12