操作系统第三章2

1、Operating SystemOperating SystemPage 12022-3-17Operating SystemOperating SystemPage 22022-3-17q处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q死锁概述死锁概述q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除Operating SystemOperating SystemPage 32022-3-173q日常生活中的例子日常生活中的例子q进程死锁的例子进程死锁的例子v竞争外部设备竞争外部设备v竞争辅存空间竞

2、争辅存空间q哲学家进餐问题哲学家进餐问题Operating SystemOperating SystemPage 42022-3-17交通死锁的示例让路！让路！ 让路！ 让路！Operating SystemOperating SystemPage 52022-3-17进程进程A A进程进程B B 申请输入设备申请输入设备申请输出设备申请输出设备 申请输出设备申请输出设备申请输入设备申请输入设备 释放输入设备释放输入设备释放输出设备释放输出设备 释放输出设备释放输出设备释放输入设备释放输入设备 如果执行次序为：进程如果执行次序为：进程A A进程进程B B.， 则发生死锁。则发生死锁。输入设备输

3、出设备BA占有占有占有占有等待等待等待等待 A在干什么？ B在干什么？竞争外设死锁示例Operating SystemOperating SystemPage 62022-3-176ABCDELMNOPQFGHIJKAABBCCDDFGHILLMMNNOOFGHISPOOLing系统死锁示例输出井进程B进程C 满啦！ 不够！ 不够！ 不够！进程AOperating SystemOperating SystemPage 72022-3-17q哲学家进餐问题（哲学家进餐问题（The Dinning Philosophers The Dinning Philosophers ProblemProbl

4、em） v5个哲学家坐在桌子边，桌上有5个碗和5支筷子v哲家家的生活方式是交替地进行思考和进餐v哲学家饥饿时便拿起两边的筷子进餐，但只有当拿到两支后才能进餐v用餐毕，放下筷子继续思考若某时刻5个哲学家同时拿起一根筷子，都在等待另一根筷子，则会陷入死锁。Operating SystemOperating SystemPage 82022-3-17q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperating Systemq可重用资源：可重复使用多次，只能互斥使用，且资源数目

5、固定，如输入输入设备、文件q可消耗资源：可动态创建和消耗，资源数目变化。如消息通信中的消息q可抢占性资源：如CPU、内存q不可抢占性资源：一旦分配不能强行收回，只能等进程自行释放。如：打印机、磁带机Page 92022-3-17Operating SystemOperating SystemPage 102022-3-171. 1.死锁的定义死锁的定义 是指多个进程运行过程中因争夺资源(不可抢占性资源)而造成的一种僵局（Deadly-Embrace），当进程处于这种僵持状态时，若无外力作用，它们将无法再向前推进。 参与死锁的进程最少是两个参与死锁的进程最少是两个 参与死锁的所有进程都在等待资源

6、参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。崩溃。Operating SystemOperating SystemPage 112022-3-17q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperating SystemPage 122022-3-173.5.2 产生死锁的原因产生死锁的原因 竞争资

7、源竞争资源 竞争不可抢占式资源(如打印机、文件)、可消耗资源 系统资源的个数系统资源的个数并发进程的申请总数；并发进程的申请总数；(2) 进程间推进顺序非法进程间推进顺序非法/资源分配不当资源分配不当 进程在运行过程中，请求和释放资源的顺序不当，进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。导致了进程死锁。 Operating SystemOperating SystemPage 132022-3-17 若系统中只有一台打印机若系统中只有一台打印机R1R1和一台读卡机和一台读卡机R2R2，供进，供进程程P1P1和和P2P2共享。若资源分配共享。若资源分配形成环路形成环路，会产生死

8、锁。，会产生死锁。R1R2P1P2分配分配分配分配请求请求请求请求Operating SystemOperating SystemPage 142022-3-17q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperating SystemPage 152022-3-17q 互斥条件互斥条件 v进程对所分配到的资源进行进程对所分配到的资源进行排它性的使用排它性的使用q 请求和保持条件请求和保持条件 v进程已经至少进程已经至少保持了一个保持了一个资源，但又提出了新资源，但又提

