《操作系统死锁》ppt课件

1、 第四章第四章 死锁死锁n死锁的概念死锁的概念n死锁的预防和防止死锁的预防和防止n死锁的检测和解除死锁的检测和解除 死锁的概念死锁的概念n死锁举例死锁举例n产生死锁的缘由产生死锁的缘由 n产生死锁的必要条件产生死锁的必要条件 n处置死锁的根本方法处置死锁的根本方法 死锁举例死锁举例1n两个小孩在一同玩耍，一个在玩皮球，另一两个小孩在一同玩耍，一个在玩皮球，另一个玩自动步枪个玩自动步枪n假设这两个小孩都要对方手中的玩具，而又假设这两个小孩都要对方手中的玩具，而又不肯先放掉本人拿着的玩具，这时就发生了不肯先放掉本人拿着的玩具，这时就发生了僵持局面。僵持局面。 死锁举例死锁举例2n设系统有一台打印机

2、和一台扫描仪，进程设系统有一台打印机和一台扫描仪，进程P1、P2并发执行，在某时辰并发执行，在某时辰T，进程，进程P1和和P2分别占分别占用了打印机和扫描仪。用了打印机和扫描仪。n在时辰在时辰T1T1T，P1又要恳求扫描仪，但又要恳求扫描仪，但由于扫描仪被由于扫描仪被P2占用，占用，P1只需等待。只需等待。n在时辰在时辰T2T2T，P2又恳求打印机，但由又恳求打印机，但由于打印机被于打印机被P1占用，占用，P2只需等待。只需等待。n如此两进程均不能执行完成。称这种景象为死锁。如此两进程均不能执行完成。称这种景象为死锁。 n在消费者在消费者-消费者问题中将消费者进程的两个消费者问题中将消费者进程

3、的两个P操操作颠倒时会发生死锁。作颠倒时会发生死锁。 n将消费者进程的两个将消费者进程的两个P操作颠倒时也会发生死锁。操作颠倒时也会发生死锁。 死锁举例死锁举例3 死锁的定义死锁的定义n一组进程中，两个或多个进程都无限期地等待永一组进程中，两个或多个进程都无限期地等待永远不会发生的条件，我们称此系统处于死锁形状。远不会发生的条件，我们称此系统处于死锁形状。n死锁死锁Deadlockn饥饿饥饿Starvation 死锁的原因死锁的原因n根本缘由：系统可以提供的资源个数比要求该资根本缘由：系统可以提供的资源个数比要求该资源的进程所需的资源个数少。源的进程所需的资源个数少。 判别判别 1 1、参与死

4、锁的一切进程都占有资源、参与死锁的一切进程都占有资源 错误：有能够有的进程在等待其他进程释放资错误：有能够有的进程在等待其他进程释放资源源 2 2、参与死锁的一切进程均正在等待资源、参与死锁的一切进程均正在等待资源 错误：有能够一个占有资源错误：有能够一个占有资源 3 3、参与死锁的一切进程中至少有两个进程占有、参与死锁的一切进程中至少有两个进程占有资源资源 错误错误 4 4、参与死锁的进程至少有两个、参与死锁的进程至少有两个 正确正确 关于死锁的一些结论关于死锁的一些结论参与死锁的进程最少是两个参与死锁的进程最少是两个 两个以上进程才会出现死锁两个以上进程才会出现死锁参与死锁的进程至少有两个

5、曾经占有资源参与死锁的进程至少有两个曾经占有资源参与死锁的一切进程都在等待资源参与死锁的一切进程都在等待资源参与死锁的进程是当前系统中一切进程的子集参与死锁的进程是当前系统中一切进程的子集注：假设死锁发生，会浪费大量系统资源，甚至导注：假设死锁发生，会浪费大量系统资源，甚至导致系统解体致系统解体 产生死锁的必要条件产生死锁的必要条件四个必要条件重点四个必要条件重点互斥条件：涉及的资源是非共享的。互斥条件：涉及的资源是非共享的。不剥夺条件：不能强行剥夺进程拥有的资源。不剥夺条件：不能强行剥夺进程拥有的资源。部分分配条件：进程在等待一新资源时继续占有已部分分配条件：进程在等待一新资源时继续占有已分

