操作系统第3章处理机调度与死锁(3)

1、Operating SystemOperating SystemPage 12022-6-5Operating SystemOperating SystemPage 22022-6-5q处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除Operating SystemOperating SystemPage 32022-6-5q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件

2、产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperating SystemPage 42022-6-5q 死锁例子死锁例子v一个由于申请不同类型资源而产生死一个由于申请不同类型资源而产生死锁的例子锁的例子v设系统有一台打印机设系统有一台打印机(R1)(R1)一台扫描仪一台扫描仪(R2)(R2)，两进程共享这两台设备。，两进程共享这两台设备。v用信号量用信号量S1S1表示表示R1R1是否可用，用信号是否可用，用信号量量S2S2表示表示R2R2是否可用，是否可用，S1S1、S2S2初值为初值为1 1。Operating SystemOperating

3、SystemPage 52022-6-5这两个进程在并发执行过程中，可能会发生死锁。这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如何修改，进程才不会发生大家可以思考一下，如何修改，进程才不会发生死锁？死锁？Operating SystemOperating SystemPage 62022-6-5q 死锁的概念死锁的概念v指指多个进程多个进程因因竞争共享资源竞争共享资源而造成的而造成的一种一种僵局僵局，若无外力作用，这些进程，若无外力作用，这些进程都将永远不能再向前推进。都将永远不能再向前推进。v即：一组进程中，每个进程都即：一组进程中，每个进程都无限等无限等待待被该组进程中

4、被该组进程中另一进程所占有的资另一进程所占有的资源源，因而永远无法得到的资源，这种，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称现象称为进程死锁，这一组进程就称为死锁进程。为死锁进程。Operating SystemOperating SystemPage 72022-6-5q 关于死锁的一些结论关于死锁的一些结论v参与死锁的进程参与死锁的进程最少是两个最少是两个 v参与死锁的进程参与死锁的进程至少有两个已经占有至少有两个已经占有资源资源v参与死锁的所有进程参与死锁的所有进程都在等待资源都在等待资源v参与死锁的进程是当前系统中所有参与死锁的进程是当前系统中所有进进程的子集程的子

5、集注：注：如果死锁发生，会浪费大量系统资源，如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。甚至导致系统崩溃。Operating SystemOperating SystemPage 82022-6-5q 永久性资源和临时性资源永久性资源和临时性资源v永久性资源：可以被多个进程多次使用（可永久性资源：可以被多个进程多次使用（可再用资源）再用资源）可抢占资源：可抢占资源：CPUCPU不可抢占资源：打印机不可抢占资源：打印机v临时性资源：只可使用一次的资源；即由一临时性资源：只可使用一次的资源；即由一个进程产生，被另一进程使用后就再也无用个进程产生，被另一进程使用后就再也无用的资源，也称为的资

6、源，也称为消耗性资源消耗性资源 如信号量如信号量, ,中断信号，同步信号等（可消耗中断信号，同步信号等（可消耗性资源）性资源）“申请申请-分配分配-使用使用-释放释放”模式模式Operating SystemOperating SystemPage 92022-6-5q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperating SystemPage 102022-6-53.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.5.1 产生死锁的原因产生死锁的原因 竞争

7、资源。竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。 (2) 进程间推进顺序非法。进程间推进顺序非法。 进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。 所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。 Operating SystemOperating SystemPage 112022-6-5q 竞争资源引起进程死锁竞争资源引起进程死锁v可剥夺和非剥夺性资源可剥夺和非剥夺性资源 可剥夺性资源可剥夺性资源是指进程在获得这类资源后，是指进程在获得这类资源后，该

8、资源该资源可以再被可以再被其他进程或系统其他进程或系统剥夺剥夺，如，如处处理机、内存理机、内存等等非剥夺性资源非剥夺性资源是指当系统把这类资源分配给是指当系统把这类资源分配给某个进程后，某个进程后，再不能强行收回再不能强行收回，只能在进程，只能在进程用完后自行释放，如磁带机、打印机等用完后自行释放，如磁带机、打印机等v竞争非剥夺性资源竞争非剥夺性资源 系统中的系统中的非剥夺性资源非剥夺性资源由于数量有限而不能由于数量有限而不能满足进程运行的需要，进程在运行过程中因满足进程运行的需要，进程在运行过程中因争夺这些资源而限入僵局争夺这些资源而限入僵局v竞争临时性资源竞争临时性资源 Operating

