操作系统原理第六章

1、1/19第第6章章 并发性并发性:死锁死锁6.1 6.1 死锁的概念死锁的概念 6.2 6.2 产生死锁的条件和处理产生死锁的条件和处理 6.3 6.3 死锁的预防死锁的预防 6.4 6.4 死锁的避免死锁的避免6.5 6.5 死锁的检测与解除死锁的检测与解除 6.6 6.6 死锁的综合处理策略死锁的综合处理策略2/196.1 6.1 死锁的概念死锁的概念死锁死锁: : 指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远组进程中另一进程所占有的资源

2、，因而永远无法得到的资源，这种现象无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。3/196.1 6.1 死锁的概念死锁的概念死锁例子：有一台打印机R1和一台卡片阅读机R2，进程P1占用打印机R1，进程P2占用卡片阅读机R2。如果Pl要求阅读机，P2要求打印机，则P1，P2便处于死锁状态。 4/196.1 6.1 死锁的概念死锁的概念产生死锁的原因：n1竞争系统资源竞争系统资源 ：如上例所示：如上例所示n2进程的推进顺序不当进程的推进顺序不当 5/192进程的推进顺序不当进程的推进顺序不当在进程在进程P1P1和和P2P2并发执行时，按照左图曲线并发执行时，按照左图曲线所示顺序推

3、进时，两进程会顺利完成，所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线的我们称这种推进顺序是合法的。若按曲线的顺序推进时，进入不安全区顺序推进时，进入不安全区D D内，两进程再推进内，两进程再推进会产生死锁。会产生死锁。6/196.2 6.2 产生死锁的条件和处理产生死锁的条件和处理互斥条件互斥条件（资源独占）请求和保持条件请求和保持条件（部分分配，占有申请）非非剥夺条件剥夺条件（不可强占）循环循环等待条件等待条件6.2.1 6.2.1 必要条件必要条件 7/191) 互斥使用（资源独占）互斥使用（资源独占）一个资源每次只能给一个进程使用2) 不可强占（不可剥夺）不可强

4、占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放6.2.1 6.2.1 必要条件必要条件 6.2 6.2 产产生死锁的条件和处理生死锁的条件和处理8/19 3) 请求和保持请求和保持（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）6.2.1 6.2.1 必要条件必要条件 6.2 6.2 产产生死锁的条件和处理生死锁的条件和处理9/19 4) 循环等待循环等待 存在一个进程等待队列 P1 , P2 , , Pn, 其中P1等待P2占有的资源，P2等待P3占有的资源，Pn等待P1占有的资源，形成一个进程等

5、待环路6.2.1 6.2.1 必要条件必要条件 6.2 6.2 产产生死锁的条件和处理生死锁的条件和处理10/196.2 6.2 产生死锁的条件和处理产生死锁的条件和处理6.2.2 6.2.2 处理死锁的基本方法处理死锁的基本方法 不让死锁发生n预防死锁预防死锁（静态策略）n避免死锁避免死锁（动态策略）让死锁发生n检测死锁检测死锁n解除死锁解除死锁11/196.3 6.3 死锁的预防死锁的预防通过破坏死锁的四个必要条件中的一个或多个以确保系统绝不会产生死锁。n1互斥条件互斥条件 ：无法破环n2破坏请求和保持条件破坏请求和保持条件 ：采用预先分配的策略，详见6.3.1 。n3破坏循环等待条件破坏

6、循环等待条件：采用有序分配的策略，详见6.3.2。 12/196.3 6.3 死锁的预防死锁的预防n4破坏非剥夺条件破坏非剥夺条件 ：可以收回已分给进程且尚未使用完毕的资源。2个方案：方案方案1 1：进程在申请新的资源不能得到满足，必须释放已占有的全部资源，进入等待队列。13/196.3 6.3 死锁的预防死锁的预防方案方案2 2：进程在请求资源得不到满足，则检查这些资源是否分给了某个进程，如果此进程正在等待更多资源，则剥夺等待进程的这些资源以满足请求进程的需要；否则请求进程等待。在等待过程中，它的某些资源也有可能被剥夺。 适用资源：适用资源：状态容易保存和恢复的，例如CPU寄存器、存储器空间

