计算机操作系统 第5章 死 锁ppt课件

1、 从进程同步的概念可以知道，当并发进程需求竞争运用资源或需求相互协作向前推进时，假设不采取同步措施，或同步措施不恰当，那么很容易导致并发进程不能向前推进而堕入僵局，即死锁景象。死锁是发生在一组相互竞争或协作的进程与线程之间的一个非正常景象。 死锁是一切操作系统都面临着的潜在问题，操作系统除了需求预防死锁、防止死锁外，还需求可以检测死锁，并从死锁中进展恢复。本章的主要内容如下： 死锁的产生； 死锁的预防； 死锁的防止； 死锁的检测和解除； 线程死锁。5.1 死锁的产生死锁的产生5.1.1 死锁产生的缘由死锁产生的缘由竞争资源引起死锁竞争资源引起死锁 在多道程序系统，多个进程共享系统的资源。系统资

2、在多道程序系统，多个进程共享系统的资源。系统资源分为二类，一类是不可抢占的资源，如打印机、源分为二类，一类是不可抢占的资源，如打印机、磁带机等。当系统把这类资源分配给某进程后，再磁带机等。当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。另一不能强行收回，只能在进程用完后自动释放。另一类是可抢占的资源，如类是可抢占的资源，如CPU、内存等。由于系统拥有、内存等。由于系统拥有的不可抢占的资源有限，多个进程共享竞争不可抢的不可抢占的资源有限，多个进程共享竞争不可抢占的资源就能够引起死锁。占的资源就能够引起死锁。进程推进顺序不当引起死锁进程推进顺序不当引起死锁 在多道程序系统

3、中，并发执行的进程推进序列不可在多道程序系统中，并发执行的进程推进序列不可予测，有些推进顺序，进程可以顺利完成，这些推予测，有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限进顺序是合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，呵期地等待永远不会发生的条件而不能向前推进，呵斥了死锁。斥了死锁。5.1.1 死锁产生的缘由续死锁产生的缘由续 进程推进顺序不当引起死锁例： 进程P和Q并发执行，进程P和Q程序如下： Process P Process Q . . Get A Get B . . Get B Get A . . Releas

4、e A Release B . . Release B Release A . . 5.1.1 死锁产生的缘由续死锁产生的缘由续PAQB当当P、Q按如下次序执行时：按如下次序执行时：P: GET A Q:GET BP:GET BQ:GET AABCS2S1S3哲学家吃面的问题哲学家吃面的问题A:P(S1)P(S3)EatingV(S3)V(S1)B:P(S2)P(S1)EatingV(S1)V(S2)C:P(S3)P(S2)EatingV(S2)V(S3)A: P(S1), B:P(S2),C:P(S3)A:P(S3) :阻塞阻塞B:P(S1):阻塞阻塞C: P(S2):阻塞阻塞AS1CS3S

5、2B5.1.2 死锁产生的条件死锁产生的条件1.1.产生死锁的必要条件产生死锁的必要条件 Conditions for Deadlock Conditions for Deadlock 互斥互斥 Mutual exclusion Mutual exclusion 条件：一个资源一次只能被一个条件：一个资源一次只能被一个进程所运用，即是排它性运用。进程所运用，即是排它性运用。不可抢占不可抢占 No preemption No preemption 条件：一个资源仅能被占有它条件：一个资源仅能被占有它的进程所释放，而不能被别的进程侵占。的进程所释放，而不能被别的进程侵占。恳求和坚持恳求和坚持 Ho

6、ld-and-wait Hold-and-wait 条件：进程曾经坚持了至少条件：进程曾经坚持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时恳求进程阻塞，但又对曾经获得的其它资源进程占有，此时恳求进程阻塞，但又对曾经获得的其它资源坚持不放。坚持不放。环路等待环路等待 Circular wait Circular wait 条件：当每类资源只需一个时，条件：当每类资源只需一个时，在发生死锁时，必然存在一个进程在发生死锁时，必然存在一个进程- -资源的环形链。如一系资源的环形链。如一系统形状的资源分配图所示，统形状的资源

