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