计算机操作系统中的死锁：了解死锁状态及检测方法

在多道程序系统中，多个进程在并发执行时可能发生一种危险——死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局（deadly embrace），当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。在前面介绍把信号量作为同步工具时已提及，若多个P和V操作顺序不当，会产生进程死锁。

3.6.1 死锁的定义

死锁可能是由于竞争资源而产生，也可能是由于程序设计的错误所造成，因此，在讨论死锁问题时，为了避免和硬件故障以及其他程序性错误纠缠在一起，特做如下假定：

（1）任意一个进程要求资源的最大数量不超过系统能提供的最大量。

（2）如果一个进程在执行中所提出的资源要求能够得到满足，那么它一定能在有限的时间内结束。

（3）一个资源在任何时间最多只为一个进程所占有。

（4）一个进程一次申请一个资源，且只在申请资源得不到满足时才处于等待状态。换言之，其他一些等待状态，例如人工干预、等待外围设备、传输结束等，在没有故障的条件下，可以在有限长的时间内结束，不会产生死锁。因此，这里不考虑这种等待。

（5）一个进程结束时释放它占有的全部资源。

（6）系统具有有限个进程和有限个资源。

现在来给出死锁的定义：一组进程处于死锁状态是指，如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。例如，n个进程P1，P2，…，P n，P i（i＝1，…，n）因为申请不到资源R j（j＝1，…，m）而处于等待状态，而R j又被P i＋1（i＝1，…，n－1）占有，P n欲申请的资源被P1占有，显然，此时这n个进程的等待状态永远不能结束，则说这n个进程处于死锁状态。

3.6.2 产生死锁的原因和条件

1）产生死锁的原因

（1）竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。

（2）进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。

2）产生死锁的条件

1971年Coffman总结出了对于可再使用资源，系统产生死锁必定同时保持四个必要条件：

（1）互斥条件（mutual exclusion）。进程应互斥使用资源，任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被设置成等待状态，直到占用者释放资源。

（2）占有和等待条件（hold and wait）。一个进程请求资源得不到满足而等待时，不释放已占有的资源。

（3）不剥夺条件（no preemption）。任一进程不能从另一进程那里抢夺资源，即已被占用的资源只能由占用进程自己来释放。

（4）循环等待条件（circular wait）。存在一个循环等待链，其中每一个进程分别等待它前一个进程所持有的资源，造成永远等待。

以上前三个条件是死锁存在的必要条件，但不是充分条件。第四个条件是前三个条件同时存在时产生的结果，所以这些条件并不完全独立。但单独考虑每个条件是有用的，只要能破坏这四个必要条件之一，死锁就可防止。

破坏第一个条件（互斥条件），使资源可同时访问而不是互斥使用，是个简单的办法，磁盘可用这种办法管理，但有许多资源往往是不能同时访问的，所以这种做法许多场合行不通。采用剥夺式调度方法可以破坏第三个条件（不剥夺条件），但剥夺调度方法目前只适用于对主存资源和处理器资源的分配，当进程在申请资源未获准许的情况下，如能主动释放资源（一种剥夺式），然后才去等待，以后再一起向系统提出申请，也能防止死锁，但这些办法不适用于所有资源。由于各种死锁防止办法施加于资源的限制条件太严格，会造成资源利用率下降。3.6.4节会介绍两种比较实用的死锁防止方法，它们能破坏第二个条件或第四个条件。

3.6.3 处理死锁的方法

为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防发生死锁。在系统中已经出现死锁后，则应及时检测到死锁的发生，并采取适当措施来解除死锁。目前，处理死锁的方法可归结为以下五种：

（1）不予处理。采用这种方式的系统通常认为系统出现死锁的概率很低或者预防死锁的代价很大，是方便性与正确性之间的一种折中，UNIX和Windows都采取这种方法。

（2）预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往太严格，因而可能会导致系统资源利用率和系统吞吐量降低。

