操作系统课件5_2

1、第五章第五章 死锁与饥饿死锁与饥饿l5.1 死锁的概念死锁的概念 5.2 死锁的类型死锁的类型l5.3 死锁的条件死锁的条件 5.4 死锁的处理死锁的处理l5.5 资源分配图资源分配图 5.6 死锁的预防死锁的预防l5.7 死锁的避免死锁的避免 5.8 死锁的发现死锁的发现l5.9 死锁的恢复死锁的恢复 5.10 鸵鸟的算法鸵鸟的算法l5.11 有关问题的讨论有关问题的讨论l5.12 饥饿与活锁饥饿与活锁 5.13 死锁与饥饿的例死锁与饥饿的例子子15.7 死锁避免死锁避免l预防死锁的方法施加一些较强的限制条件预防死锁的方法施加一些较强的限制条件使之在系统中不出现死锁使之在系统中不出现死锁l为

2、提高系统资源的利用率，万一死锁有可为提高系统资源的利用率，万一死锁有可能出现时，应避免发生，著名的算法为银能出现时，应避免发生，著名的算法为银行家算法行家算法l避免死锁的方法，施加的条件较弱，有可避免死锁的方法，施加的条件较弱，有可能获得较满意的系统性能能获得较满意的系统性能l该方法把系统分为安全和不安全状态该方法把系统分为安全和不安全状态l只要系统始终处于安全状态便可避免死锁的只要系统始终处于安全状态便可避免死锁的发生发生25.7 死锁避免死锁避免l5.7.1 安全状态与安全进程序列安全状态与安全进程序列 l5.7.2 银行家算法银行家算法(bankers Algorithm)35.7.1

3、安全状态与安全进程序列安全状态与安全进程序列l安全状态安全状态l系统处于安全状态是指系统中的所有进程能够按照某系统处于安全状态是指系统中的所有进程能够按照某一种次序依次地进行完一种次序依次地进行完l安全状态形式化定义安全状态形式化定义 ：l如果存在一个由系统中所有进程构成的安全进程序列如果存在一个由系统中所有进程构成的安全进程序列，则称系统处于安全状态。，则称系统处于安全状态。l进程序列进程序列 是安全的是安全的, 则对每个进则对每个进程程pi(1in), 它尚需要的资源数不超过系统当前它尚需要的资源数不超过系统当前剩余资源数与所有进程剩余资源数与所有进程pj(ji)当前占有资源数之当前占有资

4、源数之和和. l若系统中不存在这样一个安全序列，则称系统处若系统中不存在这样一个安全序列，则称系统处于于不安全状态不安全状态。45.7.1 安全状态与安全进程序列安全状态与安全进程序列l图图5-4给出了安全状态、不安全状态、死锁给出了安全状态、不安全状态、死锁状态之间的关系：状态之间的关系：5安全状态之例安全状态之例 l设系统有三个进程设系统有三个进程P1、P2、P3，共有，共有12台磁带机。在台磁带机。在T0时刻资源状况如下表：时刻资源状况如下表：l经分析，在经分析，在T0时刻系统是安全的，存在一时刻系统是安全的，存在一个序列个序列，按此顺序每个进程可，按此顺序每个进程可以顺利完成以顺利完成

5、 6由安全状态向不安全状态的转换由安全状态向不安全状态的转换 l如不按照安全序列分配资源，系统可能会由安全状态向不如不按照安全序列分配资源，系统可能会由安全状态向不安全状态转换，如在安全状态转换，如在T0时刻后，时刻后，P3请求请求1台，系统分配给台，系统分配给P3，则系统进入不安全状态，则系统进入不安全状态进程进程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3 7银行家算法思想银行家算法思想 l将一定数量的资金供多个用户周转使用将一定数量的资金供多个用户周转使用l当用户对资金的最大申请量不超过现存资当用户对资金的最大申请量不超过现存资金时可接纳一个

6、新客户金时可接纳一个新客户l客户可以分期借款，但借款总数不能超过客户可以分期借款，但借款总数不能超过最大的申请量。最大的申请量。l银行家对客户的借款可推迟支付，但是能银行家对客户的借款可推迟支付，但是能够使客户在有限的时间内得到借款够使客户在有限的时间内得到借款l客户得到所有的借款后能在有限的时间内客户得到所有的借款后能在有限的时间内归还归还 8银行家算法思想银行家算法思想l有三个客户有三个客户A、B、C, 共享共享10个现金单元（设一个现金单元（设一个现金单元为一万元），它们共需个现金单元为一万元），它们共需20个现金单个现金单元元l括号外为已借款数，括号内为要求数括号外为已借款数，括号内为

