《银行家算法相关ppt》由会员分享，可在线阅读，更多相关《银行家算法相关ppt（20页珍藏版）》请在金锄头文库上搜索。
1、第三章 处理机调度与死锁 产生死锁的原因和必要条件 3.5.1 产生死锁的原因产生死锁的原因可归结为如下两点：(1) 竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。(2) 进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。 第三章 处理机调度与死锁 I/O设备共享时的死锁情况 第三章 处理机调度与死锁 3.5.3 处理死锁的基本方法(1) 预防死锁。(2) 避免死锁。银行家算法(3) 检测死锁。(4) 解除死锁。报告来源http:/ http:/www.quyandai.o
2、rg/http:/ 处理机调度与死锁 系统安全状态1安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给 进程；否则，令进程等待。 第三章 处理机调度与死锁 所谓安全状态，是指系统能按某种进程顺序(P1，P2，Pn)(称P1，P2，Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。虽然并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入
3、死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于：系统在进行资源分配时，如何 使系统不进入不安全状态。 第三章 处理机调度与死锁 2安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 第三章 处理机调度与死锁 3由安全状态向不安全状态的转换如果不按照安全序列分配资源，系统可能会由安全状态进 入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把 剩余3台中的1台
4、分配给P3，则系统便进入不安全状态。因 为此时也无法再找到一个安全序列，例如，把其余的2台分 配给P2，这样，在P2完成后只能释放出4台，既不能满足P1 尚需5台的要求，也不能满足P3尚需6台的要求，致使它们 都无法推进到完成，彼此都在等待对方释放资源，即陷入 僵局，结果导致死锁。如果将剩余的2台磁带机先分配给P1 或P3，也同样都无法使它们推进到完成，因此，从给P3分 配了第3台磁带机开始，系统便又进入了不安全状态。因此 ，在P3请求资源时，尽管系统中尚有可用的磁带机，但却 不能分配给它，必须让P3一直等待到P1和P2完成，释放出 资源后再将足够的资源分配给P3，它才能顺利完成。 第三章 处
5、理机调度与死锁 3.6.3 利用银行家算法避免死锁1银行家算法中的数据结构(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。(2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果 Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 第三章 处理机调度与死锁 (3) 分配矩阵Allocation。这也是一个nm的矩阵，它
6、定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocationi,j=K，则表示进程i当前已分得R j类资源的数目为K。(4) 需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要R j类资源K个，方能完成其任务。上述三个矩阵间存在下述关系：Needi, j=Maxi, j-Allocationi, j 第三章 处理机调度与死锁 2银行家算法设Request i是进程Pi的请求向量，如果Request ij=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：(1) 如果R
7、equest ijNeedi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2) 如果RequestijAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。 第三章 处理机调度与死锁 (3) 系统试探着把资源分配给进程P i，并修改下面数据结构中的数值：Availablej:= Availablej-Request ij；Allocationi,j:= Allocationi,j+Request ij；Needi,j:= Needi,j-Request ij；(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，
8、才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资 源分配状态，让进程Pi等待。 第三章 处理机调度与死锁 3安全性算法系统所执行的安全性算法可描述如下：(1) 设置两个向量： 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。 Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi:=false；当有足够资源分配给进程时，再令Finishi:=true。 第三章 处理机调度与死锁 (2) 从进程集合中找到一个能满足下述条件的进程： Fi
9、nishi=false； Needi,jWorkj；若找到，执行步骤(3)，否则 ，执行步骤(4)。(3) 当进程Pi获得资源后，可顺利执行，直至完成，并 释放出分配给它的资源，故应执行：Workj:= Workj+Allocationi,j；Finishi:=true；go to step （2）； (4) 如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 第三章 处理机调度与死锁 4银行家算法之例假定系统中有五个进程P0，P1，P2，P3，P4和三类资源A，B，C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-16所示。
10、第三章 处理机调度与死锁 图3-16 T0时刻的资源分配表 第三章 处理机调度与死锁 (1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(见图 3-17所示)可知，在T0时刻存在着一个安全序列P1，P3，P4，P2，P0，故系统是安全的。 图3-17 T0时刻的安全序列 第三章 处理机调度与死锁 (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1，0，2)Need1(1，2，2) Request1(1，0，2)Available1(3，3，2) 系统先假定可为P1分配资源，并修改Available， Al
11、location1和Need1向量，形成的资源变化情况如下图圆括号所示第三章 处理机调度与死锁 再利用安全性算法检查此时系统是否安全。如图3-18所示。 图3-18 P1申请资源时的安全性检查 第三章 处理机调度与死锁 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0) Available(2，3，0)，让P4等待。(4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)； 系统暂时先假定可为P0分配资源，并修改有关数据， 如图3-19所示。 第三章 处理机调度与死锁 图3-19 为P0分配资源后的有关资源数据 (5) 进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。如果在银行家算法中，把P0发出的请求向量改为Request0(0，1，0)，系统是否能将资源分配给它，请读者考虑。