7、分配图所示，P1P1正在等待一个正在等待一个P2 P2 占用的资源占用的资源R2R2，P2P2正在等待一个正在等待一个P1P1占用的资源占用的资源R1R1。 5.1.2 死锁产生的条件(续)2. 资源分配图由结点和边组成。结点有二类，一类是进程结点，用园圈表示；另一类是资源结点，用小方框表示一类资源，用方框中的小圈表示资源数。边也有二类，一类是分配边，它由资源结点指向进程结点，另一类是恳求边，它由进程结点指向资源结点。前往 R1 R1R2 P1P25.1.2 死锁产生的条件死锁产生的条件(续续)3. 3. 处置死锁的根本方法处置死锁的根本方法a. a. 死锁的预防死锁的预防 静态方法：在进程执

8、行前采取的措施，经过设置某些限制条静态方法：在进程执行前采取的措施，经过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。件，去破坏产生死锁的四个必要条件之一，防止发生死锁。B.B.死锁的防止死锁的防止 动态的方法：在进程执行过程中采取的措施，不需事先采动态的方法：在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程恳求资源取限制措施破坏产生死锁的必要条件，而是在进程恳求资源时用某种方法去防止系统进入不平安形状，从而防止发生死时用某种方法去防止系统进入不平安形状，从而防止发生死锁。锁。C.C.死锁的检测和解除死锁的检测和解除 这种方法预先并不采用任

9、何限制措施，允许系统在运转过这种方法预先并不采用任何限制措施，允许系统在运转过程中发生死锁，但可经过系统设置的检测机构及时检测死锁程中发生死锁，但可经过系统设置的检测机构及时检测死锁的发生，如检测到死锁，那么采用吊销进程等死锁解除方法的发生，如检测到死锁，那么采用吊销进程等死锁解除方法使系统正常任务。使系统正常任务。5.2 死死 锁锁 预预 防防(Deadlock Prevention) 预防死锁的方法是破坏四个产生死锁的必要条件之一。1。破坏互斥条件 互斥运用是资源本身特征所决议的。运用硬软件结合可改动资源本身特性，例如采用SPOOLing技术可将“独享 打印机改动为“共享的打印机。2。破坏

10、不可抢占条件 抢占式调度法主要用于处置机和存贮器资源调度，它们的形状容易保管和恢复。但此法对外部设备和私存数据不宜运用。5.2 死死 锁锁 预预 防防(Deadlock Prevention) -13。破坏恳求和坚持条件 系统可采用资源静态予分配方式来破坏恳求坚持条件。系统要求一切进程一次性地恳求在整个运转过程中全部资源，假设系统有足够资源满足给进程，那么在运转前，一次性将其所需求的一切资源分配给该进程。这样该进程在整个运转期间，便不再提出资源要求，从而摒弃了恳求条件。这种预防死锁的方法，优点是简单、易予实现且很平安，但其资源利用率很低，进程也延迟运转。4。破坏循环等待条件 有序资源运用法 该

11、方法将一切的资源按类型进展线性排队，并赋予不同的序号。例如令输入机的序号为1，打印机序号为2，磁盘机序号为3等。5.2 死死 锁锁 预预 防防(Deadlock Prevention) -2 一切进程对资源的恳求必需严厉按资源序号递增的次序提出。这样在所构成的资源分配图中不能够再出现环路，因此摒弃了“环路等待条件，在采用这种战略时总有一个进程占据了较高序号的资源，它继续恳求的资源必然是空闲的，因此进程可以不断向前推进。这种预防死锁的战略可以提高资源利用率，但在进程运用各类资源的顺序与系统规定的顺序不同时会呵斥资源浪费的情况。资源按级分配法 该方法是把资源递增排序成假设干等级如L1、L2.Lm，

12、其中每级可包含几类资源，要求每个进程在获得了Lj级中资源之后 ，它才干恳求更高级的LKLKLj级中的资源；假设它还需恳求比LK级低的LI级LI 4 P2 4 2 2 = 4 由于找不到一个平安序列使一切进程顺序地一个个地运转终了，所以T1形状是不平安形状，由于实施分配给1台磁带机给P3的操作会引起系统形状由平安形状T0向不平安形状下的转换，所以为了防止死锁，上述的分配只是平安检测，检测后断定这样的恳求不能满足，P3为恳求1台磁带机而必需阻塞等待。3.3.利用银行家算法防止死锁利用银行家算法防止死锁 最具代表的防止死锁算法是Dijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而