6、配的资源。分配的资源。环路条件：存在一种进程的循环链，链中的每一个环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所恳进程已获得的资源同时被链中的下一个进程所恳求。求。 处置死锁的根本方法处置死锁的根本方法1、预防死锁：、预防死锁：经过设置某些限制条件，去破坏死锁四个必要条件经过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。中的一个或多个，来防止死锁。较易实现，广泛运用，但由于所施加的限制往往太较易实现，广泛运用，但由于所施加的限制往往太严厉，能够导致系统资源利用率和系统吞吐量的严厉，能够导致系统资源利用率和系统吞吐量的降低。降低。 处置

7、死锁的根本方法续处置死锁的根本方法续2 2、防止死锁：、防止死锁：不事先采取限制去破坏产生死锁的条件，而是在资不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进源的动态分配过程中，用某种方法去防止系统进入不平安形状，从而防止死锁的发生。入不平安形状，从而防止死锁的发生。实现较难，只需求较弱的限制条件，可获得较高的实现较难，只需求较弱的限制条件，可获得较高的资源利用率和系统吞吐量。资源利用率和系统吞吐量。 处置死锁的根本方法续处置死锁的根本方法续3、检测死锁：、检测死锁：事先并不采取任何限制，也不检查系统能否进入不事先并不采取任何限制，也不检查系统能否进入不平

8、安区，允许死锁发生，但可经过检测机构及时平安区，允许死锁发生，但可经过检测机构及时检测出死锁的发生，并准确确定与死锁有关的进检测出死锁的发生，并准确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生程和资源，然后采取适当措施，将系统中已发生的死锁去除掉的死锁去除掉 处置死锁的根本方法续处置死锁的根本方法续4、解除死锁：、解除死锁：与检测死锁相配套，用于将进程从死锁形状解脱出与检测死锁相配套，用于将进程从死锁形状解脱出来。来。常用的方法是吊销或挂起一些进程。以回收一些资常用的方法是吊销或挂起一些进程。以回收一些资源，再将它们分配给处于阻塞形状的进程，使之源，再将它们分配给处于阻塞形状的

9、进程，使之转为就绪形状。转为就绪形状。实现难度大，但可获得较好的资源利用率和系统吞实现难度大，但可获得较好的资源利用率和系统吞吐量。吐量。 死锁的预防和防止死锁的预防和防止n死锁的预防死锁的预防 n系统的平安形状系统的平安形状 n利用银行家算法防止死锁利用银行家算法防止死锁 死锁的预防死锁的预防n在系统设计时确定资源分配算法，保证不发生死在系统设计时确定资源分配算法，保证不发生死锁锁n详细的做法是破坏产生死锁的四个必要条件之一详细的做法是破坏产生死锁的四个必要条件之一 破坏部分分配条件破坏部分分配条件n系统要求一切进程要一次性地恳求在整个运转过系统要求一切进程要一次性地恳求在整个运转过程中所需

10、的全部资源。假设系统有足够资源那么程中所需的全部资源。假设系统有足够资源那么完全分配。完全分配。 优点：简单、易于实现且平安。优点：简单、易于实现且平安。缺陷：缺陷：一个用户在作业运转之前能够提不出他的作业将要运用的全部一个用户在作业运转之前能够提不出他的作业将要运用的全部设备。设备。用户作业必需等待，直到一切资源满足才干运转。实践上某些用户作业必需等待，直到一切资源满足才干运转。实践上某些资源能够要到运转后期才会用到。资源能够要到运转后期才会用到。一个作业运转期间，对某些设备的运用时间很短，甚至不会用一个作业运转期间，对某些设备的运用时间很短，甚至不会用到。如：当用户作业出错时才需求打印机输

11、出错误信息，但到。如：当用户作业出错时才需求打印机输出错误信息，但采用静态分配法必需把打印机分配给该作业，并长期占用。采用静态分配法必需把打印机分配给该作业，并长期占用。采用该方法对系统来说是非常浪费的。采用该方法对系统来说是非常浪费的。 破坏部分分配条件破坏部分分配条件方法分析方法分析 破坏不可剥夺条件破坏不可剥夺条件n一个已拥有资源的进程，假设它再提出新资源要一个已拥有资源的进程，假设它再提出新资源要求而不能立刻得到满足时，它必需释放曾经拥有求而不能立刻得到满足时，它必需释放曾经拥有的一切资源。以后需求时再重新恳求。的一切资源。以后需求时再重新恳求。n实现复杂、要付出很大的代价。实现复杂、

