操作系统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时辰是平安的？时辰是平安的

6、？+2-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:= Allocation

13、i,j + RequestijAllocationi,j:= Allocationi,j + Requestij；Needi,j:= Needi,j - RequestijNeedi,j:= Needi,j - Requestij；(4)(4)执行平安性算法，检查此次资源分配后系统能否处于平安执行平安性算法，检查此次资源分配后系统能否处于平安形状。形状。假设平安，将资源正式分配给进程假设平安，将资源正式分配给进程PiPi；否那么，将本次的试探分配作废，恢复原来的资源分配形状，否那么，将本次的试探分配作废，恢复原来的资源分配形状，让进程让进程PiPi等待。等待。3.3.平安性算法平安性算法(1)

14、(1)(1)(1)设置两向量：设置两向量：可供进程继续运转所需各类资源数的可供进程继续运转所需各类资源数的WorkWork 初始时初始时 Work:=Available Work:=Available。表示资源能否足够的表示资源能否足够的FinishFinish， 初始时令初始时令Finishi:=falseFinishi:=false； 资源足够时再令资源足够时再令Finishi:=trueFinishi:=true。Workj=KWorkj=K3.3.平安性算法平安性算法(2)(2)(2)(2)寻觅一个能满足下述条件的进程：寻觅一个能满足下述条件的进程： Finishi=false Fin

15、ishi=false； Needi,jWorkj; Needi,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 Availabl

17、e A B C A B C A B C P0 7 5 3 0 1 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

18、 710 4 74 3 0 0 1 0 10 5 7Need A 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

19、P0 7 5 3 0 1 0 P1 3 2 2 P2 9 0 2 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