深入理解并行编程-分割和同步设计（一）

问题导读

1.哲学家就餐问题，有哪些解决方案？

2.哲学家就餐与并发是什么关系？

在商用计算机中，多核系统已经越来越常见了，本章将描述如何设计能更好利用多核优势的软件。我们将介绍一些习语，或者叫“设计模式”，来帮助您权衡性能、可扩展性和响应时间。在上一章我们说过，您在编写并行软件时最重要的考虑是如何进行分割。正确的分割问题能够让解决办法简单、可扩展并且高性能，而不恰当的分割问题则会产生缓慢且复杂的解决方案。

1.1分割练习

本节用两个例子（哲学家就餐问题和双端队列问题）作为练习，来说明分割的价值。

1.1.1哲学家就餐问题

图1.1：哲学家就餐问题

图1.1是经典的哲学家就餐问题的示意图[Dij71]。问题中的五个哲学家一天无所事事，不是思考就是吃一种需要用两把叉子才能吃下的“滑溜溜的”意大利面。每个哲学家只能用和他左手和右手旁的叉子，一旦哲学家拿起了叉子，那么不吃到心满意足是不会放下的。

我们的目标是构建一种算法来——有点儿文学化——阻止饥饿。一种饥饿的场景是所有哲学家都同时拿起了左手边的叉子。因为他们在吃饱前不会放下叉子，并且他们还需要第二把叉子才能开始就餐，所以所有哲学家都会挨饿。

哲学家就餐问题，教科书解法 2.jpg

图1.2：哲学家就餐问题，教科书解法

Dijkstra的解决方法是使用一个全局信号量，假设通信延迟忽略不计的话，这种方法非常完美，可是在随后的几十年里这种假设变得无效了。因此，最近的解决办法是像图5.2一样为叉子编号。每个哲学家都先拿他盘子周围编号最小的叉子，然后再拿编号最高的叉子。这样坐在图中最上方的哲学家会先拿起左手边的叉子，然后是右边的叉子，而其他的哲学家则先拿起右手边的叉子。因为有两个哲学家试着去拿叉子1，而只有一位会成功，所以只有4位哲学家抢5把叉子。至少这4位中的一位肯定能拿到两把叉子，这样就能开始就餐了。

这种为资源编号并按照编号顺序获取资源的通用技术在防止死锁上经常使用。但是很容易就能想象出一个事件序列来产生这种结果：虽然大家都在挨饿，但是一次只有一名哲学家就餐。

1. P2拿起叉子1，阻止P1拿起叉子。

2. P3拿起叉子2。

3. P4拿起叉子3。

4. P5拿起叉子4。

5. P5拿起叉子5，开始就餐。

6. P5放下叉子4和5。

7. P4拿起叉子4，开始就餐。

请在进一步阅读之前，思考哲学家就餐问题的分割方法。