9、 SystemOperating SystemPage 122022-6-5I/O设设备备共共享享时时的的死死锁锁情情况况 若系统中只有一台打印机若系统中只有一台打印机R1R1和一台读卡机和一台读卡机R2R2，可，可供进程供进程P1P1和和P2P2共享。若共享。若形成环路形成环路，这样会产生死锁。，这样会产生死锁。R1R2P1P2分配分配分配分配请求请求请求请求Operating SystemOperating SystemPage 132022-6-5 进程之间通信时的死锁进程之间通信时的死锁 S2P1S3P3S1P2产生产生P2P2产生产生P3P3产生产生要求接收要求接收要求接收要求接收要

10、求接收要求接收Operating SystemOperating SystemPage 142022-6-5q进程推进顺序不当引起死锁进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)D不安全区Operating SystemOperating SystemPage 152022-6-5q若并发进程若并发进程P P1 1和和P P2 2按曲线按曲线所示的顺序推所示的顺序推进，它们将进入不安全区进，它们将进入不安全区D D内。此时内。此时P P1 1保保持了资源持了资源R R

11、1 1, P, P2 2保持了资源保持了资源R R2 2, , 系统处于系统处于不安全状态。因为，这时两进程再向前不安全状态。因为，这时两进程再向前推进，便可能发生死锁。推进，便可能发生死锁。q例如，当例如，当P P1 1运行到运行到P P1 1:Request(R:Request(R2 2) )时，将时，将因因R R2 2已被已被P P2 2占用而阻塞；当占用而阻塞；当P P2 2运行到运行到P P2 2: : Request(RRequest(R1 1) )时，也将因时，也将因R R1 1已被已被P P1 1占用而占用而阻塞，于是发生了进程死锁阻塞，于是发生了进程死锁Operating S

12、ystemOperating SystemPage 162022-6-5q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperating SystemPage 172022-6-5q 互斥条件互斥条件 v进程对所分配到的资源进行进程对所分配到的资源进行排它性的使用排它性的使用q 请求和保持条件请求和保持条件 v进程已经至少进程已经至少保持了一个保持了一个资源，但又提出了资源，但又提出了新的资源新的资源请求请求，而该资源又已被其他进程占，而该资源又已被其他进程占有有q 不剥夺

13、条件不剥夺条件 v进程已获得的资源在未使用完之前不能被剥进程已获得的资源在未使用完之前不能被剥夺夺q 环路等待条件环路等待条件v在发生死锁时，必然存在一个进程在发生死锁时，必然存在一个进程-资源循资源循环等待的环形链环等待的环形链Operating SystemOperating SystemPage 182022-6-5q死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Operating SystemOperating SystemPage 192022-6-5q 预防死锁预防死锁q 避免死锁避免死锁q 检

14、测死锁检测死锁q 解除死锁解除死锁Operating SystemOperating SystemPage 202022-6-53.5.3 处理死锁的基本方法处理死锁的基本方法 目前用于处理死锁的方法可归结为以下四种：1、预防死锁、预防死锁 通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。2、避免死锁、避免死锁 不须采用各种限制措施去破坏产生死锁的必要条件，防止系统进入不安全状态，从而避免发生死锁，只需在事先加以较弱的限制条件。3、检测死锁、检测死锁 不须检查系统是否已进入不安全区，允许系统在运行过程中发生死锁。4、 解除死锁解除死锁 常用的实施方法是撤消

15、或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。Operating SystemOperating SystemPage 212022-6-5方法方法资源分配策略资源分配策略各种可能模式各种可能模式 主要优点主要优点主要缺点主要缺点预防预防Prevention保守的；宁可资保守的；宁可资源闲置（从机制源闲置（从机制上使死锁条件不上使死锁条件不成立，即摒弃三成立，即摒弃三个必要条件）个必要条件）一次请求所有一次请求所有资源资源适用于作突发式处理的适用于作突发式处理的进程；不必剥夺进程；不必剥夺效率低；进程初始化效率低；进程初始化时间延长时间

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

17、查死锁定期检查死锁是否已经发生是否已经发生不延长进程初始化时间；不延长进程初始化时间；允许对死锁进行现场处允许对死锁进行现场处理理通过剥夺解除死锁，通过剥夺解除死锁，造成损失造成损失可以在编译时（而不必可以在编译时（而不必在运行时）就进行检查在运行时）就进行检查Operating SystemOperating SystemPage 222022-6-5q处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除

18、Operating SystemOperating SystemPage 232022-6-5q预防死锁预防死锁q系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Operating SystemOperating SystemPage 242022-6-5q 互斥条件互斥条件 v进程对所分配到的资源进行进程对所分配到的资源进行排它性的使用排它性的使用q 请求和保持条件请求和保持条件 v进程已经至少进程已经至少保持了一个保持了一个资源，但又提出了资源，但又提出了新的资源新的资源请求请求，而该资源又已被其他进程占，而该资源又已被其他进程占有有q 不剥夺条件不剥夺条件 v进程已