12、要付出很大的代价。 破坏环路条件破坏环路条件n系统中的一切资源都有一个确定的独一号码，一系统中的一切资源都有一个确定的独一号码，一切分配恳求必需以序号上升的次序进展。切分配恳求必需以序号上升的次序进展。n例如：系统中有以下设备：输入机例如：系统中有以下设备：输入机1，打印，打印机机2，穿孔机，穿孔机3，磁带机，磁带机4，磁盘，磁盘5。有一进程要先后运用输入机、磁盘、打。有一进程要先后运用输入机、磁盘、打印机，那么它恳求设备时要按输入机、打印机、印机，那么它恳求设备时要按输入机、打印机、磁盘的顺序恳求。磁盘的顺序恳求。 破坏环路条件破坏环路条件方法分析方法分析n优点：同前两法相比，其资源利用率和

13、系统吞吐优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。量有较明显的改善。n n缺陷：进程实践需求资源的顺序不一定与资源的缺陷：进程实践需求资源的顺序不一定与资源的编号一致，因此仍会呵斥资源浪费。编号一致，因此仍会呵斥资源浪费。 系统的平安形状系统的平安形状n死锁防止定义：死锁防止定义：n 在系统运转过程中，对进程发出的每一个系统在系统运转过程中，对进程发出的每一个系统可以满足的资源恳求进展动态检查，并根据检查可以满足的资源恳求进展动态检查，并根据检查结果断定能否分配资源，假设分配后系统能够发结果断定能否分配资源，假设分配后系统能够发生死锁，那么不予分配，否那么予以分配。生死锁，那

14、么不予分配，否那么予以分配。 平安形状平安形状假设系统能按某种顺序如假设系统能按某种顺序如P4,P1,Pn，称为平安序列为每个进程分配其所需的资源，称为平安序列为每个进程分配其所需的资源，直至一切进程都能运转完成，称系统处于平安形直至一切进程都能运转完成，称系统处于平安形状。假设不存在这样一个平安序列称系统处于不状。假设不存在这样一个平安序列称系统处于不平安形状。平安形状。 平安形状举例平安形状举例n有三个进程有三个进程p1、p2、p3，有，有12台磁带机。台磁带机。nP1共要求共要求10台，台，P2共要求共要求4台，台，P3共要求共要求9台。台。n在在T0时辰，时辰，p1,p2,p3分别获得

15、分别获得5、2、2台，尚台，尚有有3台空闲。台空闲。 分析分析进程最大需求已分配还需可用p110553p2422p3927经分析，在经分析，在T0T0时辰，系统是平安的。时辰，系统是平安的。由于存在一个平安序列由于存在一个平安序列p2p2、p1p1、p3p3。见以下图。见以下图。 由平安形状向不平安形状的转换由平安形状向不平安形状的转换n假设不按平安序列分配资源，那么系统能够会由假设不按平安序列分配资源，那么系统能够会由平安形状进入不平安形状。平安形状进入不平安形状。n如在如在T0T0以后，以后，P3P3要求要求1 1台磁带机，假设系统分给台磁带机，假设系统分给它一台，那么系统进入不平安形状。

16、它一台，那么系统进入不平安形状。n由于其他由于其他2 2台分给台分给P2P2，P2P2完成后，只能释放完成后，只能释放4 4台，台，这既不能满足这既不能满足P1P15 5台，也不能满足台，也不能满足P3P36 6台。台。将导致死锁。将导致死锁。n可见当可见当P3P3恳求资源时，虽然系统中有资源也不能恳求资源时，虽然系统中有资源也不能分给它。分给它。 系统进入不平安形状系统进入不平安形状进程最大需求已分配还需可用p110552p2422p3936 利用银行家算法防止死锁利用银行家算法防止死锁最有代表性的防止死锁算法，由最有代表性的防止死锁算法，由Dijkstra提出。提出。1、银行家算法中的数据

17、构造、银行家算法中的数据构造可利用资源向量可利用资源向量Available。它是一个含有。它是一个含有m个元个元素的数组，其中每个元素代表一类可利用资源的素的数组，其中每个元素代表一类可利用资源的数目。数目。如：如： ABC523 利用银行家算法防止死锁续利用银行家算法防止死锁续n最大需求矩阵最大需求矩阵Max。n*m矩阵，表示矩阵，表示n个进程的个进程的每一个对每一个对m类资源的最大需求。类资源的最大需求。ABCP1562P2331P3425P4332 利用银行家算法防止死锁续利用银行家算法防止死锁续n分配矩阵分配矩阵Allocation 。n*m矩阵，表示每个进矩阵，表示每个进程分配的资源

