补充课件4：死锁概念引入.ppt

2.8 死 锁 在多道程序系统中，并发进程改善了系统资源利用率 和提高系统的吞吐量，但可能死锁。 例一个计算机系统，它有4台磁带机和2个并发执行的进 程。某一时刻，每一进程都已占有2台磁带机，还要再 请求一台磁带机才能完成它们的任务。这时，由于系 统再无空闲的磁带机，两个进程就处于永远的等待状 态，我们就说系统产生了死锁。 2.8.1 死锁的定义和死锁产生的必要条件 1. 资源的特性 l硬件资源：如打印机、磁带机、主存等。 l软件资源：如共享变量、数据库中的加锁记录。 l可抢占资源：是这样一类资源，当资源从占用进程剥夺走 时，对进程不产生什么破坏性的影响。如主存、CPU。 l不可抢占资源：一旦分配，不能强收回，只能由其自动释 放。如打印机、磁带机。通常情况下，死锁涉及的是不可 抢占资源。 一个进程必须按下述三个顺序事件使用资源。 （1）请求资源：若请求不能立即满足，则申请者 等待。 （2）使用资源：获得资源后，可使用它。 （3）释放资源：使用完毕，将资源归还系统。 2. 死锁的定义 死锁：是指多个进程因竞争资源而造成的一种僵 局，若无外力作用，这些进程都将永远不能向 前推进。 l资源互斥使用：任一时刻只允许一个进程使用 资源 l部分分配：进程在请求其余资源时，不主动释 放已经占用的资源 l不可剥夺性：进程已经占用的资源，不会被强 制剥夺 l环路等待：环路中的每一条边是进程在请求另 一进程已经占有的资源。 3. 死锁产生的必要条件 2.8.2 解决死锁的方法 l用有向图研究解决死锁的方法。 l图中圆圈代表进程，方块代表资源。 l资源已经分配给进程用从资源 (方块)到进程 ( 圆圈)的有向弧表示； l进程请求该资源用从进程到资源的有向弧表 示。 图2.10给出进程对资源的可能情况。 T D U C 图2.10 资源分配图 (a) 分配 了一个 资源 (b) 进程B 请求一个资 源 (c)进程D和进程C 已处于死锁状态 RS AB 处理死锁的基本方法 可归结为以下4种 l鸵鸟算法。忽略死锁。 l预防死锁。通过设置某些限制条件，去破坏产生死锁 的四个必要条件中的一个或几个条件，来防止发生死 锁。 l避免死锁。是在资源的动态分配过程中，用某种方法 去防止系统进入不安全状态，从而避免发生死锁。 l检测和恢复死锁。允许死锁发生，通过设置检测机构 ，及时检测出死锁的发生，然后采取适当措施清除死 锁。 解决死锁的方法 1 鸵鸟算法（置之不理） l是解决死锁的最简单方法。即像鸵鸟一样，当遇到危 险时，将头埋进沙子里，假装毫无问题。 l当死锁在计算机中很少出现时，比如说每五年或更长 时间才出现一次时，人们就不必花费更多的精力去解 决它，而是采用类似鸵鸟一样的办法忽略它。 例 UNIX系统，它潜在地存在死锁，但它并不花功夫去 检测和解除死锁，而是忽略不去理它。 2 死锁的检测和恢复 死锁的检测和恢复技术：是指定期启动一个软 件检测系统的状态，若发现有死锁存在，则采取 措 施恢复之。 (1)死锁的检测 方法：由软件检查系统中由进程和资源构成 的 有向图是否构成一个或多个环路，若是，则存在 死 锁，否则不存在。 例假定系统有七个进程:AG;六个资源:RW。资 源 的使用情况如下: l进程A保持资源R，请求资源S。 l进程B没有保持资源，请求资源T。 l进程C也没有保持资源，请求S资源。 l进程D保持资源U，请求S和T资源。 l进程E保持T，请求V资源。 l进程F保持W，请求S资源。 l进程G保持V，请求U资源。 进程资源图如图2.11 A RS BT CS U DS TT V E WFS VGU 图2.11 进程资源图 R S W U T V A C F D G B E 环路 死锁 环路：DTEVGUD D、E、G是死锁进程 一个简单的死锁检测算法 需要一个数据结构L，用来记录系统中各节点的情况 。执行过程中，标记已检测过的弧。 类似于有向图的遍历。 对于图中的每个节点N，以N为起始节点，执行以下5步 。 将L初始化为空表，以表示所有弧都未标记过。 将当前节点加到L的末端，检查这个节点在表中是否出 现过。如果是，这个图包含一个环路，算法终止。如 果没有，转。 由这个节点再看，是否有未标记的引出弧。如果 有，转；若没有，转。 任意选择一个未标记的引出弧并标记它。然后， 将引出弧所到节点作为新的当前节点，转。 若所有从这个节点引出的弧都已标记，则返回到 前一个节点，如果这个节点是最初开始的节点， 这个图没有包含环路，算法终止；若不是初始节 点，再以该节点作为当前节点，转。 以图2.11为例： l假定从上到下，从左到右。从R开始，然后依次为A， B，C，S，D，T，E，F等。若找到了一个环路，该算 法终止。 l以R为起始节点并将L初始化为空表。将R加入表中，从 R出发，只有一个未标记的弧，标记它，随后它指向A ，将A加入L中，此时 L=R,A。由A到S也只有一个 未标记弧，标记它，将S加入表中，L=R,A,S。由 于S没有引出弧，S为终结节点，由S回退到A。由于A没 有未标记的弧，再回退到R，完成了对R的检测。 l以A为起始节点开始这个算法,重置L为空。这次检索很 快停止(因为A又指向S)。 l再从B开始。由B跟踪引出弧一直到D,得 L=B,T,E,V,G,U,D。此时D有两条引出弧,若向S方向, 由前面可知,S是终结节点(没有引出弧)。因此,由D只能 向T前进,并修改 L=B,T,E,V,G,U,D,T,由表中看出,T 出现两次,因此,该图包含环路,停止算法的执行。由于 存在环路,故存在死锁。死锁进程为D、E、G。这和我们 前面分析的一致。 (2)死锁的恢复 l取消所有的死锁进程。不管相信与否，这是OS中最常采 用的方法。 l滚回一些进程。把每个死锁进程备份到前面定义的某些 检查点，并且重新启动所有进程。这要求在系统中构造 重新运行和重新启动机制。并发进程的不确定性通常能 保证不会发生原来的死锁。 l连续取消死锁进程，直到环路断开，不再存在死锁。选 择取消进程的顺序基于某种最小代价原则。在每次取消 后，必须重新调用检查算法，以测试是否仍存在死锁。 l连续剥夺资源直到不再存在死锁。和第三个一样，需 要使用一种基于成本的选择方法，并且需要在每次剥 夺后重新调用检测算法。一个资源被剥夺的进程必须 退回到前面获得这个资源的地方。 选择原则 目前为之消耗的处理器时间最少； 目前为止产生的输出最少； 预计剩下的时间最长； 目前为止分配的资源总量最少； 优先级最低。 基本思想：允许进程动态地申请资源，一次申请一 部分资源。系统在进行资源分配之前，先计算资源分配 的安全性。若此次分配不会导致系统进入不安全状态， 便将资源分配给进程；否则，进程等待。 安全状态：是指系统能按某种顺序，如p1 , p2 , , pn (安全序列)，来为每个进程分配其所需资源，直至最大 需 求，使每个进程都可顺序完成。 3 死锁的避免 (1)资源轨迹法 l避免死锁的主要方法是以系统的安全状态为 基础的。 l 先引入一个容易理解的图2.12讨论安全的概 念。 获得A 获得B 释放A 释放B 获得B 获得A 释放B 释放A Q进程的进展 P进程的进展 12 3 4 5 6 都想要A 都想要B 图2.12 一个单处理器系统的进程资源轨迹图 水平段表示 P执行 垂直段表示Q执行 1.Q获得B，然后获得A；然后释放B和A；当P恢复执行时，它可以获得 全部资源。 2.Q获得B，然后获得A；P执行并阻塞在对A的请求上；Q释放B和A；当P 恢复执行时，它可以获得全部资源。 3.Q获得B；然后P获得A；由于在继续执行时，Q阻塞在A上而P阻塞在B 上，死锁是不可避免的。 4.P获得A；然后Q获得B；由于在继续执行时，Q阻塞在A上而P阻塞在B 上，死锁是不可避免的。 5.P获得A，然后获得B；Q执行并阻塞在对B的请求上；P释放A和B；当Q 恢复执行时，它可以获得全部资源。 6. P获得A，然后获得B；然后释放A和B；当Q获得执行时，它可以获 得全部资源。 (2)银行家算法 l最具代表性的避免死锁的算法是Dijkstra的 银行家算法，是在1965年提出的。 l这是由于该算法能用于银行系统现金贷款的 发放而得名。 l这个算法正是利用了上面图中介绍的避免进 程进入不安全区的原理。 单资源银行家算法 例单资源银行家算法用来模拟一个小城镇银行家为一批 顾 客贷款问题。 有四个顾客：A，B，C，D，每个顾客提出的最大贷款 量 分别为6、5、4、7个单位(以千美元为单位)。银行家知道 不 是所有顾客都立即需要22个单位的贷款。他只需准备10个 单 位(可少付一半准备金利率)为这些顾客服务。在这个模型 中， 顾客是进程，资源是银行贷款，而银行家就是操作系统。 如 图2.13所示。 系统拥有量:10 (a)初始状态 当前剩余量:2 (b)安全状态 当B请求1个时 当前剩余量:1 (c)不安全状态 图2.13 资源三种分配状态 C得到全部贷款后，很快将其全部贷款还清 多资源银行家算法 先定义相关变量或术语： lAvailable:系统初始资源向量, 系统初始拥有的资源向量, 从第二轮以后,就是系统剩余的资源向量:一个含有m个元 素的数组,每个元素代表一类资源拥有数目。 lMaxneed:最大资源需求矩阵,初始称进程Pi最大资源需求 矩阵,从第二轮以后,就称进程Pi剩余资源需求矩阵。n个 含有m个元素的向量组即nm矩阵,Maxneed(i,j)=k表示进 程Pi需要j类资源最大数目为k。 lDemator:最大资源需求向量:一个含有m个元素的数组, 每个元素代表一类资源最大需求数目，其中j分量为最大 资源需求矩阵j列元素之和。 lAlloctrix:已分配资源矩阵,自始至终是系统对进程Pi资源 需求的分配方案:nm矩阵，Allocable(i,j)=k表示进程i当 前已分得j类资源数目为k。 lAllocator:已分配资源向量,一个含有m个元素的数组,每 个元素代表一类资源已分配数目，其中j分量为已分配资 源矩阵j列元素之和。 lRemneed:剩余资源需求矩阵,即【上一轮剩余需求矩阵 】减【下一轮已分配矩阵】之差,初始为最大需求矩阵 :nm矩阵,Remneed(i,j)=k表示进程Pi 还需要j类资源k个 。 lRequesti:进程Pi的剩余资源需求向量,即剩余需求矩阵 Remneed第i行向量。若Requestij=k,表示进程Pi还需 要k个j类资源。 选中剩余需求矩阵中的Requesti,按下述步骤进行检测: 若RequestiMaxneedi则转,否则所需资源数超过进程 Pi申报的最大需求量,停止检测; 若RequestiAvailable则转;否则表示系统中尚无足 够资源,进程Pi必须等待; 系统将所需资源试分配给进程Pi,并更新下面相关变量的 值： Available=Available Requesti （1）资源剩余率 Allocationi = Allocationi + Requesti （2）资源满足或释放 率 Needi = Needi Requesti （3）标记终止进程 检测此次试分配,是否可使系统处于安全状态,即综合检测 上述(1)(2)(3)是否处于安全状态注:若综合检测安全,也即 系统安全检测通过,则将资源正式分给进程Pi,进程Pi最终 能运 行完毕,标记所选进程Pi为终止进程,并将其所占资源全部 归还给剩余资源向量,根据(1)(2)式有: Available= Available+ Allocationi 否则将试分配方案作废,恢复资源状态,让进程Pi继续等待 。 重复上述,继续寻找剩余需求矩阵中是否有向量 RequestiAvailable,若是且系统处于安全状态,则将资源 分配给进程Pi,待进程Pi执行完毕标记为终止进程，并释 放其占有的全部资源,继续寻找满足上述条件的进程Pi,如 此类推下去,直到所有进程标记为终止进程或有一个死锁 发生。 【备注】： 所谓综合检测(1)(2)(3)式是否安全，主要从以下几个方 面 考量： Available是否接近零向量，若是则系统已接近无资源可 分 配，显然系统是不安全的，反之就是安全的； Allocationi是否接近Maxneedi，若是则进程Pi即将满足最 大 需求，也即进程Pi即将执行完毕，很快就会释放全部资源， 这 对资源周转是安全的，反之就是不安全的； Needi是否等于零向量，若是则进程Pi已执行完毕，所获 得 资源将全部释放,不再提出资源请求,这对资源周转是安全 的, 反之就是不安全的。 例假定系统初始资源向量Available=(6342), 4个分量代 表4 类资源拥有数目。进程P1,P2,P5的最大资源需求矩阵、 已 分配资源矩阵、剩余资源需求矩阵(Maxneed-Alloctrix)分别如 下： Maxneed = 4 1 1 1 0 2 1 2 4 2 1 0 1 1 1 1 2 1 1 0 Alloctrix = 3 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0 Remneed = 1 1 0 0 0 1 1 2 3 1 0 0 0 0 1 0 2 1 1 0 利用多资源银行家算法,在确定当前系统安全状态下,寻求该 系统进程完成序列，并将所有进程标记为终止进程。 解： 根据定义及上式知有 已分配资源向量Allocator=(5322),其中j分量为已分配资 源矩阵j列元素之和; 剩余资源向量Available=Available-Allocator=(1020)； 根据多资源银行家算法,第一轮首先选中P4,