1、了解多道程序系统中，多个进程并发执行的资源分配
2、掌握死锁产生的原因，产生死锁的必要条件和处理死锁的基本方法
3、掌握银行家算法，了解资源在进程并发执行中的资源分配策略
学习内容：
考虑某一系统，它有3类资源R1，R2，R3，有5个并发进程P0，P1，P2，P3，P4。资源分配情况如下：
如果进程依次有资源请求：P0为（1,1,0），P1为（2,3,0），P3为（0,1,1），系统将怎样进行资源分配？
为什么会产生死锁？
首先我们需要知道在多道处理系统中进程是并发执行，共享消耗系统资源，这样可以提高系统的资源利用率。
比如说：有两个进程P1,P2需要竞争R1，R2两个资源，每个进程都要单独占用这两个资源一段时间
def P1():
{
request R1
request R2
release R1
release R2
}
def P2():
{
request R2
request R1
release R2
release R1
}
图中描述了各个进程是如何获取释放共享资源的过程：
P1获得了R1，P2获得了R2，由于继续执行过程中P2阻塞在R1上，R1被P1占用没有释放，但是P1要获得的R2又被P2占用着，就发生了死锁现象。
用严谨科学的术语解释死锁：在多道程序系统中，一组进程中的每一个进程均无限期的等待被该组进程中的另一个进程占用且永远不会释放的资源，这种现象称作为系统的死锁状态。
归纳起来有两点：
- 竞争资源。多个进程所共享的资源不够，引起进程间的抢夺。我家养了两条狗，但只有一个碗，每次给的饭不够两个狗吃，那不得打起来嘛！
- 进程推进的顺序不当，进程运行过程中释放资源的顺序不当，导致死锁。还是两条狗，假如说大黄先吃，吃完了再让二黄吃，这样两条狗就不会打架
- 互斥条件。即某一段时间资源只能被一个进程占用
- 请求和保持条件。当进程因请求资源而阻塞时，对已经获取的资源保持不妨
- 不剥夺条件。进程在获得的资源未使用完之前，不能被剥夺，只能自己释放
- 环路等待条件。在发生死锁时，必然存在一个进程-资源的环形链。
import numpy as np
class BankerAlgorithm():
def __init__(self, available, max, allocation, need):
"""
初始化参数
:param available: 可利用资源向量
:param max: 最大需求矩阵
:param allocation: 分配矩阵
:param need: 需求矩阵
"""
self.available = available
self.max = max
self.allocation = allocation
self.need = need
def Request(self, P, request):
"""
请求资源
:param P: 进程号，从0开始
:param request: 所请求的资源向量
:return: 若成功，打印安全序列，进行分配；否则，拒绝请求。
"""
# 判断请求向量是否小于需求向量
length = len(request)
i = 0
for i in range(length):
if request[i] > self.need[P][i]:
break
if i != len(request) - 1:
print("进程{0}所需资源超过它所宣布的最大值n".format(P))
return
# 判断请求向量是否小于可用资源向量
j = 0
for j in range(length):
if request[i] > self.available[i]:
break
if j != length - 1:
print("尚未足够的资源供{}使用", P)
return
# 试分配
avi_temp = self.available
all_temp = self.allocation
need_temp = self.need
for k in range(length):
avi_temp[k] = avi_temp[k] - request[k]
all_temp[P][k] = all_temp[P][k] + request[k]
need_temp[P][k] = need_temp[P][k] - request[k]
# 执行安全性算法，若存在安全序列，执行分配
if self.Security():
self.need = need_temp
self.allocation = all_temp
self.available = avi_temp
print("请求成功！各数据结构修改为nNeed={0}nAllocation={1}nAvailable{2}n".format(self.need, self.allocation,
self.available))
else:
print("如此分配会导致系统处于不安全状态，拒绝本次分配")
return
def Security(self):
"""
安全性算法，检验试分配后系统是否处于安全状态。
:return: 若分配后系统处于安全状态，打印安全序列并返回True；否则返回False
"""
work = self.available
finish = [False for i in range(self.need.shape[0])]
pro_number = self.need.shape[0]
pro_list = [i for i in range(pro_number)]
length = self.need.shape[1]
secureSeq = ""
# 寻找安全序列
for k in range(pro_number):
for i in pro_list:
flag = 1
for j in range(length):
if self.need[i][j] > work[j]:
flag = 0
break
if flag and finish[i] is False:
work += self.allocation[i]
finish[i] = True
secureSeq += str(i) + "->"
pro_list.remove(i)
break
for i in range(len(finish)):
if finish[i] is not True:
return False
print("存在安全序列为{0}".format(secureSeq.strip("->")))
return True
if __name__ == "__main__":
avi = np.array([3, 3, 2]) # 可利用资源向量
all = np.array([[2, 3, 1],
[1, 5, 2],
[2, 1, 0],
[3, 1, 2],
[1, 1, 1]]) # 分配矩阵
max = np.array([[10, 7, 3],
[5, 6, 4],
[4, 3, 1],
[4, 2, 5],
[3, 5, 2]]) # 最大需求矩阵
need = max - all # 需求矩阵
Test = BankerAlgorithm(avi, max, all, need)
Test.Request(0, np.array([1, 1, 0]))
Test.Request(1, np.array([2, 3, 0]))
Test.Request(2, np.array([0, 1, 1]))
结果：
存在安全序列为2->1->3->0->4 请求成功！各数据结构修改为 Need=[[7 3 2] [4 1 2] [2 2 1] [1 1 3] [2 4 1]] Allocation=[[3 4 1] [1 5 2] [2 1 0] [3 1 2] [1 1 1]] Available[12 14 8] 进程1所需资源超过它所宣布的最大值 存在安全序列为0->1->2->3->4 请求成功！各数据结构修改为 Need=[[7 3 2] [4 1 2] [2 1 0] [1 1 3] [2 4 1]] Allocation=[[3 4 1] [1 5 2] [2 2 1] [3 1 2] [1 1 1]] Available[22 26 14] Process finished with exit code 0