7、要求数 9银行家算法思想银行家算法思想l优点：优点：l保证至少有一个进程得到所需的全部资源下进行资源保证至少有一个进程得到所需的全部资源下进行资源分配，避免进程共享资源时可能产生的死锁分配，避免进程共享资源时可能产生的死锁l允许资源独占、不剥夺条件、请求和保持条件存在，允许资源独占、不剥夺条件、请求和保持条件存在，比预防死锁的限制条件放松了，资源利用率提高。比预防死锁的限制条件放松了，资源利用率提高。l系统可满足、也可拒绝进程提出的资源请求系统可满足、也可拒绝进程提出的资源请求l当一个进程的资源请求将导致不安全状态时，系统拒当一个进程的资源请求将导致不安全状态时，系统拒绝其要求，直到该资源要求

8、不会导致不安全状态时才绝其要求，直到该资源要求不会导致不安全状态时才满足此进程的资源要求（这主要由于其它进程释放了满足此进程的资源要求（这主要由于其它进程释放了资源）资源）l这样的系统总是处于安全状态。这样的系统总是处于安全状态。10银行家算法思想银行家算法思想l缺点：缺点：l要求被分配的每类资源的总数固定不变，难要求被分配的每类资源的总数固定不变，难以做到。以做到。l要求用户数保持不变，在多道程序设计中难要求用户数保持不变，在多道程序设计中难以做到以做到l保证所有用户的要求在有限的时间内得到满保证所有用户的要求在有限的时间内得到满足，但是实时用户要求更好的响应足，但是实时用户要求更好的响应l

9、要求用户说明最大资源要求，对用户来说不要求用户说明最大资源要求，对用户来说不方便且困难方便且困难11银行家算法银行家算法Bankers algorithm, E.W. Dijkstra.进程：事先申明所需资源最大量（并不分配）进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性系统：对每个可满足的资源申请命令进行安全性检查。检查。 12银行家算法银行家算法l设设n为进程总数为进程总数, m为资源类总数为资源类总数l数据结构数据结构:lint Availablem; 当前各类资源中可用资源实当前各类资源中可用资源实例的个数例的个数lAvailablej=k, 资源类

10、资源类rj当前有当前有k个资源实例可用，个资源实例可用，初始时初始时Available为系统资源总量为系统资源总量l int Claimn,m; 每个进程所需各类资源的资每个进程所需各类资源的资源实例最大量源实例最大量lint Allocationn,m; 记录每个进程占有各资记录每个进程占有各资源类中资源实例个数源类中资源实例个数l初始时初始时Allocationi,j= 013银行家算法银行家算法l数据结构数据结构:lint Needn,m; 记录每个进程尚需各资源类中记录每个进程尚需各资源类中资源实例个数资源实例个数lNeedi, j=k, 进程进程pi尚需资源类尚需资源类rj中中k个资

11、源实例个资源实例 l 初始时初始时Need=Claiml int Requestn,m; 记录每个进程当前申请各记录每个进程当前申请各资源类中资源实例个数资源类中资源实例个数lRequesti,j= k, 进程进程pi申请资源类申请资源类rj中中k个资源个资源实例实例14银行家算法银行家算法为了方便为了方便, 引入下述记法引入下述记法: 设设X,Y为下标为下标1到到L的一维数组的一维数组,C为常量为常量 定义定义 XY 当且仅当当且仅当 j，1jL, XjYj X=Y 当且仅当当且仅当 j，1jL, Xj = Yj X=C 当且仅当当且仅当 j，1jL, Xj = C15资源分配算法资源分配算

12、法Pi请求资源请求资源RequestI NeedI请求超量，错返请求超量，错返RequestI Available不满足，等待不满足，等待Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安全安全确认，确认，pi继续继续Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待等待FTFTTF16安全性检测算法安全性检测算法l为进行安全性检查为进行安全性检查, 需定

