overview
The following concepts are referenced and
Banker's Algorithm is a famous algorithm to avoid Deadlock. It is an algorithm to avoid Deadlock designed by ezger dijestra for T.H.E system in 1965. It is based on the allocation strategy of the bank lending system to judge and ensure the safe operation of the system.
When doing homework, I encountered the problem of banker algorithm. At the same time, in order to deepen my understanding of deadlock avoidance and banker algorithm, I chose to implement the algorithm by program. Originally, I wanted to write in C + +. After all, I was an old ACM player, but I didn't use it much after learning python, so I implemented it in Python.
algorithm
The matrix needs to be used in the operation. It is a little troublesome to create a matrix with the list brought by Python itself, so use the matrix brought by numpy package to create it.
Pychar does not have a numpy package. To use, you need to add a numpy package in File > setting > Project: study > Python interpreter.
Data structure required in the algorithm
- Available resource vector
A
v
a
i
l
a
b
l
e
Available
Available
It's a m m Each element of the array represents the number of available resources. If A v a i l a b l e [ j ] = K Available[j]=K Available[j]=K, it means that there are K Rj resources in the system. - Maximum demand matrix
M
a
x
Max
Max
This is a n × m n×m n × m, which defines the matrix in the system n n Each of the n processes has the greatest demand for m-class resources. If M a x [ i , j ] = K Max[i,j]=K Max[i,j]=K, it means that the maximum number of Rj resources required by process i is K K K. - Distribution matrix
A
l
l
o
c
a
t
i
o
n
Allocation
Allocation
This is also a n × m n×m n × m, which defines the number of resources currently allocated to each process for each type of resources in the system. If A l l o c a t i o n [ i , j ] = K Allocation[i,j]=K Allocation[i,j]=K, it means that process i has been allocated at present R j R_j The number of Rj} resources is K. - Demand matrix
N
e
e
d
Need
Need.
This is also a n × m n×m n × m matrix, which is used to represent the number of various resources required by each process. If N e e d [ i , j ] = K Need[i,j]=K Need[i,j]=K, it means that process i still needs R j R_j Rj # resources K K K in order to complete its task.
N e e d [ i , j ] = M a x [ i , j ] − A l l o c a t i o n [ i , j ] Need[i,j]=Max[i,j]-Allocation[i,j] Need[i,j]=Max[i,j]−Allocation[i,j]
security check
- Set two working vectors Work=AVAILABLE;FINISH
- Find a process that meets the following conditions from the process set,
FINISH==false;
NEED<=Work;
If found, execute (3); Otherwise, execute (4) - If the process obtains resources, it can be executed smoothly until it is completed, so as to release resources.
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
(4) Like all processes F i n i s h = t r u e Finish= true If Finish=true, it means safe; Otherwise, the system is unsafe.
code
def check():
work = Available.copy()
finish = [False for it in range(n)]
ans = "The safety sequence is:"
for num in range(n):
for it in range(n):
if not finish[it]:
cnt = 0
for jt in range(m):
if Need[it][jt] <= work[jt]:
cnt = cnt + 1
if cnt == m:
ans = ans + str(it)
finish[it] = True
for jt in range(m):
work[jt] += Allocation[it][jt]
if False in finish:
return "The system is in an unsafe state"
else:
return ans
Banker Algorithm
Set process c u s n e e d cusneed Request from cusneed R E Q U E S T [ i ] REQUEST [i] REQUEST[i], the banker algorithm judges according to the following rules.
- If request [cusneed] [i] < = need [cusneed] [i], turn to (2); Otherwise, an error occurs.
- If request [cusneed] [i] < = available [i], turn to (3); Otherwise, wait.
- The system tries to allocate resources and modify relevant data:
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i]
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4) The system performs safety inspection. If it is safe, the allocation is established; Otherwise, the trial allocation will be invalid, the system will be restored to its original state, and the process will wait.
code
def request():
t = int(input("Please enter which process requests resources:"))
Request = input("Please enter the number of requested resources in a string:").split(' ')
Request = [int(it) for it in Request]
for it in range(m):
if Request[it] > Need[t][it]:
return "The number of resources required exceeds the maximum it requires"
for it in range(m):
if Request[it] > Available[it]:
return "Insufficient resources"
for it in range(m):
Available[it] -= Request[it]
Allocation[t][it] += Request[it]
Need[t][it] -= Request[it]
if check() == "The system is in an unsafe state":
Available[it] += Request[it]
Allocation[t][it] -= Request[it]
Need[t][it] += Request[it]
return "The system is in an unsafe state after allocation"
else:
return "Assigned"
Total code
# Prepared by: Hu Yifeng
# Created on: April 16, 2022 17:48
# Prepared by: Hu Yifeng
# Created on: April 16, 2022 16:28
import numpy as np
def check():
work = Available.copy()
finish = [False for it in range(n)]
ans = "The safety sequence is:"
for num in range(n):
for it in range(n):
if not finish[it]:
cnt = 0
for jt in range(m):
if Need[it][jt] <= work[jt]:
cnt = cnt + 1
if cnt == m:
ans = ans + str(it)
finish[it] = True
for jt in range(m):
work[jt] += Allocation[it][jt]
if False in finish:
return "The system is in an unsafe state"
else:
return ans
def request():
t = int(input("Please enter which process requests resources:"))
Request = input("Please enter the number of requested resources in a string:").split(' ')
Request = [int(it) for it in Request]
for it in range(m):
if Request[it] > Need[t][it]:
return "The number of resources required exceeds the maximum it requires"
for it in range(m):
if Request[it] > Available[it]:
return "Insufficient resources"
for it in range(m):
Available[it] -= Request[it]
Allocation[t][it] += Request[it]
Need[t][it] -= Request[it]
if check() == "The system is in an unsafe state":
Available[it] += Request[it]
Allocation[t][it] -= Request[it]
Need[t][it] += Request[it]
return "The system is in an unsafe state after allocation"
else:
return "Assigned"
n = int(input("Please enter the number of processes:")) # Number of processes
m = int(input("Please enter the number of critical resources:")) # Critical resources
# Max maximum resource requirements, the number of resources needed by Need, the number of resources allocated by Allocation, and the number of Available and idle resources
Max, Allocation, Need = np.zeros([n, m], int), np.zeros([n, m], int), np.zeros([n, m], int)
Max.tolist(), Need.tolist(), Allocation.tolist()
for i in range(n):
data1 = input("Please enter page" + str(i) + "The maximum number of resource requirements of a process, which is entered in string:").split(' ')
data2 = input("Please enter page" + str(i) + "The number of resources allocated by processes. Enter in string:").split(' ')
for j in range(m):
Max[i][j] = int(data1[j])
Allocation[i][j] = int(data2[j])
Need[i][j] = int(data1[j]) - int(data2[j])
Available = input("Please enter the number of available resources, and input with string:").split(' ')
Available = [int(x) for x in Available]
while True:
option = input("Please enter an action( Q sign out, C Check for safety, R (request resources)")
if option == 'Q':
break
elif option == 'C':
print(check())
elif option == 'R':
print(request())
else:
print("Input error")