操作系统os03死锁ppt课件

1、操作系统操作系统Operating Systems3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件死锁死锁在多进程在运行过程中因争夺资源而造成的一种僵局，当在多进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。再向前推进。3.5.1 产生死锁的原因产生死锁的原因 竞争资源竞争资源当系统中供多个进程共享的资源，其数目不足以满足诸当系统中供多个进程共享的资源，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁进程的需要时，会引起诸进程对资源的竞争而产生死锁。 进程间推

2、进顺序非法。进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。样会导致产生进程死锁。 3.5.23.5.2产生死锁的必要条件产生死锁的必要条件互斥条件：互斥条件：进程互斥使用资源进程互斥使用资源请求和保持条件：部分分配条件请求和保持条件：部分分配条件申请新资源时不释放已占有资源申请新资源时不释放已占有资源不剥夺条件：不剥夺条件：一个进程不能抢夺其他进程占有的资源一个进程不能抢夺其他进程占有的资源环路条件：环路条件：存在一组进程循环等待资源存在一组进程循环等待资源S1S1S3S3S2S23.5.33.5.3处

3、理死锁的基本方法处理死锁的基本方法预防死锁。预防死锁。破坏产生死锁的四个必要条件中的一个或几个条件破坏产生死锁的四个必要条件中的一个或几个条件 避免死锁。避免死锁。在资源的动态分配过程中，用某种方法去防止系统进入不在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。安全状态，从而避免发生死锁。 检测死锁。检测死锁。通过系统所设置的检测机构，及时地检测出死锁的发生；通过系统所设置的检测机构，及时地检测出死锁的发生；采取适当措施，从系统中将已发生的死锁清除掉。采取适当措施，从系统中将已发生的死锁清除掉。 解除死锁。这是与检测死锁相配套的一种措施解除死锁。这是与检测死锁相配

4、套的一种措施3.6.1预防死锁预防死锁一种较简单和直观的事先预防的方法。一种较简单和直观的事先预防的方法。设置某些限制条件，去破坏产生死锁的四个必要条件中的设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁：一个或几个条件，来预防发生死锁：互斥条件互斥条件请求和保持条件请求和保持条件不剥夺条件不剥夺条件环路条件环路条件3.6.23.6.2系统安全状态系统安全状态1. 1. 安全状态安全状态指系统能按某种进程顺序指系统能按某种进程顺序(P1(P1，P2P2，Pn)Pn)，来为每个进程，来为每个进程PiPi分配其所需资源，直至满足每个进程对资源的最大需求，使分配其所需

5、资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状如果系统无法找到这样一个安全序列，则称系统处于不安全状态。态。当系统进入不安全状态后，便有可能进而进入死锁状态。当系统进入不安全状态后，便有可能进而进入死锁状态。避免死锁的实质在于：避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态系统在进行资源分配时，如何使系统不进入不安全状态2安全状态之例安全状态之例假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。T0时刻是安全的？时刻是安全的？+2-

6、2=12安全状态之例安全状态之例假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。+5-5=02安全状态之例安全状态之例假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。安全序列：安全序列：P2 、P1、P3T0时刻是安全的。时刻是安全的。+7-7=33由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。进入不安全状态。+1-1=23由安全状态向不安全状态的转换由安全状态向不安全状态的转换

7、如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。进入不安全状态。+2-2=03由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。进入不安全状态。3由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。进入不安全状态。从给从给P3P3分配了第分配了第3 3台磁带机开始，系统便又进入了不安全台磁

8、带机开始，系统便又进入了不安全状态。状态。3.6.33.6.3利用银行家算法避免死锁利用银行家算法避免死锁1 1银行家算法中的数据结构银行家算法中的数据结构(1) (1) 可利用资源向量可利用资源向量Available Available 每类资源未分配数量向量每类资源未分配数量向量含有含有m m个元素的数组个元素的数组如果如果Availablej=KAvailablej=K，则表示系统中现有，则表示系统中现有RjRj类资源类资源K K个。个。银行家算法中的数据结构银行家算法中的数据结构(2) (2) 最大需求矩阵最大需求矩阵MaxMax。一个一个n nm m的矩阵，它定义了系统中的矩阵，它定

9、义了系统中n n个进程中的每一个进程对个进程中的每一个进程对m m类资源的最大需求。如果类资源的最大需求。如果Maxi,j=KMaxi,j=K，则表示进程，则表示进程i i需要需要RjRj类资源的最大数目为类资源的最大数目为K K。Max=Max=M11M11 M12M12M1mM1mM21M21 M21M21M21M21Mn1Mn1Mn1Mn1MnmMnm银行家算法中的数据结构银行家算法中的数据结构(3) 分配矩阵分配矩阵Allocation。也是一个也是一个nm的矩阵，它定义了系统中每一类资源当前已分的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。配给每一进程的资源数。如果如

10、果Allocationi,j=K，则表示进程，则表示进程i当前已分得当前已分得R j类资源的数类资源的数目为目为K。Allocation=Allocation=A11A11 A12A12A1mA1mA21A21 A21A21A21A21An1An1An1An1AnmAnm银行家算法中的数据结构银行家算法中的数据结构(4) 需求矩阵需求矩阵Need。一个一个nm的矩阵，用以表示每一个进程尚需的各类资源数的矩阵，用以表示每一个进程尚需的各类资源数。如果如果Needi,j=K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，方能完个，方能完成其任务。成其任务。上述三个矩阵间存在下述关系：上