13、义数据结构需定义数据结构lint Workm; 记录可用资源记录可用资源lint Finishn; 记录进程是否可进行完记录进程是否可进行完17安全性检测算法安全性检测算法FWork:=AvailableFinish:=false有满足条件的有满足条件的jFinishj=falseNeedj WorkFinishj=trueWork:=Work+AllocationjT j ,finishj=trueTF安全安全不安全不安全18银行家算法例子银行家算法例子5-4R=A(10),B(5),C(7) P=p0,p1,p2,p3,p4 某时刻状态某时刻状态19银行家算法例子银行家算法例子5-4l存在

14、安全序列存在安全序列，处于安全状态，处于安全状态 20银行家算法例子银行家算法例子5-4l设设p1发出新申请发出新申请, Request1=(1,0,2)l检查检查Request1Available是否满足是否满足, 由于由于(1,0,2)(3,3,2), 假定分配资源假定分配资源, 系统状态变化为系统状态变化为 21银行家算法例子银行家算法例子5-4l可找到一个进程安全序列可找到一个进程安全序列, 系统实施资源分配系统实施资源分配l在新状态下在新状态下lp4发出发出Request4=(3,3,0)，不能实施资源分，不能实施资源分配配, 因为它超过了系统当前的资源数量因为它超过了系统当前的资源

15、数量lp0发出发出Request0=(0,2,0)，亦不能实施资源，亦不能实施资源分配分配l虽然未超过系统当前的资源数量虽然未超过系统当前的资源数量, 但资源分配将导但资源分配将导制一个不安全的状态制一个不安全的状态22银行家算法的保守性例银行家算法的保守性例5-5l考虑考虑R=A(1),B(1)，P=p1,p2l进程进程p1和和p2的活动序列分别为：的活动序列分别为：lp1：a, b, a, blp2：b, b, b, a, b, alp1和和p2的资源最大需求量均为的资源最大需求量均为A(1)，B(1) 假定假定某时刻系统状态如下：某时刻系统状态如下： 23银行家算法的保守性例银行家算法的

16、保守性例5-5l此时此时p1的的a被接受被接受l其后可能：其后可能：p1请求请求b, 或或p2请求请求bl假定假定p2请求请求b, 因因Request2=(0,1)Need2=(1,1)，该，该请求是合法的请求是合法的l又又Request2=(0,1)Available=(0,1)，该请求系统能够，该请求系统能够满足满足24银行家算法的保守性例银行家算法的保守性例5-5l假定分配系统状态变化如下假定分配系统状态变化如下 l运行安全性检测算法发现系统处于不安全状态，运行安全性检测算法发现系统处于不安全状态，取消分配，取消分配，p2等待等待25银行家算法的保守性例银行家算法的保守性例5-5lp1：

17、a, b, a, blp2：b, b, b, a, b, al实际上真正实施分配系统并不进入死锁状态，因实际上真正实施分配系统并不进入死锁状态，因为为分配后按照分配后按照lp2(b),p1(b),p1(a),p1(b)p2 (b),p2(a),p2(b),p2(a)的次序两个的次序两个进程可以执行完进程可以执行完l这是一个这是一个p1和和p2交叉执行的次序，不是一个顺序执行的次序交叉执行的次序，不是一个顺序执行的次序l银行家算法不能判断银行家算法不能判断l该例验证了前面的论断：该例验证了前面的论断：死锁状态是不安全状态死锁状态是不安全状态的真子集的真子集265.8 死锁的检测死锁的检测数据结构

18、：数据结构： Available: array1.mof integer; Allocation: array1.n,1.mof integer; Request: array1.n,1.mof integer;临时变量：临时变量： Work: array1.mof integer; Finish: array1.nof boolean;275.8.1 死锁检测算法死锁检测算法Work:=Available;Finish:=false;有满足条件的有满足条件的i:Finishi=falseRequesti WorkFinishi=true;Work:=Work+AllocationiT i ,

19、finishi=trueTFF无死锁无死锁死锁死锁FinishI=truefor allocationI=028Remarks1. 上述算法可以检测到参与死锁的全部进程，包括占有资上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。源和不占有资源的进程。如果存在如果存在i，1=i=n，finishi=false，则系统处于死锁，则系统处于死锁状态，且状态，且pi参与了死锁。参与了死锁。对当前不占有资源的进程直接将对当前不占有资源的进程直接将finish置为置为true2. 定理定理5-2：令令p是系统中所有的进程集合，是系统中所有的进程集合，p是是p的子集的子集且为系统中占