19、获得的资源在未使用完之前不能被剥进程已获得的资源在未使用完之前不能被剥夺夺q 环路等待条件环路等待条件v在发生死锁时，必然存在一个进程在发生死锁时，必然存在一个进程-资源循资源循环等待的环形链环等待的环形链Operating SystemOperating SystemPage 252022-6-5q 摒弃摒弃“请求和保持请求和保持”条件条件 v所有进程在开始运行之前必须所有进程在开始运行之前必须一次性的一次性的申请申请整个运行过程所需的全部资源整个运行过程所需的全部资源v简单、易于实现、安全简单、易于实现、安全v资源浪费严重资源浪费严重v进程延迟运行进程延迟运行Operating Syste

20、mOperating SystemPage 262022-6-5q摒弃摒弃“不剥夺不剥夺”条件条件 v进程逐个地申请所需资源进程逐个地申请所需资源v当一个已经保持了某些资源的进程当一个已经保持了某些资源的进程申请申请新资源而不能得到满足时，必须放弃新资源而不能得到满足时，必须放弃所所有已保持的资源有已保持的资源v实现复杂、代价高昂实现复杂、代价高昂v延长了进程的周转时间，还增加了系统延长了进程的周转时间，还增加了系统开销，降低了系统的吞吐量开销，降低了系统的吞吐量Operating SystemOperating SystemPage 272022-6-5q摒弃摒弃“环路等待环路等待”条件条件

21、v系统将所有资源按类型分配序号并排队系统将所有资源按类型分配序号并排队v所有进程所有进程申请申请资源必须资源必须按序号按序号递增的顺递增的顺序序v资源利用率和系统吞吐量较高资源利用率和系统吞吐量较高v但在资源管理和资源申请方面仍有问题但在资源管理和资源申请方面仍有问题Operating SystemOperating SystemPage 282022-6-5序号序号资源资源1输入机输入机2打印机打印机3磁带机磁带机进程进程需求资源需求资源P1打印机打印机磁带机磁带机P2磁带机磁带机打印机打印机存在问题：资源的需求顺序不等于存在问题：资源的需求顺序不等于序号，仍存在资源浪费。序号，仍存在资源浪

22、费。Operating SystemOperating SystemPage 292022-6-5q摒弃摒弃“环路等待环路等待”条件条件q其资源利用率和系统吞吐量，都有较明显其资源利用率和系统吞吐量，都有较明显的改善，但也存在下述严重问题：的改善，但也存在下述严重问题：v（1）资源所分配的序号，必须相对稳定，这）资源所分配的序号，必须相对稳定，这就限制了新设备类型的增加。就限制了新设备类型的增加。v（2）进程使用各资源的顺序，与系统规定的）进程使用各资源的顺序，与系统规定的顺序不同，造成对资源的浪费。顺序不同，造成对资源的浪费。v（3）按规定次序申请资源的方法，必然会限）按规定次序申请资源的方

23、法，必然会限制了用户简单、自主地编程。制了用户简单、自主地编程。 Operating SystemOperating SystemPage 302022-6-5方法方法资源分配策略资源分配策略各种可能模式各种可能模式 主要优点主要优点主要缺点主要缺点预防预防Prevention保守的；宁可资保守的；宁可资源闲置（从机制源闲置（从机制上使死锁条件不上使死锁条件不成立，即摒弃三成立，即摒弃三个必要条件）个必要条件）一次请求所有一次请求所有资源资源适用于作突发式处理的适用于作突发式处理的进程；不必剥夺进程；不必剥夺效率低；进程初始化效率低；进程初始化时间延长时间延长剥夺次数过多；多次剥夺次数过多；多

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

25、发生不延长进程初始化时间；不延长进程初始化时间；允许对死锁进行现场处允许对死锁进行现场处理理通过剥夺解除死锁，通过剥夺解除死锁，造成损失造成损失可以在编译时（而不必可以在编译时（而不必在运行时）就进行检查在运行时）就进行检查Operating SystemOperating SystemPage 312022-6-5q预防死锁预防死锁q系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Operating SystemOperating SystemPage 322022-6-5q进程推进顺序不当引起死锁进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(

26、R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)DOperating SystemOperating SystemPage 332022-6-5q安全状态安全状态v在避免死锁的方法中，允许进程在避免死锁的方法中，允许进程动态地动态地申请申请资源，但系统在进行资源分配之前，应先计资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会算此次资源分配的安全性。若此次分配不会导致系统进入导致系统进入不安全状态不安全状态，则将资源分配给，则将资源分配给进程；进程； 否则，令进程等待否则，令进程等待v所谓所谓安全状态安全状态，是指系

