银行家算法iebo.pptx

《银行家算法iebo.pptx》由会员分享，可在线阅读，更多相关《银行家算法iebo.pptx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机操作系统计算机操作系统2死锁的死锁的“3W”3W”WhatWhyHow什么是死锁？什么是死锁？为什么会发生死锁？为什么会发生死锁？怎么解决死锁？怎么解决死锁？3死锁的处理方法死锁的处理方法 （1 1）预防死锁）预防死锁）预防死锁）预防死锁：通过某些限制条件的设置，去破坏通过某些限制条件的设置，去破坏通过某些限制条件的设置，去破坏通过某些限制条件的设置，去破坏产生死锁的四个必要条件；产生死锁的四个必要条件；产生死锁的四个必要条件；产生死锁的四个必要条件；（2 2）避免死锁）避免死锁）避免死锁）避免死锁：在资源的动态分配过程中，用某种在资源的动态分配过程中，用某种在资源的动态分配过程中，用某

2、种在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；方法去防止系统进入不安全状态；方法去防止系统进入不安全状态；方法去防止系统进入不安全状态；（3 3）检测死锁）检测死锁）检测死锁）检测死锁：及时检测死锁的发生，并确定与之及时检测死锁的发生，并确定与之及时检测死锁的发生，并确定与之及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；相关的进程、资源，从而采取措施清除死锁；相关的进程、资源，从而采取措施清除死锁；相关的进程、资源，从而采取措施清除死锁；（4 4）解除死锁）解除死锁）解除死锁）解除死锁：撤消或挂起某些进程以回收一些资撤消或挂起某些进程以回收一些资撤消或挂

3、起某些进程以回收一些资撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。源，用于解脱另一些处于死锁的进程。源，用于解脱另一些处于死锁的进程。源，用于解脱另一些处于死锁的进程。4避免死锁避免死锁银行家算法银行家算法设银行家有10万周转资金，P,Q,R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q要申请2万，R要申请4万.Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐什么是银行家问题？什么是银行家问题？什么是银行家问题？什么是银行家问题？银行家-操作系统 周转资金-系统资源 贷款客户-进程当某进程请求分配资源时，系统假定先分配给

4、它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。银行家算法的实现思想银行家算法的实现思想银行家算法的实现思想银行家算法的实现思想5表表表表 示示示示 形形形形 式式式式含含含含 义义义义AvailableAvailable（可用资源数组）可用资源数组）可用资源数组）可用资源数组）Available j Available j k k现有资源现有资源现有资源现有资源 j j 的数目为的数目为的数目为的数目为 k k Max（最大需求矩阵）最大需求矩阵）最大需求矩阵）最大需求矩阵）Max i,j Max i,j k k进程进程进程进程 i i 对

5、资源对资源对资源对资源 j j 的最大需的最大需的最大需的最大需求数目为求数目为求数目为求数目为 k k Allocation（分配矩阵）分配矩阵）分配矩阵）分配矩阵）Allocation i,j Allocation i,j k k进程进程进程进程 i i 当前已分得的资源当前已分得的资源当前已分得的资源当前已分得的资源 j j 的数目为的数目为的数目为的数目为 k kNeed（需求矩阵）需求矩阵）需求矩阵）需求矩阵）Need i,j Need i,j k k进程进程进程进程 i i 尚需分配的资源尚需分配的资源尚需分配的资源尚需分配的资源 j j 的数目为的数目为的数目为的数目为 k k银

6、行家算法中的数据结构银行家算法中的数据结构6银行家算法当Pi发出资源请求，分配一个Request向量然后系统按下述流程进行执行：Requesti：是进程Pi的请求向量如果Requestij=K，表示进程i需要K个Rj类型的资源。银行家算法实现过程银行家算法实现过程78安全性算法实现过程安全性算法实现过程安全性算法两个向量：Work和FinishWork表示系统可提供给进程继续运行所需的各类资源数目（即在分配过程中，系统的可用资源数）。初始值 Work=Available;Finish表示系统是否有足够的资源分配给进程i，使之运行完成。初始值 Finishi:=false当有足够资源分配给进程时

7、 Finishi:=true910 假假假假定定定定系系系系统统统统中中中中有有有有五五五五个个个个进进进进程程程程P P0 0,P P1 1,P P2 2,P P3 3,P P4 4和和和和三三三三类类类类资资资资源源源源A,A,B,B,C C，各各各各种种种种资资资资源源源源的的的的数数数数量量量量分分分分别别别别为为为为1010、5 5、7 7，在在在在T T0 0时时时时刻刻刻刻的的的的资源分配情况如下图所示。资源分配情况如下图所示。资源分配情况如下图所示。资源分配情况如下图所示。P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA,B,C

8、A,B,CNeedNeedA,B,CA,B,CAllocationAllocationA,B,CA,B,CMaxMaxA,B,CA,B,C进进进进 程程程程资源资源资源资源 情况情况情况情况7,5,37,5,33,2,23,2,29,0,29,0,22,2,22,2,24,3,34,3,30,1,00,1,02,0,02,0,03,0,23,0,22,1,12,1,10,0,20,0,27,4,37,4,31,2,21,2,26,0,06,0,00,1,10,1,14,3,14,3,13,3,2银行家算法实例银行家算法实例11（1 1）T T0 0时刻系统是否安全？时刻系统是否安全？时刻系统是