13、得名。银行家算法的数据构造可用资源向量 Available m m为系统中资源种类数，Availablej=k表示系统中第j类资源数为k个。最大需求矩阵Maxn，m n为系统中进程数，Maxi,j=k表示进程i对j类资源的最大需求数为中k。分配矩阵Allocationn，m 它定义了系统中每一类资源当前已分配给每一进程资源数， Allocationi,j=k表示进程i已分得j类资源的数目为k个。3.3.利用银行家算法防止死锁利用银行家算法防止死锁-1-1需求矩阵Needn,m 它表示每个进程尚需的各类资源数，Needi,j=k 表示进程i还需求j类资源k个。Needi,j=Maxi,j-All

14、ocationi,j银行家算法假设在进程并发执行时进程i提出恳求j类资源k个后，表示为Requestij=k。系统按下述步骤进展平安检查： 假设RequestiNeedi那么继续以下检查，否那么显示需求恳求超出最大需求值的错误。 假设RequestiAvailable那么继续以下检查，否那么显示系统无足够资源，Pi阻塞等待。 系统试探把要求的资源分配给进程i并修正有关数据构造的值： Available = Available-Requesti ； Allocationi =Allocationi+Requesti ； Needi=Needi-Requesti ； 3.利用银行家算法防止死锁-2

15、 系统执行平安性算法，检查此次资源分配后，系统能否处于平安形状，假设平安，才正式将资源分配给进程i，以完本钱次分配；否那么将试探分配作废，恢复原来的资源分配形状，让进程Pi等待。平安性算法平安性算法执行步骤如下：A.初始化设置任务向量Workm表示系统可提供的各类资源数目，用以维护原数据构造有关值。Work = Available，设置完成标志向量 Finishn。Finishi = false 表示i进程尚末完成，如值为true那么表示进程i已完成。B.从进程集合n中找到一个能满足下述二个条件: Finishi = false和NecdiWork，如找到那么执行步骤C，如找不到同时满足以上二

16、条件的进程那么执行步骤D。3.3.利用银行家算法防止死锁利用银行家算法防止死锁-3-3C.当进程i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下： work = work+Allocationi ； Finishi=true ；转执行步骤B。D.假设一切的Finishiture，那么表示系统处于平安形状，否那么系统处于不平安形状。银行家算法例：银行家算法例： 假定系统中有五个进程P0、P1、P2、P3、P4和三种类型资源A、B、C，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时辰资源分配情况如下 所示。 Max Allocation Need Available

