关于进程中死锁问题的研究摘要死锁问题是Dijkstra于1965年研究银行家算法时首先提出的，也是计算机操作系统乃至并发程序设计中非常重要但又最难处理的问题之一。

实际上死锁问题是一种具有普遍性的现象。

不仅在计算机系统中，就是在其它各个领域乃至日常生活中，也都是屡见不鲜的。

掌握对死锁的处理方法，对于指导我们的现实生活，都会有积极地意义。

本文研究的是操作系统进程中的死锁问题。

从理论上说，死锁问题的研究涉及到计算机科学中一个基本问题，即并行程序的终止性问题。

本文将通过对死锁的基本概念、产生的原因和产生死锁的四个必要条件的了解，找出合理的预防、避免、检测和解除的有效方法，并将其运用到实际问题中去。

关键字：死锁的预防死锁的避免银行家算法死锁的检测死锁的解除一、死锁的基本概念1.1 死锁的概念当两个或两个以上的进程因竞争系统资源而无休止的相互等待时，我们就称这些进程是死锁的，或者说它们处于死锁状态。

1.2 死锁产生的原因1、各进程竞争有限的资源。

2、进程推进顺序不当。

1.3 产生死锁的四个必要条件1、互斥条件。

指在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待直至其占用者释放。

2、请求和保持条件。

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

3、不可剥夺条件。

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

4、环路条件。

指存在一个等待进程集合{}n P P P P ,,,,210 ，0P 正在等待一个1P 占用的资源，1P 正在等待一个2P 占用的资源，…，n P 正在的等待一个由0P 占用的资源。

这些进程及其请求的资源构成一个“进程——资源”的有向循环图。

二、死锁的处理2.1 死锁的预防死锁的预防是排除死锁的静态策略，因为我们已经知道了导致死锁产生的四个必要条件，那么我们只须破坏这四个条件中的一个即可预防死锁。

为此介绍如下4种方法。

1、共享使用法允许一个资源部件可以由多个进程“同时”使用。

这种方法在早期曾使用过，但实践证明这种方法对有些资源是行不通的。

如对宽行就是由各个进程“同时”使用，结果在打印纸上交替出现了不同进程的不同信息，从而给用户带来很大的不便，故对此类资源一般都采用独占方式。

由于对大多数资源来说互斥使用是完全必要的，所以通过破坏互斥条件来防止死锁是不现实的。

2、预先静态分配法在进程调度程序选择进程时，仅当进程所需要的全部资源都能满足时，才调度它进入内存运行。

或者说，在进程尚处于运行前的静态情况下，就为它分配了所需要的全部资源。

显然这是一种简单而安全的预防死锁的方法，但是，若资源搭配不当，就会导致进程将延迟运行，资源利用率低。

3、采用剥夺式调度法这种方法主要用在处理器和存储器资源调度上，是调度进程自身的开销，以及主存和磁盘的对换进程、数据的开销。

但对于需要由操作员装卸私有数据的外围设备，此法就不宜使用。

这种方法实现起来比较复杂，且要付出很大的代价，还可能导致反复地请求和释放资源，而使进程的执行无限延迟。

这不仅延长了进程的周转时间，还增加了系统的开销，降低了系统的吞吐量。

4、有序资源使用法系统设计者把系统中所有资源都赋予一个唯一的编号。

如令输入机为1，打印机为2，穿孔机为3，磁带机为4，等等。

此法要求每个进程均应按照严格递增的次序请求资源，并且除非前一要求得到满足，否则不允许做进一步请求。

这种方法较前一种方法提高了资源的利用率。

特别是只要系统把比较重要或稀少的资源安排为较高的序号，便可能使最有价值的资源的利用率大大提高。

但是，因为进程实际需要资源的次序并不一定与系统规定的次序相符，因此可能提前分配了暂时不需要的小序号资源，从而造成资源的浪费。

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

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

下面将详细介绍银行家算法。

1、银行家算法中的数据结构（1）可利用资源向量Available这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目。

