关于进程中死锁问题的研究

关于进程中死锁问题的研究

摘要

死锁问题是Dijkstra于1965年研究银行家算法时首先提出的，也是计算机操作系统乃至并发程序设计中非常重要但又最难处理的问题之一。实际上死锁问题是一种具有普遍性的现象。不仅在计算机系统中，就是在其它各个领域乃至日常生活中，也都是屡见不鲜的。掌握对死锁的处理方法，对于指导我们的现实生活，都会有积极地意义。本文研究的是操作系统进程中的死锁问题。从理论上说，死锁问题的研究涉及到计算机科学中一个基本问题，即并行程序的终止性问题。本文将通过对死锁的基本概念、产生的原因和产生死锁的四个必要条件的了解，找出合理的预防、避免、检测和解除的有效方法，并将其运用到实际问题中去。

关键字：死锁的预防 死锁的避免 银行家算法 死锁的检测 死锁的解除

一、死锁的基本概念

1.1 死锁的概念

当两个或两个以上的进程因竞争系统资源而无休止的相互等待时，我们就

称这些进程是死锁的，或者说它们处于死锁状态。 1.2 死锁产生的原因

1、各进程竞争有限的资源。 2、进程推进顺序不当。 1.3 产生死锁的四个必要条件

1、互斥条件。指在一段时间内，一个资源只能由一个进程独占使用，若

别的进程也要求该资源，则须等待直至其占用者释放。

2、请求和保持条件。指进程已经保持了至少一个资源，但又提出新的请求，而该资源已被其他进程占用，此时请求进程阻塞，但又不释放自己已获得的资源。

3、不可剥夺条件。进程所获得的资源在未使用完之前，不能被其他进程强行夺走，而只能由其自身释放。

4、环路条件。指存在一个等待进程集合?P0,P1,P2,?,Pn?，P0正在等待一个P1占用的资源，P1正在等待一个P2占用的资源，?，Pn正在的等待一个由P0占用的资源。这些进程及其请求的资源构成一个“进程——资源”的有向循环图。

二、死锁的处理

2.1 死锁的预防

死锁的预防是排除死锁的静态策略，因为我们已经知道了导致死锁产生的四个必要条件，那么我们只须破坏这四个条件中的一个即可预防死锁。为此介绍如下4种方法。

1、共享使用法

允许一个资源部件可以由多个进程“同时”使用。这种方法在早期曾使用过，但实践证明这种方法对有些资源是行不通的。如对宽行就是由各个进程“同时”使用，结果在打印纸上交替出现了不同进程的不同信息，从而给用户带来很大的不便，故对此类资源一般都采用独占方式。由于对大多数资源来说互斥使用是完全必要的，所以通过破坏互斥条件来防止死锁是不现实的。

2、预先静态分配法

在进程调度程序选择进程时，仅当进程所需要的全部资源都能满足时，才调度它进入内存运行。或者说，在进程尚处于运行前的静态情况下，就为它分配了所需要的全部资源。显然这是一种简单而安全的预防死锁的方法，但是，若资源搭配不当，就会导致进程将延迟运行，资源利用率低。

3、采用剥夺式调度法

这种方法主要用在处理器和存储器资源调度上，是调度进程自身的开销，以及主存和磁盘的对换进程、数据的开销。但对于需要由操作员装卸私有数据的外围设备，此法就不宜使用。这种方法实现起来比较复杂，且要付出很大的代价，还可能导致反复地请求和释放资源，而使进程的执行无限延迟。这不仅延长了进程的周转时间，还增加了系统的开销，降低了系统的吞吐量。

4、有序资源使用法

系统设计者把系统中所有资源都赋予一个唯一的编号。如令输入机为1，

打印机为2，穿孔机为3，磁带机为4，等等。此法要求每个进程均应按照严格递增的次序请求资源，并且除非前一要求得到满足，否则不允许做进一步请求。这种方法较前一种方法提高了资源的利用率。特别是只要系统把比较重要或稀少的资源安排为较高的序号，便可能使最有价值的资源的利用率大大提高。但是，因为进程实际需要资源的次序并不一定与系统规定的次序相符，因此可能提前分配了暂时不需要的小序号资源，从而造成资源的浪费。 2.2 死锁的避免

死锁的避免是一种排除死锁的动态策略，允许进程动态地申请资源，但系统在分配资源之前，要先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，便将资源进行分配 ，否则不予以分配。

Dijkstra的银行家算法是最具代表性的避免死锁的算法，这种方法是以银行系统所采用的借贷策略为基础建立的模型。下面将详细介绍银行家算法。

1、银行家算法中的数据结构 （1）可利用资源向量Available

