操作系统中进程死锁的探讨

摘要：在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但由于系统中资源分配不当或进程间推进顺序非法可能发生死锁。死锁是不能完全避免的，只能尽可能的去完善操作系统中的各项功能体系的设计，减少死锁的发生概率。通过简单实例，从死锁产生的原因和条件出发，讨论了避免和解除死锁的几种方法。

关键词：死锁；银行家算法；进程；共享资源

中图分类号：TP316文献标识码：A文章编号：1009-3044(2012)01-0201-03

The Discussion of Process Deadlock in Operating System

ZHANG Jun

(hulunbuir College, Hulunbuir 021008, China)

Abstract: Although people can improve the using rate of resources and throughput of system by means of the concurrency of multiple processes in multiprogramming system, deadly lock can still occur due to improper resource allocation and illegal execution sequence. Deadly lock is unavoidable. People can only improve the design of the all kinds of functions architecture of OS to decrease the occurrence of deadly lock.The thesis discusses some means to avoid and release deadly lock from the reasons and conditions through some simple examples.

Key words: deadly lock; banker algorithm; process; sharing resourses

1死锁的引入

在计算机的许多专业课（如操作系统、数据库系统以及网络通信）中，由于进程的并发执行和资源的共享，当系统中资源分配顺序或者进程推进顺序不当时就会造成系统死锁。处于死锁状态的系统中，进程之间互相等待资源而永远不能继续向前推进，严重地影响了系统的可靠性。

在日常生活中经常会出现一种现象，图1给出了某一个街区交通死锁的情况，从图中可以看到四个街区的路口都被连续的车辆堵塞，使得各车辆无法再前进的状态，这四个街口正是车流相互竞争的共享资源，谁占据后都不愿意主动放弃，最后造成谁也不会释放自己占有的资源，谁也得不到所需资源，大家都处在相互等待中，形成所谓的死锁。

在操作系统中也有类似的情况。在两个或多个并发进程中，如果每个进程锁定了其他进程试图锁定的资源，此时会造成这些进程都想得到资源而又都得不到资源，永久阻塞，从而出现死锁。图2是两个进程发生死锁的例子（p1和p2是进程，s1和s2是共享资源），p1占有s1，p2占有s2，p1申请s2却申请不到，因为p2没执行完不会放弃s2，只能等待，p2申请s1也申请不到，因为p1没执行完不会放弃s1，只能等待，p1和p2互相等待永远不可能发生的事件，操作系统中这样的现象就是死锁。

2可以死锁的资源

每个用户进程要想得到执行可能获取或等待获取各种资源。以下类型的资源可能会造成阻塞，并最终导致死锁。

1）锁。等待获取资源（如对象、页、行、元数据和应用程序）的锁可能导致死锁。如图2所示，进程P1在S1上有共享锁（S锁）并等待获取S2的排他锁（X锁）。进程P2在S2上有共享锁（S锁）并等待获取S1的排他锁（X锁）。这将导致一个锁循环，其中，P1和P2都等待对方释放已锁定的资源。

2）工作线程。排队等待可用工作线程的任务可能导致死锁。如果排队等待的任务拥有阻塞所有工作线程的资源，则将导致死锁。例如，进程P1获取S1的 共享锁（S锁）后，进入睡眠状态。在所有可用工作线程上运行的进程正尝试获取S1的排他锁（X锁）。因为进程P1无法获取其他工作线程，所以无法执行完并释放S1的锁，这将导致死锁。3）内存。当并发请求等待获得内存，而当前的可用内存无法满足其需要时，可能发生死锁。例如，两个并发查询（Q1和Q2）作为用户定义函数执行，分别获取10MB和20MB的内存。如果每个查询需要30MB，而可用总内存10MB，则Q1和Q2必须等待对方释放内存，然后申请执行，这将导致死锁。

4）用户资源。线程等待可能被用户应用程序控制的资源时，该资源将被视为外部资源或用户资源，并将按锁进行处理。

除了以上资源还有进程互斥体，查询语句等多种资源，这里不再列举。

3死锁产生的条件

3.1进程数条件

1）参与死锁的进程最少是两个；

2）参与死锁的进程至少有两个已经占有资源；3）参与死锁的所有进程都在等待资源；

4）参与死锁的进程是当前系统中所有进程的子集。

3.2必要条件

1）互斥条件：至少有一个资源必须处于非共享模式（即一次只有一个进程使用）。如果另一个进程申请该资源，那么申请进程必须延迟直到该资源释放为止，涉及的资源是非共享的。

2）不剥夺条件：资源不能被抢占（即只在进程完成其任务之后，才会释放其资源）。不能强行剥夺进程拥有的资源。

3）请求和保持条件：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程占有进程在等待一新资源时继续占有已分配的资源。

