处理机调与死锁part3.pptx

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