死锁

为什么会发生死锁

生活中常见的交通堵死，一大堆汽车因为争夺行路权，互不相让而造成阻塞。又或者因车辆发生故障抛锚或两辆车相撞而造成道路阻塞。
在这种情况下，所有的车都停下来，谁也无法前行，这就是死锁。

除了交通之外，人类活动中到处充满着死锁的概念。

例如，一个机构里的领导集团对某个问题意见相左，无法达成协议，从而造成机构行为瘫痪。
死锁的发生，归根结底是因为对资源的竞争。
因为大家都想要某种资源，但又不能随心所欲地得到所有资源，在争夺的僵局中，导致任何人无法继续推进。

在一个多道编程的环境里，一个系统里存在多个线程，而这些线程共享该计算机系统里的资源。
因为资源竞争而造成系统无法继续推进就难以避免了。

这里所说的资源就是一个程序工作时需要的东西：磁盘驱动器、锁、信号量、数据表格等。
资源既可以是硬件，如 CPU、内存、磁盘等，也可以是软件，看不见摸不着，如锁、信号量等。
根据资源是否可以抢占分为：可抢占资源和不可抢占资源。
可抢占资源当然是可以从持有者手中强行抢夺过来的资源，且不会发生系统运行紊乱；
不可抢占资源则不能从持有者手中强行抢夺。如果强心抢夺，则将造成系统运行错误。

当然，从绝对概念上说，没有什么资源是不可抢占的。因此，不可抢占只不过是相对意义上的概念。目标是保证每个程序都能正确运行。
如果抢占一个线程所持有的资源后，还能找到某种方式让该程序正确运行下去，则该资源就是可抢占的；否则，就是不可抢占的。

例如，CPU 是可抢占资源。因此可以将一个线程强行从 CPU 下拽下来，换上另一个线程来运行。
被抢占的线程可以在稍后继续运行，并正确结束。而 CD 刻录机就是不可抢占资源，如果在刻录光盘的中途将某个线程赶出来，接着刻录另一个线程的数据，则该张光盘将成为废品。
锁、打印机等也属于不可抢占资源。

死锁的描述

我们知道，线程的执行需要资源，它们都要求以某种顺序来使用资源。如果请求被拒绝了，那就等待。线程使用资源的顺序通常如下：

(1) 请求资源
(2) 使用资源
(3) 释放资源

线程在资源请求没有批准的情况下必须等待。这种等待有两种应对方式：一是阻塞等待；二是立即返回，执行别的事情，等以后再请求。
当然也可以失败退出，终止线程。就像我们在没有资源的情况下停止工作一样。

如果线程采用第 2 种方式(立即返回)，则不会发生死锁，因为没有等待。但如果采用第一种方式，则死锁就有可能发生。
例如，如果有 n 个线程，T1, ..., Tn，n 个资源, R1, ... Rn。
其中 T1 持有资源 R1，但又请求资源 Ri+1，这样就将形成死锁。可以用有向图来表示资源的占用和需求关系。以方框代表资源，圆圈代表线程。
从资源指向线程的实线表示该资源已被该线程获得，从线程指向资源的虚线表示该线程在等待该资源。

n 个线程因循环等待资源而形成死锁：

n个线程因循环等待资源而形成死锁

可以看出，每个线程都在等待某一个资源，因此没有线程可以推进，从而形成死锁。

到现在可以给死锁下一个正式定义了：如果有一组线程，每个线程都在等待一个资源，因此没有线程可以推进，从而形成死锁。

到现在可以给死锁下一个正式定义了：如果有一组线程，每个线程都在等待一件事情的发生，而这个事件只能由该组线程里面的另一个线程发出，
则称这组线程发生了死锁。

这里的事件通常是资源的释放。在死锁状态中，没有线程可以执行、释放资源或被叫醒。

例如，有线程 A 和线程 B，如果线程 A 和线程 B 交替执行，线程 A 首先执行，获得锁 x；然后线程 B 执行，获得锁 y；
但在线程 B 试图获得锁 x 的时候将被拒绝(因为线程 A 持有锁 x)，因此将等待锁 x；
这个时候线程 A 再执行，试图获得锁 y，因此锁 y 被线程 B 持有，线程 A 将等待锁 y 上。
至此，线程 A 和线程 B 皆不能执行，也皆不能释放锁(因为已经等待另一把锁)，从而造成死锁，如图所示：

线程AB因竞争锁xy而形成死锁

当然，上述代码并不一定会发生死锁。如果线程 A 先执行，获得 x 和 y 两把锁之后线程 B 再执行，则将不会发生死锁。
事实上，上述代码发生死锁的可能性远低于不发生死锁的可能。
但在讨论死锁问题时，我们需要关注的是死锁的可能，而不是死锁的概率。

死锁的 4 个必要条件

从上面可以看出，死锁的发生必须具备一定的条件。可以看出来，死锁的一个必要条件似乎是循环等待。
除此之外，死锁还需要具备别的条件吗？当然。死锁的发生必须满足 4 个条件，分别细说如下

条件1:
死锁发生的必要条件是资源有限。即一个系统里面的资源数量有限，以致无法同时满足所有的线程的资源需求。
这个条件非常直观，如果每个线程都有足够资源同时推进，自然不会发生死锁。就像人类社会，如果每个人的资源需求都获得满足，想要什么就能获得什么，那你还不满意吗？
自然不会发生竞争、争斗和战争。遗憾的是，资源是有限的，你运气好就等到资源，运气不好就等不到，而且这种不好的运气是时常发生的。