9、否安全？时刻系统是否安全？执行安全性算法进行检查：执行安全性算法进行检查：执行安全性算法进行检查：执行安全性算法进行检查：向量初值向量初值向量初值向量初值 Work:Work:AvailableAvailable(3,3,2)(3,3,2)；Finish i:Finish i:falsefalse；（；（；（；（i i0,1,40,1,4）在进程集合中找到在进程集合中找到在进程集合中找到在进程集合中找到 NeedNeed1 1(1,2,2)(1,2,2)WorkWork 且且且且 Finish 1 Finish 1 falsefalse；则设则设则设则设 P P1 1 顺利执行完成，从而有：顺

10、利执行完成，从而有：顺利执行完成，从而有：顺利执行完成，从而有：WorkWork:WorkWorkAllocationAllocation1 1 (3,3,2)(3,3,2)(2,0,0)(2,0,0)(5,3,2)(5,3,2)Finish 1:Finish 1:truetrue银行家算法实例银行家算法实例12Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue5 3 22 0

11、01 2 23 3 2P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 113Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue7 4 35 3 22 1 10 1 1P3true5 3 22 0 01 2 23 3 2P1AllocationAlloc

12、ationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 114Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue7 5 37 4 30 1 07 4 3true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P3P1AllocationAllocat

13、ionNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 115Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2

14、P0P2P3P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 116Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1true10 5 70 0 24 3 110 5 5P4FinishFinishWork+AllocationWork+Al

15、locationAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P117 发现：目前可执行的所有资源分配工作完成之后，发现：目前可执行的所有资源分配工作完成之后，发现：目前可执行的所有资源分配工作完成之后，发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量各个进程对应的状态向量各个进程对应的状态向量各个进程对应的状态向量 Finish i Finish

16、 i truetrue；且对应于该向且对应于该向且对应于该向且对应于该向量置为量置为量置为量置为“true”true”的进程编号依次为：的进程编号依次为：的进程编号依次为：的进程编号依次为：1 1 33 00 2 2 4 4，故：故：故：故：系统存在安全序列系统存在安全序列系统存在安全序列系统存在安全序列 P P1 1，P P3 3，P P0 0，P P2 2，P P4 4 所以，所以，所以，所以，T T0 0 时刻系统处于安全状态！时刻系统处于安全状态！时刻系统处于安全状态！时刻系统处于安全状态！银行家算法实例银行家算法实例18Chapter 3 Chapter 3 处理机调度与死锁处理机调

17、度与死锁处理机调度与死锁处理机调度与死锁 由分析知：执行完由分析知：执行完由分析知：执行完由分析知：执行完 P P1 1、P P3 3 的资源分配请求之后，系的资源分配请求之后，系的资源分配请求之后，系的资源分配请求之后，系统可用的资源数量可以满足其它统可用的资源数量可以满足其它统可用的资源数量可以满足其它统可用的资源数量可以满足其它 3 3 个进程的资源请求，个进程的资源请求，个进程的资源请求，个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：则此时的资源分配顺序已无关紧要。所以：则此时的资源分配顺序已无关紧要。所以：则此时的资源分配顺序已无关紧要。所以：安全序列可以不唯一安全序列可以

18、不唯一安全序列可以不唯一安全序列可以不唯一！true10 5 70 0 24 3 110 5 5P4FinishFinishWork+AllocatioWork+Allocation nAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P119（2 2）P P1 1 发出请求发出请求发出请求发出请求Request(1,0,2)Request(1,0,2)，系统能分配资源

19、吗？，系统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？执行银行家算法：执行银行家算法：执行银行家算法：执行银行家算法：RequestRequest1 1(1,0,2)(1,0,2)NeedNeed1 1(1,2,2)(1,2,2)；Request Request1 1(1,0,2)(1,0,2)Available(3,3,2)Available(3,3,2)；系统为系统为系统为系统为P P1 1进行进行进行进行预分配预分配预分配预分配，并修改，并修改，并修改，并修改AvailableAvailable，AllocationAllocation1 1 和和和和 NeedNeed1 1向

20、量：向量：向量：向量：银行家算法实例银行家算法实例RequestRequest1 1(1,0,2)(1,0,2)，NeedNeed1 1，Available Available 20 AvailableAvailable:AvailableAvailableRequestRequest1 1 (3,3,2)(3,3,2)(1,0,2)(1,0,2)(2,3,0)(2,3,0)AllocationAllocation1 1:AllocationAllocation1 1RequestRequest1 1 (2,0,0)(2,0,0)(1,0,2)(1,0,2)(3,0,2)(3,0,2)Need

