4 . 5 死锁 D e a d l o c k s 多道程序的并发执行可以改善系统的资源利用率，但也可能导致死锁的发生。4 . 5 . 1 死锁的概念死锁是指多个进程因竞争系统资源或相互通信而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。死锁例：当两辆车在十字路口逼近时，它们要完全停下来，且在一辆车开走之前，另一辆车不能启动。日常生活中的死锁例假设一条河上有一座独木桥，若桥两端的人相向而行此时死锁发生了 4 . 5 . 2 死锁产生的原因和必要条件死锁产生的原因是与资源的使用相关。下面介绍资源分类。可剥夺和非剥夺资源可剥夺资源是指某进程获得这类资源后，该资源可以被其他进程或系统剥夺。如C P U，存储器。非剥夺资源又称不可剥夺资源，是指系统将这类资源分配给进程后，再不能强行收回，只能在进程使用完后主动释放。如打印机、读卡机。注意：竞争可剥夺资源不会产生死锁！永久性资源和消耗性资源永久性资源：可顺序重复使用的资源。如打印机。消耗性资源：由一个进程产生，被另一个进程使用短暂时间后便无用的资源，又称为临时性资源。如消息。竞争永久性资源和临时性资源都可能产生死锁。 死锁产生的原因死锁产生的原因是：竞争资源：多个进程竞争资源，而资源又不能同时满足其需求。进程推进顺序不当：进程申请资源和释放资源的顺序不当。竞争非剥夺资源引起的死锁竞争非剥夺资源例。如，打印机R 1和读卡机R 2供进程P 1和P 2共享。P 1R1 R2P 2竞争消耗性资源引起的死锁如消息通信按下述顺序进行，则不会发生死锁：P 1：. . . R e l e a s e ( S 1 )；R e q u e s t ( S 2 )；. . .P 2：. . . R e l e a s e ( S 2 )；R e q u e s t ( S 1 )；. . .若按下述顺序，则可能发生死锁：P 1：. . . R e q u e s t ( S 2 )；R e l e a s e ( S 1 )；. . .P 2：. . . R e q u e s t ( S 1 )；R e l e a s e ( S 2 )；. . .P 1S 2 S 1P 2进程推进顺序不当引起的死锁当进程P 1、P 2共享资源A、B时，若推进顺序合法则不会产生死锁，否则会产生死锁。合法的推进路线： 不合法的推进线路：P 2释放AP 2释放BP 2申请AP 2申请BP 1申请A P 1申请B P 1释放A P 1释放B死锁区死锁点死锁产生的必要条件互斥条件：在一段时间内某资源仅为一个进程所占有。请求和保持条件：又称部分分配条件、占用并等待条件。当进程因请求资源被阻塞时，已分配资源保持不放。不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。循环等待条件：死锁发生时，存在一个进程资源的循环。注意死锁是因资源竞争造成的僵局通常死锁一般至少涉及两个进程死锁与部分进程及资源相关4 . 5 . 3 处理死锁的基本方法用于处理死锁的方法主要有：忽略死锁。这种处理方式又称鸵鸟算法，指像鸵鸟一样对死锁视而不见。 预防死锁：设置某些限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。避免死锁：在资源的动态分配过程中，用某种方法来防止系统进入不安全状态。检测死锁及解除：系统定期检测是否出现死锁，若出现则解除死锁。4 . 5 . 4 死锁的预防预防死锁。通过破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。特点：较易实现，广泛使用，但限制较严，资源利用率低。破坏互斥条件互斥是设备本身固有的属性，此条件不能破坏。破坏请求和保持条件要求进程一次申请它所需的全部资源，若有足够的资源则分配给进程，否则不分配资源，进程等待。这种方法称为静态资源分配法。特点：简单、安全且易于实现；但资源利用率低，进程延迟运行。破坏不剥夺条件一个已获得某些资源的进程，若新的资源请求得不到满足，则它必须释放已获得的所有资源。特点：实现较复杂，释放已获得资源可能造成前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。 破坏循环等待条件将所有资源按类型排队，并赋予不同序号，要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。这种方法称为有序资源分配法。特点：比前两种方法资源利用率高，吞吐量大。但要求资源序号相对稳定，从而限制了新设备的增加；使用资源的顺序与系统规定顺序不同，造成资源的浪费；使用资源的次序限制用户编程。为什么有序资源分配法可以防止死锁1假设循环已经出现并且含于环中的进程是p0、p n，这意味着p i正占有r i类资源，而请求r i + 1类资源，设函数f能获得资源序号，则有f（r i）来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利完成，则称此时的系统状态为安全状态，称序列为安全序列。不安全状态若某一时刻系统中不存在一个安全序列，则称此时的系统状态为不安全状态。进入不安全状态后，便可能进而进入死锁状态；因此避免死锁的本质是使系统不进入不安全状态。安全状态例 T 0时刻，系统资源状态如下：7 2 9 P 32 2 4 P 23 5 5 1 0 P 1可用 需要 已分配 最大需求 进程这时可用资源能满足P 2的需要，P 2获得运行需要的所有资源并能顺利运行结束。P 2运行结束的系统资源状态这时可用资源能满足P 1的需要，P 1获得运行需要的所有资源并能顺利运行结束。7 2 9 P 32 2 4 P 25 5 5 1 0 P 1可用 需要 已分配 最大需求 进程P 2、P 1运行结束的统资源状态这时可用资源能满足P 3的需要，P 3获得运行需要的所有资源并能顺利运行结束。因此存在一个安全序列，系统状态安全。7 2 9 P 32 2 4 P 21 0 5 5 1 0 P 1可用 需要 已分配 最大需求 进程由安全状态向不安全状态转换若在T 0之后，又将1个资源分配给了P 3，则系统进入了不安全状态：6 3 9 P 32 2 4 P 22 5 5 1 0 P 1可用 需要 已分配 最大需求 进程银行家算法 B a n k e r s A l g o r i t h m最具代表性的死锁避免算法是D i j k s t r a的银行家算法。 假定系统中有n个进程P1、P2、P n ，m类资源R1、R2、Rm，银行家算法中使用的数据结构如下：1）可用资源向量A vai l a bl e可利用资源向量A vai l a bl e是一个含有m个元素的数组，其中每一个元素代表一类资源的空闲资源数目。如果A vai l a bl e ( j )k，表示系统中现有空闲的Rj类资源k个。2）最大需求矩阵Ma x最大需求矩阵M a x是一个nm的矩阵，定义了系统中每个进程对m类资源的最大需求数目。如果M a x ( i，j )k ，表示进程P i需要Rj类资源的最大数目为k。3）分配矩阵A l l oca t i on分配矩阵A l l oca t i on是一个nm 的矩阵，定义了系统中每一类资源当前已分配给每一个进程的资源数目。如果A l l oca t i on ( i，j )k ，表示进程P i当前已分到Rj类资源的数目为k。 A l l oca t i oni表示进程P i的分配向量，由矩阵A l l oca t i on的第i行构成。4）需求矩阵N e e d需求矩阵N e e d是一个nm 的矩阵，它定义了系统中每一个进程还需要的各类资源数目。如果N e e d ( i，j )k，表示进程Pi还需要Rj类资源k个。N e e d i表示进程P i的需求向量，由矩阵N e e d的第i行构成。三个矩阵间的关系： N e e d ( i，j )M a x ( i，j )A l l oca t i on ( i，j )银行家算法设R e ques t i是进程Pi的请求向量，R e ques t i ( j )k表示进程P i请求分配Rj类资源k个。当P i发出资源请求后，系统按下述步骤进行检查：银行家算法描述 1）如果R e q u e s t iN e e d i ，则转向步骤2 ；否则出错。 2）如果R e q u e s t iA v a i l a b l e ，则转向步骤3；否则P i等待。 3）试分配并修改数据结构： A vai l a bl e Avai l a bl eR e ques t i ； A l l oca t i oni A l l oca t i oni R e ques t i ； N e e d i N e e d i R e ques t i ； 4）系统执行安全性算法，检查此次资源分配是否安全。若安全，才正式分配；否则，试分配作废，让进程Pi等待。安全性算法( 1 ) S a f e t y A l g o r i t h m 1）设置两个向量 Wor k：表示系统可提供给进程继续运行的各类空闲资源数目，含有m个元素，执行安全性算法开始时，Wor kA vai l a bl e 。 F i ni s h：表示系统是否有足够的资源分配给进程，使之运行完成，开始时，F i ni s h ( i )f a l s e；当有足够资源分配给进程Pi时，令F i ni s h ( i )t r ue 。 2）从进程集合中找到一个能满足下述条件的进程： F i ni s h ( i ) = f a l s e ； N e e d iWor k ；如找到则执行步骤3；否则执行步骤4。安全性算法( 2 ) 3）当进程P i获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行： Wo r kWo r k A l l o c a t i o n i ； F i n i s h ( i )t r u e ； G o t o s t e p 2 ； 4）若所有进程的F i ni s h ( i )都为t r ue ，则表示系统处于安全状态；否则，系统处于不安全状态。 银行家算法例假定系统中有5个进程 P 0、P 1、P 2、P 3、P 4和三种类型的资源A、B、C，数量分别为1 2、5、9，在T 0时刻的资源分配情况如下所示。3 3 2 7 4 3 1 1 0 8 5 3 P 04 3 1 1 0 2 5 3 3 P 40 1 1 2 1 1 2 2 2 P 36 0 0 3 0 3 9 0 3 P 2A B C A B C A B C A B C1 2