操作系统概念：第八章 死锁

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