浅谈操作系统中的死锁问题

1、浅谈操作系统中的死锁问题【摘要】经济飞速发展，计算机的应用越来越广，而作为计算机的入口，操作系统 的研究越來越重要。而死锁问题是我们一直不断致力于的重要课题。死锁是多个进程为竞 争系统资源或彼此间通信而引起的永久性的阻塞现象木文主耍讨论死锁的基本概念，然 后讨论解决死锁的3种途径：死锁预防，死锁检测，死锁避免.【关键字】 死锁；死锁条件；死锁处理一引言在计算机系统中，系统资源是有限的，但是在往往涉及到进程对有限资源的占有问题, 在早期的系统中，曲于系统结构，规模以及系统资源分配等问题都相对简单，使随着计算 机急速的不断发展，软件系统变得庞大复杂，系统资源的种类日益增多，而h许多资源是 独占资源

2、，有由于进程之间的相互通信等，使得系统岀现死锁现象大大增加。死锁的出现, 是系统无法正常运行，给系统带来了极大的危害。为此，关于死锁问题的研究已成为操作 系统理论的重耍课题z。木文就操作系统的死锁相关问题进行讨论。二死锁的概叙死锁是进程死锁的简称，是曲dijkstra于1965年研究银行家算法时首先提出來的。它 是计算机操作系统乃至并发程序设计屮最难处理的问题之一。实际上，死锁问题不仅在计 算机系统中存在，在我们日常生活中它也广泛存在。1. 什么是死锁所谓死锁，是指两个或两个以上的进程在执行过程屮，因争夺资源而造成的一种互 相等待的现象，若无外力作用，它们都将无法推进卞去。此时称系统处于死锁状

3、态或系统 产生了死锁，这些永远在互相等待的进程称为死锁进程。曲于资源占用是互斥的，当某 个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法 继续运行，这就产生了一种特殊现彖死锁。2. 产生死锁的条件计算机耍能产生死锁问题必需满足如下的四个条件，缺一不可。<1）互斥条件。即某个资源在i段吋间内只能由一个进程占有，不能同吋被两个或 两个以上的进程占有。这种独占资源如cd-rom驱动器，打印机等等，必须在占有该资 源的进程主动释放它之后，其它进程才能占冇该资源。这是曲资源本身的属性所决定的。 如独木桥就是一种独占资源，两方的人不能同吋过桥。2不可抢占条件。进程所获得

4、的资源在未使用完毕z前，资源屮请者不能强行 地从资源占冇者手中夺取资源，而只能曲该资源的占冇者进程自行释放。如过独木桥的人 不能强迫对方后退,也不能非法地将对方推下桥，必须是桥上的人自己过桥后空出桥面（即 主动释放占有资源），对方的人才能过桥。3占有且申请条件。进程至少已经占有一个资源，但又申请新的资源；由于该 资源已被另外进程占有，此吋该进程阻塞；但是，它在等待新资源之吋，仍继续占用已占 有的资源。还以过独木桥为例，甲乙两人在桥上相遇。甲走过一段桥面（即占有了一些资 源），述需耍走其余的桥而（申请新的资源），但那部分桥而被乙山冇（乙走过一段桥而）。 甲过不去，前进不能，又不后退；乙也处于同样

5、的状况。（4）循环等待条件。存在一个进程等待序列pl, p2, pn,其中p1等待p2 所占冇的某一资源，p2等待p3所占有的某一源，,而pn等待p1所占冇的的某一资 源，形成一个进程循环等待环。就像前面的过独木桥问题，甲等待乙占有的桥面，而乙又 等待甲占冇的桥面，从而彼此循环等待。三死锁的处理前面介绍了死锁发生吋的四个必要条件，只要破坏这四个必要条件屮的任意一个条件, 死锁就不会发生。这就为解决死锁问题提供了可能。一般地，解决死锁的方法分为死锁的 预防，避免，检测与恢复三种。将在下而分别加以介绍1死锁预防（1）破坏”不可剥夺”条件在允许进程动态中请资源的前提下规定，一个进程在中请新资源的要求

6、不能立即得到满 足时，便处于等待状态，而一个处于等待状态的进程的全部资源可以被剥夺.就是说,这些资 源隐形的释放了,被剥夺的资源重新加入到资源表中，仅当该进程重新获得它原有的资源以 及得到新申请的资源时，才能重新启动执行具体实施方案冇两个.方案一:若一个进程已占用了某些资源，又要屮请一个新的资源，在屮请新的资源时，不能 立即得到满足，在变为等待状态之前，该进程必须释放已占冇的所冇资源.方案二:若一个进程申请某些资源，首先系统应检查这些资源是否可用，如果可用,就分配 给该进程.否则，系统检查这些资源是否分配给另外某个等待进程.若是，则系统将剥夺所需 资源，分配给这个进程.如果资源没冇被等待进程占