9、出了新的资源的资源请求请求，而该资源又已被其他进程占有，而该资源又已被其他进程占有q 不剥夺条件不剥夺条件 v进程已获得的资源在未使用完之前不能被剥夺进程已获得的资源在未使用完之前不能被剥夺q 循环等待条件循环等待条件v在发生死锁时，必然存在一个进程在发生死锁时，必然存在一个进程-资源循环资源循环等待的环形链等待的环形链Operating SystemOperating SystemPage 162022-3-17q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperati

10、ng SystemPage 172022-3-173.5.3 处理死锁的基本方法处理死锁的基本方法 目前用于处理死锁的方法可归结为以下四种：目前用于处理死锁的方法可归结为以下四种：1 1、预防死锁、预防死锁 通过设置某些限制条件，去破坏产生死锁的四个通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。必要条件中的一个或几个条件，来防止发生死锁。2 2、避免死锁、避免死锁防止系统进入不安全状态，从而避免发生死锁，防止系统进入不安全状态，从而避免发生死锁，只需在事先加以较弱的限制条件。只需在事先加以较弱的限制条件。Operating SystemOperating

11、 SystemPage 182022-3-173 3、检测死锁、检测死锁 只须检查系统是否已进入不安全区，允许系只须检查系统是否已进入不安全区，允许系统在运行过程中发生死锁。统在运行过程中发生死锁。4 4、 解除死锁解除死锁 常用的实施方法是撤消或挂起一些进程，以常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。塞状态的进程，使之转为就绪状态，以继续运行。Operating SystemOperating SystemPage 192022-3-17q破坏死锁产生的四个必要条件的

12、破坏死锁产生的四个必要条件的一个或几个一个或几个Operating SystemOperating SystemPage 202022-3-17q打破打破“互斥条件互斥条件” 允许进程同时访问某些资源。（但有些允许进程同时访问某些资源。（但有些资源不可以还应该保证互斥访问，如打印资源不可以还应该保证互斥访问，如打印机）机）Operating SystemOperating SystemPage 212022-3-17q 摒弃摒弃“请求和保持请求和保持”条件条件 所有进程在开始运行之前必须所有进程在开始运行之前必须一次性的一次性的申请申请整个运行过程所需的全部资源整个运行过程所需的全部资源v简单

13、、易于实现、安全简单、易于实现、安全v资源浪费严重资源浪费严重v进程延迟运行进程延迟运行Operating SystemOperating SystemPage 222022-3-17q摒弃摒弃“不剥夺不剥夺”条件条件 剥夺那些处于等待状态的进程的资源（申剥夺那些处于等待状态的进程的资源（申请新资源而不能得到满足）请新资源而不能得到满足）v实现复杂、代价高昂实现复杂、代价高昂v延长了进程的周转时间，还增加了系统延长了进程的周转时间，还增加了系统开销，降低了系统的吞吐量开销，降低了系统的吞吐量Operating SystemOperating SystemPage 232022-3-17q摒弃摒

14、弃“循环循环等待等待”条件条件系统将所有资源按类型分配序号并排队系统将所有资源按类型分配序号并排队所有进程所有进程申请申请资源必须资源必须按序号按序号递增的顺序递增的顺序v资源利用率和系统吞吐量较高资源利用率和系统吞吐量较高v但在资源管理和资源申请方面仍有问题但在资源管理和资源申请方面仍有问题Operating SystemOperating SystemPage 242022-3-17序号序号资源资源1输入机输入机2打印机打印机3磁带机磁带机进程进程需求资源需求资源P1打印机打印机磁带机磁带机P2磁带机磁带机打印机打印机存在问题：资源的需求顺序不等于存在问题：资源的需求顺序不等于序号，仍存在

15、资源浪费。序号，仍存在资源浪费。进程的资源需求顺序进程的资源需求顺序资源编号资源编号Operating SystemOperating SystemPage 252022-3-17方法方法资源分配策略资源分配策略各种可能模式各种可能模式 主要优点主要优点主要缺点主要缺点预防预防Prevention保守的；宁可资保守的；宁可资源闲置（从机制源闲置（从机制上使死锁条件不上使死锁条件不成立，即摒弃三成立，即摒弃三个必要条件）个必要条件）一次请求所有一次请求所有资源资源适用于作突发式处理的适用于作突发式处理的进程；不必剥夺进程；不必剥夺效率低；进程初始化效率低；进程初始化时间延长时间延长剥夺次数过多；

