系统常见死锁问题及处理.ppt

1、韩都衣舍官网 青岛韩都衣舍打折优惠 韩都衣舍怎么样 韩都衣舍官方旗舰店 韩都衣舍韩国衣服之家 ,1,系统常见死锁问题及处理,系统模型 死锁特点 死锁处理方法 死锁预防 死锁避免 死锁检测 死锁恢复,2,系统模型,资源类型：系统拥有的各种资源 资源类型实例：属于某种资源类型的一个资源 进程使用资源原则 使用前申请 使用后释放 总数不能超过系统所有资源总量 进程使用资源顺序 申请 使用 释放 死锁（deadlock）状态：当一组进程的每个进程等待一个事件，而这一事件只能由这一组进程的另一进程引起 “事件”主要指资源获取和释放 “资源”可能是物理资源也可能是逻辑资源,3,引起死锁的两个原因,竞争不可

2、剥夺（抢占）资源 相同资源类型 不同资源类型 进程推进顺序不当 A:Req(R1); B:Req(R2); A:Req(R2); B:Req(R1); A:Rel(R1); A:Rel(R2); A:Rel(R2); B:Rel(R1) 修改请求和释放资源次序可以避免死锁： A:Req(R1); Rel(R1); B:Req(R2); Req(R1); Rel(R2); A:Req(R2); Rel(R2); B:Rel(R1),4,死锁特点,1、死锁的特征（四个必要条件） 互斥 占有并等待 非抢占 循环等待 四个条件同时满足会引起死锁,5,2、资源分配图,用图的方式精确描述死锁问题 资源分配

3、图的构成 节点集合V 进程节点集合P（圆形） 资源类型节点集合R（矩形圆点） 边集合E 申请边：PiRj 分配边： Rj Pi 结论 如果图没有环，那么系统没有进程死锁 如果图有环，那么可能存在死锁 若每个资源类型只有一个实例，有环有死锁（充分必要） 若每个资源类型有多个实例，有环未必死锁（必要不充分）,6,资源分配图例,P1,P2,P3,R4,R3,R2,R1,1、资源分配图,P1,P2,P3,R4,R3,R2,R1,2、存在死锁的资源分配图,7,P1,P2,P3,R2,R1,3、存在环但无死锁的资源分配图,P4,8,思考：,一个计算机系统中有某种资源 10 个，供n个交互型进程使用，每个进

4、程都需要 3 个资源。当n最大为何值时，系统能让尽量多的进程运行完而不会发生死锁？ 死锁是否会只涉及一个进程或一个资源？,n=8,否,9,死锁处理方法,预防或避免死锁 确保系统决不会进入死锁状态 检测死锁，并加以恢复 允许系统进入死锁状态 忽视死锁问题 认为死锁不可能发生 包括UNIX在内的很多操作系统采用,10,死锁预防,主要思想：通过限制资源申请，确保死锁出现的四个必要条件之一不成立 破坏互斥条件 非共享资源：必须有互斥条件 共享资源：不要求互斥访问，不会涉及死锁 破坏占有并等待条件 思想：当一个进程申请一个资源时，不能占有其他资源 每个进程在执行前申请并获得所有资源 允许进程在没有资源时

5、才可申请资源 缺点 资源利用率可能比较低 可能发生饥饿,11,破坏非抢占条件 如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占 破坏循环等待条件 对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源 死锁预防的缺点 设备使用率低 系统吞吐率低,12,死锁避免,主要思想：动态的检测资源分配状态以确保循环等待条件不可能成立 1、安全状态 若存在一个安全序列，则系统处于安全状态 例,最大需求 当前需求 P0 10 5 P1 4 2 P2 9 2,说明：某系统有12台磁带驱动器 P0：最多要求10台 P1：最多要求4台 P2：最多要求9台,P1 分配2；用完释

6、放4；则系统剩余5 P0 分配5；用完释放10；则系统剩余10 P2 分配7；用完释放9；则系统剩余12,13,死锁,不安全,安全,安全、不安全和死锁状态空间,结论： 安全状态不是死锁状态 死锁状态是不安全状态 不是所有不安全状态都是死锁状态,14,2、资源分配图算法,前提：每种资源类型只有一个实例 需求边PiRj表示进程Pi可能在将来某个时刻申请资源Rj,，用虚线表示 如果把需求边转换为申请边继而转换为分配边之后，资源分配图中没有环，那么Pi可以申请并得到Rj,P1,P2,R2,R1,P1,P2,R2,R1,死锁避免的资源分配图 不安全状态,15,3、银行家算法,数据结构 Available

7、：Availablej=k，资源类型Rj 现有k个实例 Max：Maxi,j=k，进程Pi最多可申请k个Rj的实例 Allocation：Allocationi,j=k，进程Pi现在已经分配了k个Rj的实例 Need：Needi,j=k，进程Pi还可能申请k个Rj的实例 Needi,j = Maxi,j - Allocationi,j 符号说明 X=Y（X和Y是长度为n的向量），当且仅当对所有i=1,2,n，Xi=Yi Allocationi 表示分配给进程Pi的资源（将Allocation每行作为向量） Need同Allocation,16,安全性算法,用于确定计算机系统是否处于安全状态 设

8、Work和Finish分别是长度为m和n的向量，初始化Work:=Available，Finishi=false(i=1,2,n) 查找 i 使其满足 Finishi = false Needi =Work 若没有这样的 i 存在，转到4）。 Work := Work + Allocationi Finishi := true 返回到2） 如果对所有 i，Finishi = true，则系统处于安全状态,17,资源请求算法,设Requesti 为进程Pi的请求向量 如果Requesti = Needi ，那么转到第2）步。否则，产生出错条件，因为进程已超过了其请求。 如果Requesti =A