20、有资源的进程集合，则且为系统中占有资源的进程集合，则p中存在死锁的充中存在死锁的充要条件是要条件是p中存在死锁。中存在死锁。29死锁例子死锁例子例子：例子：R=A(7),B(2),C(6); P=p0,p1,p2,p3,p4 Allocation Request Available Work Finish A B C A B C A B C A B C p0: 0 1 0 0 0 0 0 0 0p1: 2 0 0 2 0 2 p2: 3 0 3 0 0 0p3: 2 1 1 1 0 0p4: 0 0 2 0 0 2 未死锁。未死锁。此时，此时，Request2=(0,0,1), 死锁，参与死锁

21、进程死锁，参与死锁进程p1,p2,p3,p4305.8.2 死锁检测时刻死锁检测时刻l何时进行死锁检测主要取决于两个因素何时进行死锁检测主要取决于两个因素l死锁发生的频率；死锁发生的频率； l死锁所涉及的进程个数死锁所涉及的进程个数l通常在如下时刻进行死锁检测通常在如下时刻进行死锁检测l 进程等待时检测进程等待时检测 l 定时检测定时检测 l 资源利用率降低时检测资源利用率降低时检测315.9 死锁的恢复死锁的恢复l重新启动重新启动(system restart) l简单，代价大，涉及未参与死锁的进程简单，代价大，涉及未参与死锁的进程l终止进程终止进程(terminating processe

22、s)l终止参与死锁的进程并收回所占资源终止参与死锁的进程并收回所占资源, 死锁得以解除死锁得以解除l两种处理策略两种处理策略: l一次性撤销所有参与死锁的全部进程一次性撤销所有参与死锁的全部进程, 方法简单方法简单, 代价较高代价较高l逐一撤销参与死锁的进程逐一撤销参与死锁的进程l按照某种算法选择一个参与死锁的进程按照某种算法选择一个参与死锁的进程l将其撤销并收回其占有的全部资源将其撤销并收回其占有的全部资源l判断是否还存在死锁判断是否还存在死锁, 如果是选择下一个将被淘汰的进程如果是选择下一个将被淘汰的进程l重复直至死锁解除重复直至死锁解除325.9 死锁的恢复死锁的恢复l剥夺资源剥夺资源(

23、preempting resources)l剥夺死锁进程所占有的全部或部分资源剥夺死锁进程所占有的全部或部分资源l实现时分为两种情形实现时分为两种情形:l逐步剥夺逐步剥夺: 一次剥夺死锁进程所占有的一个或一组一次剥夺死锁进程所占有的一个或一组资源资源, 如死锁尚未解除继续剥夺如死锁尚未解除继续剥夺, 直至死锁解除直至死锁解除l一次剥夺一次剥夺: 一次性地剥夺参与死锁进程所占有的全一次性地剥夺参与死锁进程所占有的全部资源部资源l进程回退进程回退(process rollback)l让参与死锁的进程回退到以前没有发生死锁让参与死锁的进程回退到以前没有发生死锁的某个点处的某个点处, 并由此点开始继续

24、并由此点开始继续, 希望进程交希望进程交叉执行时不再发生死锁叉执行时不再发生死锁335.10 鸵鸟算法鸵鸟算法(ostrich algorithm)l仿鸵鸟遇到危险时将头埋在沙子里的传说仿鸵鸟遇到危险时将头埋在沙子里的传说而得名而得名l对死锁采取视而不见的处理方法对死锁采取视而不见的处理方法l是目前实际系统采用最多的策略是目前实际系统采用最多的策略l当死锁真正发生且影响系统正常运行时，手当死锁真正发生且影响系统正常运行时，手工干预工干预重新启动重新启动 345.10 鸵鸟算法鸵鸟算法l视而不见视而不见l工程师观点工程师观点(考虑死锁发生的频率考虑死锁发生的频率,危害危害,处理处理代价代价)l死

25、锁发生频率死锁发生频率 危害危害l数学家观点数学家观点l必须处理，无论代价如何必须处理，无论代价如何355.11 有关问题的讨论有关问题的讨论l关于充要性算法关于充要性算法l是一个复杂的问题是一个复杂的问题, 不存在完美的死锁处理方不存在完美的死锁处理方法法l关于两阶段封锁关于两阶段封锁l在数据库管理系统中，一个原子事务可能涉在数据库管理系统中，一个原子事务可能涉及多个数据项及多个数据项l为保证数据完整性，在访问数据项之前需要为保证数据完整性，在访问数据项之前需要对其加锁对其加锁(共享锁或排它锁共享锁或排它锁)l当多个事务同时运行时，加锁冲突可能会导当多个事务同时运行时，加锁冲突可能会导致死锁

