操作系统课程.pptx

《操作系统课程.pptx》由会员分享，可在线阅读，更多相关《操作系统课程.pptx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1本章主要内容系统模型死锁特点死锁处理办法死锁预防死锁避免死锁检测死锁恢复第1页/共42页2死锁问题一组阻塞进程分别占有一定的资源并等待获取另外一些已经被同组其他进程所占有的资源。实例一系统拥有两个磁带驱动器P1 和 P2分别占有其中的一台，而且相互需要另外的一台。实例二信号量A和B，初始值都为1 P0 P1wait(A);wait(B)wait(B);wait(A)第2页/共42页3过桥的实例第3页/共42页48.1 系统模型资源类型：R1,R2,RmCPU 周期，内存空间，I/O设备每个资源类型Ri有Wi个实例每个进程用以下方式利用资源申请使用释放第4页/共42页58.2 死锁特点如果以下

2、四个条件同时满足，那么就会引起死锁互斥：至少有一个资源必须处于非共享模式；即一次只有一个进程使用。如果另一资源申请该资源，那么申请进程必须延迟直到该资源释放为止。占有并等待：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。非抢占：资源不能被抢占；即，只有进程完成其任务之后，才会释放其资源。循环等待：有一组进程P0,P1,Pn，P0等待的资源为P1所占有，P1等待的资源为P2所占有，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。第5页/共42页6资源分配图节点的集合V和边的集合EV分为两类P P1,P2,Pn,系统活动进程的集合R=R1,R2,Rm,系统所有

3、资源类型的集合请求边：有向边 P1-Rj分配边：有向边 Rj-Pi第6页/共42页7 第7页/共42页8资源分配图实例第8页/共42页9有死锁情况的资源分配图第9页/共42页10存在环但无死锁的资源分配图第10页/共42页11基本事实如果图不包含环，则不存在死锁如果图包含环，则如果每种资源类型只有一个实例，则死锁如果每种资源类型存在若干个实例，则只是有可能会发生死锁。第11页/共42页128.3 死锁处理方法可使用协议以预防预防或避免避免死锁，确保系统永远不会进入死锁状态可允许系统进入死锁状态，然后检测检测它，并加以恢复恢复可忽略忽略这个问题，认为死锁不可能在系统内发生。这种方法为绝大多数操作

4、系统如UNIX使用。（鸼鸟算法）第12页/共42页138.4 死锁预防出现死锁有四个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生。互斥通常不能通过否定互斥条件来预防死锁。有资源本身是非共享的。占有并等待当一个进程申请一个资源时，它不能占有其他资源。执行前申请并获得所有资源申请其他资源之前，必须释放其现在已分配的所有资源缺点资源利用率可能比较低可能发生饥饿第13页/共42页14 非抢占：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占。通常应用于其状态可以保存和恢复的资源，如CPU寄存器和内存空间，不能适用于其他资源如打印机和磁带驱动器。循环等待对所

5、有资源进行完全排序，且要求每个进程按递增顺序来申请资源第14页/共42页158.5 死锁避免避免死锁的另一种方法要求有关如何申请资源的附加信息最简单且有效的模型要求每个进程事先声明它所需要的每种资源的最大数量死锁避免算法动态检查资源分配状态，以保证不存在循环等待的条件。资源分配状态通过可用资源数量、已分配资源数量，及进程最大申请数量来定义第15页/共42页16安全状态当一个进程申请一个可用资源的时候，系统必须决定这次分配是否会使系统处在一种安全状态如果存在所有进程的一种安全序列，则系统是安全的进程序列，如果对于每个Pi，Pi申请的资源小于当前可用资源加上所有进程Pj（其中j i）所占有的资源，

6、那么这一顺序为安全序列。如果没有这样的序列存在，则系统状态就处于不安全第16页/共42页17 如果系统是安全的，则不会死锁如果系统不安全，可能会发生死锁死锁避免：确保系统永远不会进入不安全状态第17页/共42页18安全、不安全、死锁状态空间第18页/共42页19例子考虑一个系统，共有12台磁带驱动器和三个进程P0,P1,P2。其最大需求与当前占有量如下表所示最大需求当前占有P0105P142P292在时刻t0时，系统处于安全状态，因为顺序满足安全条件。如果在时刻t1时，进程P2申请并又得到了1台磁带驱动器，系统就不安全了。为什么？第19页/共42页20资源分配图算法除了申请边和分配边外，可引入

7、一新类型的边，称为需求边。需求边Pi-Rj表示进程Pi可能在将来某个时候申请资源Rj，用虚线表示当进程Pi申请资源Rj时，需求边Pi-Rj变成了申请边。当进程Pi释放Rj时，分配边Rj-Pi变成了需求边。系统必须事先要求资源第20页/共42页21死锁避免的资源分配图第21页/共42页22资源分配图的不安全状态第22页/共42页23银行家算法多实例每个进程必须事先声明资源最大使用量当一个进程申请资源时，有可能必须等待进程得到所有资源后，它必须在某个确定的时间之后将资源返回给系统第23页/共42页24银行家算法的数据结构设n为系统进程个数，m为资源类型的种类Available：长度为m的向量。如果

