银行家算法Python实现

银行家算法Python实现"/>

银行家算法Python实现

银行家 算法

银行家算法属于避免死锁的一种算法。

基本原理

银行家算法：当一个新进程进入系统时，该进程必须申明在运行过程中所需要的每种资源的最大数目，且该数目不能超过系统拥有的资源总量。当进程请求某组资源时，系统必须先确定系统中是否有足够的该类资源供以分配给该进程。若有，通过安全性算法来计算，将资源分配给该进程后，是否会使系统处于不安全状态，如果不会处于安全状态，则将资源分配给该进程，否则让进程等待。若没有，进程等待。

• 数据结构

  实现银行家算法，必须有四种数据结构，用以描述系统中可使用的资源数目、所有进程对于各类资源的最大需求、系统中已分配资源的情况、各进程还需要多少资源的情况

  • 可利用资源向量 A v a i l a b l e Available Available， A v a i l a b l e [ j ] = K Available[j]=K Available[j]=K 表示系统中现有可利用的 R j R_j Rj​类资源 K K K个
  • 最大需求矩阵 M a x Max Max， M a x [ i , j ] = K Max[i,j]=K Max[i,j]=K 表示进程 i i i需要 R j R_j Rj​类资源的最大数目为 K K K个
  • 分配矩阵 A l l o c a t i o n Allocation Allocation， A l l o c a t i o n [ i , j ] = K Allocation[i, j]=K Allocation[i,j]=K 表示进程 i i i已分得 R j R_j Rj​类资源 K K K个
  • 需求矩阵 N e e d Need Need， N e e d [ i , j ] = K Need[i,j]=K Need[i,j]=K 表示进程 i i i还需要 R j R_j Rj​类资源 K K K个

  有关系：
  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]

• 银行家算法描述

​ 设 R e q u e s t i [ j ] Request_i[j] Requesti​[j]是进程 i i i的请求向量， R e q u e s e t i [ j ] = K Requeset_i[j]=K Requeseti​[j]=K表示进程 i i i请求K个 R j R_j Rj​类资源。当进程发出资源请求后，算法执行步骤如下：

1. ​ 如果 R e q u e s t i [ j ] ≤ N e e d [ i , j ] Request_i[j]\leq Need[i,j] Requesti​[j]≤Need[i,j]，跳至步骤2；否则，认为出错，因为请求的超过它所需要的。

2. ​ 如果 R e q u e s t i [ j ] ≤ A v a i l a b l e [ i , j ] Request_i[j]\leq Available[i,j] Requesti​[j]≤Available[i,j]，跳至步骤3；否则，认为系统暂时满足不了该进程的需求，进程等待

3. ​ 系统尝试着将请求的资源分配给该进程，并修改数据结构中的数值：
   A v a i l a b l e [ i , j ] = A v a i l a b l e [ i , j ] − R e q u e s t i [ j ] A l l o c a t i o n [ i , j ] = A l l o c a t i o n [ i , j ] + R e q u e s t i [ j ] N e e d [ i , j ] = N e e d [ i , j ] − R e q u e s t i [ j ] Available[i,j]=Available[i,j]-Request_i[j] \\ Allocation[i,j]=Allocation[i,j]+Request_i[j] \\ Need[i,j]=Need[i,j]-Request_i[j] Available[i,j]=Available[i,j]−Requesti​[j]Allocation[i,j]=Allocation[i,j]+Requesti​[j]Need[i,j]=Need[i,j]−Requesti​[j]

4. 执行安全性算法，判断如此分配后，系统是否处于安全状态，如果处于安全状态，则执行分配；否则，本次尝试分配作废，进程等待。