这个条件也称为资源互斥条件。即资源不能共享，在一个时候只能由一个线程使用。这个和资源有限是等价的。
如果资源可以同时被多个线程使用，则将不会发生死锁。

条件2:
死锁的另外一个必要条件是持有等待。即一个线程在请求新的资源时，其已经获得的资源并不释放，而是继续持有。

线程的工作过程是请求某些资源，进行工作，然后请求新的资源，继续工作。当工作结束时释放所有资源。
如下代码所示(这里假定第一阶段的工作量是有限的)：

阶段1. while (not done) {
    acquire some resources;
    work
}
阶段2. release all resources;

如果不是这样，死锁也不能发生。因为一个线程在请求资源时，其并没有任何资源，自然就不会阻挠别的线程运行。
阻挠别的线程运行的线程必定已经获得了其所需的全部资源，因而能够顺利执行到结束，并最终释放资源。

条件3:
死锁的另外一个条件是不能抢占。如果可以抢占一个资源，则也不会发生死锁。
例如，上面的例子中，如果线程 A 可以从线程 B 手中抢占锁 y，则死锁不会发生。
从这里可以推断出，凡事可以抢占的资源，均不会成为死锁的原因。例如，我们不会因为对 CPU 的争夺而产生死锁

条件4：
就是我们已经提过的循环等待条件。这是死锁的最后一个条件。
如果你等我、我等你，大家都这样等着对方，就产生了死锁。

哲学家就餐问题

讨论死锁所用的一个经典例子是“哲学家就餐问题”。哲学家每天只做两件事情：思考和吃饭。
他们每天不停地思考人生的哲理，如人从什么地方来，人为什么是现在这个样子，人类往哪里去等深刻的问题。
当然，思考久了就会感到饥饿，而饥饿了就要吃饭。但吃饭是有规矩的。

吃饭的规矩就是：哲学家围坐在一个圆桌边，每个人的左右两边均放着一根筷子。
如果要吃饭，需要获得左右两边的筷子(不能用一根筷子吃饭)，如图所示：

哲学家就餐问题

我们很自然地得到一个算法，对于每一个哲学家，运行如下地算法：

(1) 等待左边地筷子可用，然后拿起左边地筷子。
(2) 等待右边地筷子可用，然后拿起右边地筷子
(3) 吃饭
(4) 放下两根筷子

显然，如果每个哲学家穿插着执行，将出现每个哲学家都拿起左边筷子，而等待右边筷子的情况，死锁将发生。

死锁的应对

如何应对死锁呢？只要看看人类是如何应对生活中的死锁(难题)，就可以推测出操作系统是如何应对死锁的。
那么人有哪些办法来应对生活中的难题呢？从高级境界来看，只有两种策略，即

允许死锁发生
不让死锁发生

每种策略又有两种子对策。对于第 1 种策略，其两个子对策就是：

(1) 假装没有看见，不予理睬
(2) 在死锁发生后，想办法予以解决

对于第 2 种策略，其两种子策略为：

(1) 通过生活中的仔细检点，避免难题出现
(2) 通过将发生死锁的必要条件消除，杜绝死锁的发生

操作系统应对死锁的策略与人类应对难题的策略一样，也是两大种、四小种。下面我们分别予以讨论

顺其自然：不予理睬

这是人类面对难题时经常采取的办法，或者是大部分人遇到困难时采取的办法。

研究商业操作系统的人不认为死锁是什么大问题，因为经过分析发现，死锁发生的频率不太高(当然这点有争议)，所以不必管它。
另外，防止死锁的代价很高，防止死锁比重启 100 此代价还高，因此不如直接重启。如果死锁发生，重启即可。
这就是为什么 Windows、Linux 和其他商业操作系统都没有采取死锁防止措施，这就是为什么你的电脑经常死机的原因。

在操作系统设计时经常不得不进行折中，是想尽量方便，偶尔出点错误呢？还是保证系统完全正确，但是费了很大力气？当然是前者。
计算机科学的一个原则就是寻求方便。当然，如果牵涉的是高可靠性系统、实时控制系统，那就另当别论了，那绝对不允许死锁

先礼后兵：死锁检测与修复

防止死锁非常麻烦，但是我们很愿意采取不予理睬的策略来应对死锁。
但是在某些时候，还得防止死锁，例如对待高可靠性系统、实时系统等。

另外，如果你是一个不厌其烦的人，或者你是一个有决心、有意志力的人，当然就不会允许在面对困难时无所作为了。
你会绞尽脑汁，想尽办法来解决难题。而这也正是我们操作系统解决死锁的第 2 种策略：死锁检测与修复。

1. 检测死锁

如果想纠正死锁，自然得知道是否已经死锁了。所以死锁修正的第一件事是要检测死锁。这个似乎很简单。
死锁的原因是资源竞争，只要我们对资源的拥有和对资源的请求都清楚了，问题就解决了。
或者说，就是将线程的资源占用和需求关系用一个有向图表示出来，然后查看图中有没有循环。如果有，就发生死锁；如果没有，就没有发生死锁。

这个说起来很容易，但是要检测却不容易。
如果在每次资源分配发生变化时，做一次这样的检查，系统效率将出现明显下降。

一种效率较高的算法是利用矩阵。这种算法用到两个矩阵：一个叫资源分配矩阵，另一个叫资源等待矩阵。
矩阵的每一行代表一个线程，每一列代表一种资源。
在资源分配矩阵中，行列交叉的数值代表该线程已经拥有该资源的数量；
在资源等待矩阵中，行列交叉的数值代表特定行还需要特定资源的数量。

资源分配矩阵