16、多次剥夺次数过多；多次对资源重新起动对资源重新起动不便灵活申请新资源不便灵活申请新资源资源剥夺资源剥夺适用于状态可以保存和适用于状态可以保存和恢复的资源恢复的资源资源资源按序申请按序申请避免避免Avoidance是是“预防预防”和和“检测检测”的折衷的折衷（在运行时判断（在运行时判断是否可能死锁）是否可能死锁）寻找可能的安寻找可能的安全的运行顺序全的运行顺序 不必进行剥夺不必进行剥夺使用条件：必须知道使用条件：必须知道将来的资源需求；进将来的资源需求；进程可能会长时间阻塞程可能会长时间阻塞检测检测Detection宽松的；只要允宽松的；只要允许，就分配资源许，就分配资源定期检查死锁定期检查死锁

17、是否已经发生是否已经发生不延长进程初始化时间；不延长进程初始化时间；允许对死锁进行现场处允许对死锁进行现场处理理通过剥夺解除死锁，通过剥夺解除死锁，造成损失造成损失可以在编译时（而不必可以在编译时（而不必在运行时）就进行检查在运行时）就进行检查Operating SystemOperating SystemPage 262022-3-17q 系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Operating SystemOperating SystemPage 272022-3-17q安全状态安全状态v系统在进行系统在进行资源分配之前资源分配之前，先计算此次资源，先计算此

18、次资源分配的安全性。若此次分配不会导致系统进分配的安全性。若此次分配不会导致系统进入入不安全状态不安全状态，则将资源分配给进程；，则将资源分配给进程； 否则，否则，令进程等待。令进程等待。v所谓所谓安全状态安全状态，是指系统能按某种进程执行，是指系统能按某种进程执行顺序顺序(P1, P2, (P1, P2, ，Pn)Pn)顺利地完成顺利地完成，则系统，则系统处于安全状态。处于安全状态。执行序列执行序列P1, P2, P1, P2, , Pn, Pn序列为安全序列序列为安全序列。如果系统无法找到这样一。如果系统无法找到这样一个安全序列，则称系统处于个安全序列，则称系统处于不安全状态。不安全状态。

19、Operating SystemOperating SystemPage 282022-3-17 2. 安全状态之例安全状态之例 假定系统中有三个进程假定系统中有三个进程P P1 1、 P P2 2和和P P3 3，共有，共有1212台磁带机。台磁带机。进程进程P P1 1总共要求总共要求1010台磁带机，台磁带机，P P2 2和和P P3 3分别要求分别要求4 4台和台和9 9台。假台。假设在设在T T0 0时刻，进程时刻，进程P P1 1、P P2 2和和P P3 3已分别获得已分别获得5 5台、台、2 2台和台和2 2台磁台磁带机，尚有带机，尚有3 3台空闲未分配，如下表所示：台空闲未分

20、配，如下表所示： 29P324P23510P1可 用 已 分 配 最 大 需 求 进 程 41 5100109312存在安全序列：存在安全序列：P2-P1-P3，系统处于安全状态。，系统处于安全状态。Operating SystemOperating SystemPage 292022-3-17 3. 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 但是，若在但是，若在T0时刻以后，时刻以后，P3又请求又请求1台磁带机，台磁带机， 若此时系统把剩余若此时系统把剩余3台中的台中的1台分配给台分配给P3，则系统便进，则系统便进入不安全状态。入不安全状态。进 程 最 大 需 求 已 分 配

21、 可 用 P11053P242P3923240 4不安全状态Operating SystemOperating SystemPage 302022-3-17q预防死锁预防死锁q系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Operating SystemOperating SystemPage 312022-3-173.6.3 利用银行家算法避免死锁利用银行家算法避免死锁 1. 银行家算法中的数据结构银行家算法中的数据结构 (1) 可利用资源向量可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值初始值是系统中

