1、Operating SystemOperating SystemPage 12022-5-24Operating SystemOperating Systemq处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除Page 22022-5-24Operating SystemOperating Systemq死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理
2、死锁的基本方法处理死锁的基本方法Page 32022-5-24Operating SystemOperating Systemq 死锁例子死锁例子v一个由于申请不同类型资源而产生死一个由于申请不同类型资源而产生死锁的例子锁的例子v设系统有一台打印机设系统有一台打印机(R1)(R1)一台扫描仪一台扫描仪(R2)(R2)，两进程共享这两台设备。，两进程共享这两台设备。v用信号量用信号量S1S1表示表示R1R1是否可用，用信号是否可用，用信号量量S2S2表示表示R2R2是否可用，是否可用，S1S1、S2S2初值为初值为1 1。Page 42022-5-24Operating SystemOperat
3、ing System这两个进程在并发执行过程中，可能会发生死锁。这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如何修改，进程才不会发生大家可以思考一下，如何修改，进程才不会发生死锁？死锁？Page 52022-5-24Operating SystemOperating Systemq 死锁的概念死锁的概念v指指多个进程多个进程因因竞争共享资源竞争共享资源而造成的而造成的一种一种僵局僵局，若无外力作用，这些进程，若无外力作用，这些进程都将永远不能再向前推进。都将永远不能再向前推进。v即：一组进程中，每个进程都即：一组进程中，每个进程都无限等无限等待待被该组进程中被该组进程中另一进
4、程所占有的资另一进程所占有的资源源，因而永远无法得到的资源，这种，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称现象称为进程死锁，这一组进程就称为死锁进程。为死锁进程。Page 62022-5-24Operating SystemOperating Systemq 关于死锁的一些结论关于死锁的一些结论v参与死锁的进程参与死锁的进程最少是两个最少是两个 v参与死锁的进程参与死锁的进程至少有两个已经占有至少有两个已经占有资源资源v参与死锁的所有进程参与死锁的所有进程都在等待资源都在等待资源v参与死锁的进程是当前系统中所有参与死锁的进程是当前系统中所有进进程的子集程的子集注：注：如果死
5、锁发生，会浪费大量系统资源，如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。甚至导致系统崩溃。Page 72022-5-24Operating SystemOperating Systemq 永久性资源和临时性资源永久性资源和临时性资源v永久性资源：可以被多个进程多次使用（可永久性资源：可以被多个进程多次使用（可再用资源）再用资源）可抢占资源：可抢占资源：CPUCPU不可抢占资源：打印机不可抢占资源：打印机v临时性资源：只可使用一次的资源；即由一临时性资源：只可使用一次的资源；即由一个进程产生，被另一进程使用后就再也无用个进程产生，被另一进程使用后就再也无用的资源，也称为的资源，也称为消耗
6、性资源消耗性资源 如信号量如信号量, ,中断信号，同步信号等（可消耗中断信号，同步信号等（可消耗性资源）性资源）“申请申请-分配分配-使用使用-释放释放”模式模式Page 82022-5-24Operating SystemOperating Systemq死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Page 92022-5-24Operating SystemOperating System3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.5.1 产生死锁的原因产生死锁的原因 (1) 竞争资源
7、。竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。 (2) 进程间推进顺序非法。进程间推进顺序非法。 进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。 所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。 Page 102022-5-24Operating SystemOperating Systemq 竞争资源引起进程死锁竞争资源引起进程死锁v可剥夺和非剥夺性资源可剥夺和非剥夺性资源 可剥夺性资源可剥夺性资源是指进程在获得这类资源后，是指进程在获得这类资源后，该资
8、源该资源可以再被可以再被其他进程或系统其他进程或系统剥夺剥夺，如，如处处理机、内存理机、内存等等非剥夺性资源非剥夺性资源是指当系统把这类资源分配给是指当系统把这类资源分配给某个进程后，某个进程后，再不能强行收回再不能强行收回，只能在进程，只能在进程用完后自行释放，如磁带机、打印机等用完后自行释放，如磁带机、打印机等v竞争非剥夺性资源竞争非剥夺性资源 系统中的系统中的非剥夺性资源非剥夺性资源由于数量有限而不能由于数量有限而不能满足进程运行的需要，进程在运行过程中因满足进程运行的需要，进程在运行过程中因争夺这些资源而限入僵局争夺这些资源而限入僵局v竞争临时性资源竞争临时性资源 Page 11202
9、2-5-24Operating SystemOperating SystemI/O设设备备共共享享时时的的死死锁锁情情况况 若系统中只有一台打印机若系统中只有一台打印机R1R1和一台读卡机和一台读卡机R2R2，可，可供进程供进程P1P1和和P2P2共享。若共享。若形成环路形成环路，这样会产生死锁。，这样会产生死锁。R1R2P1P2分配分配分配分配请求请求请求请求Page 122022-5-24Operating SystemOperating System 进程之间通信时的死锁进程之间通信时的死锁 S2P1S3P3S1P2产生产生P2P2产生产生P3P3产生产生要求接收要求接收要求接收要求接收
10、要求接收要求接收Page 132022-5-24Operating SystemOperating Systemq进程推进顺序不当引起死锁进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)D不安全区Page 142022-5-24Operating SystemOperating Systemq若并发进程若并发进程P P1 1和和P P2 2按曲线按曲线所示的顺序推所示的顺序推进，它们将进入不安全区进，它们将进入不安全区D D内。此时内。此时P P1 1保保持了资源持了资源
11、R R1 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占用而占用而阻塞，于是发生了进程死锁阻塞，于是发生了进程死锁Page 152
12、022-5-24Operating SystemOperating Systemq死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Page 162022-5-24Operating SystemOperating Systemq 互斥条件互斥条件 v进程对所分配到的资源进行进程对所分配到的资源进行排它性的使用排它性的使用q 请求和保持条件请求和保持条件 v进程已经至少进程已经至少保持了一个保持了一个资源，但又提出了资源，但又提出了新的资源新的资源请求请求，而该资源又已被其他进程占，而该资源又已被其他进程占有有
13、q 不剥夺条件不剥夺条件 v进程已获得的资源在未使用完之前不能被剥进程已获得的资源在未使用完之前不能被剥夺夺q 环路等待条件环路等待条件v在发生死锁时，必然存在一个进程在发生死锁时，必然存在一个进程-资源循资源循环等待的环形链环等待的环形链Page 172022-5-24Operating SystemOperating Systemq死锁的基本概念死锁的基本概念q产生死锁的原因产生死锁的原因q产生死锁的必要条件产生死锁的必要条件q处理死锁的基本方法处理死锁的基本方法Page 182022-5-24Operating SystemOperating Systemq 预防死锁预防死锁q 避免死锁
14、避免死锁q 检测死锁检测死锁q 解除死锁解除死锁Page 192022-5-24Operating SystemOperating System3.5.3 处理死锁的基本方法处理死锁的基本方法 目前用于处理死锁的方法可归结为以下四种：1、预防死锁、预防死锁 通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。2、避免死锁、避免死锁 不须采用各种限制措施去破坏产生死锁的必要条件，防止系统进入不安全状态，从而避免发生死锁，只需在事先加以较弱的限制条件。3、检测死锁、检测死锁 不须检查系统是否已进入不安全区，允许系统在运行过程中发生死锁。4、 解除死锁解除死锁 常用
15、的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。Page 202022-5-24Operating SystemOperating System方法方法资源分配策略资源分配策略各种可能模式各种可能模式 主要优点主要优点主要缺点主要缺点预防预防Prevention保守的；宁可资保守的；宁可资源闲置（从机制源闲置（从机制上使死锁条件不上使死锁条件不成立，即摒弃三成立，即摒弃三个必要条件）个必要条件）一次请求所有一次请求所有资源资源适用于作突发式处理的适用于作突发式处理的进程；不必剥夺进程；不必剥夺效率低；进程初始化效率低；进程
16、初始化时间延长时间延长剥夺次数过多；多次剥夺次数过多；多次对资源重新起动对资源重新起动不便灵活申请新资源不便灵活申请新资源资源剥夺资源剥夺适用于状态可以保存和适用于状态可以保存和恢复的资源恢复的资源资源资源按序申请按序申请避免避免Avoidance是是“预防预防”和和“检测检测”的折衷的折衷（在运行时判断（在运行时判断是否可能死锁）是否可能死锁）寻找可能的安寻找可能的安全的运行顺序全的运行顺序 不必进行剥夺不必进行剥夺使用条件：必须知道使用条件：必须知道将来的资源需求；进将来的资源需求；进程可能会长时间阻塞程可能会长时间阻塞检测检测Detection宽松的；只要允宽松的；只要允许，就分配资源许
17、，就分配资源定期检查死锁定期检查死锁是否已经发生是否已经发生不延长进程初始化时间；不延长进程初始化时间；允许对死锁进行现场处允许对死锁进行现场处理理通过剥夺解除死锁，通过剥夺解除死锁，造成损失造成损失可以在编译时（而不必可以在编译时（而不必在运行时）就进行检查在运行时）就进行检查Page 212022-5-24Operating SystemOperating Systemq处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与
18、解除死锁的检测与解除Page 222022-5-24Operating SystemOperating Systemq预防死锁预防死锁q系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Page 232022-5-24Operating SystemOperating Systemq 互斥条件互斥条件 v进程对所分配到的资源进行进程对所分配到的资源进行排它性的使用排它性的使用q 请求和保持条件请求和保持条件 v进程已经至少进程已经至少保持了一个保持了一个资源，但又提出了资源，但又提出了新的资源新的资源请求请求，而该资源又已被其他进程占，而该资源又已被其他进程占有有q 不剥夺
19、条件不剥夺条件 v进程已获得的资源在未使用完之前不能被剥进程已获得的资源在未使用完之前不能被剥夺夺q 环路等待条件环路等待条件v在发生死锁时，必然存在一个进程在发生死锁时，必然存在一个进程-资源循资源循环等待的环形链环等待的环形链Page 242022-5-24Operating SystemOperating Systemq 摒弃摒弃“请求和保持请求和保持”条件条件 v所有进程在开始运行之前必须所有进程在开始运行之前必须一次性的一次性的申请申请整个运行过程所需的全部资源整个运行过程所需的全部资源v简单、易于实现、安全简单、易于实现、安全v资源浪费严重资源浪费严重v进程延迟运行进程延迟运行Pa
20、ge 252022-5-24Operating SystemOperating Systemq摒弃摒弃“不剥夺不剥夺”条件条件 v进程逐个地申请所需资源进程逐个地申请所需资源v当一个已经保持了某些资源的进程当一个已经保持了某些资源的进程申请申请新资源而不能得到满足时，必须放弃新资源而不能得到满足时，必须放弃所所有已保持的资源有已保持的资源v实现复杂、代价高昂实现复杂、代价高昂v延长了进程的周转时间，还增加了系统延长了进程的周转时间，还增加了系统开销，降低了系统的吞吐量开销，降低了系统的吞吐量Page 262022-5-24Operating SystemOperating Systemq摒弃摒
21、弃“环路等待环路等待”条件条件v系统将所有资源按类型分配序号并排队系统将所有资源按类型分配序号并排队v所有进程所有进程申请申请资源必须资源必须按序号按序号递增的顺递增的顺序序v资源利用率和系统吞吐量较高资源利用率和系统吞吐量较高v但在资源管理和资源申请方面仍有问题但在资源管理和资源申请方面仍有问题Page 272022-5-24Operating SystemOperating System序号序号资源资源1输入机输入机2打印机打印机3磁带机磁带机进程进程需求资源需求资源P1打印机打印机磁带机磁带机P2磁带机磁带机打印机打印机存在问题：资源的需求顺序不等于存在问题：资源的需求顺序不等于序号，仍
22、存在资源浪费。序号，仍存在资源浪费。Page 282022-5-24Operating SystemOperating Systemq摒弃摒弃“环路等待环路等待”条件条件q其资源利用率和系统吞吐量，都有较明显其资源利用率和系统吞吐量，都有较明显的改善，但也存在下述严重问题：的改善，但也存在下述严重问题：v（1）资源所分配的序号，必须相对稳定，这）资源所分配的序号，必须相对稳定，这就限制了新设备类型的增加。就限制了新设备类型的增加。v（2）进程使用各资源的顺序，与系统规定的）进程使用各资源的顺序，与系统规定的顺序不同，造成对资源的浪费。顺序不同，造成对资源的浪费。v（3）按规定次序申请资源的方法
23、，必然会限）按规定次序申请资源的方法，必然会限制了用户简单、自主地编程。制了用户简单、自主地编程。 Page 292022-5-24Operating SystemOperating System方法方法资源分配策略资源分配策略各种可能模式各种可能模式 主要优点主要优点主要缺点主要缺点预防预防Prevention保守的；宁可资保守的；宁可资源闲置（从机制源闲置（从机制上使死锁条件不上使死锁条件不成立，即摒弃三成立，即摒弃三个必要条件）个必要条件）一次请求所有一次请求所有资源资源适用于作突发式处理的适用于作突发式处理的进程；不必剥夺进程；不必剥夺效率低；进程初始化效率低；进程初始化时间延长时间延
24、长剥夺次数过多；多次剥夺次数过多；多次对资源重新起动对资源重新起动不便灵活申请新资源不便灵活申请新资源资源剥夺资源剥夺适用于状态可以保存和适用于状态可以保存和恢复的资源恢复的资源资源资源按序申请按序申请避免避免Avoidance是是“预防预防”和和“检测检测”的折衷的折衷（在运行时判断（在运行时判断是否可能死锁）是否可能死锁）寻找可能的安寻找可能的安全的运行顺序全的运行顺序 不必进行剥夺不必进行剥夺使用条件：必须知道使用条件：必须知道将来的资源需求；进将来的资源需求；进程可能会长时间阻塞程可能会长时间阻塞检测检测Detection宽松的；只要允宽松的；只要允许，就分配资源许，就分配资源定期检查
25、死锁定期检查死锁是否已经发生是否已经发生不延长进程初始化时间；不延长进程初始化时间；允许对死锁进行现场处允许对死锁进行现场处理理通过剥夺解除死锁，通过剥夺解除死锁，造成损失造成损失可以在编译时（而不必可以在编译时（而不必在运行时）就进行检查在运行时）就进行检查Page 302022-5-24Operating SystemOperating Systemq预防死锁预防死锁q系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Page 312022-5-24Operating SystemOperating Systemq进程推进顺序不当引起死锁进程推进顺序不当引起死锁P2Re
26、l(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)DPage 322022-5-24Operating SystemOperating Systemq安全状态安全状态v在避免死锁的方法中，允许进程在避免死锁的方法中，允许进程动态地动态地申请申请资源，但系统在进行资源分配之前，应先计资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会算此次资源分配的安全性。若此次分配不会导致系统进入导致系统进入不安全状态不安全状态，则将资源分配给，则将资源分配给进程；进程； 否则，令进程等待否则，令
27、进程等待v所谓所谓安全状态安全状态，是指系统能按某种进程顺序，是指系统能按某种进程顺序(P1, P2, (P1, P2, ，Pn)(Pn)(称称P1, P2, , PnP1, P2, , Pn序序列为安全序列列为安全序列) )，来为每个进程，来为每个进程PiPi分配其所需分配其所需资源，直至满足每个进程对资源的最大需求，资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于找到这样一个安全序列，则称系统处于不安不安全状态全状态Page 332022-5-24Operating SystemOpera
28、ting System 2. 安全状态之例安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 29P324P23510P1可 用 已 分 配 最 大 需 求 进 程 41 5100109312存在安全序列：存在安全序列：P2-P1-P3，系统处于安全状态。，系统处于安全状态。Page 342022-5-24Operating SystemOperating System 3. 由安全
29、状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机， 若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。进 程 最 大 需 求 已 分 配 可 用 P11053P242P3923240 4不安全状态Page 352022-5-24Operating SystemOperating Systemq预防死锁预防死锁q系统安全状态系统安全状态q利用银行家算法避免死锁利用银行家算法避免死锁Page 362022-5-24Operating SystemOperating Syst
30、em3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁 1. 银行家算法中的数据结构银行家算法中的数据结构 (1) 可利用资源向量可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej = K，则表示系统中现有，则表示系统中现有Rj类资源类资源K个。个。 Page 372022-5-24Operating SystemOperating System (2) 最大需求矩阵最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n
31、个进程中的每一个进程对m类资源的最大需求。如果Maxi,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 =
32、 Maxi,j Allocationi,j Page 382022-5-24Operating SystemOperating System 2. 银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Requestij = K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果Requestij Needi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Requestij Availablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 Page 392022-5-24Op
33、erating SystemOperating System (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej := Availablej - Requestij; Allocationi,j := Allocationi,j + Requestij; Needi,j := Needi,j - Requestij; (4) 系统执行安全性算法安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 Page 402022-5-24Ope
34、rating SystemOperating System3. 安全性算法安全性算法 (1) 设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work := Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi := false; 当有足够资源分配给进程时， 再令Finishi := true。 Page 412022-5-24Operating SystemOperating System (2) 从进程集合中找到一个能满足下述条件的进程： Finishi
35、 = false; Needi,j Workj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj := Worki + Allocationi,j; Finishi := true; go to step 2; (4) 如果所有进程的Finishi = true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 Page 422022-5-24Operating SystemOperating System4. 银行家算法之例银行家算法之例 假定系统中有五个进程P0, P1, P2
36、, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。 图 3-15 T0时刻的资源分配表 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeedi,j = Maxi,j Allocationi,j Page 432022-5-24Operating SystemOperating System(1) T0时刻的安全性： 图 3-16 T0时刻的安全序列 truetruetruetr
37、uetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork + AllocationAllocationNeedWork存在安全序列：存在安全序列：P1-P3-P4-P2-P0，系统在系统在T0时刻处于安全状态。时刻处于安全状态。Page 442022-5-24Operating SystemOperating System (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0,
38、2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Page 452022-5-24Operating SystemOperating System 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。 Request1(1，0，2) 2C3B11023C
39、31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Page 462022-5-24Operating SystemOperating System 再利用安全性算法检查此时系统是否安全。 truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocation
40、NeedWork图 3-17 P1申请资源时的安全性检查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足系统处于安全状态，可以满足P1资源分配请求。资源分配请求。Page 472022-5-24Operating SystemOperating System (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0)Available(2, 3, 0)，让P4等待。MaxAllocationNeedAvailableA
41、BCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431/Page 482022-5-24Operating SystemOperating System (4) P0请求资源：P0发出请求向量Request0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020
42、P2902302600P3222211011P4433002431Page 492022-5-24Operating SystemOperating System 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。 Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030图 3-18 为P0分配资源后的有关资源数据 不安全状态Page 502022-5-24Operating SystemOp
43、erating System (5) P0请求资源：P0发出请求向量改为Request0(0, 1, 0)，系统按银行家算法进行检查： Request0(0, 1, 0)Need0(7, 4, 3); Request0(0, 1, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Page 512022-5-24Operating SystemOperating System 系统先假定可为P0分配资源，并修改A
44、vailable, Allocation0和Need0向量，由此形成的资源变化情况如图所示。 Request0(0, 1, 0) 0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Page 522022-5-24Operating SystemOperating System 再利用安全性算法检查此时系统是否安全。 truetruetruetruetrueFinish75532C55332B20212C02010B03110C03312
45、B55320C53322B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork图 3-17 P1申请资源时的安全性检查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足系统处于安全状态，可以满足P0资源分配请求。资源分配请求。Page 532022-5-24Operating SystemOperating Systemq处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产
46、生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除Page 542022-5-24Operating SystemOperating Systemq死锁的检测死锁的检测q死锁的解除死锁的解除Page 552022-5-24Operating SystemOperating System 允许死锁发生，操作系统不断监视系统允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行死锁并以最小的代价恢复操作系统运行Page 56
47、2022-5-24Operating SystemOperating Systemq检测时机检测时机v 当进程等待时检测死锁当进程等待时检测死锁 其缺点是系统的开销大其缺点是系统的开销大v 定时检测定时检测 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁Page 572022-5-24Operating SystemOperating System3.7 死锁的检测与解除死锁的检测与解除 3.7.1 死锁的检测死锁的检测 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须：（1）保存有关资源的请求和分配信息；（2）提供一种算法，以利用这
48、些信息来检测系统是否进入死锁状态。 Page 582022-5-24Operating SystemOperating Systemq资源分配资源分配图图(Resource Allocation Graph)(Resource Allocation Graph) 用有向图描述进程的死锁用有向图描述进程的死锁v优点：准确、形象优点：准确、形象 系统由若干类资源构成，一类资源称系统由若干类资源构成，一类资源称为一个为一个资源类资源类；每个资源类中包含若干个；每个资源类中包含若干个同种资源，称为同种资源，称为资源实例资源实例Page 592022-5-24Operating SystemOperat
49、ing System3.7 死锁的检测与解除死锁的检测与解除 系统死锁可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个对偶G =（N，E），具有下述形成的定义和限制：（1）N被分为两个互斥的子集，一组进程结点P=（p1，p2，pn），一组资源结点R=r1，r2，rn，N=PR。在图3-19所示的例子中：1. 资源分配图资源分配图(Resource Allocation Graph) Page 602022-5-24Operating SystemOperating System3.7 死锁的检测与解除死锁的检测与解除 3.7.1 死锁的检测死锁的检测 1. 资源分配图资源分配图
50、(Resource Allocation Graph) 图 3-19 每类资源有多个时的情况 P=p1，p2，R=r1，r2，N=r1，r2 p1，p2 P1P2r1r2Page 612022-5-24Operating SystemOperating Systemq资源分配图资源分配图v表示法表示法: :资源类资源类: :用方框表示用方框表示（资源的不同类型）（资源的不同类型）资源实例资源实例: :用方框中的用方框中的圆点表示（存在于每圆点表示（存在于每个资源中）个资源中） 进程进程 : :用圆圈中加进程用圆圈中加进程名表示名表示分配边：分配边：资源实例资源实例进进程的一条有向边程的一条有向