7、等。14/196.3 6.3 死锁的预防死锁的预防方法有两种：方法有两种：n一种是要求每个进程在运行之前便申请它所需的全部资源n另一种是，规定每个进程在请求新的资源之前必须释放其已占用的全部资源。6.3.1 6.3.1 预先分配策略预先分配策略 15/196.3 6.3 死锁的预防死锁的预防缺点：缺点：n一是资源利用率较低；n二是有可能产生“饥饿”现象，即如果一个进程需要几种竞争较激烈的资源，而总不能完全得到满足的话，则该进程将无限期地等待。所以，这种方法在实际中用得较少。所以，这种方法在实际中用得较少。6.3.1 6.3.1 预先分配策略预先分配策略 16/196.3 6.3 死锁的预防死锁

8、的预防把系统中所有资源编号，进程在申请资源时必须按资源编号的递增次序进行，否则操作系统不予分配6.3.2 6.3.2 有序分配策略有序分配策略 -破坏“循环等待”条件17/196.3 6.3 死锁的预防死锁的预防6.3.2 6.3.2 有序分配策略有序分配策略例如：资源编号1，2，3，10P1：申请申请1申请申请3申请申请9P2：申请申请1申请申请2申请申请5P3 P1018/196.4 6.4 死锁的避免死锁的避免定义定义:系统运行过程中， 允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程

9、等待。 最具有代表性的避免死锁算法是银行家算法。19/196.4.1 6.4.1 系统安全状态系统安全状态 安全状态：安全状态：如果系统能按某种顺序（如如P4，P1，,Pn, 称为安全序列称为安全序列）为每个进程分配其所需的资源，直至每个进程都能顺利地完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。 安全状态一定是没有死锁发生的。20/196.4.1 6.4.1 系统安全状态系统安全状态 安全状态之例安全状态之例： 有三个进程p1,p2,p3，有12台磁带机。P1共要求10台，P2共要求4台，P3共要求9台。在T0时刻，p1,p2,p3分别获得5、2、2台，尚有3台空闲

10、。进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223 经分析，在经分析，在T0时刻，系统是安全的。因为时刻，系统是安全的。因为存在一个安全序列存在一个安全序列p2、p1、p3。21/196.4.1 6.4.1 系统安全状态系统安全状态 由安全状态向不安全状态的转换由安全状态向不安全状态的转换：如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。进程最大需求已分配还需可用p110552p2422p3936 因为其余因为其余2 2台分给台分给P2P2，P2P2完成后，只能释完成后，只能释放放4 4台，这既不能满足台，这既不能满足P1P1（5 5台），也不

11、能满足台），也不能满足P3P3（6 6台），将导致死锁。台），将导致死锁。22/196.4.2 6.4.2 银行家算法银行家算法 1.1.银行家算法中的数据结构银行家算法中的数据结构 （1）可利用资源向量可利用资源向量AvailableAvailable。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。如： ABC52323/196.4.2 6.4.2 银行家算法银行家算法 1.1.银行家算法中的数据结构银行家算法中的数据结构 （2）最大需求矩阵）最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。ABCP1562P2331P3425P433224/19

12、6.4.2 6.4.2 银行家算法银行家算法 1.1.银行家算法中的数据结构银行家算法中的数据结构 （3）分配矩阵）分配矩阵Allocation 。n*m矩阵，表示每个进程分配的资源数。ABCP1212P2121P3222P413225/196.4.2 6.4.2 银行家算法银行家算法 1.1.银行家算法中的数据结构银行家算法中的数据结构 （4）需求矩阵）需求矩阵Need 。n*m矩阵，表示每个进程还需要各类资源数。ABCP1352P2211P3223P423226/196.4.2 6.4.2 银行家算法银行家算法 2.2.银行家算法银行家算法 当进程pi提出资源申请时，系统执行下列步骤：（1

13、）若）若RequestiNeedi,转（转（2）；）； 否则错误返回否则错误返回(需要资源数超过最大值)（2）若若RequestiAvailable, 转（转（3）；否则进程等待）；否则进程等待(无足够资源)27/196.4.2 6.4.2 银行家算法银行家算法 2.2.银行家算法银行家算法 （3）系统试试分配资源，则有：Available:=Available- Request i;Allocation i:= Allocation i+ Request i;Need i :=Need i Request i（4）执行安全性算法安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安

