200
深入理解並行編程-分割和同步設計（一）
在商用計算機中，多核係統已經越來越常見了，本章將描述如何設計能更好利用多核優勢的軟件。我們將介紹一些習語，或者叫“設計模式”，來幫助您權衡
性能、可擴展性和響應時間。在上一章我們說過，您在編寫並行軟件時最重要的考慮是如何進行分割。正確的分割問題能夠讓解決辦法簡單、可擴展並且高性能，而
不恰當的分割問題則會產生緩慢且複雜的解決方案。
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：那麼“水平並行化”裏的“水平”是什麼意思呢？
文章轉自 並發編程網-ifeve.com
最後更新：2017-05-22 16:37:25