银行家算法

Dijkstra的银行家算法是最具有代表性的避免死锁的算法，这个算法因能用于银行系统现金贷款的发放而得名。

安全状态

所谓安全状态，是指系统能按某种进程顺序（P1，P2，...，Pn）（称<P1,P2,...,Pn>为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 避免死锁的实质在于:系统进行资源分配时,如何使系统不进入安全状态。

系统处于不安全状态后,不一定进入死锁状态,但是,只要系统处于安全状态,系统便一定不会进入死锁状态。

相关数据结构

Available ——可利用的资源数 Available[j]=K 表示系统中现有Rj类资源K个 Max ——资源最大需求数 Max[i,j]=K 表示进程i需要Rj类资源的最大数目为K Allocation ——已分配资源数 Allocation[i,j]=K 表示进程i当前已分得Rj类资源的数目为K Need ——还需资源数 Need[i,j]=K 表示进程i还需要Rj类资源K个 存在关系 —— Need[i,j] = MAx[i,j] - Allocation[i,j]

银行家算法

Request_i[j] = K,表示进程Pi需要K个Rj类型的资源.当Pi发出资源请求后,系统按如下步骤进行检查:

1. 如果Request_i[j] ≤ Need[i,j],便转向步骤2；否则认为出错,因为他所需要的资源数超过它所宣布的资源最大需求数。
2. 如果Request_i[j] ≤ Available[i,j],便转向步骤3；否则,表示尚无足够资源,Pi必须等待。
3. 系统试探着把资源分配给进程给Pi,并修改下面数据结构中的数值: Available［j］: =Available［j］- Request_i［j］； Allocation［i,j］: =Allocation［i,j］+ Request_i［j］； Need［i,j］: =Need［i,j］- Request_i［j］；
4. 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配；否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

安全性算法(设置向量)

1. 首先设置两个向量: ① ** Work ** 表示系统可以提供给进程继续运行所需的各类资源数目。在执行安全算法开始时,Work:=Available。 ②** Finish ** 表示系统是否有足够的资源分配给进程,使之运行完成。开始时Finish[i]:=false；当有足够资源分配给进程时,令Finish[i]:=true。
2. 再从进程集合中找到一个能满足下述条件的进程: ① Finish[i] = false； ② Need[i,j] ≤ Work[i]； 若找到,执行步骤3,否则,执行步骤4。
3. 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行 : Work[j]:= Work[i]+ Allocation[i,j] ; Finish[i]:= true ; go to step 2;
4. 
   
5. 如果所有进程的Finish[i] = true都满足,则表示系统处于安全状态；否则,系统处于不安全状态。

6. 

银行家算法例题

在银行家算法中，若出现下述资源分配情况：

题目中的资源数应当看作是对四种资源的不同请求数，例如对于‘Available’=‘1 6 2 2’，我们应理解为系统当前四种资源可用个数分别为‘1’、‘6’、‘2’、‘2’。 &nbsp; 解题思路：

• 首先明白各个表头的含义，Allocation——该进程已分配的资源数；Need——该进程还需要的资源数；Available——系统当前可分配的资源数。
• 目前系统中的可用资源为‘1 6 2 2’，与各个进程还需要的资源数进行比较，寻找可为其进行资源分配的进程。
• 试探性地为进程分配资源，若系统存在安全序列，则证明安全。

解：（1）

1. 首先根据目前系统中可用资源为‘1 6 2 2’，只满足P0还需要的资源数，故第一步先为P0分配资源。P0获得运行所需的全部资源后，完成执行，归还资源，此时系统中可用资源为‘Work + Allocation’=‘1 6 5 4’，即为下一步中的‘Work’。

2. 此时系统中可用资源为‘1 6 5 4’，再查看各个进程的‘Need’，只满足P3，故为P3分配资源。P3执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘1 9 8 6’。

3. 此时系统中可用资源为‘1 9 8 6’，再查看各个进程的‘Need’，可以发现P1和P4均可满足，此时我们可以任选一进程为其分配资源，此处笔者选择P1进行资源分配。P1执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘2 9 8 6’。

4. 此时系统中可用资源为‘2 9 8 6’，再查看各个进程的‘Need’，可以发现P2和P4均可满足，此时我们仍然是可以任选一进程为其分配资源，此处笔者选择P2进行资源分配。P2执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘3 12 13 10’。

5. 此时系统中可用资源为‘3 12 13 10’，再查看各个进程的‘Need’，可以发现P4可满足，为P4进行资源分配。P4执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘3 12 13 10’。
6. 至此全部进程均已成功分配资源并运行结束。并且所有进程的‘Finish’=true都满足，系统处于安全状态，且系统的一个安全序列为<P0,P3,P1,P2,P4>。 该系统不止一个安全序列。

（2）

解题思路：按照银行家算法对该请求进行比较、判断。

• Request ≤ Need？ 若不成立，则出错，因为请求的资源超过其最大资源需求。
• Request ≤ Available？ 若不成立，则等待，因为系统可供分配的资源个数无法满足该进程。
• 尝试分配，并将‘Available’、‘Allocation’、‘Need’进行修改，判断安全性。
• Available = Available - Request
• Allocation = Allocation + Request
• Need = Need - Request

1. Request（1，2，2，2）≤ Need（2，3，5，6）成立
2. Request（1，2，2，2）≤ Available（1，6，2，2）成立
3. 做出如下修改： Available = Available - Request 即Available =（0，4，0，0） Allocation = Allocation + Request 即Allocation =（2，5，7，6） Need = Need - Request 即Need =（1，1，3，4） 在尝试分配的过程中，我们可以发现若满足P2提出的请求Request（1，2，2，2），此时无进程的‘Need’可被‘Available’满足，该系统不存在一个安全序列。因此系统不会将资源分配给P2。该类型题目一般是重复问题（1）的步骤，但是这道题目比较简单，不用列表就可以看出