14、全的，则恢复原状态，进程等待28/196.4.2 6.4.2 银行家算法银行家算法 3.3.安全性算法安全性算法 为进行安全性检查，定义数据结构：Work:ARRAY1.m of integer;Finish:ARRAY1.n of Boolean;m代表资源的数量，n代表进程的数量 29/196.4.2 6.4.2 银行家算法银行家算法 3.3.安全性算法安全性算法(1) Work:=Available; Finish:=false;(2) 寻找满足条件的 i ： a.Finishi=false; b.NeediWork;如果不存在，则转(4)30/196.4.2 6.4.2 银行家算法银行

15、家算法 3.3.安全性算法安全性算法(3) Work:=Work+Allocationi; Finishi:=true; 转(2)(4) 若对所有所有i, Finishi=true,则系统处于安全状态，否则处于不安全状态31/194. 4. 银行家算法举例：银行家算法举例： 设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图: 资源情况资源情况进程进程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30

16、 1 00 1 07 4 37 4 33 3 23 3 2P1P13 2 23 2 22 0 02 0 01 2 21 2 2P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1(1) T0时刻可以找到一个安全序列时刻可以找到一个安全序列p1,p3,p4,p2,p0, 系统是安全的系统是安全的32/194. 4. 银行家算法举例：银行家算法举例： (2) P1发出请求发出请求Request(1,0,2)，执行银行家算法，执行银行家算法: 资源情

17、况资源情况进程进程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 1 00 1 07 4 37 4 33 3 23 3 22 3 02 3 0P1P13 2 23 2 22 0 02 0 03 0 23 0 21 2 21 2 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 2

18、4 3 14 3 1可以找到一个安全序列可以找到一个安全序列p1,p3,p4,p0,p2，系统是安全的，可以将可以将P1的请求分配给它。的请求分配给它。33/194. 4. 银行家算法举例：银行家算法举例： () P4发出请求发出请求Request(3,3,0), 执行银行家算法执行银行家算法: 资源情况资源情况进程进程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 1 00 1 07 4 37 4 32 3 02 3 0P1P

19、13 2 23 2 23 0 23 0 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1Available=（2, 3, 0），RequestiAvailable ），所以P4等待。34/194. 4. 银行家算法举例：银行家算法举例： (4) P0请求资源请求资源Request（0，2，0），执行银行），执行银行家算法，家算法，试试分配后分配后: 资源情况资源情况进程进程MaxMaxA B CA B CAllocati

20、onAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 3 00 3 07 2 37 2 32 1 02 1 0P1P13 2 23 2 23 0 23 0 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1Available(2,1,0) 不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配的请求不

21、能分配35/196.5 6.5 死锁的检测与解除死锁的检测与解除 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除死锁解除死锁并以最小的代价恢复操作系统运行36/196.5.1 6.5.1 死锁的检测死锁的检测 1.资源分配图（资源分配图（SRAG） 由二元组G=G=（V V，E E） V V：结点集，分为P(进程)，R(资源)两部分 P=p1,p2,pn,P=p1,p2,pn, R=r1,r2,rm R=r1,r2,rm E E：边的集合，其元素为有序二元组: (pi,rj)(pi,rj)或(rj,pi)(rj,pi) 37/196.5.1 6

22、.5.1 死锁的检测死锁的检测 1.资源分配图（资源分配图（SRAG） 表示法表示法资源类资源类: :用方框表示（资源的不同类型）资源实例资源实例: :用方框中的黑圆点表示（存在于每个资源中） 进程进程 : :用圆圈中加进程名表示分配边：分配边：资源实例进程的一条有向边申请边：申请边：进程资源类的一条有向边 38/196.5.1 6.5.1 死锁的检测死锁的检测 资源分配图示例39/196.5.1 6.5.1 死锁的检测死锁的检测 2. 死锁判定法则死锁判定法则 (1)如果资源分配图(SRAG)中没有环路没有环路，则系统内没有死锁没有死锁。(2)如果SRAG中有环有环路，且每类资源只有资源只有