26、致死锁365.11 有关问题的讨论有关问题的讨论l关于可剥夺资源问题关于可剥夺资源问题l进程不会因为处理机而死锁进程不会因为处理机而死锁l当内存和虚存均不能满足时会发生死锁，如当内存和虚存均不能满足时会发生死锁，如果有足够大的虚存，则不会死锁果有足够大的虚存，则不会死锁375.11 有关问题的讨论有关问题的讨论l关于消耗型资源问题关于消耗型资源问题l前面有关死锁的讨论基本针对可重用资源前面有关死锁的讨论基本针对可重用资源(reusable resource)l这类资源一次只能分给一个进程，使用完后这类资源一次只能分给一个进程，使用完后资源仍存在，可分配给其它进程使用，这是资源仍存在，可分配给其

27、它进程使用，这是操作系统管理的主要资源操作系统管理的主要资源l另一类资源称为消耗型资源另一类资源称为消耗型资源(consumable resource)，亦称生灭资源，指在系统运行过，亦称生灭资源，指在系统运行过程中动态产生、动态消亡的资源程中动态产生、动态消亡的资源l对消耗型资源死锁的处理比较困难对消耗型资源死锁的处理比较困难385.12 饥饿与饿死饥饿与饿死l当等待时间给进程推进和响应带来明显影当等待时间给进程推进和响应带来明显影响时，称发生了响时，称发生了进程饥饿进程饥饿(starvation)，当，当饥饿到一定程度的进程所赋予的任务即使饥饿到一定程度的进程所赋予的任务即使完成也不再具有

28、实际意义时称该完成也不再具有实际意义时称该进程被饿进程被饿死死(starve to death). l 活锁活锁(live lock)：l 在忙式等待条件下发生的饥饿，称为在忙式等待条件下发生的饥饿，称为活锁活锁395.12 饥饿与饿死饥饿与饿死l饥饿：没有时间上界的等待，如：饥饿：没有时间上界的等待，如：l排队等待排队等待l忙式等待忙式等待l饿死：等待时间超过极限饿死：等待时间超过极限(deadline)l饿死饿死 vs 死锁死锁l死锁进程处于等待状态，饿死不然死锁进程处于等待状态，饿死不然l死锁可以检测，饿死不然死锁可以检测，饿死不然l饥饿和饿死与资源分配策略饥饿和饿死与资源分配策略(po

29、licy)有关有关l防止饥饿与饿死从公平性考虑，确保所有进程不被忽防止饥饿与饿死从公平性考虑，确保所有进程不被忽视，如视，如FCFS分配算法分配算法405.12 饥饿与饿死饥饿与饿死l饿死与死锁有一定联系：都是竞争资源而饿死与死锁有一定联系：都是竞争资源而引起，有明显差别，主要表现在：引起，有明显差别，主要表现在：l从进程状态考虑，死锁进程都处于等待状态从进程状态考虑，死锁进程都处于等待状态l死锁进程等待永远不会被释放的资源，饿死死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资进程等待会被释放但却不会分配给自己的资源源l死锁一定发生循环等待，饿死则不然，通过死锁一定

30、发生循环等待，饿死则不然，通过资源分配图可检测死锁，不能检测饿死资源分配图可检测死锁，不能检测饿死l死锁一定涉及多个进程，饥饿或被饿死的进死锁一定涉及多个进程，饥饿或被饿死的进程可能只有一个程可能只有一个415.13 可复用资源死锁的静态分析可复用资源死锁的静态分析l定义定义5-7 一次只能分配给一个进程使用的资源称为可复用一次只能分配给一个进程使用的资源称为可复用资源资源l如打印机、磁带机，释放后可分配给其它进程如打印机、磁带机，释放后可分配给其它进程l定义定义5-8 由相对独立的若干资源构成的资源集合称为组合由相对独立的若干资源构成的资源集合称为组合资源，其中每个相对独立的资源成为子资源资