• 安全性算法描述：

  1. 设置两个向量

     • 工作向量 W o r k Work Work，表示系统可提供给进程继续运行的各类资源数目，算法执行之前，令 W o r k = A v a i l a b l e Work=Available Work=Available
     • F i n i s h Finish Finish：表示系统是否有足够的资源分配给进程，使进程完成。开始时令 F i n i s h [ i ] = F a l s e Finish[i]=False Finish[i]=False，如果有足够的资源分配给进程，则令 F i n i s h [ i ] = T r u e Finish[i]=True Finish[i]=True

  2. 从进程集中寻找满足下列条件的进程：

     1. F i n i s h [ i ] = F a l s e Finish[i]=False Finish[i]=False
     2. N e e d [ i , j ] ≤ W o r k [ j ] Need[i,j]\leq Work[j] Need[i,j]≤Work[j]

     若找到，跳至步骤3，否则执行步骤4

  3. 更新数据结构的数值。进程 i i i获得资源后，执行，直至完成进程，并释放他占有的资源，即：
     W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i , j ] F i n i s h [ i ] = T r u e g o t o s t e p 2 Work[j]=Work[j]+Allocation[i,j] \\ Finish[i] = True \\ go\quad to\quad step 2 Work[j]=Work[j]+Allocation[i,j]Finish[i]=Truegotostep2

  4. 如果所有的进程都满足 F i n i s h [ i ] = T r u e Finish[i]=True Finish[i]=True，表示分配资源后系统将处于安全状态，执行分配。否则，尝试分配作废，进程等待。

实例

编程实现

import numpy as npclass BankerAlgorithm():def __init__(self, available, max, allocation, need):"""初始化参数:param available: 可利用资源向量:param max: 最大需求矩阵:param allocation: 分配矩阵:param need: 需求矩阵"""self.available = availableself.max = maxself.allocation = allocationself.need = needdef Request(self, P, request):"""请求资源:param P: 进程号，从0开始:param request: 所请求的资源向量:return: 若成功，打印安全序列，进行分配；否则，拒绝请求。"""# 判断请求向量是否小于需求向量length = len(request)i = 0for i in range(length):if request[i] > self.need[P][i]:breakif i != len(request) - 1:print("进程{0}所需资源超过它所宣布的最大值".format(P))return# 判断请求向量是否小于可用资源向量j = 0for j in range(length):if request[i] > self.available[i]:breakif j != length - 1:print("尚未足够的资源供{}使用", P)return# 试分配avi_temp = self.availableall_temp = self.allocationneed_temp = self.needfor 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_tempself.allocation = all_tempself.available = avi_tempprint("请求成功！各数据结构修改为\nNeed={0}\nAllocation={1}\nAvailable{2}\n".format(self.need, self.allocation, self.available))else:print("如此分配会导致系统处于不安全状态，拒绝本次分配")returndef Security(self):"""安全性算法，检验试分配后系统是否处于安全状态。:return: 若分配后系统处于安全状态，打印安全序列并返回True；否则返回False"""work = self.availablefinish = [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 = 1for j in range(length):if self.need[i][j] > work[j]:flag = 0breakif flag and finish[i] is False:work += self.allocation[i]finish[i] = TruesecureSeq += str(i) + "->"pro_list.remove(i)breakfor i in range(len(finish)):if finish[i] is not True:return Falseprint("存在安全序列为{0}".format(secureSeq.strip("->")))return Trueif __name__ == "__main__":avi = np.array([3, 3, 2])  # 可利用资源向量need = np.array([[7, 4, 3],[1, 2, 2],[6, 0, 0],[0, 1, 1],[4, 3, 1]])  # 需求矩阵all = np.array([[0, 1, 0],[2, 0, 0],[3, 0, 2],[2, 1, 1],[0, 0, 2]])  # 分配矩阵max = np.array([[7, 5, 3],[3, 2, 2],[9, 0, 2],[2, 2, 2],[4, 3, 3]])  # 最大需求矩阵Test = BankerAlgorithm(avi, max, all, need)Test.Request(1, np.array([1, 0, 2]))

返回结果为：

存在安全序列为1->3->0->2->4
请求成功！各数据结构修改为
Need=[[7 4 3][0 2 0][6 0 0][0 1 1][4 3 1]]
Allocation=[[0 1 0][3 0 2][3 0 2][2 1 1][0 0 2]]
Available[10  5  7]

))

返回结果为：```python
存在安全序列为1->3->0->2->4
请求成功！各数据结构修改为
Need=[[7 4 3][0 2 0][6 0 0][0 1 1][4 3 1]]
Allocation=[[0 1 0][3 0 2][3 0 2][2 1 1][0 0 2]]
Available[10  5  7]