23、一个一个，则有环有环是系统存在死锁存在死锁的必要充分条件。(3)如果SRAG中有环路有环路，但每类资源的个每类资源的个数不全为数不全为1 1，则可以利用对对SRAGSRAG化简化简的方法，来检测系统是否存在死锁 40/19资源分配图示例资源分配图示例有环无死锁41/19资源分配图示例资源分配图示例 有环有死锁42/196.5.1 6.5.1 死锁的检测死锁的检测资源分配图化简资源分配图化简1）找一个非孤立进程结点且只有分配边，去掉分配边，将其变为孤立结点2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边3）重复以上步骤，若所有进程成为孤立结点，称该图是可完全简化的，否则

24、称该图是不可完全简化的。死锁状态的充分条件是：当且仅当资源分配图是不死锁状态的充分条件是：当且仅当资源分配图是不可完全简化的。可完全简化的。( (死锁定理死锁定理) )43/196.5.1 6.5.1 死锁的检测死锁的检测 资源分配图化简示例：资源分配图化简示例：44/196.5.1 6.5.1 死锁的检测死锁的检测 3.死锁检测算法死锁检测算法 算法的策略是查找一个进程，使得可用资源可以满足该进程的资源请求，然后假设同意这些资源，让进程运行直到完成，再释放它的所有资源，然后算法寻找另一个可以满足资源请求的进程。45/19死锁的检测算法死锁的检测算法 数据结构：数据结构：nAvailable：

25、每类资源的可用数目 nAllocation：进程所分得的资源个数 nRequest ：进程的资源请求 46/19死锁的检测算法死锁的检测算法 算法步骤：算法步骤：1 令Work：=Available。对于i1，2，n，如果Allocationi=0则Finishitrue，否则Finishifalse。2找到一个下标i，使得 Finishifalse，并且 RequestiWork 如果不存在这样的i，则转向步骤转向步骤4；47/19死锁的检测算法死锁的检测算法 3Work：=Work + Allocationi Finishi:=true 转步骤步骤2；4如果对于所有的i=1，2，n，存在一

26、个或以上Finishi:=false, 则系统出现了死锁，死锁进程为该Pi进程。48/19死锁检测算法示例：死锁检测算法示例：假设有资源R1、R2、R3、R4、R5和进程P1、P2、P3、P4的需求矩阵、分配矩阵，可用资源向量如表所示。 1. Allocation4=0, 所以Finish4=ture, Finish1-3=false 资源资源进程进程RequestRequestR1 R2 R3 R4 R5R1 R2 R3 R4 R5AllocationAllocationR1 R2 R3 R4 R5R1 R2 R3 R4 R5AvailableAvailableR1 R2 R3 R4 R5R

27、1 R2 R3 R4 R5P1P10 1 0 0 10 1 0 0 11 0 1 1 01 0 1 1 00 0 0 0 10 0 0 0 1P2P20 0 1 0 10 0 1 0 11 1 0 0 01 1 0 0 0P3P30 0 0 0 10 0 0 0 10 0 0 1 00 0 0 1 0P4P41 0 1 0 11 0 1 0 10 0 0 0 00 0 0 0 049/19死锁检测算法示例：死锁检测算法示例：2. Work=(0 0 0 0 1) 3. Request3 Work，因此Finish3=ture，可用资源Work (0 0 0 0 1) (0 0 0 1 0) （

28、 0 0 0 1 1 ）。 资源资源进程进程RequestRequestR1 R2 R3 R4 R5R1 R2 R3 R4 R5AllocationAllocationR1 R2 R3 R4 R5R1 R2 R3 R4 R5AvailableAvailableR1 R2 R3 R4 R5R1 R2 R3 R4 R5P1P10 1 0 0 10 1 0 0 11 0 1 1 01 0 1 1 00 0 0 0 10 0 0 0 10 0 0 1 10 0 0 1 1P2P20 0 1 0 10 0 1 0 11 1 0 0 01 1 0 0 0P3P30 0 0 0 10 0 0 0 10 0 0 0 00 0 0 0 00 0 0 1 00 0 0 1 00 0 0 0 00 0 0 0 0P4P41 0 1 0 11 0 1 0 10 0 0 0 00 0 0 0 050/19死锁检测