27、统能按某种进程顺序，是指系统能按某种进程顺序(P1, P2, (P1, P2, ，Pn)(Pn)(称称P1, P2, , PnP1, P2, , Pn序序列为安全序列列为安全序列) )，来为每个进程，来为每个进程PiPi分配其所需分配其所需资源，直至满足每个进程对资源的最大需求，资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于找到这样一个安全序列，则称系统处于不安不安全状态全状态Operating SystemOperating SystemPage 342022-6-5 2. 安全状态之例安

28、全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 29P324P23510P1可 用 已 分 配 最 大 需 求 进 程 41 5100109312存在安全序列：存在安全序列：P2-P1-P3，系统处于安全状态。，系统处于安全状态。Operating SystemOperating SystemPage 352022-6-5 3. 由安全状态向不安全状态的转换由安全状态向不安全状态的

29、转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机， 若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。进 程 最 大 需 求 已 分 配 可 用 P11053P242P3923240 4不安全状态Operating SystemOperating SystemPage 362022-6-5q预防死锁预防死锁q系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Operating SystemOperating SystemPage 372022-6-53.6.3 利用银行家算法避免死锁利用银行家算

30、法避免死锁 1. 银行家算法中的数据结构银行家算法中的数据结构 (1) 可利用资源向量可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej = K，则表示系统中现有，则表示系统中现有Rj类资源类资源K个。个。 Operating SystemOperating SystemPage 382022-6-5 (2) 最大需求矩阵最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max

31、i,j = K，则表示进程，则表示进程i需要需要Rj类资源的最大数目为类资源的最大数目为K。 (3) 分配矩阵分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，表示进程，表示进程i当前已分得当前已分得Rj类资源的数目为类资源的数目为K。 (4) 需求矩阵需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j = K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，个，方能完成其任务。 Needi,j = Maxi,j Allocationi,j Oper

32、ating SystemOperating SystemPage 392022-6-5 2. 银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Requestij = K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果Requestij Needi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Requestij Availablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 Operating SystemOperating SystemPage 402022-6

33、-5 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej := Availablej - Requestij; Allocationi,j := Allocationi,j + Requestij; Needi,j := Needi,j - Requestij; (4) 系统执行安全性算法安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 Operating SystemOperating SystemPage 412022-6-5

34、3. 安全性算法安全性算法 (1) 设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work := Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi := false; 当有足够资源分配给进程时， 再令Finishi := true。 Operating SystemOperating SystemPage 422022-6-5 (2) 从进程集合中找到一个能满足下述条件的进程： Finishi = false; Needi,j Workj； 若找到，

35、执行步骤(3)， 否则，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj := Worki + Allocationi,j; Finishi := true; go to step 2; (4) 如果所有进程的Finishi = true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 Operating SystemOperating SystemPage 432022-6-54. 银行家算法之例银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为

36、10、5、7，在T0时刻的资源分配情况如图 3-15 所示。 图 3-15 T0时刻的资源分配表 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeedi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 442022-6-5(1) T0时刻的安全性： 图 3-16 T0时刻的安全序列 truetruetruetruetrueFinish77532C54443B02210C10