11、述三个矩阵间存在下述关系：Needi, j=Maxi, j- Allocationi, j 2 2银行家算法银行家算法(1)(1)设设Requestij=KRequestij=K，表示，表示PiPi需要需要K K个个RjRj类资源。类资源。PiPi发出资源请求发出资源请求RequestiRequesti后，系统按下述步骤进行检查：后，系统按下述步骤进行检查：(1)(1)如果如果RequestijNeedi,jRequestijNeedi,j，转向步骤，转向步骤(2)(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布否则认为出错，因为它所需要的资源数已超过它所宣布的的 最大值。最大值。(

12、2)(2)如果如果RequestijAvailablejRequestijAvailablej，转向步骤，转向步骤(3)(3)； 否则，表示尚无足够资源，否则，表示尚无足够资源，PiPi须等待。须等待。 2 2银行家算法银行家算法(2)(2)(3)(3)系统试探把资源分配给进程系统试探把资源分配给进程PiPi，并修改数据结构中的值：，并修改数据结构中的值：Availablej:= Availablej - RequestijAvailablej:= Availablej - Requestij；Allocationi,j:= Allocationi,j + RequestijAllocatio

13、ni,j:= Allocationi,j + Requestij；Needi,j:= Needi,j - RequestijNeedi,j:= Needi,j - Requestij；(4)(4)执行安全性算法，检查此次资源分配后系统是否处于安全执行安全性算法，检查此次资源分配后系统是否处于安全状态。状态。若安全，将资源正式分配给进程若安全，将资源正式分配给进程PiPi；否则，将本次的试探分配作废，恢复原来的资源分配状态，让否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程进程PiPi等待。等待。3.3.安全性算法安全性算法(1)(1)(1)(1)设置两向量：设置两向量：可供进程继续运

14、行所需各类资源数的可供进程继续运行所需各类资源数的WorkWork 初始时初始时 Work:=Available Work:=Available。表示资源是否足够的表示资源是否足够的FinishFinish， 初始时令初始时令Finishi:=falseFinishi:=false； 资源足够时再令资源足够时再令Finishi:=trueFinishi:=true。Workj=KWorkj=K3.3.安全性算法安全性算法(2)(2)(2)(2)寻找一个能满足下述条件的进程：寻找一个能满足下述条件的进程： Finishi=false Finishi=false； Needi,jWorkj; Ne

15、edi,jWorkj;找到执行步骤找到执行步骤(3)(3)，否则执行步骤，否则执行步骤(4)(4)。(3)(3)进程进程PiPi获得资源，执行完成后释放它的资源，故应执行：获得资源，执行完成后释放它的资源，故应执行：Workj:= Workj+Allocationi,jWorkj:= Workj+Allocationi,j；Finishi:=trueFinishi:=true；go to step 2go to step 2； (4)(4)如果所有进程的如果所有进程的Finishi=trueFinishi=true都满足，则表示系统处于都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

16、安全状态；否则，系统处于不安全状态。 实例说明系统所处的安全或不安全状态实例说明系统所处的安全或不安全状态假定系统中有五个进程假定系统中有五个进程P0P0，P1P1，P2P2，P3P3，P4P4三类资源三类资源AA，B B，C C 。 A A类资源共有类资源共有1010个个B B类资源共有类资源共有5 5个个C C类资源共有类资源共有7 7个。个。（1在时刻在时刻T0,系统目前资源分配情况如下：系统目前资源分配情况如下：每个进程目前还需资源为每个进程目前还需资源为Need 进程进程 Max Allocation Available A B C A B C A B C P0 7 5 3 0 1

17、0 3 3 2 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2NeedA B C 7 4 31 2 26 0 00 1 1 4 3 1 进程进程 Work Need Allocation Work=Work+allocation A B C A B C A B C A B C5 3 23 3 21 2 2 2 0 05 3 20 1 1 2 1 17 4 37 4 3P1P3P4P2P04 3 1 0 0 27 4 57 4 56 0 0 3 0 210 4 710 4 74 3 0 0 1 0 10 5 7Need A

18、B C P0 7 4 3 P1 1 2 2 A B C P2 6 0 0P3 0 1 1 A B C P4 4 3 1可以断言可以断言T0时刻，系统处于安全状态时刻，系统处于安全状态因为序列因为序列P1,P3,P4,P2,P0能满足安全性条件。能满足安全性条件。（2进程进程P1申请资源申请资源request1=(1,0,2) ，系统能将资源，系统能将资源分配给它吗？分配给它吗？NeedA B C7 4 36 0 00 1 14 3 1 进程进程 Max Allocation Available A B C A B C A B C P0 7 5 3 0 1 0 P1 3 2 2 P2 9 0 2

19、 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2检查检查: request1(1,0,2) Need1(1,2,2) and request1(1,0,2) Available(3,3,2) 结果满足条件，试分配。结果满足条件，试分配。3 0 2 0 2 02 3 0得到新状态：得到新状态： 2 0 03 3 21 2 2判定新状态是否安全判定新状态是否安全?找到一个进程序列找到一个进程序列 可保证进程可保证进程P1运行完毕并归还资源运行完毕并归还资源进程进程 Work Need Allocation work+allocation A B C A B C A B C A B C5 3 22 3 00 2 0 3 0 25 3 20 1 1 2 1 17 4 37 4 3P1P3P4P0P24 3 1 0 0 27 4 57 4 57 4 3 0 1 07 5 57 5 56 0 0 3 0 2 10 5 7 A B CP0 7 4 3P1 0 2 0P2 6 0 0P3 0