7、冇，那么，该进程必须等待在等待过程中, 其资源也有可能被剥夺.（2）破坏”请求和保持”条件第一种发放是每个进程必须在开始执行前就中请它所需要的全部资源，仅当系统能满足 进程的资源申请要求月把资源一次性分配给进程后,该进程才能开始执行这是静态分配资 源策略，而资源的动态分配是指进程需要使用资源时才提出屮请，系统在进行分配静态分 配资源策略的优点是简单，安全，容易实施;但其缺点是言重浪费系统资源，会造成一些资源 在很长吋间内得不到使用，降低资源利用率.第二种方法是仅当进程没有占用资源时才允许它去屮请资源，如果进程已经占用了某些 资源而又要在申请资源,则它应先归还所占的资源后再申请新资源这种方法也存

8、在着资源 利用率低的缺点.（3）破坏“循环等待”条件采用资源有序分配策略,其基本思想是将系统中所有资源顺序编号，一般原则是，较为紧 缺，稀少的资源的编号较大进程申请资源时,必须严格按照资源编号的顺序进行，否则系统 不予分配.即一个进程只有得到编号小的资源,才能屮请编号较大的资源;释放资源时，应按 编号递减的次序进行.例如，设扫描仪，打印机,磁带机，磁盘的编号依次为1245.这样所冇进程对资源的巾请, 严格的按编号递增的次序提出可以证明，采用资源有序分配策略，不会出现进程的循环等待，即破坏了循环等待条件.下面我们以解决经典的进程同步问题哲学家就餐问题來考查如何利用资源冇序分配法防止死锁.有5个哲

9、学家以思考，用餐交替进行的方式生活，它们坐在一张圆桌边，桌了上有5个盘了和5只筷了，如图84所示.当一个哲学家思考时，他与邻座的哲学家没有任何联系，当一个哲 学家感觉到饿了，他就试图拿起他左右两边的筷子用餐如果他的邻座已经拿到了筷子，则 他可能只拿到一只升值一只筷子也拿不到当一个饥饿的哲学家得到了两只筷子，他就可以 用餐.当他用餐完毕，她就放下筷子并再次开始思考.对上述问题的一个简单的解决反感是 为每只筷子设置一个信号量，一个哲学家通过在相应信号量上执行p操作抓起一只筷子，通 过执行v操作放下已知筷了,5个信号量构成一个数组：var chopstick array0.4 of semaphor

10、e;毎个信号量都置初值为1.于是，哲学家 1(1<=1<=5)进程可描述如下：repeat思考；p(chopsticki); 拿左筷子p(choopstick(i+ l)m0d5 );拿右筷子用餐；v(chopsticki);放左筷子v(chopstick(i+l)mod5);放右筷子until false;以上解法虽然可以保证互斥使用筷子,但有可能产生死锁假设5个哲学家同时抓起各自 左边的筷子，于是5个信号量的值都为0,此吋，当每一个哲学家企图拿起他右边的筷子吋, 便出现了循环等待的局面-死锁.为了防止死锁的产生，口j以采用资源的冇序分配法，规定每个哲学家想用餐时总是先拿编 号小

11、的筷子在拿编号大的筷子就不会出现死锁现在，因此，哲学家i(lv=iv=4)进程的程序仍 然不变，而第5个哲学家进程的程序可作如下改进：repeat 思考；p(chopstick 1); 拿右筷子p(chopstick 5);拿左筷子用餐v(chopsticklj);放右筷 了v(chopstick 5);放左筷子until false;下而我们分析一下，当每个哲学家都想用餐时，可能冇4个哲学家都已拿到了 t己左边的 一支筷了，而剩卜的第5个哲学家拿不到编号小的筷了而等待,改哲学家不可能去拿另一支 筷子因此,4个哲学家中的一个哲学家就冇机会拿起其右边的筷子而可以用餐，用餐后放下 一双筷子，以使另

12、一个哲学家又可得到右边的筷子去用餐，同意的，其他哲学家也都先后可 吃到饭，从而防止死锁.一般为了提高资源的利用率，通常应该按照大多数进程使用资源的 次序对资源进行编号，先使用者编号小，后世用者编号大.2死锁的检测与恢复一般来说，由于操作系统有并发，共享以及随机性等特点，通过预防和避免的手段 达到排除死锁的口的是很困难的。这需要较大的系统开销，而且不能充分利用资源。为 此，一种简便的方法是系统为进程分配资源吋，不采取任何限制性措施，但是提供了检 测和解脱死锁的手段：能发现死锁并从死锁状态中恢复出来。因此，在实际的操作系统 屮往往采用死锁的检测与恢复方法来排除死锁。死锁检测与恢复是指系统设有专门的

13、机构，当死锁发生时，该机构能够检测到死锁发 生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态 中恢复出来。(1) 死锁的检测死锁检测算法是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路，则系统中一定没有死锁。下面简单介绍系统对资源的分配情况，用资源分配图表示，如图1和图2p1图1资源分配图图2资源分配图图屮所示为一个小的死锁的例子。这时进程p1占有资源r1而申请资源r2,进程p2 占有资源r2而中请资源r1,按循环等待条件，进程和资源形成了环路，所以系统是死 锁状态。进程pl, p2是参与死锁的进程。下面我们再来看一看死锁检测算

