《操作系统课程》PPT课件

操作系统概念,第八章：死锁,2,本章主要内容,系统模型死锁特点死锁处理办法死锁预防死锁避免死锁检测死锁恢复,3,死锁问题,一组阻塞进程分别占有一定的资源并等待获取另外一些已经被同组其他进程所占有的资源。实例一系统拥有两个磁带驱动器P1和P2分别占有其中的一台，而且相互需要另外的一台。实例二信号量A和B，初始值都为1P0P1wait(A);wait(B)wait(B);wait(A),4,过桥的实例,5,8.1系统模型,资源类型：R1,R2,RmCPU周期，内存空间，I/O设备每个资源类型Ri有Wi个实例每个进程用以下方式利用资源申请使用释放,6,8.2死锁特点,如果以下四个条件同时满足，那么就会引起死锁互斥：至少有一个资源必须处于非共享模式；即一次只有一个进程使用。如果另一资源申请该资源，那么申请进程必须延迟直到该资源释放为止。占有并等待：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。非抢占：资源不能被抢占；即，只有进程完成其任务之后，才会释放其资源。循环等待：有一组进程P0,P1,Pn，P0等待的资源为P1所占有，P1等待的资源为P2所占有，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。,7,资源分配图,节点的集合V和边的集合EV分为两类PP1,P2,Pn,系统活动进程的集合R=R1,R2,Rm,系统所有资源类型的集合请求边：有向边P1-Rj分配边：有向边Rj-Pi,8,9,资源分配图实例,10,有死锁情况的资源分配图,11,存在环但无死锁的资源分配图,12,基本事实,如果图不包含环，则不存在死锁如果图包含环，则如果每种资源类型只有一个实例，则死锁如果每种资源类型存在若干个实例，则只是有可能会发生死锁。,13,8.3死锁处理方法,可使用协议以预防或避免死锁，确保系统永远不会进入死锁状态可允许系统进入死锁状态，然后检测它，并加以恢复可忽略这个问题，认为死锁不可能在系统内发生。这种方法为绝大多数操作系统如UNIX使用。（鸼鸟算法）,14,8.4死锁预防,出现死锁有四个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生。互斥通常不能通过否定互斥条件来预防死锁。有资源本身是非共享的。占有并等待当一个进程申请一个资源时，它不能占有其他资源。执行前申请并获得所有资源申请其他资源之前，必须释放其现在已分配的所有资源缺点资源利用率可能比较低可能发生饥饿,15,非抢占：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占。通常应用于其状态可以保存和恢复的资源，如CPU寄存器和内存空间，不能适用于其他资源如打印机和磁带驱动器。循环等待对所有资源进行完全排序，且要求每个进程按递增顺序来申请资源,16,8.5死锁避免,避免死锁的另一种方法要求有关如何申请资源的附加信息最简单且有效的模型要求每个进程事先声明它所需要的每种资源的最大数量死锁避免算法动态检查资源分配状态，以保证不存在循环等待的条件。资源分配状态通过可用资源数量、已分配资源数量，及进程最大申请数量来定义,17,安全状态,当一个进程申请一个可用资源的时候，系统必须决定这次分配是否会使系统处在一种安全状态如果存在所有进程的一种安全序列，则系统是安全的进程序列，如果对于每个Pi，Pi申请的资源小于当前可用资源加上所有进程Pj（其中jRj表示进程Pi可能在将来某个时候申请资源Rj，用虚线表示当进程Pi申请资源Rj时，需求边Pi-Rj变成了申请边。当进程Pi释放Rj时，分配边Rj-Pi变成了需求边。系统必须事先要求资源,22,死锁避免的资源分配图,23,资源分配图的不安全状态,24,银行家算法,多实例每个进程必须事先声明资源最大使用量当一个进程申请资源时，有可能必须等待进程得到所有资源后，它必须在某个确定的时间之后将资源返回给系统,25,银行家算法的数据结构,设n为系统进程个数，m为资源类型的种类Available：长度为m的向量。如果availablej=k，那么资源类型Rj现有k个实例Max：nm矩阵定义每个进程的最大需求。如果Maxi,j=k,那么进程Pi最多可申请k个资源类型Rj的实例Allocation：nm矩阵定义每个进程现在所分配的各种资源类型的实例数量。如果AllocationI,j=k，那么进程Pi现在已分配了k个资源类型Rj的实例。Need：nm矩阵表示每个进程还需要的剩余的资源。如果Needi,j=k,那么进程Pi还可能申请k个资源类型Rj的实例。Needi,j=Maxi,jAllocationi,j,26,安全性算法,设Work和Finish分别是长度为m和n的向量。按如下方式进行初始化：Work=AvailableFinishi=false(i=1,2,n)查找这样的i使其满足Finishi=falseNeedi=Work如果没有这样的i存在，那么就转到第4步Work:=Work+AllocationiFinishi:=true返回到第2步如果对所有i，Finishi=true，那么系统处于安全状态,27,对进程Pi的资源请求算法,设Requesti为进程Pi的请求向量。如果Requestij=k,那么进程Pi需要资源类型Rj的实例数量为k。当进程Pi做出资源请求时，会采取如下动作。如果Requesti=Needi，那么转到第2步，否则，产生出错条件，这是因为进程Pi已超过了其请求。如果Requesti=Available，那么转到第3步。否则，Pi必须等待，这是因为没有可用资源。假定系统可以分配给进程Pi所请求的资源，并按如下方式修改状态：Available:=AvailableRequesti;Allocationi:=Allocationi+Requesti;Needi:=NeediRequesti;如果安全，则资源分配给Pi如果不安全，则Pi必须等待，并恢复到原来资源分配状态。,28,算法实例,P0,P1,P2,P3,P4；资源A有10个实例，B有5个实例，C有7个实例在T0时刻AllocationMaxAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433,29,矩阵Need的内容定义成Max-AllocationNeedABCP0743P1122P2600P3011P4431系统是安全的，因为序列满足安全条件,30,现在假定进程P1再请求一个资源类型A和2个资源类型C，这样Request1=(1,0,2)因为Request1Pj表示Pi等待Pj释放一个Pi所需的资源周期性地调用在图中进行搜索的算法从图中检测环的算法需要n2级别操作，其中n为图中的节点数。,33,资源分配图和对应的等待图,34,(二)每种资源类型的多个实例,Available：长度为m的向量，表示各种资源的可用实例Allocation：nm矩阵，表示当前各进程的资源分配情况Request：nm矩阵，表示当前各进程的资源请求情况。如果Requesti,j=k,那么Pi现在需要k个资源Rj,35,检测算法,设Work和Finish分别是长m和n的矢量，初始化如下：Work:=Available对i=1,2,n，如果Allocationi不为0,则Finishi:=false，否则Finishi:=true找出这样的下标i，使之同时满足Finishi=falseRequesti=Work如果没有这样的i，则转到第四步Work:=Work+AllocationiFinishi:=true转到第2步如果对某个i（1=i=n)，Finishi=false，则系统死锁。而且，如果Finishi=false,则进程Pi死锁,36,实例,37,38,应用检测算法,应何时调用检测算法，取决于两个因素：死锁可能发生的频率是多少？当死锁发生时，有多少进程会受影响？当某个进程提出请求且得不到满足时，才会出现死锁，这时可以调用死锁检测算法。但死锁后的每一个请求都会造成死锁。因此，可能需要对于之后的每个请求都调用死锁检测算法，但会引起相当的计算开销。只是在一个不频繁的时间间隔里调用检测算法，如每小时一次或当CPU使用率低于40%时。在不定的时间点调用检测算法，通常不能确定死锁进程中是哪些引起了死锁。,39,8.7死锁恢复,人工处理死锁让系统从死锁状态中自动恢复打破死锁状态有两个方法简单地终止一个或多个进程以打破循环等待从一个或多个死锁进程那里抢占一个或多个资源,40,(一)进程终止,有两种方法通过终止进程以取消死锁终止所有进程一次只终止一个进程直到取消死锁循环为止确定终止哪个进程或哪些进程可以打破死锁需要考虑的因素进程的优先级是什么？进程已计算了多久，进程在完成其指定任务