处理机调度与死锁续PPT课件.ppt

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