14、法。算法使用的数据结构是如下这些：占有矩阵a：十m阶，其中n表示并发进程的个数，m表示系统的各类资源的个数, 这个矩阵记录了每一个进程当前占有各个资源类中资源的个数。申请矩阵r： n*m阶，其屮n表示并发进程的个数，m表示系统的各类资源的个数， 这个矩阵记录了每一个进程当前要完成工作需要屮请的各个资源类中资源的个数。空闲 向量t：记录当前m个资源类中空闲资源的个数。完成向量f：布尔型向量值为真（tee） 或假（false）,记录当前n个并发进程能否进行完。为真即能进行完，为假则不能进行完。 临时向量w：开始时w： =to算法步骤：（1）w： =t,对于所冇的 i=l, 2, n,如果 ai=o

15、,则 f小=true；否则,fi： =false（2）找满足下面条件的下标i：fi：二false 并ji ri <=w如果不存在满足上面的条件i,则转到步骤(4)。(3) w： =w+aifi： =true转到步骤(2)(4) 如果存在i, fi： =false,则系统处于死锁状态，且pi进程参与了死锁。什麽吋候 进行死锁的检测取决于死锁发牛的频率。如果死锁发牛的频率高，那麽死锁检测的频率也 耍相应捉高，这样一方而可以捉高系统资源的利用率，一方而可以避免更多的进程卷入死 锁。如果进程屮请资源不能满足就立刻进行检测，那麽每当死锁形成时即能被发现，这和 死锁避免的算法相近，只是系统的开销较大

16、。为了减小死锁检测带來的系统开销，一般采 取每隔一段吋间进行一次死锁检测，或者在cpu的利用率降低到某一数值吋，进行死锁 的检测。(2) 死锁的恢复一旦在死锁检测吋发现了死锁，就要消除死锁，使系统从死锁状态屮恢复过来。(1) 最简单，最常用的方法就是进行系统的重新启动，不过这种方法代价很大，它意味 着在这z前所冇的进程已经完成的计算工作都将付z东流，包括参与死锁的那些进程，以 及未参与死锁的进程。(2) 撤消进程，剥夺资源。终止参与死锁的进程，收冋它们占有的资源，从而解除死锁。 这时又分两种情况：一次性撤消参与死锁的全部进程，剥夺全部资源；或者逐步撤消参与 死锁的进程，逐步收回死锁进程占有的资

17、源。一般来说，选择逐步撤消的进程时要按照一 定的原则进行，目的是撤消那些代价最小的进程，比如按进程的优先级确定进程的代价; 考虑进程运行吋的代价和与此进程相关的外部作业的代价等因素。此外，还有进程回退策略，即让参与死锁的进程回退到没有发生死锁前某一点处，并 曲此点处继续执行，以求再次执行时不再发生死锁。虽然这是个较理想的办法，但是操作 起来系统开销极大，要有堆栈这样的机构记录进程的每一步变化，以便今后的回退，有吋 这是无法做到的。3死锁的避免死锁避免的基木思想是:系统对进程发出每一个系统能够满足的资源屮请进行动态检 查,并根据检查结果决定是否分配资源，如果分配后系统可能发生死锁，则不予分配，否

18、则予 以分配这是一种保证系统不进入死锁状态的动态策略.死锁避免和死锁预防的区别在于，死锁预防是设法至少破坏产生死锁的四个必要条件 之一，严格的防止死锁的出现,而死锁避免则不那么严格的限制产生死锁的必要条件的存在, 因为即使死锁的必要条件存在，也不一定发生死锁死锁避免是在系统运行过程屮注意避免 死锁的最终发牛.(1)安全与不安全状态由于在避免死锁的策略中允许进程动态的屮请资源，因而系统需提供某种方法在进行 资源分配之前，先分析资源分配的安全性当估计到口j能冇死锁发生时就应设法避免死锁的 发牛.如果操作系统能保证所有的进程在有限的吋间内得到需要的全部资源，则称系统处 于”安全状态",否则

19、说系统是不安全的所谓安全状态是是指，如果存在一个由系统中所冇进程构成的安全序列pl,.pn,则 系统处于安全状态一个进程序列pl,.pn是安全的，如果对于其屮每一个进程 pi(lv=iv=n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程pj(jvi)当前占 冇资源量z和.系统处于安全状态则不会发生死锁如果不存在任何一个安全序列,则系统 处于不安全状态.不安全状态一定导致死锁，但不安全状态不一定是死锁状态.即系统若处 于不安全状态则口j能发生死锁(2)银行家算法最著名的死锁避免算法是由dijkstra|1965和habermann! 1969提出来的银行家算法.这 一名称的來力是基于

20、该算法将操作系统比作一个银行家，操作系统的各种资源比作周转资 金，中请资源比作向银行贷款的顾客，那么操作系统的资源分配问题就如同银行家利用其资 金贷款的问题，一方而银行家能贷款给若干顾客，满足顾客对资金的要求;另一方面,银行家 可以安全的收冋其全部贷款而不至于破产.就像操作系统能满足每个进程对资源的要求，同 吋整个系统不会产生死锁.为保证资金的安全，银行家规定：(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；(2) 顾客可以分歧贷款，但贷款的总数不能超过最大需求量；(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款;(4