22、所配置的该类全部可用资源的数目全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej = K，则表示系统中现有，则表示系统中现有Rj类资源类资源K个。个。 Operating SystemOperating SystemPage 322022-3-17 (2) 最大需求矩阵最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j = K，则表示进程，则表示进程i需要需要Rj类资源的最大数目为类资源的最大数目为K。 (3) 分配矩阵分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源

23、当前已分配给每一进程的资源数。如果Allocationi,j=K，表示进程，表示进程i当前已分得当前已分得Rj类资源的数目为类资源的数目为K。 (4) 需求矩阵需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j = K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，个，方能完成其任务。 Needi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 332022-3-17 2. 银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Requestij =

24、K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果Requestij Needi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Requestij Availablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 Operating SystemOperating SystemPage 342022-3-17 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej := Availablej - Requestij; Allocationi,j :

25、= Allocationi,j + Requestij; Needi,j := Needi,j - Requestij; (4) 系统执行安全性算法执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 Operating SystemOperating SystemPage 352022-3-173. 安全性算法安全性算法 (1) (1) 设置两个向量：设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行的各类资源数目，它含有m个元素，在执行安全算法开始时

26、，Work := Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi := false; 当有足够资源分配给进程时， 再令Finishi := true。 Operating SystemOperating SystemPage 362022-3-17 (2) (2) 从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程： Finishi = false; Needi,j Workj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3) (3) 当进程当进程PiPi获得资源后，可顺利执行，直至

27、完成，并释获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：放出分配给它的资源，故应执行： Workj := Worki + Allocationi,j; Finishi := true; go to step 2; (4) (4) 如果所有进程的如果所有进程的Finishi = trueFinishi = true都满足，都满足， 则表示系则表示系统处于安全状态；否则，系统处于不安全状态。统处于安全状态；否则，系统处于不安全状态。 Operating SystemOperating SystemPage 372022-3-174. 银行家算法之例银行家算法之例 假定系统中有

28、五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。 图 3-15 T0时刻的资源分配表 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeedi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 382022-3-17(1) T0时刻的安全性： 图 3-16 T0时刻的安全序列

29、truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork + AllocationAllocationNeedWork存在安全序列：存在安全序列：P1-P3-P4-P2-P0，系统在系统在T0时刻处于安全状态。时刻处于安全状态。Operating SystemOperating SystemPage 392022-3-17 (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： R

30、equest1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 402022-3-17 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图所示。 Request1(1，0，2) 2C3B110

31、23C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Operating SystemOperating SystemPage 412022-3-17 再利用安全性算法检查此时系统是否安全。 truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocat

32、ionNeedWork图 3-17 P1申请资源时的安全性检查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足系统处于安全状态，可以满足P1资源分配请求。资源分配请求。Operating SystemOperating SystemPage 422022-3-17 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0)Available(2, 3, 0)，让P4等待。MaxAllocationNeedAvailab

33、leABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 432022-3-17 (4) P0请求资源：P0发出请求向量Request0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P13223020

34、20P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 442022-3-17 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。 Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030图 3-18 为P0分配资源后的有关资源数据 不安全状态Operating SystemOperating System

35、Page 452022-3-17 (5) P0请求资源：P0发出请求向量改为Request0(0, 1, 0)，系统按银行家算法进行检查： Request0(0, 1, 0)Need0(7, 4, 3); Request0(0, 1, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 462022-3-17 系统先假定可为P0分配资源，并修

36、改Available, Allocation0和Need0向量，由此形成的资源变化情况如图所示。 Request0(0, 1, 0) 0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Operating SystemOperating SystemPage 472022-3-17 再利用安全性算法检查此时系统是否安全。 truetruetruetruetrueFinish75532C55332B20212C02010B03110C033

37、12B55320C53322B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork图 3-17 P1申请资源时的安全性检查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足系统处于安全状态，可以满足P0资源分配请求。资源分配请求。Operating SystemOperating SystemPage 482022-3-17作业：作业：系统某时刻的资源分配情况如下：系统某时刻的资源分配情况如下： 资资源源进程进程Allocation NeedAvailableA B CA

38、 B CA B CP1P2P3P4P53 1 10 0 01 1 01 0 10 0 01 0 00 1 23 0 00 1 02 1 01 2 0试问：试问：1)该状态是否安全？该状态是否安全？ 2) 若进程若进程P2提出请求提出请求request2(0,1,0)，系统能否将资源，系统能否将资源分配给它？分配给它？ 3)若进程若进程P5提出请求提出请求request5(0,1,0),能否分配？能否分配？Operating SystemOperating SystemPage 492022-3-17q处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系