18、数。程分配的资源数。ABCP1212P2121P3222P4132 利用银行家算法防止死锁续利用银行家算法防止死锁续n需求矩阵需求矩阵Need 。n*m矩阵，表示每个进程还需矩阵，表示每个进程还需求各类资源数。求各类资源数。ABCP1352P2211P3223P4232 例例n设系统有五个进程和三类资源，每类资源分别有设系统有五个进程和三类资源，每类资源分别有10、5、7。在。在T0时辰资源分配情况如图：时辰资源分配情况如图： 银行家算法描画银行家算法描画当进程当进程pi提出资源恳求时，系统执行以下步骤：提出资源恳求时，系统执行以下步骤：1假设假设RequestiNeedi，转，转2； 否那么

19、错误前往否那么错误前往2假设假设RequestiAvailable， 转转3；否那么进程等待；否那么进程等待 银行家算法描画续银行家算法描画续3假设系统分配了资源，那么有：假设系统分配了资源，那么有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti4执行平安性算法，假设系统新形状是平安的，执行平安性算法，假设系统新形状是平安的，那么分配完成，假设系统新形状是不平安的，那那么分配完成，假设系统新形状是不平安的，那么恢复原形状，进程等待。么恢复原形状，进程等待。 平安性算法平安

20、性算法n为进展平安性检查，定义数据构造：为进展平安性检查，定义数据构造：nWork:ARRAY0.m-1 of integer;nFinish:ARRAY0.n-1 of Boolean;nm代表资源的数量，代表资源的数量，n代表进程的数量代表进程的数量 平安性算法步骤平安性算法步骤(1) Work:=Available; Finish:=false;(2) 寻觅满足以下条件的寻觅满足以下条件的i： a) Finishi=false; b) NeediWork;假设不存在，那么转假设不存在，那么转(4) 平安性算法步骤续平安性算法步骤续(3) Work:=Work+Allocationi; F

21、inishi:=true; 转转(2)(4) 假设对一切假设对一切i,Finishi=true,那么系统处于平那么系统处于平安形状，否那么处于不平安形状安形状，否那么处于不平安形状 T0时辰的平安性检查时辰的平安性检查T0时辰可以找到一个平安序列时辰可以找到一个平安序列p1,p3,p4,p2,p0. 系统是平安的。系统是平安的。 例例1：T0时辰时辰P1恳求资源恳求资源P1发出恳求发出恳求Request(1,0,2)，执行银行家算法，执行银行家算法 执行平安性算法执行平安性算法可以找到一个平安序列可以找到一个平安序列p1,p3,p4,p0,p2. 系统是平安的，可以将系统是平安的，可以将P1的

22、恳的恳求分配给它。求分配给它。 例例2：P4恳求资源恳求资源nP4发出恳求发出恳求Request(3,3,0)，执行银行家算法，执行银行家算法nAvailable=2 3 0n不能经过算法第不能经过算法第2步步 RequestiAvailable ，所以，所以P4等待。等待。 例例3：P0恳求资源恳求资源nRequest0，2，0，执行银行家算法，执行银行家算法 进展平安性检查进展平安性检查nAvailable2,1,0已不能满足任何进程需求，已不能满足任何进程需求，所以系统进入不平安形状，所以系统进入不平安形状，P0的恳求不能分配的恳求不能分配 n练习：有三类资源练习：有三类资源A(17)A

23、(17)、B(5)B(5)、C(20)C(20)。有。有5 5个进个进程程P1P5P1P5。T0T0时辰系统形状如下：时辰系统形状如下：n问问(1)T0(1)T0时辰能否为平安形状，给出平安序列。时辰能否为平安形状，给出平安序列。n(2)T0(2)T0时辰，时辰，P2: Request(0,3,4)P2: Request(0,3,4)，能否分配，为，能否分配，为什么？什么？n(3)(3)在在(2)(2)的根底上的根底上P4P4：Request(2,0,1)Request(2,0,1)，能否分配，能否分配，为什么？为什么？n(4)(4)在在(3)(3)的根底上的根底上P1P1：Request(0

24、,2,0)Request(0,2,0)，能否分配，能否分配，为什么？为什么？ 最大需求已分配P15 5 92 1 2P25 3 64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 1 4 解：解：(1) T0时辰得出平安系列时辰得出平安系列最大需求已分配NeedP15 5 92 1 23 4 7P25 3 64 0 21 3 4P34 0 114 0 50 0 6P44 2 52 0 42 2 1P54 2 43 1 41 1 0A(17)、B(5)、C(20)Work=available=2 3 3先求出先求出Need和和Work WorkAllocationNe

