算法目的：预防死锁
数据结构
假设有m个资源，n个进程。
- 可利用资源数组Available[m]，Availabe[i]为i类资源现可用的数目；
- 最大需求矩阵Max[n*m]，Max[i,j]为进程i需要j资源的最大数目；
- 分配矩阵Allocation[n*m]，Allocation[i,j]为进程i当前已分配到j资源的数目；
- 需求矩阵Need[n*m]，Need[i,j]为进程i还需要多少j资源才能完成。
银行家算法
- 找到一个所需的资源不大于现有资源的进程；
- 系统进行试探，把资源分配给该进程，更新Available、Allocation、Need数组；
- 执行安全性算法。
安全性算法
设置两个数组，work和finish。work = Available，finish[i] = 0。
- 从进程集合中找到一个能满足以下条件的进程：
- finish[i] = 0
- Need[I,*] <= work[*]
- 找到进程i获得资源后可顺利执行，直至完成，并释放分配给它的资源，执行以下步骤：
- work[j] = work[j] + Allocation[i,j]
- finish[i] = 1
- go to step 1
- 如果finish全为1则处于安全状态。
代码：
Available = []
Max = []
Allocation = []
Need = []
def find_i(finish, ne, work):
for i in range(len(finish)):
flag = 0 # 记录每个进程可被满足资源的数量
for j in range(len(work)):
if finish[i] == 0:
if work[j] < ne[i][j]:
continue
else:
flag += 1
if flag == len(work): # 如果全都满足则可以运行该进程
return I
return -1
def safety(av, al, ne, choice):
work = av[:]
finish = [0] * m
list = []
while True:
i = find_i(finish, ne, work)
if i != -1:
for j in range(len(work)):
work[j] = work[j] + al[i][j]
finish[i] = 1
list.append(i)
else:
if len(finish) == len(tuple(finish)) and finish[0] == 1:
if choice == 0:
print('该时刻存在的安全序列:', list)
return 1
else:
return list
else:
return 0
if __name__ == '__main__':
f = open('银行家.txt', 'r')
lines = f.readlines()
m = len(lines) - 1 # 进程数量
# m = int(input('输入进程数量:'))
Max = [[]] * m
Allocation = [[]] * m
Need = [[]] * m
# n = int(input('输入资源数量:'))
print(lines[0])
lines[0] = list(map(lambda x: int(x), lines[0].split()))
n = len(lines[0]) # 资源数量
Available = lines[0]
# for i in range(n):
# # Available.append(int(input('输入第'+str(i+1)+'个资源的数量:')))
# for j in range(m):
# Max[j].append(int(input('输入第'+str(j+1)+'个进程对该资源的最大需求:')))
# Allocation[j].append(int(input('输入第'+str(j+1)+'个进程已分配到的该资源:')))
# Need[j].append(int(input('输入第'+str(j+1)+'个进程还需多少该资源才能完成:')))
lines = lines[1:]
for i in range(len(lines)):
lines[i] = list(map(lambda x: int(x), lines[i].split()))
Max[i] = lines[i][:n]
Allocation[i] = lines[i][n:2*n]
Need[i] = lines[i][2*n:]
for i in range(n):
a = 0
for j in range(m):
a += Allocation[j][I]
Available[i] -= a
print(Available)
list = [] # 安全序列
while len(list) < m or not list:
a = int(input('输入请求资源还是直接输出安全序列？'))
if a == 0:
flag = 1
request = [int(i) for i in input('输入请求资源的进程及资源的数量:').split()]
i = request[0]
k = request[1:] # 该进程对所有资源对需求
av = Available[:]
al = Allocation[:]
ne = Need[:]
for j in range(n):
if k[j] <= Need[i][j] and k[j] <= Available[j]:
av[j] -= k[j]
al[i][j] += k[j]
ne[i][j] -= k[j]
# print(av)
else:
print('没有足够的资源!')
flag = 0
if safety(av, al, ne, 0) and flag:
Allocation = al
Available = av
Need = ne
list.append(i)
print(list)
else:
print('不能分配！')
else:
list = safety(Available, Allocation, Need, 1)
print(list)
可以选择自己输入还是读取本地文件。
本地文件内容如下：
10 5 7 # 有三个资源，每个资源可用的数量。
7 5 3 0 1 0 7 4 3 # 每个进程占一行，读文件的时候把注释删掉。
3 2 2 2 0 0 1 2 2 # 具体情况如下图所示。
9 0 2 3 0 2 6 0 0
2 2 2 2 1 1 0 1 1
4 3 3 0 0 2 4 3 1
计算机操作系统（第四版）113页