这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目。如果

Available[j]?K，

则表示系统中现有Rj类资源K个。 （2）最大需求矩阵Max

这是一个n?m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果

Max[i,j]?K，

则表示进程i需要Rj类资源的最大数目为K。 （3）分配矩阵Allocation

这也是一个n?m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果

Allocation[i,j]?K，

则表示进程i当前已分得Rj类资源的数目为K。

（4）需求矩阵Need

这也是一个n?m的矩阵，用以表示每一个进程尚需的各类资源数。如果

Need[i,j]?K，

则表示进程i还需要Rj类资源K个，方能完成其任务。

并且上述的三个矩阵有如下关系：

Need[i,j]?Max[i,j]?Alloction[i,j]。

2、银行家算法的实现 （1）进程申请资源的情况

设Requesti进程Pi的请求向量，如果

Requesti[j]?K，

表示进程Pi需要Rj类资源数为K个。Requesti[j]与Need[i,j]的关系可能有以下3种情况：

① Requesti[j]>Need[i,j].

表示该进程的资源需求量已经超过它所宣布的最大值，因此认为出错。 ② Requesti[j]=Need[i,j].

表示该进程现在对它所需求的全部资源一次申请完成。 ③ Requesti[j]

表示该进程现在对它所需的资源再进行部分申请，剩余的资源以后可再次申请。

（2）银行家算法的描述

当进程Pi发出资源请求后，系统按一下步骤进行检查： ① 如果

Allocation[i,j]?Requesti[j]?Need[i,j]，

便转向步骤②；否则认为出错，因为它所需求的资源数已超过它宣布的最大值。 ② 如果

Requesti[j]?Available[i,j]，

便转向步骤③；否则，表示尚无足够资源，Pi须等待。

③ 假设系统将资源分配给Pi，则需修改下面数据结构中的数值：

Allocation[i,j]?Allocation[i,j]?Requesti[j]； Allocation[j]?Allocation[j]?Requesti[j]； Need[i,j]?Need[i,j]?Requesti[j]；

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

① 设置两个如下的工作向量： ⅰ.Work

Work??W1,W2,?,Wm?，

表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素。 ⅱ. Finish

Finish??F1,F2,?,Fn?，

表示系统是否有足够的资源分配给进程，使之完成任务。并令

Work[j]?Available[j]； Finish[i]?FALSE。

② 查找这样的进程Pi使其满足：

Finish[i]?FALSE； Need[i,j]?Work[j]；

若找到，执行步骤③；否则，执行步骤④。

③ 当进程Pi获得资源后，可顺利执行，直至完成任务，并释放出分配给它的资源。此时，令

Work[j]?Work[j]?Available[i,j]；

Finish[i]?TRUE；

转向步骤②。

④ 如果对所有进程的Finish[i]?TRUE都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

4、银行家算法示例

假定系统中有5个进程?P和3种资源?A,B,C?，其中A资源1,P2,P3,P4,P5?，的数量为17，B资源的数量为5，C资源的数量为20。T0时刻系统状态如表2-1所示。

表2-1 T0时刻系统状态

进程 已分配资源数量 A B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍需求资源数 A 3 1 0 2 1 B 4 3 0 2 1 C 7 4 6 1 0 P1 P2 2 4 4 2 3 P3 P4 P5

（1）T0时刻的安全性。利用安全性算法对T0时刻进行分析，可知存在一个安全序列?P5,P4,P3,P2,P1?，故此时系统是安全的。

（2）P2请求资源。P2发出请求向量Request2?0,3,4?，系统按银行家算法进行检查。

①Request2?0,3,4??Need2?1,3,4?；

?2,3,3?，让P2的等待。 ②Request2?0,3,4??Available

（3）P4请求资源。P4发出请求向量Request4?2,0,1?，系统按银行家算法进行检查。

①Request4?2,0,1??Need4?2,2,1?； ②Request4?2,0,1??Available?2,3,3?；

③系统先假定可为P4分配资源，并修改Available、Allocation4和Need4向量，由此形成的资源变化为：

?0,3,2?；AllocationAvailable4?4,0,5?；Need4?0,2,0?。

④再利用安全性算法检查此时系统是否安全。经检查，找到一个安全序列

?P5,P4,P3,P2,P1?,因此，系统安全，可以将P4所申请的资源分配给它。

（4）在（3）的基础上，P1?0,2,0?，系统按银行家算法进1请求资源Request行检查。

①Request1?0,2,0??Need1?3,4,7?

?0,3,2?； ②Request1?0,2,0??Available③系统先假定可为P并修改Available、Allocation1和Need1向量，1分配资源，由此形成的资源变化为：

