admin 管理员组

文章数量: 887021

银行家算法

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. 如果所有进程的Finish[i] = true都满足,则表示系统处于安全状态；否则,系统处于不安全状态。

银行家算法例题

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

ProcessAllocationNeedAvailable
P00 0 3 20 0 1 21 6 2 2
P11 0 0 01 7 5 0
P21 3 5 42 3 5 6
P30 3 3 20 6 5 2
P40 0 1 40 6 5 6

试问：
（1）该状态是否安全？
（2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

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

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

解：（1）

进程\资源WorkNeedAllocationWork + AllocationFinish
P01 6 2 20 0 1 20 0 3 21 6 5 4true
  1. 首先根据目前系统中可用资源为‘1 6 2 2’，只满足P0还需要的资源数，故第一步先为P0分配资源。P0获得运行所需的全部资源后，完成执行，归还资源，此时系统中可用资源为‘Work + Allocation’=‘1 6 5 4’，即为下一步中的‘Work’。
进程\资源WorkNeedAllocationWork + AllocationFinish
P01 6 2 20 0 1 20 0 3 21 6 5 4true
P31 6 5 40 6 5 20 3 3 21 9 8 6true
  1. 此时系统中可用资源为‘1 6 5 4’，再查看各个进程的‘Need’，只满足P3，故为P3分配资源。P3执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘1 9 8 6’。
进程\资源WorkNeedAllocationWork + AllocationFinish
P01 6 2 20 0 1 20 0 3 21 6 5 4true
P31 6 5 40 6 5 20 3 3 21 9 8 6true
P11 9 8 61 7 5 01 0 0 02 9 8 6true
  1. 此时系统中可用资源为‘1 9 8 6’，再查看各个进程的‘Need’，可以发现P1和P4均可满足，此时我们可以任选一进程为其分配资源，此处笔者选择P1进行资源分配。P1执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘2 9 8 6’。
进程\资源WorkNeedAllocationWork + AllocationFinish
P01 6 2 20 0 1 20 0 3 21 6 5 4true
P31 6 5 40 6 5 20 3 3 21 9 8 6true
P11 9 8 61 7 5 01 0 0 02 9 8 6true
P22 9 8 62 3 5 61 3 5 43 12 13 10true
  1. 此时系统中可用资源为‘2 9 8 6’，再查看各个进程的‘Need’，可以发现P2和P4均可满足，此时我们仍然是可以任选一进程为其分配资源，此处笔者选择P2进行资源分配。P2执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘3 12 13 10’。
进程\资源WorkNeedAllocationWork + AllocationFinish
P01 6 2 20 0 1 20 0 3 21 6 5 4true
P31 6 5 40 6 5 20 3 3 21 9 8 6true
P11 9 8 61 7 5 01 0 0 02 9 8 6true
P22 9 8 62 3 5 61 3 5 43 12 13 10true
P43 12 13 100 6 5 60 0 1 43 12 14 14true
  1. 此时系统中可用资源为‘3 12 13 10’，再查看各个进程的‘Need’，可以发现P4可满足，为P4进行资源分配。P4执行完成后归还资源，此时系统中可用资源为‘Work + Allocation’=‘3 12 13 10’。
  2. 至此全部进程均已成功分配资源并运行结束。并且所有进程的‘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）的步骤，但是这道题目比较简单，不用列表就可以看出

本文标签： 例题 银行家 算法 操作系统

版权声明：本文标题：操作系统 银行家算法及相关例题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1715796405h651682.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。