处理机调与死锁续.pptx

第四章（续）第四章（续）死锁死锁n死锁的基本概念死锁的基本概念n死锁的解决方案死锁的解决方案 （预防，避免，检测及解除）（预防，避免，检测及解除）n资源分配图资源分配图死锁的现象死锁的现象一、死锁的基本概念一、死锁的基本概念1.1.死锁的定义死锁的定义 一组进程中，每个进程都无限等待被该一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为永远无法得到的资源，这种现象称为进进程死锁程死锁，这一组进程就称为，这一组进程就称为死锁进程死锁进程死锁（死锁（Deadlock）饥饿（饥饿（Starvation）参与死锁的进程最少是两个参与死锁的进程最少是两个 （两个以上进程才会出现死锁）（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃甚至导致系统崩溃关于死锁的一些结论关于死锁的一些结论2.产生死锁的原因产生死锁的原因1、争夺资源引起死锁争夺资源引起死锁 例例1：P1，P2两个进程争夺打印机和读卡机。两个进程争夺打印机和读卡机。P1P2打印机 P1P1已经申请到打印机，已经申请到打印机，又申请读卡机。又申请读卡机。P2P2已经申请到读卡机，已经申请到读卡机，又申请打印机。又申请打印机。打印机和读卡机为打印机和读卡机为非剥夺性资源。非剥夺性资源。读卡机n例2、P1，P2，P3 三个进程之间通信：n P1产生消息S1，接收P3产生的消息S3；n P2产生消息S2，接收P1产生的消息S1；n P3产生消息S3，接收P2产生的消息S2；按以下次序运行：P1：Request（S3）；Release（S1）P2：Request（S1）；Release（S2）P3：Request（S2）；Release（S3）2 2、进程推动顺序不当引起的死锁、进程推动顺序不当引起的死锁P1P3S2S3S1P1P2P3按照以上的顺序执行会产生死锁吗？按照以上的顺序执行会产生死锁吗？S Si i临时性资源临时性资源获得获得A获得获得B获得获得A获得获得B释放释放A释放释放B释放释放B释放释放AP请求请求AP请求请求BQ请请求求AQ请请求求B死锁区死锁区P,Q都申请都申请AP,Q都申请都申请B资源资源永久性资源：可以被多个进程多次使用永久性资源：可以被多个进程多次使用（可再用资源）（可再用资源）*可抢占资源可抢占资源n不可抢占资源不可抢占资源临时性资源：只可使用一次的资源；如信临时性资源：只可使用一次的资源；如信号量号量,中断信号，同步信号等（可消耗性中断信号，同步信号等（可消耗性资源）资源）“申请申请-分配分配-使用使用-释放释放”模式模式3.产生死锁的四个必要条件产生死锁的四个必要条件n互斥使用（资源独占）互斥使用（资源独占）n不可强占（不可剥夺）不可强占（不可剥夺）n请求和保持（部分分配，占有申请）请求和保持（部分分配，占有申请）n循环等待循环等待1)互斥使用（资源独占）互斥使用（资源独占）一个资源每次只能给一个进程使用一个资源每次只能给一个进程使用2)不可强占（不可剥夺）不可强占（不可剥夺）资源申请者不能强行的从资源占有者手中资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放夺取资源，资源只能由占有者自愿释放 3)请求和保持请求和保持（部分分配，占有申请）（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有一个进程在申请新的资源的同时保持对原有资源的占有资源的占有（只有这样才是动态申请，动态分配）（只有这样才是动态申请，动态分配）4)循环等待循环等待 存在一个进程等待队列存在一个进程等待队列 P1,P2,Pn,其中其中P1等待等待P2占有的资源，占有的资源，P2等待等待P3占占有的资源，有的资源，Pn等待等待P1占有的资源，占有的资源，形成一个进程等待环路形成一个进程等待环路二、死锁的解决方案二、死锁的解决方案1.产生死锁的例子产生死锁的例子 申请不同类型资源产生死锁申请不同类型资源产生死锁P1P1：申请打印机申请打印机申请扫描仪申请扫描仪使用使用释放打印机释放打印机释放扫描仪释放扫描仪P2P2：申请扫描仪申请扫描仪申请打印机申请打印机使用使用释放打印机释放打印机释放扫描仪释放扫描仪申请同类资源产生死锁申请同类资源产生死锁（如内存）（如内存）设有资源设有资源R R，R R有有m m个分配单位，由个分配单位，由n n个进程个进程P P1 1,P,P2 2,P,Pn n（n mn m）共享。假设每个进）共享。假设每个进程对程对R R的申请和释放符合下列原则：的申请和释放符合下列原则：*一次只能申请一个单位一次只能申请一个单位 *满足总申请后才能使用满足总申请后才能使用 *使用完后一次性释放使用完后一次性释放m=2m=2，n=3n=3资源分配不当导致死锁产生资源分配不当导致死锁产生2.解决死锁的方法解决死锁的方法n鸵鸟策略鸵鸟策略 不理睬死锁。从工程角度考虑死锁概率及解不理睬死锁。从工程角度考虑死锁概率及解决的代价决的代价n预防策略预防策略 破坏死锁的四个必要条件之一破坏死锁的四个必要条件之一n避免策略避免策略 采用某种算法判断资源申请是否满足，以采用某种算法判断资源申请是否满足，以动态地回避死锁动态地回避死锁n检测和解除检测和解除 检测出发生的死锁并采取措施予以解除检测出发生的死锁并采取措施予以解除3.死锁预防死锁预防定义：定义：在系统设计时确定资源分配算法，保在系统设计时确定资源分配算法，保证不发生死锁证不发生死锁 具体的做法是破坏产生死锁的四个必具体的做法是破坏产生死锁的四个必要条件之一要条件之一死锁预防死锁预防破坏破坏“不可剥夺不可剥夺”条件条件 在允许进程动态申请资源前提下规定，在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到一个进程在申请新的资源不能立即得到满足而变为等待状态之前，满足而变为等待状态之前，必须释放已必须释放已占有的全部资源占有的全部资源，若需要再重新申请，若需要再重新申请破坏破坏“请求和保持请求和保持”条件条件 要求每个进程在运行前必须一次性申请要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程它所要求的所有资源，且仅当该进程所要资源均可满足时才给予所要资源均可满足时才给予一次性分一次性分配配死锁预防死锁预防破坏破坏“循环等待循环等待”条件条件 采用资源有序分配法：采用资源有序分配法：把系统中所有资源编号，进程在申请资把系统中所有资源编号，进程在申请资源时必须严格按资源编号的源时必须严格按资源编号的递增次序递增次序进进行，否则操作系统不予分配行，否则操作系统不予分配死锁预防死锁预防如何证明按资源有序分配法进行分配肯定不会产如何证明按资源有序分配法进行分配肯定不会产生死锁？生死锁？ni j 表示：资源表示：资源 Ri 先于资源先于资源 Rjn假设进程假设进程A和和B处于死锁状态，因为处于死锁状态，因为A已已经拥有了经拥有了Ri并申请并申请Rj；同时；同时B已经拥有了已经拥有了Rj并申请并申请Ri。n即：即：nPA:Ri Rj 即有即有 i jnPB:Rj Ri 即有即有 j i破坏破坏“循环等待循环等待”条件条件例如：例如：1 1，2 2，3 3，1010P1：申请申请1申请申请3申请申请9P2：申请申请1申请申请2申请申请5P3 P10回顾回顾n进程调度进程调度n调度算法调度算法n死锁预防死锁预防n破环必要条件破环必要条件4.死锁避免死锁避免n允许死锁前三个条件的成立，但作一定的判断允许死锁前三个条件的成立，但作一定的判断选择以确保永远不会达到死锁点选择以确保永远不会达到死锁点n采用某种算法动态判断当前资源分配请求是否采用某种算法动态判断当前资源分配请求是否有可能导致死锁，如可能导致死锁，则拒绝本有可能导致死锁，如可能导致死锁，则拒绝本次资源申请要求或是中止该进程的运行次资源申请要求或是中止该进程的运行死锁避免定义死锁避免定义定义：定义：在系统运行过程中，对进程发出的每一个在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否配后系统可能发生死锁，则不予分配，否则予以分配则予以分配死锁避免和死锁预防的区别？死锁避免和死锁预防的区别？安全状态与不安全状态安全状态与不安全状态安全状态：安全状态：如果存在一个由系统中所有进程构成的如果存在一个由系统中所有进程构成的安全序列安全序列P P1 1，P Pn n，则系统处于安全状，则系统处于安全状态态死锁避免死锁避免安全序列：安全序列：一个进程序列一个进程序列PP1 1，P Pn n 是安全的，如是安全的，如果对于每一个进程果对于每一个进程P Pi i(1(1i in n），它以后），它以后尚需要的资源量不超过系统当前剩余资尚需要的资源量不超过系统当前剩余资源量与所有进程源量与所有进程P Pj j(j i)(j i)当前占有资当前占有资源量之和，系统处于安全状态源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的安全状态一定是没有死锁发生的)安全状态与不安全状态安全状态与不安全状态不安全状态不安全状态:不存在一个安全序列，不安全不存在一个安全序列，不安全状态可能导致死锁状态可能导致死锁目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量P15105P2242P3297系统剩余量系统剩余量3共有共有12台磁带机台磁带机 T0时刻分配情况如下：时刻分配情况如下：T0时刻是否安全？如果此时时刻是否安全？如果此时P3又请求一台磁又请求一台磁带机，又是否安全？带机，又是否安全？银行家算法银行家算法n n：系统中进程的总数：系统中进程的总数m m：资源类总数：资源类总数Available:Available:ARRAY1.m of integer;ARRAY1.m of integer;Max:Max:ARRAY1.n,1.m of integer;ARRAY1.n,1.m of integer;银行家算法银行家算法Allocation:Allocation:ARRAY1.n,1.m of integer;ARRAY1.n,1.m of integer;Need:Need:ARRAY1.n,1.m of integer;ARRAY1.n,1.m of integer;Request:Request:ARRAY1.n,1.m of integer;ARRAY1.n,1.m of integer;银行家算法银行家算法简记符号：简记符号：AvailableAvailableMaxiMaxiAllocationiAllocationiNeediNeediRequestiRequesti必须满足的关系必须满足的关系1、资源总数、资源总数=可用资源数可用资源数+已分配资源数已分配资源数Ri=AvailableAvailable+AllocationiAllocationi2、申请量不能超过需求量、申请量不能超过需求量RequestiRequesti=NeediNeedi3、已分配数不可能超过它所需的资源数、已分配数不可能超过它所需的资源数AllocationiAllocationi=MaxiMaxi银行家算法银行家算法当进程当进程pipi提出资源申请时，系统执行下列步提出资源申请时，系统执行下列步骤：骤：（1 1）若）若RequestiRequestiNeedi,Needi,转（转（2 2）；）；否则错误返回否则错误返回（2 2）若若RequestiRequestiAvailable,Available,转（转（3 3）；）；否则进程等待否则进程等待(3(3）假设系统分配了资源，则有：）假设系统分配了资源，则有：Available:=Available-Requesti;Available:=Available-Requesti;Allocationi:=Allocationi:=Allocationi+Requesti;Allocationi+Requesti;Needi:=Needi-RequestiNeedi:=Needi-Requesti若系统新状态是安全的，则分配完成若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，若系统新状态是不安全的，则恢复原状态，进程等待进程等待银行家算法银行家算法为进行安全性检查，定义数据结构：为进行安全性检查，定义数据结构：Work:ARRAY1.m of integer;Work:ARRAY1.m of integer;Finish:ARRAY1.n of Boolean;Finish:ARRAY1.n of Boolean;银行家算法银行家算法安全性检查的步骤：安全性检查的步骤：(1)Work:=Available;(1)Work:=Available;Finish:=false;Finish:=false;(2)(2)寻找满足条件的寻找满足条件的i i：a.Finishi=false;a.Finishi=false;b.Needi b.NeediWorkWork;如果不存在，则转如果不存在，则转(4)(4)银行家算法银行家算法(3)Work:=Work+Allocationi;(3)Work:=Work+Allocationi;Finishi:=true;Finishi:=true;转转(2)(2)(4)(4)若对所有若对所有i,Finishi=true,i,Finishi=true,则系则系统处于安全状态，否则处于不安全统处于安全状态，否则处于不安全状态状态MaxA B CP07 5 3 P1P22P3AllocationA B CNeedA B CAvailableA B C资源资源进程进程0 1 0 7 4 3 3 3 2 3 2 2 2 0 0 1 2 2 9 2 0 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3 1 P4假设系统中有假设系统中有5个进程和个进程和3类资源，各种资源的数量类资源，各种资源的数量分别为分别为10、5、7。在。在T0时刻的资源分配图如下时刻的资源分配图如下T0时刻的安全性？安全序列时刻的安全性？安全序列?若若P1申请申请(1,0,2)，能否分配？，能否分配？(3 0 2)(0 2 0)(2 3 0)死锁避免策略死锁避免策略（Deadlock avoidance strategyDeadlock avoidance strategy）当一个进程请求一组资源时，假设请求得到准许当一个进程请求一组资源时，假设请求得到准许，相应地改变系统状态，然后决定结果是否是安相应地改变系统状态，然后决定结果是否是安全状态。如果是的话，那么准许该请求或者全状态。如果是的话，那么准许该请求，或者说给该进程分配相应的资源；否则，拒绝本次说给该进程分配相应的资源；否则，拒绝本次资源分配请求，即阻塞该进程直至准许该请求资源分配请求，即阻塞该进程直至准许该请求 还能保证安全状态。还能保证安全状态。即：即：通过银行家算法，确保进程和资源总是处于安通过银行家算法，确保进程和资源总是处于安全状态。全状态。死锁检测：死锁检测：允许死锁发生，操作系统不断监视系允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系解除死锁并以最小的代价恢复操作系统运行统运行5.5.死锁的检测与解除死锁的检测与解除死锁的检测与解除死锁的检测与解除检测时机：检测时机：当进程等待时检测死锁当进程等待时检测死锁 （其缺点是系统的开销大）（其缺点是系统的开销大）定时检测定时检测 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁死锁的解除死锁的解除 重要的是以最小的代价恢复系统的运行。重要的是以最小的代价恢复系统的运行。有如下几种方法：有如下几种方法：1 1）重新启动）重新启动 2 2）撤消进程）撤消进程 3 3）剥夺资源）剥夺资源 4 4）进程回退）进程回退三、资源分配图三、资源分配图 用有向图描述进程的死锁用有向图描述进程的死锁 准确、形象准确、形象 系统由若干类资源构成，一类资源称为一系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同个资源类；每个资源类中包含若干个同种资源，称为资源实例种资源，称为资源实例资源分配图资源分配图 二元组二元组G=G=（V V，E E）V V：结点集，分为：结点集，分为P P，R R两部分两部分 P=p1,p2,P=p1,p2,pn,pn R=r1,r2,R=r1,r2,rm,rm E E：边的集合，其元素为有序二元组：边的集合，其元素为有序二元组 (pi,rj)(pi,rj)或或(rj,pi)(rj,pi)资源分配图资源分配图表示法表示法资源类（资源的不同类型）资源类（资源的不同类型）用方框表示用方框表示资源实例（存在于每个资源中）资源实例（存在于每个资源中）用方框中的黑圆点表示用方框中的黑圆点表示进程进程 用圆圈中加进程名表示用圆圈中加进程名表示资源分配图资源分配图分配边：分配边：资源实例资源实例进程的一条有向边进程的一条有向边申请边：申请边：进程进程资源类的一条有向边资源类的一条有向边有环有死锁有环有死锁有环无死锁有环无死锁资源分配图资源分配图死锁定理死锁定理 如果资源分配图中没有环路，则系统中如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中没有死锁，如果图中存在环路则系统中可能存在死锁可能存在死锁 如果每个资源类中只包含一个资源实例，如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件则环路是死锁存在的充分必要条件资源分配图资源分配图资源分配图化简：资源分配图化简：1 1）找一个非孤立点进程结点且只有分配边，）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点去掉分配边，将其变为孤立结点2 2）再把相应的资源分配给一个等待该资源）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配的进程，即将某进程的申请边变为分配边边How to Reduce a Resource Allocation Graph?R1R2R3P1P3P2P4How to Reduce a Resource Allocation Graph?R1R2R3P1P3P2P4How to Reduce a Resource Allocation Graph?R1R2R3P1P3P2P4死锁定理死锁定理n引理：引理：一个给定的一个给定的 进程进程资源图资源图 的全部化简的全部化简序列导致序列导致 同一同一 不可化简图。不可化简图。n死锁定理：死锁定理：S S是死锁状态，当且仅当是死锁状态，当且仅当S S的的 进程进程-资资源图不是可完全化简图。源图不是可完全化简图。Summary三级调度三级调度Summary(cont.)Summary(cont.)死锁死锁死锁死锁原因原因资源资源竞争竞争进程进程推进推进顺序顺序不当不当死锁死锁必要必要条件条件环路环路等待等待条件条件不剥不剥夺条夺条件件请求请求和保和保持条持条件件互斥互斥条件条件死锁死锁预防预防死锁死锁避免避免死锁死锁检测检测死锁死锁解除解除银行银行家算家算法法破坏破坏四个四个必要必要条件条件中的中的一个一个化简化简资源资源分配分配图图剥夺剥夺资源资源撤消撤消进程进程死锁死锁处理处理死锁死锁定理定理Problem 1n下列调度算法中，不是作业调度算法的下列调度算法中，不是作业调度算法的有有 ，。A.轮转法轮转法 B.优先数法优先数法 C.先来先服务法先来先服务法 D.多级反馈队列算法多级反馈队列算法【思考与练习思考与练习】某系统中有某系统中有11台打印机，台打印机，N个进程共享打个进程共享打印机资源，每个进程要求印机资源，每个进程要求3台。当台。当N的取的取值不超过值不超过 时，系统不会发生死锁。时，系统不会发生死锁。Problem 2n某个系统使用多级反馈队列法，总共设置了某个系统使用多级反馈队列法，总共设置了六级队列，假设第一级队列的时间片长度为六级队列，假设第一级队列的时间片长度为2秒，以后每一级的时间片长度都是上一级秒，以后每一级的时间片长度都是上一级长度的两倍。现在需要执行一个运行时间为长度的两倍。现在需要执行一个运行时间为31秒种的进程，则该进程的执行将被中断秒种的进程，则该进程的执行将被中断 次，它在第次，它在第 级队列是完成运行。级队列是完成运行。Problem 3n设系统中仅有一个资源类，其中共有设系统中仅有一个资源类，其中共有3个个资源实例，使用此类资源的进程共有资源实例，使用此类资源的进程共有3个，个，每个进程至少请求一个资源，它们所需每个进程至少请求一个资源，它们所需资源最大量的总和为资源最大量的总和为X，则发生死锁的必，则发生死锁的必要条件是：要条件是：。(当当X满足什么条件时？满足什么条件时？)Problem 4n现有如下作业序列现有如下作业序列 作业作业1 提交时间提交时间8.00，完成时间，完成时间1.00；作业作业2 提交时间提交时间8.30，完成时间，完成时间3.00；作业作业3 提交时间提交时间9.00，完成时间，完成时间0.10；作业作业4 提交时间提交时间9.30，完成时间，完成时间0.50；试用试用FCFS和和SJF调度算法处理，问哪种调调度算法处理，问哪种调度算法性能更好？度算法性能更好？Problem 5n假定系统有进程集合假定系统有进程集合P0,P1,P2,P3,P4，资，资源集合（源集合（A,B,C），资源数量为（），资源数量为（10，8，7）。某时刻系统状态如图。）。某时刻系统状态如图。试给出进程的剩余请求矩阵并判断当前试给出进程的剩余请求矩阵并判断当前系统是否处于安全状态？系统是否处于安全状态？AllocationMaxAvailableP0020773331P1210332P2302912P3212233P4012434Problem 6n关于处理机调度，试问：关于处理机调度，试问：（1）什么是处理机三级调度？）什么是处理机三级调度？（2）处理机三级调度分别在什么情况下）处理机三级调度分别在什么情况下发生？发生？（3）各级调度分别完成什么工作？）各级调度分别完成什么工作？Problem 7n有有5个进程个进程A,B,C,D,E。它们到达的时间。它们到达的时间分别是分别是:0,1,2,3,4。所要求服务的时间分别。所要求服务的时间分别是：是：4,3,5,2,4。分别采用（。分别采用（1）先来先服）先来先服务（务（FCFS）调度算法；（）调度算法；（2）短作业优）短作业优先（先（SJF）调度算法）调度算法;(3)时间片轮转调度时间片轮转调度算法算法(设时间片设时间片=1)。分别计算每个进程的。分别计算每个进程的平均周转时间及平均带权周转时间。平均周转时间及平均带权周转时间。Problem 8在银行家算法中，若出现下述资源分配情况在银行家算法中，若出现下述资源分配情况 试问：试问：（1）该状态是否安全？）该状态是否安全？（2）如果进程）如果进程P2提出请求提出请求Request2（1，2，2，2）后，系统能否将资源分配给它？）后，系统能否将资源分配给它？AllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656