（3）避免死锁。该方法同样属于事先预防的策略，但它并不需要事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只需要事先施加较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但在实现上有一定的难度。目前在较完善的系统中常用此方法来避免发生死锁。

（4）检测死锁。这种方法并不需要事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后采取适当措施，从系统中将已发生的死锁清除掉。

（5）解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪态，以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

3.6.4 死锁的预防

预防死锁的方法是使四个必要条件中的第二至四个条件之一不能成立，来避免发生死锁。至于必要条件一，因为它是由设备的固有特性所决定的，不仅不能改变，还应加以保证。

1.静态分配策略

所谓静态分配，是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。无疑所有并发执行的进程要求的资源总和不超过系统拥有的资源数。采用静态分配后，进程在执行中不再申请资源，因而不会出现占有了某些资源再等待另一些资源的情况，即破坏了第二个条件（占有和等待条件）的出现。静态分配策略实现简单，被许多操作系统采用。但这种策略严重降低了资源利用率，因为在每个进程所占有的资源中，有些资源在进程较后的执行时间里才使用，甚至有些资源在例外的情况下被使用。这样，就可能造成一个进程占有了一些几乎不用的资源而使其他想用这些资源的进程产生等待。

2.层次分配策略

层次分配策略将阻止第四个条件（循环等待条件）的出现。在层次分配策略下，资源被分成多个层次，一个进程得到某一层的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源，当另一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，那么必须先释放该层中的已占资源。

这种策略的一个变种是按序分配策略。把系统的所有资源排列成一个顺序，例如，系统若共有n个进程，共有m个资源，用r i表示第i个资源，于是这m个资源是：

r1，r2，…，r m规定如果进程不得在占用资源r i（1≤i≤m）后再申请r j（j＜i）。不难证明，按这种策略分配资源时系统不会发生死锁。

层次分配比静态分配在实现上要多花一点代价，但它提高了资源使用率。然而，如果一个进程使用资源的次序和系统内规定各层资源的次序不同时，这种提高可能不明显。假如系统中的资源从高到低按序排列为：卡片输入机、行式打印机、卡片输出机、绘图仪和磁带机。若一个进程在执行中，较早地使用绘图仪，而仅到快结束时才用磁带机。但是系统规定，磁带机所在层次低于绘图仪所在层次。这样进程使用绘图仪前就必须先申请到磁带机，这台磁带机就在一长段时间里空闲着直到进程执行到结束前才使用，这无疑是低效率的。

3.6.5 死锁的避免

破坏死锁的四个条件之一能防止系统发生死锁，但这会导致低效的进程运行和资源使用率。死锁的避免则相反，它允许系统中同时存在四个必要条件，如果能掌握并发进程中与每个进程有关的资源动态申请情况，在资源申请时做出合理的选择，仍然可以避免死锁的发生。即在为申请者分配资源前先测试系统状态，若把资源分配给申请者会产生死锁，则拒绝分配；否则接受申请，为它分配资源。死锁避免是通过对每一次资源申请进行分析来判断它是否能安全地分配，这个算法是银行家算法。

1.单种资源的银行家算法

Dijkstra（1965）提出了一种能够避免死锁的调度方法，称为银行家算法，它的模型基于一个小城镇的银行家，现将该算法描述如下：假定一个银行家拥有资金，数量为∑，被N个客户共享。银行家对客户提出下列约束条件：

（1）每个客户必须预先说明自己所要求的最大资金量。

（2）每个客户每次提出部分资金量申请和获得分配。

（3）如果银行满足了客户对资金的最大需求量，那么客户在资金运作后，应在有限时间内全部归还银行。

只要每个客户遵守上述约束，银行家将保证做到：若一个客户所要求的最大资金量不超过∑，则银行一定接纳该客户，并可处理他的资金需求；银行在收到一个客户的资金申请时，可能因资金不足而让客户等待，但保证在有限时间内让客户获得资金。

