并发编程网 - ifeve.com

原文链接     作者：paul    译者：谢宝友，鲁阳，陈渝

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

1.1分割练习

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

1.1.1哲学家就餐问题

图1.1：哲学家就餐问题

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

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

图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，开始就餐。

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

图1.3：哲学家就餐问题，分割解法

图1.3是一种方法，里面只有4位而不是5位哲学家，这样可以更好的说明分割技术。最上方和最右边的哲学家合用一对叉子，而最下方和最左边的哲学家合用一对叉子。如果所有哲学家同时感觉饿了，至少有两位能同时就餐。另外如图中所示，现在叉子可以捆绑成一对儿，这样可以同时拿起或者放下，这就简化了获取和释放算法。

小问题1.1： 哲学家就餐问题还有更好的解法吗？

这是“水平并行化”[Inm85]的一个例子，或者叫“数据并行化”，这么叫是因为哲学家之间没有依赖关系。在数据处理型的系统中，“数据并行化”是指一种类型的数据只会穿过一系列同类型软件组件其中的一个。

小问题1.2：那么“水平并行化”里的“水平”是什么意思呢？