21、Need1 1:NeedNeed1 1RequestRequest1 1 (1,2,2)(1,2,2)(1,0,2)(1,0,2)(0,2,0)(0,2,0)银行家算法实例银行家算法实例21 执行安全性算法执行安全性算法执行安全性算法执行安全性算法：a.Work:a.Work:AvailableAvailable(2,3,0)(2,3,0)；Finish i:Finish i:falsefalse；b.b.在进程集合中找到在进程集合中找到在进程集合中找到在进程集合中找到 NeedNeed1 1(0,2,0)(0,2,0)WorkWork；b.b.在进程集合中找到在进程集合中找到在进程集合中找到

22、在进程集合中找到 NeedNeed3 3(0,1,1)(0,1,1)WorkWork（5 5，3 3，2 2）且且且且 Finish 3 Finish 3 falsefalse；c.c.则设则设则设则设 P P1 1可顺利执行完成，从而有：可顺利执行完成，从而有：可顺利执行完成，从而有：可顺利执行完成，从而有：WorkWork:WorkWorkAllocationAllocation1 1 (2,3,0)(2,3,0)(3,0,2)(3,0,2)(5,3,2)(5,3,2)Finish Finish 1 1:truetrue银行家算法实例银行家算法实例22c.c.则设则设则设则设 P P3 3

23、 顺利执行完成，从而有：顺利执行完成，从而有：顺利执行完成，从而有：顺利执行完成，从而有：WorkWork:WorkWorkAllocationAllocation3 3 (5,3,2)(5,3,2)(2,1,1)(2,1,1)(7,4,3)(7,4,3)Finish 3:Finish 3:truetrue 执行安全性算法检查时，仍能够得到安全序列执行安全性算法检查时，仍能够得到安全序列执行安全性算法检查时，仍能够得到安全序列执行安全性算法检查时，仍能够得到安全序列 P1P1，P3P3，P0P0，P2P2，P4 P4，故请求向量，故请求向量，故请求向量，故请求向量 RequestRequest

24、1 1(1,0,(1,0,2)2)发出时系统安全！发出时系统安全！发出时系统安全！发出时系统安全！银行家算法实例银行家算法实例23（3 3）P P4 4发出请求发出请求发出请求发出请求Request(3,2,1)Request(3,2,1)，系统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：RequestRequest4 4(3,2,0)(3,2,0)NeedNeed4 4(4,3,1)(4,3,1)；Request Request4 4(3,2,1)(3,2,1)Ava

25、ilable(2,3,0)Available(2,3,0)故：故：故：故：P P4 4 资源请求失败，让其等待！资源请求失败，让其等待！资源请求失败，让其等待！资源请求失败，让其等待！银行家算法实例银行家算法实例24（4 4）P P0 0发出请求发出请求发出请求发出请求Request(0,2,0)Request(0,2,0)，系统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？，系统能分配资源吗？执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：执行银行家算法进行检查：RequestRequest0 0(0,2,0)(0,2,0)NeedNeed0 0(7,4,3)

26、(7,4,3)；Request Request0 0(0,2,0)(0,2,0)Available(2,3,0)Available(2,3,0)；系统为系统为系统为系统为 P P0 0 作预分配，并修改有关数据：作预分配，并修改有关数据：作预分配，并修改有关数据：作预分配，并修改有关数据：银行家算法实例银行家算法实例25 Available Available:AvailableAvailableRequestRequest0 0 (2,3,0)(2,3,0)(0,2,0)(0,2,0)(2,1,0)(2,1,0)AllocationAllocation0 0:AllocationAlloca

27、tion0 0RequestRequest0 0 (0,1,0)(0,1,0)(0,2,0)(0,2,0)(0,3,0)(0,3,0)Need Need0 0 :NeedNeed0 0RequestRequest0 0 (7,4,3)(7,4,3)(0,2,0)(0,2,0)(7,2,3)(7,2,3)银行家算法实例银行家算法实例26MaxMaxAllocationAllocationNeedNeedAvailableAvailableP07 5 30 3 07 2 32 1 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 3

28、0 0 24 3 1 显然，对于所有进程，条件显然，对于所有进程，条件显然，对于所有进程，条件显然，对于所有进程，条件NeedNeedi iAvailableAvailable，均不成，均不成，均不成，均不成立。因此，立。因此，立。因此，立。因此，P P0 0 此次资源请求预分配的结果，使系统进入不此次资源请求预分配的结果，使系统进入不此次资源请求预分配的结果，使系统进入不此次资源请求预分配的结果，使系统进入不安全状态，故应撤消此次预分配。安全状态，故应撤消此次预分配。安全状态，故应撤消此次预分配。安全状态，故应撤消此次预分配。银行家算法实例银行家算法实例27练习练习 资源资源进程进程Allocation NeedAvailabler1 r2 r3r1 r2 r3r1 r2 r3P0P1P2P3P43 1 10 0 01 1 01 0 10 0 01 0 00 1 23 0 00 1 02 1 01 2 0在银行家算法中，若出现下面的资源分配情况：28试问：1)该状态是否安全？2)如果进程P2提出请求Request(0，1，0)，系统能否将资源分配给它？3)如果系统立即满足P2的上述请求，则系统是否立即进入死锁状态？练习练习