在银行家算法中，客户可看作进程，资金可看作资源，银行家可看作操作系统，这里叙述的是单资源银行家算法，还可以扩展到多资源银行家算法。

一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所有的贷款（即所有的进程得到所需的全部资源并终止）。图3-8b所示的状态是安全的，能使Marvin运行结束，然后释放所有的4个单位资金。如此反复下去便可以满足Suzanne或者Barbara的请求，等等。考虑假如给Barbara另一个她申请的资源，如图3-8b所示，则得到如图3-8c所示的状态，该状态是不安全的。如果所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，而仅仅是可能产生死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。

图3-8 三种资源分配状态

银行家算法就是对每一个请求进行检查，检查这次资源申请是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。

图3-9 多种资源的银行家算法

2.多种资源的银行家算法

将安全状态检测类推到多种资源的银行家算法中（图3-9），检查一个状态是否安全的步骤如下：

（1）查找右边矩阵是否有一行，其未被满足的设备数均小于或等于向量A。如果找不到，则系统将死锁，因为任何进程都无法运行结束。

（2）若找到这样一行，则可以假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量A上。

（3）重复以上两步，直到所有的进程都标记为结束。若达到所有进程结束，则状态是安全的，否则将发生死锁。

如果在第一步中同时存在若干进程均符合条件，则不管挑选哪一个运行都没有关系，因为可用资源或者将增多，或者在最坏情况下保持不变。图中所示的状态是安全的，进程B现在再申请一台打印机，可以满足它的请求，而且保持系统状态仍然是安全的（进程D可以结束，然后是A或E，剩下的进程最后结束）。假设进程B获得一台打印机后，E试图获得最后的一台打印机，若分配给E，可用资源向量将减到（1 000），这时将导致死锁。显然E的请求不能立即满足，必须延迟一段时间。

3.相关数据结构及算法流程

1）银行家算法中的数据结构

（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］＝K，则表示系统中现有R j类资源K个。

（2）最大需求矩阵Max。这是一个n×m矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i，j］＝K，则表示进程i需要R j类资源的最大数目为K。(www.xing528.com)

（3）分配矩阵Allocation。这也是一个n×m矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i，j］＝K，则表示进程i当前已分得R j类资源的数目为K。

（4）需求矩阵Need。这也是一个n×m矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i，j］＝K，则表示进程i还需要R j类资源K个，方能完成其任务。

上述三个矩阵间存在下述关系：

Need［i，j］＝Max［i，j］－Al location［i，j］

2）银行家算法流程

设Request i是进程P i的请求向量，如果Request i［j］＝K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：

（1）如果Request i［j］≤Need［i，j］，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Requesti［j］≤Available［j］，便转向步骤（3）；否则表示尚无足够资源，Pi须等待。

（3）系统试探着把资源分配给进程P i，并修改下面数据结构中的数值：

Avai lable［j］：＝Available［j］－Request i［j］；

Al locat ion［i，j］：＝Al location［i，j］＋Request i［j］；

Need［i，j］：＝Need［i，j］－Request i［j］；

（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程P i，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程P i等待。

3）安全性算法

（1）设置两个向量：

①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work：＝Available。

②Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］：＝false；当有足够资源分配给进程时，再令Finish［i］：＝true。

（2）从进程集合中找到一个能满足下述条件的进程：

①Finish［i］＝false。

②Need［i，j］≤Work［j］；若找到，执行步骤（3），否则，执行步骤（4）。

（3）当进程P i获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work［j］：＝Work［j］＋Al location［i，j］；

Finish［i］：＝true；

go to step 2；

（4）如果所有进程的Finish［i］＝true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

4.举例

假定系统中有五个进程｛P0，P1，P2，P3，P4｝和三类资源｛A，B，C｝，各种资源的数量分别为10、5、7，在T 0时刻的资源分配情况见表3-1。

表3-1 T0时刻的资源分配表