25、edW+AFinishP52 3 33 1 41 1 05 4 7TP45 4 72 0 42 2 17 4 11TP37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20TWork=2 3 3 (2) P2: Request(0,3,4)n因因 Available =2 3 3 Request(0,3,4) 所以不能分配所以不能分配 (3) P4：Request(2,0,1)Available =2 3 3AllocationNeedAvailableP12 1 23 4 70 3 2P24

26、 0 21 3 4P34 0 50 0 6P44 0 50 2 0P53 1 41 1 0 有平安序列有平安序列P4 P5 P3 P2 P1 可以分配可以分配WorkAllocationNeedW+AFinishP40 3 24 0 50 2 04 3 7TP54 3 73 1 41 1 07 4 11TP37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20T (4) P1：Request(0,2,0)AllocationNeedAvailableP12 3 23 2 70 1 2P24 0

27、 21 3 4P34 0 50 0 6P44 0 50 2 0P53 1 41 1 00 1 2 已不能满足任何进程的需求，不能分配已不能满足任何进程的需求，不能分配 死锁的检测和解除死锁的检测和解除死锁检测：死锁检测：允许死锁发生，操作系统不断监视系统进展情况，允许死锁发生，操作系统不断监视系统进展情况，判别死锁能否发生判别死锁能否发生一旦死锁发生那么采取专门的措施，解除死锁并以一旦死锁发生那么采取专门的措施，解除死锁并以最小的代价恢复操作系统运转最小的代价恢复操作系统运转 检测时机：检测时机： 当进程等待时检测死锁当进程等待时检测死锁 其缺陷是系统的开销大其缺陷是系统的开销大 定时检测定时

28、检测 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁 死锁的解除死锁的解除 重要的是以最小的代价恢复系统的运转。方法如重要的是以最小的代价恢复系统的运转。方法如下：下： 1重新启动重新启动 2吊销进程吊销进程 3剥夺资源剥夺资源 4进程回退进程回退 资源分配图资源分配图n 用有向图描画进程的死锁用有向图描画进程的死锁n 准确、笼统准确、笼统n n 系统由假设干类资源构成，一类资源称为一个系统由假设干类资源构成，一类资源称为一个资源类；每个资源类中包含假设干个同种资源，资源类；每个资源类中包含假设干个同种资源，称为资源实例称为资源实例 二元组二元组G=V，E V：结点集，分为：结点集，

29、分为P，R两部分两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合，其元素为有序二元组：边的集合，其元素为有序二元组 (pi,rj)或或(rj,pi) 表示法表示法资源类资源的不同类型资源类资源的不同类型 用方框表示用方框表示资源实例存在于每个资源中资源实例存在于每个资源中 用方框中的黑圆点圈表示用方框中的黑圆点圈表示进程进程 用圆圈中加进程名表示用圆圈中加进程名表示 分配边：分配边： 资源实例资源实例进程的一条有向边进程的一条有向边恳求边：恳求边： 进程进程资源类的一条有向边资源类的一条有向边 例例 死锁定理死锁定理n假设资源分配图中没有环路，那么系统中没有死假设资源分配图中没

30、有环路，那么系统中没有死锁，假设图中存在环路那么系统中能够存在死锁锁，假设图中存在环路那么系统中能够存在死锁n假设每个资源类中只包含一个资源实例，那么环假设每个资源类中只包含一个资源实例，那么环路是死锁存在的充分必要条件路是死锁存在的充分必要条件 资源分配图化简资源分配图化简1找一个非孤立点进程结点且只需分配边，去掉找一个非孤立点进程结点且只需分配边，去掉分配边，将其变为孤立结点分配边，将其变为孤立结点2再把相应的资源分配给一个等待该资源的进程，再把相应的资源分配给一个等待该资源的进程，即将某进程的恳求边变为分配边即将某进程的恳求边变为分配边3反复以上步骤，假设一切进程成为孤立结点，反复以上步骤，假设一切进程成为孤立结点，称该图是可完全简化的，否那么称该图是不可完称该图是可完全简化的，否那么称该图是不可完全简化的。全简化的。死锁形状的充分条件是：当且仅当资源分配图是不死锁形状的充分条件是：当且仅当资源分配图是不可完全简化的。可完全简化的。 有环有死锁有环有死锁 有环无死锁有环无死锁 有平安系列如下有平安系列如下WorkAllocationNeedW+AFinishP12 2 03 0 20 2 05 2 2TP35 2 22 1 10 1 17 3 3TP47 3 30 0 24 3 17 3 5TP07 3 50 2