4）环路等待条件：有一组进程{P0，P1，...，Pn}，P0等待的资源为P1所占有，P1等待的资源为P2所占有，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有，形成一个循环链。

四个条件必须同时满足才会出现死锁，或者说只要使上述四个必要条件中的某一个不满足，则死锁就可以解除。

4死锁的检测

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

死锁的检测也可以用称为系统资源分配图的有向图进行更精确地检测。这种图有一个结点的集合V和一个边的集合E组成。如果图没有环，那么系统就没有进程死锁。如果图有环，那么可能存在死锁。死锁状态的充分条件是当且仅当该状态的进程资源分配图是不可完全化简的。资源分配图的化简过程如下：

1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点。

2）把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边。

3）如果进程资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只有产生死锁的必要条件而不是充分条件。如果能在进程资源分配图中消去此进程的所有请求边和分配边，成为孤立点。经一系列化简，使所有进程成为孤立结点。

5死锁的预防

死锁的预防是一种较简单和直观的事先预防的方法。通过设置某些限制条件，以破坏产生死锁的四个必要条件中的一个或几个来防止死锁的发生。

1）破坏第一个条件。使资源可同时访问而不是互斥使用，这是个简单的方法，磁盘可用这种方法管理，但有许多资源往往是不能同时访问，所以这种做法许多场合行不通。

2）破坏第二个条件。采用剥夺式调度方法可破坏第二个条件，但只适用于对存储资源和处理器资源的分配。当进程已经拥有一些资源，再去申请其他资源未获得成功时，如果主动释放资源（一种剥夺式），然后采取等待，待所需资源都空闲时，再一起向系统提出申请，也能防止死锁。此方法可以用AND型的信号量来实现。

3）破坏第三个条件或第四个条件。许多防止死锁的办法施加于资源的限制条件太严格，会造成资源利用率和吞吐率低。两种比较实用的预防死锁的方法，它们能破坏第三个条件或第四个条件：执行前一次性申请全部资源，没有占有资源时才能分配资源。确保占有并等待条件不会在系统内出现，必须保证当一个进程申请一个资源时，它不能占有其他资源。一种可以使用的协议是每个进程在执行前申请并获得所有资源。另外一种协议允许进程在没有资源时才可申请资源；确保“非抢占”，为了确保这一条件不成立，可使用如下协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占；确保“循环等待”，确保此条件不成立的方法是对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。

6死锁的避免

该方法同样是使用事先预防的策略，在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。这种方法只需事先加以较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但在实现上有一定的难度。

最具有代表性的避免死锁的算法是银行家算法：银行家拥有一笔周转资金，客户要求分期贷款，如果客户能够得到各期贷款，

就一定能够归还贷款，否则就一定不能归还贷款，银行家应谨慎的贷款，防止出现坏账。

银行家算法的基本思想：系统中的所有进程进入进程集合；在安全状态下系统收到进程的资源请求后，先把资源试探性分配给它；系统用剩下的可用资源和进程集合中其他进程还需要的资源作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而保证这个进程运行完毕并归还全部资源；把这个进程从集合中去掉，系统的剩余资源更多了，反复执行上述步骤；最后，检查进程集合，若为空表明本次申请可行，系统处于安全状态，可实施本次分配；否则有进程执行不完，系统处于不安全状态，本次资源分配暂不实施，让申请进程等待。如图3所示。

图3

所以在进程执行过程中求得一个安全序列就可以避免死锁。

7死锁的解除

如果死锁发生会浪费大量系统资源，甚至导致系统崩溃。所以发生率死锁必须给予解除。可采用以下几种简单方法。

1）立即结束所有进程的执行，并重新启动操作系统。方法简单，但以前工作全部作废，损失可能很大。

2）撤销陷于死锁的所有进程，解除死锁继续执行。

3）逐个陷于死锁的进程，回收其资源，直至死锁解除。

4）剥夺陷于死锁的进程占有的资源，但并不撤销它，直至死锁解除。

5）根据系统保存的checkpoint，让所有进程回退，直至足以解除死锁。

6）当检测到死锁时，如果存在某些未卷入死锁的进程，而这些进程随着建立一些新的抑制进程能执行到结束，则它们可能释放足够的资源来解除死锁。

参考文献：

[1] MSDN[EB/OL].msdn.省略.

[2]赵宁.操作系统中多进程并行时的死锁问题[J].铁路计算机应用杂志,2007(12).

[3]王继奎.基于银行家算法的进程安全序列全搜索算法[J].甘肃科学学报,2009(2).

[4]汪江桦.关于操作系统中死锁问题的探讨[J].科技信息,2009(17).

[5]汤子瀛.计算机操作系统[M].西安:西安电子科技大学出版社,2000.

[6]徐小青.操作系统[M].北京:中国物资出版社,1998.

[7]史美林.计算机操作系统教程[M].北京:清华大学出版社,2006.