操作系统概念本章主要内容n系统模型n死锁特点n死锁处理办法n死锁预防n死锁避免n死锁检测n死锁恢复死锁问题n一组阻塞进程分别占有一定的资源并等待获取另外一些已经被同组其他进程所占有的资源。n实例一n系统拥有两个磁带驱动器nP1 和 P2分别占有其中的一台，而且相互需要另外的一台。n实例二n信号量A和B，初始值都为1 P0 P1wait(A);wait(B)wait(B);wait(A)过桥的实例8.1 系统模型n资源类型：R1, R2, , RmnCPU 周期， 内存空间，I/O设备n每个资源类型Ri有Wi个实例n每个进程用以下方式利用资源n申请n使用n释放8.2 死锁特点n如果以下四个条件同时满足，那么就会引起死锁n互斥：至少有一个资源必须处于非共享模式；即一次只有一个进程使用。如果另一资源申请该资源，那么申请进程必须延迟直到该资源释放为止。n占有并等待：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。n非抢占：资源不能被抢占；即，只有进程完成其任务之后，才会释放其资源。n循环等待：有一组进程P0, P1, , Pn，P0等待的资源为P1所占有，P1等待的资源为P2所占有，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。资源分配图n节点的集合V和边的集合EnV分为两类nP P1, P2, , Pn, 系统活动进程的集合nR = R1, R2, , Rm, 系统所有资源类型的集合n请求边：有向边 P1-Rjn分配边：有向边 Rj-Pi 资源分配图实例有死锁情况的资源分配图存在环但无死锁的资源分配图基本事实n如果图不包含环，则不存在死锁n如果图包含环，则n如果每种资源类型只有一个实例，则死锁n如果每种资源类型存在若干个实例，则只是有可能会发生死锁。8.3 死锁处理方法n可使用协议以预防预防预防预防或避免避免避免避免死锁，确保系统永远不会进入死锁状态n可允许系统进入死锁状态，然后检测检测检测检测它，并加以恢复恢复恢复恢复n可忽略忽略忽略忽略这个问题，认为死锁不可能在系统内发生。这种方法为绝大多数操作系统如UNIX使用。（鸼鸟算法）8.4 死锁预防n出现死锁有四个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生。n互斥n通常不能通过否定互斥条件来预防死锁。有资源本身是非共享的。n占有并等待n当一个进程申请一个资源时，它不能占有其他资源。执行前申请并获得所有资源申请其他资源之前，必须释放其现在已分配的所有资源n缺点资源利用率可能比较低可能发生饥饿 n非抢占：n如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占。n通常应用于其状态可以保存和恢复的资源，如CPU寄存器和内存空间，不能适用于其他资源如打印机和磁带驱动器。n循环等待n对所有资源进行完全排序，且要求每个进程按递增顺序来申请资源8.5 死锁避免n避免死锁的另一种方法要求有关如何申请资源的附加信息n最简单且有效的模型要求每个进程事先声明它所需要的每种资源的最大数量n死锁避免算法动态检查资源分配状态，以保证不存在循环等待的条件。n资源分配状态通过可用资源数量、已分配资源数量，及进程最大申请数量来定义安全状态n当一个进程申请一个可用资源的时候，系统必须决定这次分配是否会使系统处在一种安全状态n如果存在所有进程的一种安全序列，则系统是安全的n进程序列，如果对于每个Pi，Pi申请的资源小于当前可用资源加上所有进程Pj（其中j i）所占有的资源，那么这一顺序为安全序列。如果没有这样的序列存在，则系统状态就处于不安全 n如果系统是安全的，则不会死锁n如果系统不安全，可能会发生死锁n死锁避免：确保系统永远不会进入不安全状态安全、不安全、死锁状态空间例子n考虑一个系统，共有12台磁带驱动器和三个进程P0, P1, P2。其最大需求与当前占有量如下表所示最大需求当前占有P0105P142P292n在时刻t0时，系统处于安全状态，因为顺序满足安全条件。n如果在时刻t1时，进程P2申请并又得到了1台磁带驱动器，系统就不安全了。n为什么？资源分配图算法n除了申请边和分配边外，可引入一新类型的边，称为需求边。n需求边Pi-Rj表示进程Pi可能在将来某个时候申请资源Rj，用虚线表示n当进程Pi申请资源Rj时，需求边Pi-Rj变成了申请边。n当进程Pi释放Rj时，分配边Rj-Pi变成了需求边。n系统必须事先要求资源死锁避免的资源分配图资源分配图的不安全状态银行家算法n多实例n每个进程必须事先声明资源最大使用量n当一个进程申请资源时，有可能必须等待n进程得到所有资源后，它必须在某个确定的时间之后将资源返回给系统银行家算法的数据结构n设n为系统进程个数，m为资源类型的种类nAvailable：长度为m的向量。如果availablej = k，那么资源类型Rj现有k个实例nMax：nm矩阵定义每个进程的最大需求。如果Maxi, j = k, 那么进程Pi最多可申请k个资源类型Rj的实例nAllocation：nm矩阵定义每个进程现在所分配的各种资源类型的实例数量。如果AllocationI, j = k，那么进程Pi现在已分配了k个资源类型Rj的实例。nNeed：nm矩阵表示每个进程还需要的剩余的资源。如果Needi, j = k, 那么进程Pi还可能申请k个资源类型Rj的实例。nNeedi, j = Maxi, j Allocationi, j安全性算法1.设Work和Finish分别是长度为m和n的向量。按如下方式进行初始化：1.Work = Available2.Finishi = false (i = 1, 2, , n)2.查找这样的i使其满足1.Finishi = false2.Needi = Work3.如果没有这样的i存在，那么就转到第4步3.Work := Work + Allocationi1.Finishi := true2.返回到第2步4.如果对所有i，Finishi = true，那么系统处于安全状态对进程Pi的资源请求算法n设Requesti为进程Pi的请求向量。如果Requestij = 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;4.如果安全，则资源分配给Pi5.如果不安全，则Pi必须等待，并恢复到原来资源分配状态。算法实例nP0, P1, P2, P3, P4；资源A有10个实例，B有5个实例，C有7个实例n在T0时刻AllocationMaxAvailable A B CA B CA B CP0 0 1 07 5 33 3 2P1 2 0 03 2 2P2 3 0 29 0 2P3 2 1 12 2 2P4 0 0 24 3 3 n矩阵Need的内容定义成Max-AllocationNeedA B CP07 4 3P11 2 2P26 0 0P30 1 1P44 3 1n系统是安全的，因为序列满足安全条件 n现在假定进程 P1再请求一个资源类型A和2个资源类型C，这样Request1 = (1, 0, 2)n因为Request1 = Available，则假定这个请求可满足，会有如下新状态：AllocationNeedAvailableA B CA B CA B CP00 1 07 4 32 3 0P13 0 20 2 0P23 0 16 0 0P32 1 10 1 1P40 0 24 3 1n执行安全算法，并找到顺序满足安全要求。因此，可以立即允许进程P1的这个请求。8.6 死锁检测n允许系统进入死锁状态n检测算法n恢复机制(一) 每种资源类型只有单个实例n等待图n从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。n节点表示进程nPi-Pj表示Pi等待Pj释放一个Pi所需的资源n周期性地调用在图中进行搜索的算法n从图中检测环的算法需要n2级别操作，其中n为图中的节点数。资源分配图和对应的等待图(二) 每种资源类型的多个实例nAvailable：长度为m的向量，表示各种资源的可用实例nAllocation：nm矩阵，表示当前各进程的资源分配情况nRequest：nm矩阵，表示当前各进程的资源请求情况。如果Requesti, j = k, 那么Pi现在需要k个资源Rj检测算法1.设Work和Finish分别是长m和n的矢量，初始化如下：nWork := Availablen对i = 1, 2, , n，如果Allocationi不为0,则Finishi := false，否则Finishi := true2.找出这样的下标i，使之同时满足nFinishi = falsenRequesti = Workn如果没有这样的i，则转到第四步3.Work := Work + Allocationi1.Finishi := true2.转到第2步4.如果对某个i（1= i = n)，Finishi = false，则系统死锁。而且，如果Finishi = false, 则进程Pi死锁实例 应用检测算法n应何时调用检测算法，取决于两个因素：n死锁可能发生的频率是多少？n当死锁发生时，有多少进程会受影响？n当某个进程提出请求且得不到满足时，才会出现死锁，这时可以调用死锁检测算法。n但死锁后的每一个请求都会造成死锁。因此，可能需要对于之后的每个请求都调用死锁检测算法，但会引起相当的计算开销。n只是在一个不频繁的时间间隔里调用检测算法，如每小时一次或当CPU使用率低于40%时。n在不定的时间点调用检测算法，通常不能确定死锁进程中是哪些引起了死锁。8.7 死锁恢复n人工处理死锁n让系统从死锁状态中自动恢复n打破死锁状态有两个方法n简单地终止一个或多个进程以打破循环等待n从一个或多个死锁进程那里抢占一个或多个资源(一) 进程终止n有两种方法通过终止进程以取消死锁n终止所有进程n一次只终止一个进程直到取消死锁循环为止n确定终止哪个进程或哪些进程可以打破死锁需要考虑的因素n进程的优先级是什么？n进程已计算了多久，进程在完成其指定任务之前还需要多久？n进程使用了多少什么类型的资源（是否容易抢占？）n进程需要多少资源以完成？n多少进程需要被终止？n进程是交互的还是批处理的？(二) 资源抢占n如果要求使用抢占来处理死锁，那么有三个问题需要处理：n选择一个牺牲品n回滚：必须将被抢占进程的状态恢复到某个安全状态n饥饿：如何保证资源不会总是从同一个进程被抢占。作业nP196n8.2 8.4 8.13nP197n8.9 8.13