8、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,j Allocationi,j第24页/共42页25安全性算法1.设Work和Finish分别是长度为m和n的向量。按如下方式进行初

9、始化：Work=AvailableFinishi=false(i=1,2,n)2.查找这样的i使其满足Finishi=falseNeedi=Work如果没有这样的i存在，那么就转到第4步3.Work:=Work+AllocationiFinishi:=true返回到第2步4.如果对所有i，Finishi=true，那么系统处于安全状态第25页/共42页26对进程Pi的资源请求算法设Requesti为进程Pi的请求向量。如果Requestij=k,那么进程Pi需要资源类型Rj的实例数量为k。当进程Pi做出资源请求时，会采取如下动作。1.如果Requesti=Needi，那么转到第2步，否则，产生

10、出错条件，这是因为进程Pi已超过了其请求。2.如果Requesti=Available，那么转到第3步。否则，Pi必须等待，这是因为没有可用资源。3.假定系统可以分配给进程Pi所请求的资源，并按如下方式修改状态：1.Available:=Available Requesti;2.Allocationi:=Allocationi+Requesti;3.Needi:=Needi Requesti;如果安全，则资源分配给Pi如果不安全，则Pi必须等待，并恢复到原来资源分配状态。第26页/共42页27算法实例P0,P1,P2,P3,P4；资源A有10个实例，B有5个实例，C有7个实例在T0时刻Allo

11、cationMaxAvailable 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第27页/共42页28 矩阵Need的内容定义成Max-AllocationNeedA B CP07 4 3P11 2 2P26 0 0P30 1 1P44 3 1系统是安全的，因为序列满足安全条件第28页/共42页29 现在假定进程 P1再请求一个资源类型A和2个资源类型C，这样Request1=(1,0,2)因为Request1=Available，则假定这个请求可满足，会有如下新状态

12、：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的这个请求。第29页/共42页308.6 死锁检测允许系统进入死锁状态检测算法恢复机制第30页/共42页31(一)每种资源类型只有单个实例等待图从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。节点表示进程Pi-Pj表示Pi等待Pj释放一个Pi所需的资源周期性地调用在图中进行搜索的算法从图中检测环的算法需要

13、n2级别操作，其中n为图中的节点数。第31页/共42页32资源分配图和对应的等待图第32页/共42页33(二)每种资源类型的多个实例Available：长度为m的向量，表示各种资源的可用实例Allocation：nm矩阵，表示当前各进程的资源分配情况Request：nm矩阵，表示当前各进程的资源请求情况。如果Requesti,j=k,那么Pi现在需要k个资源Rj第33页/共42页34检测算法1.设Work和Finish分别是长m和n的矢量，初始化如下：Work:=Available对i=1,2,n，如果Allocationi不为0,则Finishi:=false，否则Finishi:=true

14、2.找出这样的下标i，使之同时满足Finishi=falseRequesti=Work如果没有这样的i，则转到第四步3.Work:=Work+Allocationi1.Finishi:=true2.转到第2步4.如果对某个i（1=i=n)，Finishi=false，则系统死锁。而且，如果Finishi=false,则进程Pi死锁第34页/共42页35实例第35页/共42页36 第36页/共42页37应用检测算法应何时调用检测算法，取决于两个因素：死锁可能发生的频率是多少？当死锁发生时，有多少进程会受影响？当某个进程提出请求且得不到满足时，才会出现死锁，这时可以调用死锁检测算法。但死锁后的每一

15、个请求都会造成死锁。因此，可能需要对于之后的每个请求都调用死锁检测算法，但会引起相当的计算开销。只是在一个不频繁的时间间隔里调用检测算法，如每小时一次或当CPU使用率低于40%时。在不定的时间点调用检测算法，通常不能确定死锁进程中是哪些引起了死锁。第37页/共42页388.7 死锁恢复人工处理死锁让系统从死锁状态中自动恢复打破死锁状态有两个方法简单地终止一个或多个进程以打破循环等待从一个或多个死锁进程那里抢占一个或多个资源第38页/共42页39(一)进程终止有两种方法通过终止进程以取消死锁终止所有进程一次只终止一个进程直到取消死锁循环为止确定终止哪个进程或哪些进程可以打破死锁需要考虑的因素进程的优先级是什么？进程已计算了多久，进程在完成其指定任务之前还需要多久？进程使用了多少什么类型的资源（是否容易抢占？）进程需要多少资源以完成？多少进程需要被终止？进程是交互的还是批处理的？第39页/共42页40(二)资源抢占如果要求使用抢占来处理死锁，那么有三个问题需要处理：选择一个牺牲品回滚：必须将被抢占进程的状态恢复到某个安全状态饥饿：如何保证资源不会总是从同一个进程被抢占。第40页/共42页41作业P1968.2 8.4 8.13P1978.9 8.13第41页/共42页42感谢您的观看！第42页/共42页