11.8　死锁

因为线程可以变为阻塞，且因为对象可以拥有互斥锁，这些锁能够阻止线程在锁被释放之前访问这个对象。所以就有可能出现这种情况，某个线程在等待另一个线程而第2个线程又在等待别的线程，以此类推，直到这个链上的最后一个线程回过头来等待第1个线程。这样就会得到一个由互相等待的线程构成的连续的循环，而使任何线程都不能运行。这称为死锁（deadlock）。

如果试图运行一个程序，它立刻就死锁了，人们马上就会知道程序出了问题，并且可以跟踪程序的执行过程来找到问题所在。真正的问题在于，这个程序似乎运行良好，但却隐藏着死锁的可能性。在这种情况下，死锁可能发生但事先却得没有任何征兆，所以它潜伏在程序里，直到客户发现它出其不意地发生了。（并且这个死锁的过程可能很难重复显现。）因此，仔细设计程序来预防死锁是开发并发程序的一个关键的要素。

现在看一个由Edsger Dijkstra虚构的有关死锁的经典问题：哲学家聚餐（dining philosopher）问题。该问题的基本描述指定了5个哲学家（不过这里的例子允许任意数目的哲学家）。这些哲学家将花费他们的部分时间用来进行思考，花费其余部分时间进餐。当他们进行思考时，不需要任何共享资源，但是在他们进餐时使用有限数量的餐具。在原始的问题描述中，餐具就是叉子，每个人需要用两个叉子从桌子中央的碗里取意大利面条，但似乎将餐具说成是筷子更合理。显然，只要每个哲学家进餐就需要两根筷子。

该问题引入了一个难点：作为哲学家，他们只有很少的钱，所以只买得起5根筷子。哲学家们围坐在桌子周围，哲学家与哲学家之间放一根筷子。当一个哲学家想进餐时，他必须同时得到他左边的那根筷子和右边的那根筷子。如果该哲学家的旁边（左边或右边）有人正在使用他所需要的筷子，则我们的这个哲学家就必须等待，直到所需要的筷子变成可用的。

两个哲学家Philosopher不可以同时用take（）拿同一根筷子Chopstick，因为take（）用一个互斥锁Mutex进行同步。另外，如果筷子已经被一个Philosopher占用，另一个Philosopher可以在可用条件available Condition上用wait（）等待，直到Chopstick的当前持有者调用drop（）放下筷子（这也必须同步以防竞争条件，并且保证多处理器系统中的内存可见性）使Chopstick变为可用的。

每个Philosopher持有其左边和右边Chopstick对象的引用，所以可以尝试拿起它们。Philosopher的目的是用部分时间进行思考，用另一部分时间进餐，在main（）函数中就是这样表达的。然而读者会注意到，如果Philosopher花很少的时间进行思考，当他们试图进餐时都来对Chopstick进行竞争，死锁就会更快地发生。所以，可以这样试验一下，思考算子ponderFactor用于衡量一个Philosopher花费在思考和进餐上的时间长度趋势。一个较小的ponderFactor将增加死锁的可能性。

在Philosopher：run（）中，每个Philosopher仅仅不断地重复进行思考和进餐。可以看到Philosopher用于思考的时间量是随机的，然后试图用take（）拿右边的Chopstick，再用take（）拿左边的Chopstick，用于进餐的时间量亦是随机的，然后再次重复这样做。对输出到控制台的操作进行同步，就像在本章中较早时见到的一样。

这个问题很有趣，因为它显示了一个程序可能表面上看起来运行正确，但事实上有死锁的倾向。为了演示这一点，可以使用命令行参数调整因子来影响进餐哲学家的总数及每个哲学家花费思考的时间。如果有许多哲学家或者他们花费很多时间进行思考，那么，虽然有死锁的可能性，但也许永远也看不到死锁。值为0的命令行参数趋向于使死锁尽快发生。^[1]

注意，Chopstick对象不需要内部标识符；而是通过其在数组c中的位置来识别它们。在构造Chopstick对象时，赋予每个Philosopher一个左边和一个右边的Chopstick对象的引用；这些是在Philosopher可以进餐之前必须获取的餐具。除最后一个Philosopher外，将Philosopher的座位安排在贴近的一双Chopstick对象之间来初始化每个Philosopher。最后一个Philosopher的右边Chopstick是顺序号为第0根Chopstick，这样就完成了环绕桌子的座位摆放。因为最后一个Philosopher就座的右边紧挨着第1个Philosopher，他们俩共享第0根筷子。这样的安排可能在某一时间点上所有的哲学家同时试图进餐，并且等待紧挨着他们的哲学家放下筷子，这样程序将会死锁。

如果这些线程（哲学家）花费在其他任务（思考）上的时间越多于花费在进餐上的时间，则他们需要共享资源（筷子）时发生冲突的可能性就会越低，因此可以使人相信，这个程序是没有死锁的（使用非0的ponder值），尽管事实上它可能会死锁。

为了修正这个问题，必须明白如果同时满足以下4种条件，死锁就会发生：

1）相互排斥。线程使用的资源至少有一个必须是不可共享的。在这种情况下，一根筷子一次就只能被一个哲学家使用。

2）至少有一个进程必须持有某一种资源，并且同时等待获得正在被另外的进程所持有的资源。也就是说，要发生死锁一个哲学家必须持有一根筷子并且等待另一根筷子。

3）不能以抢占的方式剥夺一个进程的资源。所有进程只能把释放资源作为一个正常事件。我们的哲学家是有礼貌的，他们不会从别的哲学家手中抢夺筷子。

4）出现一个循环等待，一个进程等待另外的进程所持有的资源，而这个被等待的进程又等待另一个进程所持有的资源，以此类推直到某个进程去等待被第1个进程所持有的资源。因此，头尾相接环环相扣，因此大家都被锁住了。在DeadlockingDiningPhilosophers.cpp中，是因为每个哲学家都试图先得到右边的筷子，而后再得到左边的筷子，所以发生了循环等待。

因为必须所有这些条件都满足才会引发死锁，那么只需阻止其中一个条件发生就可防止产生死锁。在这个程序中，防止死锁最容易的办法是破坏条件四。这个条件发生的原因是由于每个哲学家都试图以特定的顺序拿筷子：先右后左。正因为如此，才可能进入这样的情形：每个人都把持着其右边的筷子，而等待得到其左边的筷子，由此导致循环等待条件产生。然而，如果最后一个哲学家被初始化为先尝试拿左边的筷子，然后再拿右边的筷子，那么该哲学家将永远无法阻止右边紧挨着的哲学家拿到他自己左边的筷子。在这种情形下，就防止了循环等待。这只是问题的一种解决方法，读者也可以通过阻止其他条件发生来解决该问题（更具体的细节请参考论述高级的线程处理的书籍）：

通过确保最后一个哲学家在拿起和放下其右边筷子之前先拿起和放下其左边筷子，就可以消除死锁，程序将会流畅地运行。

没有编程语言上的支持可以帮助防止死锁；这取决于你是否能通过谨慎的设计来避免死锁。这对于那些正试图调试一个发生死锁程序的人来说并不是什么值得安慰的消息。

[1]在写本章内容的时候，Cygwin（www.cygwin.com）正在进行调整变化，改善对它的线程处理的支持。利用Cygwin的这个可利用版本下的程序，我们仍然不能观察死锁行为。举个例子，该程序在Linux系统下很快地就会死锁。