?0,1,2?；AllocationAvailable1?2,3,2?；Need1?3,2,7?。

?0,1,2?已不能 ④再利用安全性算法检查此时系统是否安全。此时，Available满足任何进程的需求，故若实施分配，系统将进入不安全状态，此时系统不分配资源。

2.3 死锁的检测与解除

1、死锁的检测

死锁检测方法对资源的分配不加限制，只要有剩余的资源，就可把资源分配给申请的进程，允许系统有死锁发生，这样可能会造成死锁。关键是当死锁发生时系统能够尽快检测到，并及时解除死锁，使系统恢复正常运行。因此，采用这种方法必须解决3个问题，一是何时检测死锁发生，二是如何判断系统是否出现

了死锁，三是当发现死锁发生时如何解除死锁。

由于死锁检测算法允许系统发生死锁，因此，最好的情况是一旦死锁产生，就能立即检测到，也就是说死锁发现得越早越好。

死锁一般是在资源分配时发生，所以将死锁的检测时机定在有资源请求时是比较合理的，但是采用这种方法检测的次数过于频繁，若没有死锁，将占用CPU非常大的时间开销。

另一种方法是周期性检测，即每隔一定时间检测一次，或者根据CPU的使用效率去检测，先为CPU的使用率设定一个低的阀值，每当发现CPU使用率降到该阀值以下时就启动检测程序，以减少由于死锁造成CPU的无谓操作。

2、死锁的解除

一旦在死锁检测时发现了死锁，就要消除死锁，使系统从死锁状态中恢复过来。一般主要采用两种方法：

（1）撤销法。即撤销已死锁的进程，系统可回收被撤销的进程所占用的资源，并进行分配，以达到解除死锁的目的。

①撤销涉及死锁的所有进程。这种方法能彻底破坏死锁的循环等待状态，但是，因为有些进程可能已经运行了很长时间，由于被撤销而使得产生的部分结果被删除，再重新执行时还要再次进行计算和运行。

②一次撤销一个进程。这种方法是每次按照一定的次序撤销一个进程，而选择撤销进程的次序基于最小代价原则。在每次撤销一个进程后，要调用死锁检测算法，以检测是否仍然存在死锁。

（2） 剥夺法，即从一个或几个死锁的进程那里剥夺足够数量的资源，再把释放的资源分配给另一些死锁的进程，以便足以解除死锁。该方法也需要基于最小代价原则选择要剥夺的资源。同样也需要在每次剥夺一个资源后，要调用死锁检测算法，以检测是否仍然存在死锁。

关于最小代价，可以考虑一下几个方面： ①到目前为止消耗的处理机时间最少； ②到目前为止产生的输出最少； ③预计剩下的执行时间最长； ④到目前为止分配的资源总量最少；

⑤进程的优先级最低；

⑥撤销进程对其他进程的影响最小。

总而言之，我们理解死锁产生的原因，尤其是产生死锁的四个必要条件，就可以最大可能地预防、避免、检测和解除死锁。所以当我们在设计系统、调度进程等时，要尽量不让这些条件成立，只要保证一个条件不满足，死锁就不会发生；要确定合理分配资源的算法，避免进程永久占用系统资源。此外，也要避免进程在等待状态的情况下占用资源。因此，我认为对死锁的处理问题上，最重要的就是要处理好资源的分配问题，资源分配合理就可以大大避免了死锁问题。

目前也有人认为死锁并非属于程序正确性问题的范畴，而是一种经济上的争执。因此有些计算机部门，为了节省解决死锁问题的耗费，当死锁机会不太多时，宁可冒着死锁的风险。我认为对死锁机会非常少的系统来说，持这种观点是可以理解的。但对于那些复杂的大型计算机系统，特别是实时系统，则绝不应该掉以轻心。系统进程、用户进程的并发运行，互相通讯，以及资源的动态申请等，死锁产生的可能性很大。尤其在实时系统中，飞行器的实时控制，生命支持系统的监督控制等，死锁问题更显得十分严峻。所以我们必须对死锁问题加以重视，以便提高我们的工作效益。

三、参考文献

[1] 王鸿武，《操作系统》，湖南：国防科技大学出版社，1980年。

[2] 郁红英 李春强，《计算机操作系统》，北京：清华大学出版社，2008年。 [3] 范策 许宪成等，《计算机操作系统教程——核心与设计原理》，北京：清华大学出版社，2007年。

[4] 王红等，《操作系统原理及应用（Linux）》，北京：中国水利水电出版社，2005年。

本文来源：https://www.bwwdw.com/article/o3ut.html