9、vailable，那么转到第3）步。否则， Pi等待，因为没有可用资源。 假定系统可以分配给进程Pi 所请求的资源，并按如下方式修改状态： Available:= Available Requesti ; Allocationi := Allocationi + Requesti ; Needi := Needi Requesti ; 调用安全性算法确定新状态是否安全 安全操作完成且进程Pi分配到其所需要的资源 不安全进程Pi必须等待，并将数据结构恢复到原状态（即 3）的逆操作）,18,银行家算法举例,说明： 5个进程P0P4， 3种资源类型A、B、C，且实例个数分别为10、5、7 T0时刻状

10、态如图所示,Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3,19,问题： T0时刻是否为安全状态？若是，给出安全序列 若在T0时刻进程P1请求资源（1，0，2），是否能实施分配？为什么？ 在（2）的基础上，若进程P4请求资源（3，3，0），是否能实施分配？为什么？ 在（3）的基础上，若进程P0请求资源（ 0，2，0），是否能实施分配？为什么？,20,转换（Need）,21,、T0时刻是安全的，存在

11、安全序列,22,1 Request（1，0，2） Request（1，0，2） 系统试探为P1分配资源后，资源情况是：,2 3 0,4 执行安全性算法，得到安全序列 :, P1请求资源Request(1，0，2), 执行银行家算法:,23, P0请求资源Request（0，2，0） ,执行银行家算法: 1 Request（0，2，0） Request（0，2，0） 系统试探为P0分配资源后，资源情况是：,4 再进行安全性检查，Available(2, 1, 0)不能满足任何进程，进入不安全状态，恢复旧数据结构， P0等待。, P4请求资源Request（3，3，0） ,执行银行家算法: 1 R

12、equest(3, 3, 0) Request(3, 3, 0) =Available(2, 3, 0), P4 等待.,24,练习,Allocation Max Available A B C A B C A B C P1 2 1 2 5 5 9 2 3 3 P2 4 0 2 5 3 6 P3 4 0 5 4 0 11 P4 2 0 4 4 2 5 P5 3 1 4 4 2 4,说明： 5个进程P1P5， 3种资源类型A、B、C，且实例个数分别为17、5、20 T0时刻状态如图所示,25,问题： T0时刻是否为安全状态？若是，给出安全序列 若在T0时刻进程P2请求资源（0，3，4），是否能实

13、施分配？为什么？ 在（2）的基础上，若进程P4请求资源（2，0，1），是否能实施分配？为什么？ 在（3）的基础上，若进程P1请求资源（ 0，2，0），是否能实施分配？为什么？,26,转换（Need）,27,（1）T0时刻是安全的，存在安全序列,28,1 Request（0，3，4） Request（0，3，4）Available（2，3，3）； 没有可用资源，不能分配，需等待！,（2） P2请求资源Request(0，3，4), 执行银行家算法:,29,1 Request（2，0，1） Request（2，0，1） 系统试探为P4分配资源后，资源情况是：,0 3 2,4 执行安全性算法，得到安

14、全序列 :,（3）P4请求资源Request(2，0，1), 执行银行家算法:,30,（4）P1请求资源Request（0，2，0） ,执行银行家算法: 1 Request（0，2，0） Request（0，2，0） 系统试探为P1分配资源后，资源情况是：,4 再进行安全性检查，Available(0, 1, 2)不能满足任何进程，进入不安全状态，恢复旧数据结构， P1等待。,0 1 2,31,死锁检测,对于不采用死锁预防和死锁避免但处理死锁的系统应提供： 一个用来检查系统状态从而确定是否出现了死锁的算法 一个用来从死锁状态中恢复的算法 检测恢复方案会有额外的开销,32,1、每种资源类型只有单

15、个实例,思想：将资源分配图转换成对应的等待图，看是否有环。 转换方法举例如下：,P1,P2,P4,P3,P5,R1,R5,R4,R3,R2,P4,P5,P3,P2,P1,资源分配图,对应的等待图,33,2、每种资源类型有多个实例,思想：类似于银行家算法，描述如下 设Work和Finish分别是长度为m和n的向量，初始化Work:=Available，若 Allocationi不为0，则 Finishi = false，否则，Finishi = true (i=1,2,n) 查找 i 使其满足 Finishi = false Requesti =Work 若没有这样的 i 存在，转到4）。 Wo

16、rk := Work + Allocationi Finishi := true 返回到2） 如果对某个 i，Finishi = false，则系统死锁（进程Pi死锁）,34,例,说明： 5个进程P0P4， 3种资源类型A、B、C，且实例个数分别为7、2、6 T0时刻状态如下,Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2,35,问题： T0时刻是否处于死锁状态？为什么？ 若在T0时刻进程

17、P2请求资源（0，0，1），新的状态是否处于死锁状态？为什么？,36,（1）T0时刻是安全的，存在安全序列,37,Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 1 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2,（2）P2请求资源（0，0，1）后的新状态：,对于i=1,2,3,4，均有Requesti(0,1,0)，因此死锁！,38,3、应用检测算法,何时调用检测算法所取决的因素 死锁可能发生的频率 当死锁发生时，受影响的进程数量 常用方式 对于每个请求都调用死锁检测算法计算开销 在一个不频繁的时间间隔里调用检测算法通常不能确定死锁进程中是哪些