39、统中的调度多处理机系统中的调度q死锁概述死锁概述q预防死锁的方法预防死锁的方法q避免死锁避免死锁 q死锁的检测与解除死锁的检测与解除Operating SystemOperating SystemPage 502022-3-17q死锁的检测死锁的检测q死锁的解除死锁的解除Operating SystemOperating SystemPage 512022-3-17 允许死锁发生，操作系统不断监视系统允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行死锁并

40、以最小的代价恢复操作系统运行Operating SystemOperating SystemPage 522022-3-17q资源分配图资源分配图v表示法表示法: :资源类资源类: :用方框表示（资用方框表示（资源的不同类型）源的不同类型）资源实例资源实例: :用方框中的圆用方框中的圆点表示（存在于每个资点表示（存在于每个资源中）源中） 进程进程 : :用圆圈中加进程名用圆圈中加进程名表示表示分配边：分配边：资源实例资源实例进程进程的一条有向边的一条有向边申请边：申请边：进程进程资源类的资源类的一条有向边一条有向边P1P2r1r2获得获得申请申请Operating SystemOperatin

41、g SystemPage 532022-3-17q死锁定理死锁定理 如果资源分配图中没有环路，则系统如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中中没有死锁，如果图中存在环路则系统中可能存在死锁。可能存在死锁。 如果如果每个资源类中只包含一个资源实每个资源类中只包含一个资源实例例，则环路是死锁存在的充分必要条件。，则环路是死锁存在的充分必要条件。Operating SystemOperating SystemPage 542022-3-17q死锁定理死锁定理有环有死锁有环有死锁Operating SystemOperating SystemPage 552022-3-17

42、q死锁定理死锁定理有环无死锁有环无死锁Operating SystemOperating SystemPage 562022-3-17q死锁定理死锁定理资源分配图化简资源分配图化简v找出一个既不阻塞又非独立的进程结点找出一个既不阻塞又非独立的进程结点pipi，在顺利，在顺利的情况下的情况下pipi可获得资源而继续运行，再释放所有资可获得资源而继续运行，再释放所有资源。消去源。消去pipi所有的请求边和分配边，将其变为孤立所有的请求边和分配边，将其变为孤立结点结点v再把相应的资源分配给一个等待该资源的进程，即再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边将某进程的申请边变

43、为分配边v在进行一系列化简后若能消去图中所有的边，使所在进行一系列化简后若能消去图中所有的边，使所有进程结点成为孤立结点，则称该图是有进程结点成为孤立结点，则称该图是可完全简化可完全简化的的；否则是；否则是不可完全简化的不可完全简化的vS S为死锁的充分条件是：为死锁的充分条件是：当且仅当当且仅当S S状态的资源分配状态的资源分配图是不可完全简化的图是不可完全简化的。该充分条件称为。该充分条件称为死锁定理死锁定理Operating SystemOperating SystemPage 572022-3-17q死锁定理死锁定理资源分配图的简化资源分配图的简化 Operating SystemOp

44、erating SystemPage 582022-3-17q死锁检测中的数据结构死锁检测中的数据结构 v可利用资源向量可利用资源向量AvailableAvailable它表示了它表示了m m类资源中每一类资源的可用类资源中每一类资源的可用数目数目v把不占用资源的进程把不占用资源的进程( (向量向量Allocation:=0Allocation:=0) )记入记入L L表中，表中， 即即LiLLiLv从进程集合中找到一个从进程集合中找到一个RequestRequesti iWorkWork的的进程，做如下处理：进程，做如下处理： 将其资源分配图简化，释放出资源，将其资源分配图简化，释放出资源，增加工作向量增加工作向量Work=Work+AllocationWork=Wo