如果][，jAvailable=KR类资源K个。

则表示系统中现有j（2）最大需求矩阵Maxn⨯的矩阵，它定义了系统中n个进程中的每一个进程对m类资这是一个m源的最大需求。

如果Max=],[，ijKR类资源的最大数目为K。

则表示进程i需要j（3）分配矩阵Allocationn⨯的矩阵，它定义了系统中每一类资源当前已分配给每一进这也是一个m程的资源数。

如果Allocation=],[，ijKR类资源的数目为K。

则表示进程i当前已分得j（4）需求矩阵Need这也是一个m n ⨯的矩阵，用以表示每一个进程尚需的各类资源数。

如果K j i Need =],[，则表示进程i 还需要j R 类资源K 个，方能完成其任务。

并且上述的三个矩阵有如下关系：],[],[],[j i Alloction j i Max j i Need -=。

2、银行家算法的实现 （1）进程申请资源的情况设i quest Re 进程i P 的请求向量，如果K j quest i =][Re ，表示进程i P 需要j R 类资源数为K 个。

][Re j quest i 与],[j i Need 的关系可能有以下3种情况：① ][Re j quest i >],[j i Need .表示该进程的资源需求量已经超过它所宣布的最大值，因此认为出错。

② ][Re j quest i =],[j i Need .表示该进程现在对它所需求的全部资源一次申请完成。

③ ][Re j quest i <],[j i Need .表示该进程现在对它所需的资源再进行部分申请，剩余的资源以后可再次申请。

（2）银行家算法的描述当进程i P 发出资源请求后，系统按一下步骤进行检查： ① 如果],[][Re ],[j i Need j quest j i Allocation i ≤+，便转向步骤②；否则认为出错，因为它所需求的资源数已超过它宣布的最大值。

② 如果],[][Re j i Available j quest i ≤，便转向步骤③；否则，表示尚无足够资源，i P 须等待。

③ 假设系统将资源分配给i P ，则需修改下面数据结构中的数值：][Re ],[],[j quest j i Allocation j i Allocation i +=； ][Re ][][j quest j Allocation j Allocation i -=； ][Re ],[],[j quest j i Need j i Need i -=；④ 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

若安全，才正式将资源分配给i P ，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程i P 等待。

（3）安全性算法① 设置两个如下的工作向量： ⅰ.Work()m W W W W ork ,,,21 =，表示系统可提供给进程继续运行所需的各类资源数目，它含有m 个元素。

ⅱ. Finish[]n F F F Finish ,,,21 =，表示系统是否有足够的资源分配给进程，使之完成任务。

并令][][j Available j Work =； FALSE i Finish =][。

② 查找这样的进程i P 使其满足：FALSE i Finish =][； ][],[j Work j i Need ≤；若找到，执行步骤③；否则，执行步骤④。

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

此时，令],[][][j i Available j W ork j W ork +=；TRUE i Finish =][；转向步骤②。

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

4、银行家算法示例假定系统中有5个进程{}54321,,,,P P P P P ，和3种资源{}C B A ,,，其中A 资源的数量为17，B 资源的数量为5，C 资源的数量为20。

0T 时刻系统状态如表2-1所示。

表2-1 0T 时刻系统状态（1）0T 时刻的安全性。

利用安全性算法对0T 时刻进行分析，可知存在一个安全序列{}12345,,,,P P P P P ，故此时系统是安全的。

（2）2P 请求资源。

2P 发出请求向量()4,3,0Re 2quest ，系统按银行家算法进行检查。

①()()4,3,14,3,0Re 22Need quest ≤；②()()3,3,24,3,0Re 2Availablequest >，让2P 的等待。

（3）4P 请求资源。

4P 发出请求向量()1,0,2Re 4quest ，系统按银行家算法进行检查。

①()()1,2,21,0,2Re 44Need quest ≤； ②()()3,3,21,0,2Re 4Available quest ≤；③系统先假定可为4P 分配资源，并修改Available 、Allocation 4和Need 4向量，由此形成的资源变化为：()2,3,0Available ；()5,0,44Allocation ；()0,2,04Need 。

④再利用安全性算法检查此时系统是否安全。

经检查，找到一个安全序列{}12345,,,,P P P P P ,因此，系统安全，可以将4P 所申请的资源分配给它。

（4）在（3）的基础上，1P 请求资源()0,2,0Re 1quest ，系统按银行家算法进行检查。

①()()7,4,30,2,0Re 11Need quest ≤②()()2,3,00,2,0Re 1Availablequest ≤； ③系统先假定可为1P 分配资源，并修改Available 、Allocation 1和Need 1向量，由此形成的资源变化为：()2,1,0Available ；()2,3,21Allocation ；()7,2,31Need 。

④再利用安全性算法检查此时系统是否安全。

此时，()2,1,0Available已不能满足任何进程的需求，故若实施分配，系统将进入不安全状态，此时系统不分配资源。

2.3 死锁的检测与解除1、死锁的检测死锁检测方法对资源的分配不加限制，只要有剩余的资源，就可把资源分配给申请的进程，允许系统有死锁发生，这样可能会造成死锁。