37、010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork + AllocationAllocationNeedWork存在安全序列：存在安全序列：P1-P3-P4-P2-P0，系统在系统在T0时刻处于安全状态。时刻处于安全状态。Operating SystemOperating SystemPage 452022-6-5 (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2

38、)Available1(3, 3, 2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 462022-6-5 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。 Request1(1，0，2) 2C3B11023C31024B21200C01001B32223C32025B404P

39、4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Operating SystemOperating SystemPage 472022-6-5 再利用安全性算法检查此时系统是否安全。 truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork图 3-17 P1申请资源时的安全性检查 存在安全序列

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

41、P2902302600P3222211011P4433002431/Operating SystemOperating SystemPage 492022-6-5 (4) P0请求资源：P0发出请求向量Request0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Oper

42、ating SystemOperating SystemPage 502022-6-5 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。 Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030图 3-18 为P0分配资源后的有关资源数据 不安全状态Operating SystemOperating SystemPage 512022-6-5 (5) P0请求资源：P0发出请求向量改为Req

43、uest0(0, 1, 0)，系统按银行家算法进行检查： Request0(0, 1, 0)Need0(7, 4, 3); Request0(0, 1, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 522022-6-5 系统先假定可为P0分配资源，并修改Available, Allocation0和Need0向量，由此形成的资源变化情

44、况如图所示。 Request0(0, 1, 0) 0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Operating SystemOperating SystemPage 532022-6-5 再利用安全性算法检查此时系统是否安全。 truetruetruetruetrueFinish75532C55332B20212C02010B03110C03312B55320C53322B10367P27047P45302P17077P0720

45、5P3AAAAWork + AllocationAllocationNeedWork图 3-17 P1申请资源时的安全性检查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足系统处于安全状态，可以满足P0资源分配请求。资源分配请求。Operating SystemOperating SystemPage 542022-6-5q处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测

46、与解除Operating SystemOperating SystemPage 552022-6-5q死锁的检测死锁的检测q死锁的解除死锁的解除Operating SystemOperating SystemPage 562022-6-5 允许死锁发生，操作系统不断监视系统允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行死锁并以最小的代价恢复操作系统运行Operating SystemOperating SystemPage 572022-6-5q检测时

47、机检测时机v 当进程等待时检测死锁当进程等待时检测死锁 其缺点是系统的开销大其缺点是系统的开销大v 定时检测定时检测 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁Operating SystemOperating SystemPage 582022-6-53.7 死锁的检测与解除死锁的检测与解除 3.7.1 死锁的检测死锁的检测 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须：（1）保存有关资源的请求和分配信息；（2）提供一种算法，以利用这些信息来检测系统是否进入死锁状态。 Operating SystemOperating Sy

48、stemPage 592022-6-5q资源分配图资源分配图(Resource Allocation Graph)(Resource Allocation Graph) 用有向图描述进程的死锁用有向图描述进程的死锁v优点：准确、形象优点：准确、形象 系统由若干类资源构成，一类资源称系统由若干类资源构成，一类资源称为一个为一个资源类资源类；每个资源类中包含若干个；每个资源类中包含若干个同种资源，称为同种资源，称为资源实例资源实例Operating SystemOperating SystemPage 602022-6-53.7 死锁的检测与解除死锁的检测与解除 系统死锁可利用资源分配图来描述。该

49、图是由一组结点N和一组边E所组成的一个对偶G =（N，E），具有下述形成的定义和限制：（1）N被分为两个互斥的子集，一组进程结点P=（p1，p2，pn），一组资源结点R=r1，r2，rn，N=PR。在图3-19所示的例子中：1. 资源分配图资源分配图(Resource Allocation Graph) Operating SystemOperating SystemPage 612022-6-53.7 死锁的检测与解除死锁的检测与解除 3.7.1 死锁的检测死锁的检测 1. 资源分配图资源分配图(Resource Allocation Graph) 图 3-19 每类资源有多个时的情况 P=

50、p1，p2，R=r1，r2，N=r1，r2 p1，p2 P1P2r1r2Operating SystemOperating SystemPage 622022-6-5q资源分配图资源分配图v表示法表示法: :资源类资源类: :用方框表示用方框表示（资源的不同类型）（资源的不同类型）资源实例资源实例: :用方框中的用方框中的圆点表示（存在于每圆点表示（存在于每个资源中）个资源中） 进程进程 : :用圆圈中加进程用圆圈中加进程名表示名表示分配边：分配边：资源实例资源实例进进程的一条有向边程的一条有向边申请边：申请边：进程进程资源类资源类的一条有向边的一条有向边P1P2r1r2获得获得申请申请Ope

51、rating SystemOperating SystemPage 632022-6-5q死锁定理死锁定理 如果资源分配图中没有环路，则系统如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中中没有死锁，如果图中存在环路则系统中可能存在死锁。可能存在死锁。 如果如果每个资源类中只包含一个资源实每个资源类中只包含一个资源实例例，则环路是死锁存在的充分必要条件。，则环路是死锁存在的充分必要条件。Operating SystemOperating SystemPage 642022-6-5q死锁定理死锁定理有环有死锁有环有死锁Operating SystemOperating Sys

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

53、请边变为分配边即将某进程的申请边变为分配边v在进行一系列化简后若能消去图中所有的边，使在进行一系列化简后若能消去图中所有的边，使所有进程结点成为孤立结点，则称该图是所有进程结点成为孤立结点，则称该图是可完全可完全简化的简化的；否则是；否则是不可完全简化的不可完全简化的v已经证明：所有的化简顺序都得到相同的不可简已经证明：所有的化简顺序都得到相同的不可简化图。同样可以证明，化图。同样可以证明，S S为死锁的充分条件是：为死锁的充分条件是：当当且仅当且仅当S S状态的资源分配图是不可完全简化的状态的资源分配图是不可完全简化的。该。该充分条件称为充分条件称为死锁定理死锁定理Operating Sys

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