31、源，其中每个相对独立的资源成为子资源l如：如：lp(2)，tape(3)，mouse(1)构成的资源集合构成的资源集合lp(2)，tape(3)，mouse(1)llp(2)，tape(3)，mouse(1)为子资源为子资源l定义定义5-9 由相同类型的子资源构成的组合资源，称为同种由相同类型的子资源构成的组合资源，称为同种组合资源组合资源42可复用资源死锁的静态分析算法可复用资源死锁的静态分析算法(子资源仅含一个实例子资源仅含一个实例)条件：已知各个进程有关资源的活动序列；条件：已知各个进程有关资源的活动序列；判断：有无死锁可能性。判断：有无死锁可能性。步骤步骤1：以每个进程占有资源，申请资

32、源作为一个状态，：以每个进程占有资源，申请资源作为一个状态， 记作：记作：(pi：aj：ak1,akn)=(进程进程：请求：占有：请求：占有);步骤步骤2：以每个状态为一个节点；：以每个状态为一个节点；步骤步骤3：如：如s1所申请资源为所申请资源为s2所占有，则由所占有，则由s1向向s2画一有向画一有向 弧（相同进程间不画，因为一个进程不会等待自己弧（相同进程间不画，因为一个进程不会等待自己 占有的资源）；占有的资源）；步骤步骤4：找出所有环路；：找出所有环路；可复用资源死锁的静态分析算法可复用资源死锁的静态分析算法(子资源仅含一个实例子资源仅含一个实例)44步骤步骤5：判断环路上状态是否能同

33、时到达，如是有死锁可能：判断环路上状态是否能同时到达，如是有死锁可能 性，否则无死锁可能性。性，否则无死锁可能性。 (1)环路中有相同进程，不能到达环路中有相同进程，不能到达(一个进程不可以一个进程不可以 处于两种状态处于两种状态)； (2)环路中有相同被占有资源，不能到达环路中有相同被占有资源，不能到达(一个简单一个简单 资源不可以分配给两个进程资源不可以分配给两个进程)。 如果发现环路，且环路无相同的进程，也没有相同的如果发现环路，且环路无相同的进程，也没有相同的进程，不能判断是否发生死锁，需要进一步分析进程，不能判断是否发生死锁，需要进一步分析死锁分析例子死锁分析例子(p1:d:c)(p

34、1:a:d)(p1:b:da)(p2:e:d)(p2:b:e)(p2:f:eb)(p3:e:c)(p3:f:c)(p3:a:cf)R=A，B，C，D，E，F，Gp1：c d c a b d a bp2：d e d b f e b f p3：c e c f a c f a死锁分析例子死锁分析例子(p1:d:c)(p1:a:d)(p1:b:da)(p2:e:d)(p2:b:e)(p2:f:eb)(p3:e:c)(p3:f:c)(p3:a:cf)R=A，B，C，D，E，F，Gp1：c d c a b d a bp2：d e d b f e b f p3：c e c f a c f a步骤步骤3：如：

35、如s1所申请资所申请资源为源为s2所占有，则由所占有，则由s1向向s2画一有向弧画一有向弧死锁分析例子死锁分析例子p1：c d c a b d a bp2：d e d b f e b f p3：c e e f a e f a12证明：线证明：线1不可达；不可达；反证：假定线反证：假定线1可达，则线可达，则线2可达。可达。 p2先于先于p1; p3先于先于p2; p1先于先于p3, 矛盾。矛盾。p1:p2:pn:a5.14 同种组合资源死锁的必要条件同种组合资源死锁的必要条件M：资源数量：资源数量 N：使用该类资源进程的数量：使用该类资源进程的数量 ：所有进程所需要该类资源的总量：所有进程所需要

36、该类资源的总量假定死锁，假定死锁，n个进程参与了死锁个进程参与了死锁(2 n N)参与死锁的进程所需资源的总量参与死锁的进程所需资源的总量 M+n未参与死锁进程所需资源的总量未参与死锁进程所需资源的总量 N-n所有进程所需资源的总量所有进程所需资源的总量M+n+N-n=M+N当当 M+N时，一定没有死锁；时，一定没有死锁；当当M+N时，至少有一个交叉有死锁。时，至少有一个交叉有死锁。例子例子例例1. M=15； N=4；P1(4); P2(6); P3(1); P4(7) =4+6+1+7=18M+N=19 无死锁可能性。无死锁可能性。例例2. M=15; N=4；P1(5); P2(6); P3(1); P4(7) =5+6+1+7=19 M+N=19 有死锁可能性。有死锁可能性。死锁情况：死锁情况： P1：a a a a a P2：a a a a a a P3：a P4：a a a a