17、A B CA B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1试问： T0时辰能否平安？ P1恳求资源Request1(1,0,2)能否允许？ P4恳求资源Request4(3,3,0)能否允许？ 银行家算法例银行家算法例-1-1 T0时辰能否平安？ 从表中可找出一个序列(P1 、 P3、 P4 、 P2 、 P0使各进程顺序地一个个地执行完成。 Max Allocation Need Availa

18、ble Available ( 分 配 资 源 前 ) (释放资源后 A B C A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7 P1 3 2 2 2 0 0 1 2 2 = 3 3 2 5 3 2 P2 9 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7 P3 2 2 2 2 1 1 0 1 1 = 5 3 2 7 4 3 P4 4 3 3 0 0 2 4 3 1 = 7 4 3 7 4 5 平安序列为P1、P3、P4、P2、P0，T0时辰系统是平安的。 P1恳求资源Request1(1,0,2)可否允许

19、？银行家算法例银行家算法例-2-2Request1(1,0,2)Need1(1,2,2)，P1恳求在最大需求范围内。Request1(1,0,2) Available(3,3,2)，可用资源可满足P1恳求需求。试探把要求的资源分配给进程P1并修正有关数据构造的数值：Available = Available(3，3，2)Request1(1,0,2)=Available(2,3,0)；Need1 = Need1(1,2,2)Request1(1,0,2)= Need1(0,2,0)；Allocation1 =Allocation1(2,0,0)+Request1(1,0,2)=Allocati

20、on1(3,0,2)；利用平安性算法检查试探将资源分配后形状的平安性如下：银行家算法例银行家算法例-3-3 Max Allocation Need Available Available (分配资源前) (释放资源后 A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7P1 3 2 2 3 0 2 0 2 0 = 2 3 0 5 3 2P2 9 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7P3 2 2 2 2 1 1 0 1 1 = 5 3 2 7 4 3P4 4 3 3 0 0 2 4 3 1 =

21、7 4 3 7 4 5 由于先分配资源给P1进程符合按平安序列P1、P3、P4、P2、P0分配资源，所以试探将资源分配给进程P1后的形状是平安的，可将资源分配给进程P1。P4恳求资源Request4(3,3,0)能否允许？Request4(3,3,0)Need4(4,3,1)，P4恳求在最大需求范围内。Request4(3,3,0)Available(2,3,0)不成立，即可用资源暂不能满足P4恳求资源需求，P4阻塞等待。 5.4 死锁的检测和解除死锁的检测和解除(Deadlock Detection) 5.4.1 死锁的检测死锁的检测 死锁的防止算法添加了系统的开销，死锁的检测采用资源分死锁

22、的防止算法添加了系统的开销，死锁的检测采用资源分配图的简化判别能否发生了不平安形状。如发现系统处于不配图的简化判别能否发生了不平安形状。如发现系统处于不平安形状时，即执行死锁解除的战略，采用此法开销相对减平安形状时，即执行死锁解除的战略，采用此法开销相对减少。少。1.资源分配图的简化：资源分配图的简化： 系统处于某系统处于某S形状时可用资源分配图表示，可用资源分配图简形状时可用资源分配图表示，可用资源分配图简化来判别系统能否处于死锁形状。资源分配图简化的方法如化来判别系统能否处于死锁形状。资源分配图简化的方法如下：在资源分配图中找一个既不阻塞又非孤立的进程结点下：在资源分配图中找一个既不阻塞又

23、非孤立的进程结点PI如某进程既无已分配的资源也不需恳求资源，即既无分配如某进程既无已分配的资源也不需恳求资源，即既无分配边又无恳求边，那么该进程结点是孤立结点，让它获得所边又无恳求边，那么该进程结点是孤立结点，让它获得所需资源而继续运转直至终了，再释放它拥有的一切的资源，需资源而继续运转直至终了，再释放它拥有的一切的资源，这相当于取消这相当于取消PI的分配边和恳求边，使它成为孤立结点。的分配边和恳求边，使它成为孤立结点。 经过以上简化，如一切的进程结点都是孤立结点那么称资源经过以上简化，如一切的进程结点都是孤立结点那么称资源分配图是可完全简化的。假设不能经过任何过程使该图完全分配图是可完全简化

24、的。假设不能经过任何过程使该图完全简化，那么该图是不可完全简化的。资源分配图简化如以下简化，那么该图是不可完全简化的。资源分配图简化如以下图：图： R1 R2 R1 R2 。P1 资源分配图的简化例：资源分配图的简化例：。 。P1P2。 。 。P1P2。 。P2。R1 R1 R2R25.4.1 死锁的检测死锁的检测-12.2.死锁定理：死锁定理： S S为死锁形状的充分条件是：尚且仅当为死锁形状的充分条件是：尚且仅当S S形状的资源分形状的资源分配图是不可完全简化的，该充分条件称为死锁定理。配图是不可完全简化的，该充分条件称为死锁定理。3. 3. 死锁检测的数据和算法类似于银行家算法。死锁检测

25、的数据和算法类似于银行家算法。5.4.2 死锁解除死锁解除 当检测死锁的软件判别死锁存在时，就要解除死锁，使系统从死锁中恢复。 1利用终了死锁进程释放资源 强迫性地从系统中吊销一个或多个死锁的进程以断开循环等待链，并收回分配给终止进程的全部资源供剩下的进程运用。借助于吊销进程来解除死锁可以运用两种方法。一种是吊销全部的死锁进程，这显然会断开死锁环路，但代价太大。另一种方法是逐个吊销死锁的进程直至死锁环路消除。这里存在一个按照什么原那么进展逐个吊销进程的问题。目前较适用而又简便的方法是吊销那些代价最小的进程。所谓影响一个进程的吊销代价要素有该进程的优先权，该进程运转到今的运转代价包括CPU时间，

26、运用资源的种类和时间等、与相关的作业类型和外部代价等。死锁的解除死锁的解除-12利用资源抢占利用资源抢占死锁恢复的另一种方法是运用一个有效的挂起和解死锁恢复的另一种方法是运用一个有效的挂起和解除机构来挂起一些死锁的进程，其本质是从被挂除机构来挂起一些死锁的进程，其本质是从被挂起的进程那里抢占资源以解除死锁，许多学者以起的进程那里抢占资源以解除死锁，许多学者以为在此领域的研讨任务比起其它死锁恢复的方法为在此领域的研讨任务比起其它死锁恢复的方法更为重要。问题：现场包扩更为重要。问题：现场包扩CPU、内存、外设、内存、外设的形状维护不益处理的形状维护不益处理3利用回退释放资源利用回退释放资源例如一个系统提供了检查点和重新启动的便利的话，例