处理机调度与死锁pa课件

第三章 处理机调度与死锁 处理机调度与死锁pa课件1第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的层次处理机调度的层次 3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.3 3.3 调度算法调度算法 3.4 3.4 实时调度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 第三章 处理机调度与死锁 处理机调度与死锁pa课件23.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.5.1 产生死锁的原因产生死锁的原因 竞争资源。竞争资源。(2)进程间推进顺序非法。进程间推进顺序非法。第三章 处理机调度与死锁 处理机调度与死锁pa课件31.竞争资源引起进程死锁竞争资源引起进程死锁 可剥夺和非剥夺性资源可剥夺和非剥夺性资源 2)竞争非剥夺性资源竞争非剥夺性资源 3)竞争临时性资源竞争临时性资源 第三章 处理机调度与死锁 处理机调度与死锁pa课件4图 3-12 I/O设备共享时的死锁情况 R1R2P1P2第三章 处理机调度与死锁 处理机调度与死锁pa课件5图 3-13 进程之间通信时的死锁 S2P1S3P3S1P2第三章 处理机调度与死锁 处理机调度与死锁pa课件62.进程推进顺序不当引起死锁进程推进顺序不当引起死锁 1)进程推进顺序合法 图 3-14 进程推进顺序对死锁的影响 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D第三章 处理机调度与死锁 处理机调度与死锁pa课件7 2)进程推进顺序非法 若并发进程P1和P2按曲线所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1,P2保持了资源R2,系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2:Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。第三章 处理机调度与死锁 处理机调度与死锁pa课件83.5.2 产生死锁的必要条件产生死锁的必要条件 互斥条件(2)请求和保持条件(3)不剥夺条件(4)环路等待条件 第三章 处理机调度与死锁 处理机调度与死锁pa课件93.5.3 处理死锁的基本方法处理死锁的基本方法预防死锁。(2)避免死锁。(3)检测死锁。(4)解除死锁。第三章 处理机调度与死锁 处理机调度与死锁pa课件103.6 预防死锁的方法预防死锁的方法 3.6.1 预防死锁预防死锁 摒弃“请求和保持”条件 2.摒弃“不剥夺”条件 3.摒弃“环路等待”条件 第三章 处理机调度与死锁 处理机调度与死锁pa课件113.6.2 系统安全状态系统安全状态 1.安全状态安全状态 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。所谓安全状态，是指系统能按某种进程顺序(P1,P2,，Pn)(称P1,P2,Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。第三章 处理机调度与死锁 处理机调度与死锁pa课件12 2.安全状态之例安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223第三章 处理机调度与死锁 处理机调度与死锁pa课件13【例】用银行家算法判断下述每个状态是否安全。如果一个【例】用银行家算法判断下述每个状态是否安全。如果一个状态是安全的，说明所有进程是如何能够运行完毕的。如果状态是安全的，说明所有进程是如何能够运行完毕的。如果一个状态是不安全的，说明为什么可能出现死锁。一个状态是不安全的，说明为什么可能出现死锁。状态状态A A占有台数占有台数最大需求最大需求用户用户1 1用户用户2 2用户用户3 3用户用户4 42 26 64 47 75 56 60 02 2可供分配的台数可供分配的台数1 1安全安全第三章 处理机调度与死锁 处理机调度与死锁pa课件14状态状态B B占有台数占有台数最大需求最大需求用户用户1 1用户用户2 2用户用户3 3用户用户4 44 48 83 39 95 58 80 02 2可供分配的台数可供分配的台数2 2找不到序列，不安全找不到序列，不安全第三章 处理机调度与死锁 处理机调度与死锁pa课件15 3.由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。第三章 处理机调度与死锁 处理机调度与死锁pa课件16*安全性算法安全性算法 (1)设置两个向量：设置两个向量：工作向量工作向量Work:它表示系统可提供给进程继续运行它表示系统可提供给进程继续运行所需的各类资源数目，它含有所需的各类资源数目，它含有m个元素，在执行安全算法开个元素，在执行安全算法开始时，始时，Work =Available;Finish:它表示系统是否有足够的资源分配给进程，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做使之运行完成。开始时先做Finishi =false;当有足够当有足够资源分配给进程时，资源分配给进程时，再令再令Finishi =true。第三章 处理机调度与死锁 处理机调度与死锁pa课件17 (2)从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若若找到，找到，执行步骤执行步骤(3)，否则，执行步骤否则，执行步骤(4)。(3)当进程当进程Pi获得资源后，可顺利执行，直至完成，并获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：释放出分配给它的资源，故应执行：Workj =Workj+Allocationi,j;Finishi =true;go to step 2;(4)如果所有进程的如果所有进程的Finishi=true都满足，都满足，则表示系则表示系统处于安全状态；否则，系统处于不安全状态。统处于安全状态；否则，系统处于不安全状态。第三章 处理机调度与死锁 处理机调度与死锁pa课件18之前安全状态例题之前安全状态例题 我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223第三章 处理机调度与死锁 处理机调度与死锁pa课件19WorkNeedAllocationWork+AllocationFinish3FalseFalse False 进进 程程 最最 大大 需需 求求 已已 分分 配配 可可 用用 P1P2P310495223P2P1P32 2555 510107 212此时存在一个安全序列此时存在一个安全序列P2,P1,P3，故该状态是安全的。，故该状态是安全的。TrueTrueTrue