（1）T 0时刻的安全性：利用安全性算法对T 0时刻的资源分配情况进行分析（表3-2）可知，在T 0时刻存在着一个安全序列｛P1，P3，P4，P2，P0｝，故系统是安全的。

表3-2 T0时刻安全性分析

由所进行的安全性检查得知，可以找到一个安全序列｛P1，P3，P4，P2，P0｝。因此，系统是安全的，可以立即将P1所申请的资源分配给它。

（3）P4请求资源：P4发出请求向量Request 4（3，3，0），系统按银行家算法进行检查：

①Request 4（3，3，0）≤Need 4（4，3，1）。

②Request 4（3，3，0）≤Available（2，3，0），让P4等待。

（4）P0请求资源：P0发出请求向量Requst 0（0，2，0），系统按银行家算法进行检查：

①Request 0（0，2，0）≤Need 0（7，4，3）。

②Request 0（0，2，0）≤Available（2，3，0）。

③系统暂时先假定可为P分配资源，并修改有关数据，见表3-4。

表3-4 P0分配资源后的有关资源数据

（5）进行安全性检查：可用资源Available（2，1，0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

如果在银行家算法中，把P0发出的请求向量改为Request 0（0，1，0），系统是否能将资源分配给它，请读者考虑。

3.6.6 死锁的检测及解决

当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须做到：①保存有关资源的请求和分配信息；②提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。

1.资源分配图

系统死锁可利用资源分配图（resource allocation graph）来描述。该图是由一组结点N和一组边E所组成的一个对偶G＝（N，E），它具有下述形式的定义和限制：

（1）把N分为两个互斥的子集，即一组进程结点P＝｛p1，p2，…，p n｝和一组资源结点R＝｛r1，r2，…，r n｝，N＝P∪R。在图3-10所示的例子中，P＝｛P1，P2，P3，P4｝，R＝｛R1，R2｝，N＝｛R1，R2｝∪｛P1，P2，P3，P4｝。

（2）凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e＝｛pi，rj｝是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e＝｛rj，pi｝是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。图3-10中示出了两个请求边和四个分配边，即E＝｛（P1，R2），（R1，P1），（R1，P2），（R2，P3），（P3，R1），（R2，P4）｝。

用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的Rj，而分配边则应始于方框中的一个点。图3-10示出了一个资源分配图。图中，P1进程已经分得了一个R1资源，并又请求一个R2资源；P2进程分得一个R1资源；P3进程分得了一个R2资源，并又请求一个R1资源，P4分得一个R2资源。

2.死锁的检测

可以利用下列步骤运行一个“死锁检测”程序，对进程-资源分配图进行分析和简化，以此方法来检测系统是否处于死锁状态：

图3-10 资源分配图

（1）如果进程-资源分配图中无环路，则此时系统没有发生死锁。

（2）如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，环路中的进程便为死锁进程。

（3）如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在未必会发生死锁。如果能在进程-资源分配图中找出一个既不阻塞又非独立的进程，它在有限的时间内有可能获得所需资源类中的资源继续执行，直到运行结束，再释放其占有的全部资源。相当于消去了图中此进程的所有请求边和分配边，使之成为孤立结点。接着可使进程-资源分配图中另一个进程获得前面进程释放的资源继续执行，直到完成又释放出它所占用的所有资源，相当于又消去了图中若干请求边和分配边。如此下去，经过一系列简化后，若能消去图中所有边，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的。系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。

3.死锁的解除

当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是：

（1）剥夺资源。从其他进程剥夺足够数量的资源给死锁进程，以解除死锁状态。

（2）撤销进程。最简单的撤销进程的方法是使全部死锁进程都夭折；稍微温和一点的方法是按照某种顺序逐个地撤销进程，直至有足够的资源可用，使死锁状态消除为止。在出现死锁时，可采用各种策略来撤销进程。例如，为解除死锁状态所需撤销的进程数目最小；或者撤销进程所付出的代价最小等。