对死锁的思考【1】/thinking in deadlocks

开篇

死锁是操作系统中的重要概念，和操作系统中的其他重要概念一样，对它的正确理解将帮助你写出更加高效、优秀的程序。

这里没有晦涩的定义，只有易懂的描述和生动的例子。相信你看了之后会有所收获。

什么是死锁

简单的说，死锁就是电脑里的硬件资源或者软件资源不够用了。

为什么会有这种情况呢？比如说A占有资源m，请求资源n。B占有资源n请求资源m。进程A和B都会因为请求不到自己的资源而睡眠。

下面将进一步介绍。

更形象的描述-死锁建模：

为了能对死锁进行更好的分析，我们为死锁建模。就是用一个有向图来表示进程和资源的使用情况，圆形节点表示进程，方形节点表示资源。

资源指向进程的边表示该进程占有该资源，进程指向资源表示进程请求分配资源。

如图： 

a): 进程A占有资源R。b)进程B申请资源S。

c):进程D占有资源T，申请资源U

　 进程C占有资源U，申请资源T。

如上c) 出现死锁。进程C等待着资源T，资源T被进程D占有，进程D有等待进程C占有的资源U。这样两个进程就这么等待下去。

死锁的定义

有了上面的基础，现在来看死锁的规范定义：

A set of processes is deadlocked if each process in the set is waiting for an
event that only another process in the set can cause.

一个进程集合中的每个进程都在等待只有该进程集合中的进程才能引发的事件

死锁产生的条件：

1、互斥条件：每个资源要么已经分配给一个进程，要么是可用的。

2、占有和等待条件:已经占有资源的进程可以申请其他资源。

3、不可抢占条件：已经被占有的资源不能被其他的进程抢占， 只有占有它的进程才能显示释放。

4、环路等待条件：死锁发生时，系统中有两个或两个以上的进程一条环路，该环路中的每一个进程都在等待下一个进程所占有的资源。

　　死锁发生时，以上的四个条件必须同时满足，如果有其中的一个条件不满足，死锁就不会发生。

那么 ，只要让上面的条件不满足就能避免死锁的发生了吗？是的，这将在下文死锁的预防中讨论.

死锁的检测

每种类型一个资源的死锁检测：

通过上面的描述，应该对死锁有了一些认识了吧。那么，如何检测一个进程集合中是否会存在死锁呢？

有了上面的经验，只要吧进程集合中的每个进程和各自占有和请求的资源用刚才的死锁建模表示出来，然后再判断，如果存在圈，

就能证明里面有死锁的存在了。 

用实例能更好的说明问题：里面有A到G七个进程，R到W六中资源；

1、进程A占有资源R，请求资源S

2、进程B不占有任何资源，请求资源T

3、进程C不占任何资源，请求资源S

4、D占有资源U，请求资源S和T

5、E有资源T，请求资源V

6、F有资源W，请求资源S

7、G有资源V，需要资源U

 以上进程集合和资源的关系可用下图表示：

很直观的，就能看到图中存在一个圈，所以存在死锁。

还是简单的分析下吧 ：从D点入手，D需要T，T被E占有，E需要V，V被G占有，G需要U，U被D占有。圈里的每个进程都在等待他的下一个

所占有的资源，所有的进程就无限的等待下去。显然， 上述进程集合发生了死锁。

所以对于这种情况，可以记录下进程集合中各个进程和资源的关系，通过判断图中是否存在圈的方法来检测是否存在死锁。

判断图中是否存在圈可以用图的深度优先搜索来实现，可以参考前面的博文：图的深度优先搜索详解/Depth-first search/C++

大家可能已经注意到了，从开始到现在我们讨论的资源都有一个特点，就是每一种类型的资源只有一个。如上面的例子中，资源R只有1个，

S也是一样只有一个。对于计算机中的某些资源，某些资源可能确实只有一个，比如打印机，扫描仪等等，而还有很多类型的资源，可以存在多个。比如内存空间，寄存器等。

刚才分析了每种类型资源只有一个的死锁的情况，下面看每种类型资源有多个的情况:

每种类型多个资源的死锁检测：

对于这种情况，就需要另外的一种表示方法了。对于任何问题的分析，总是要先把它表述出来。

下面对资源和进程分开讨论；

资源：

对于一个资源，它要么被某个进程占有，要么可以被申请占有。这里假设资源类型编号为1、2、、、、m的资源。

资源的总数用E1，E2、、、Em来表示

剩余的资源用A1，A2、、、Am来表示 

比如资源类型E2表示扫描仪，那么E2=1就表示系统中有一台扫描仪。A2=0表示剩余的扫描仪为0；

进程：假设进程集合中有编号为1、2、、、、n的进程。

由于我们考虑的是死锁，对于一个进程，我们要记录的是它占有的资源，它需要的资源。

这里用两个矩阵表示：Cij 的值表示进程i占有资源j的数目。Rij表示进程i需要资源j的个数；

参见下图：

每种资源的总数=已被进程占有的数量+剩余数量     根据上图，用数学表达式表述为：

 对于任意的一个进程 i 如果Ri1,Ri2、、、Rim都小于对应的A1，A2、、、、Am，说明这个进程可以被执行，所以可以先看进程集合里面有没有这中可以被执行的进程，让他们执行，完成后释放所占有的资源。这时候剩余资源变多了，在判断进程集合中是否还有可以被执行的进程，如果有，就执行，然后释放资源。重复以上过程，如果最后进程集合中所有进程都被执行了，说明不存在死锁，反之，如果最后进程集合中还有不能被执行的进程，那么进程集合存在死锁。光说理论太枯燥了，而且不容易理解。下面用实例说话;

先看资源和进程的状态图吧：

图中共有四种资源，总数和剩余数量分别用E和A表示出来了

共有3个进程，他们占有的资源和需要的资源分别用矩阵C和R表示。

进程1：需要第一种资源2个，第四种资源1个，而第四资源没有了，所以进程1不能被先执行。

进程2：需要第一种资源1个，第三种资源1个，剩余资源也不能满足需要，所以不能执行。

进程3：需要第一种资源2个，第二种资源1个，剩余资源可满足请求，所以进程3执行。

进程3执行后，释放占有资源。更新A:(2,2,2,0),这时进程2可以执行了，继而进程1也能执行 ，所以该进程集合不存在死锁。

假如图中情况有所改变，进程2需要第四种资源1个，资源二1个和资源一两个，那么所有的请求都得不到满足，系统进入死锁。

这篇博文主要阐述了死锁的定义和死锁的检测、

死锁的恢复、死锁的避免、死锁的预防将在下一篇博文中阐述。