 |
-- 會員 / 註冊 --
|
 |
|
|
|
深入理解并行編程 ( 簡體 字) |
| 作者：謝寶友,魯陽 | 類別：1. -> 程式設計 -> 綜合 |
| 譯者： |
| 出版社：電子工業出版社 |  3dWoo書號： 47141
詢問書籍請說出此書號！【缺書】
NT售價： 645 元 |
| 出版日：7/1/2017 |
| 頁數：524 |
| 光碟數：0 |
|
站長推薦：  |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787121315084 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：作者序
我希望能夠說本書的誕生源于甜蜜和光明，但這無疑是個謊言。和許多需要長年堅持努力的事情一樣，本書經過了大量挫折才得以誕生。
你看，大約10年前，在并發領域的一個行業專家小組研討會上，我很榮幸得以提問最后一個問題。一些參會的專家長篇大論地討論了并行編程的高難度，所以我問為什么并行編程不會在10或20年內成為司空見慣的事情。大多數小組成員一點都不喜歡這個問題。事實上，第一個小組成員試圖用一個簡短的回答敷衍了事，但我很容易地做了簡短的反駁。無奈，他嘗試給出了第二個簡短回答，我也繼續反駁。幾輪之后，他大聲喊叫：“像你這樣的人應該用錘子敲敲頭！”我不甘示弱地回答道：“那你可要排隊才能敲得到。”
我不認為這種交流是特別有啟發性的，相反這展示了一個毫無疑問的事實：這位“業內”專家對于并行編程一無所知。不過在場的其他聽眾卻認為這場對話非常有啟發性，尤其是那一位感謝我提出這個問題的聽眾，他的眼里甚至含著淚水。他像學徒一樣在Sequent 計算機系統公司學到了并行編程的訣竅，正如我曾經所做的那樣。后來他跳槽去了另一家公司，他的新雇主開始涉足并行編程。出乎他意料之外，事情發展得并非一帆風順。正如他所說，“我已經足足跟他們說了兩年，只要你用正確的辦法，這并不是很難，但他們完全不聽我的話！”
現在，我們很容易將這個悲傷故事里面的團隊作為反面教材。但是在他們的看法中，并行編程等于用你自己的智力傷害自己。除非你了解實現并行性的正確方法，否則在意識到遇到麻煩之前，你越聰明，挖的坑就越深。因此，你越聰明，并行編程看起來就越難。不僅如此，在這件事發生時，極少有人知道如何進行并行編程，這意味著大多數人剛剛開始了解到他們為自己挖的并行編程坑的深度。
即使如此，當這個人用哽咽的聲音講述他的故事，眼淚滑過他的臉龐時，我意識到我不得不做一些事。那就是寫眼前這本書，這里面不僅僅濃縮我自己四分之一個世紀的經歷，還有其他人加起來數不清幾個世紀的經歷。
我的母語是英語，英語是我唯一可以聲稱掌握了的語言。但幸運的是，感謝魯陽和謝寶友所付出的巨大努力，現在中文版翻譯即將面世。我希望這本書不僅可以幫助你學習我所知道的知識，從而不再需要擔心并行編程，還能使你能夠創建屬于自己的并行編程新發現！
Paul E. McKenney
推薦序
讀著《深入理解并行編程》的樣章，我的腦海里不斷地浮現出9年前的一幕幕。我在網上尋找操作系統的志同道合者，看到一個稅收專業中專畢業者的自薦信，其時他已具有10年的IT行業工作經驗，從事過大量手機、通信行業軟件研發工作，擔任過項目總監研發管理工作，在電信應用開發方面已經做得比較成功。但他對操作系統有濃厚的興趣、執著的追求，放棄了在高層應用軟件方面的既有優勢，專注于操作系統的研究。離職在家，利用半年時間開發出一個嵌入式操作系統模型，計劃兩年內研發一款自研操作系統。有感于他的執著和熱愛，我向公司爭取破格錄取他。我認為做一個操作系統不難，但做生態難，做商業成功難，建議他深入學習開源Linux的技術，站到巨人肩膀上，再結合操作系統團隊的商業模式探索，爭取把操作系統做成功。于是，他如癡如醉地研究Linux內核，在一年時間里，每天晚上堅持花三個小時以上的時間鉆研《深入理解Linux內核》這本書，還將自己的讀書心得筆記共享到團隊論壇上，并對開源內核進行注解，分享到開源論壇上。
2008年正是多核架構快速發展之時，操作系統的支持參差不齊，驅動、應用開發模式不成熟，既有單態單核單進程的業務應用如何進行重構和演進，方案設計、開發聯調、故障排查、系統調優又會遇到很多復雜和棘手的問題，中興通訊操作系統團隊需要支撐公司所有產品、各種CPU架構、各種復雜業務場景，團隊面臨著前所未有的技術和進度壓力。團隊成員除了在研發一線通過不斷實踐進行被動積累和提升外，也加強了主動的理論知識提升，閱讀《深入理解并行編程》就是其中之一。令我印象非常深刻的是，多核故障往往比較隨機和復雜，難以復現和理解，但以謝寶友為代表的團隊成員往往可以通過閱讀業務、驅動、內核代碼就定位到故障根源，整理出故障邏輯，我認為這與他們的系統理論水平提升是分不開的。非常欣慰的是，我們成功地解決了這個過渡時期涌現的諸如多核內存序相關故障，利用無鎖并行編程優化了系統性能。時至今日，我們團隊已經從30人發展到數百人，嵌入式操作系統已全面應用于公司所有產品，在全球穩定商用，并且擴展應用到電力、鐵路、汽車等領域，2016年獲得了第四屆中國工業大獎。
另一方面，站在技術的角度來看，在計算機領域，并行編程的困難是眾所周知的。
有4、5年編程經驗的讀者，可能或多或少遇到過并行編程的問題，最著名的問題可能就是死鎖。讀者需要掌握調試死鎖問題的技巧，以及避免死鎖問題的編程技術。
喜歡深入思考的讀者，在理解并解決死鎖問題之后，可能還會閱讀并行編程方面的書籍，進一步接觸到活鎖、饑餓等更有趣的并行編程問題。中興通訊操作系統團隊的同事，就曾經在開源虛擬化軟件中遇到過類似的問題：虛擬機容器在互斥鎖的保護下，輪詢系統狀態并等待狀態變化。這樣的輪詢操作造成了進程調度不及時，系統狀態遲遲不能變化。這是一個典型的活鎖問題。在多核系統越來越普及的今天，類似的活鎖問題更容易出現。解決這類問題，需要經驗豐富的工程師，借助多種調試工具，花費不少的時間。
但是，并行編程僅僅與鎖相關嗎？
在摩爾定律尚未失效時，并行編程確實主要與鎖緊密相關。但是，我們看看霍金向IT工程師所提出的兩個難題：
1．有限的光速；
2．物質的原子特性。
這兩個難題最終會將CPU頻率的理論上限限制在10GHz以內，不可避免地使摩爾定律失效。要繼續提升硬件性能，需要借助于多核擴展。
要充分發揮多核系統的性能，必須提升并行軟件的擴展性。也就是說，并行軟件需要盡量減少鎖沖突，避免由于鎖競爭而引起性能急劇下降。這不是一件簡單的事情！我們知道，Linux操作系統在接近20年的時候內，一直受到大內核鎖的困擾。為了徹底拋棄大內核鎖，開源社區近幾年內做出了艱辛的努力，才實現了這個目標。即使如此，Linux內核仍然大量使用不同種類的鎖，并且不可能完全放棄鎖的使用。
也許你會說，在多核系統中，有一種簡單的避免鎖的方法，就是原子變量。在某些架構中，原子變量是由單條指令實現的，性能“想必”不差，使用方法也簡單。曾經有一位具有十多年編程經驗的工程師也表達過類似的觀點。在此，有兩個問題需要回答。
1．這樣的原子操作指令，其性能真的不差？它的執行周期是否可能達到上千個時鐘周期？
2．對于多個相互之間有邏輯關聯的變量，原子操作是否滿足要求？
實際上，多核系統中的并行軟件，除了常見的鎖之外，還需要使用冒險指針、RCU、內存屏障這樣的重量級并行編程工具。這些編程工具都屬于“無鎖編程”的范疇。
即使在Linux內核開源社區工作10年以上的資深工程師，也不一定能真正靈活自如地使用RCU、內存屏障來進行并行編程。因此，真正了解并行編程的讀者，難免在面對并行編程難題時，有一種“撫襟長嘆息”的感覺。
然而，我們知道，有很多重要的應用依賴于并行——圖形渲染、密碼破解、圖像掃描、物理與生物過程模擬等。有一個極端的例子，在證券交易所，為了避免長距離傳輸引起的通信延遲（理論上，光束繞地球一周需要大概130ms），需要將分析證券交易的計算機放到更接近證券交易的地方，并且壓榨出計算機的所有性能。這樣，才能保證達成有利的證券交易。可以毫不夸張地說，對軟件性能有苛刻需求的軟件工程師和大型軟件開發企業，都需要真正掌握并行編程的藝術，特別是“無鎖編程”的藝術。一旦真正掌握了，它就會為你帶來意想不到的性能提升。曾經有一位著名企業的高級專家，在應用了本書所述的RCU后，軟件性能提升了大約10倍。
本書正是這樣一本深入講解多核并行編程，特別是無鎖編程的好書。
首先，本書作者Paul具有40年軟件編程職業生涯，他大部分的工作都與并行編程相關。即使在領導IBM Linux中心時，他仍然堅持每天編程，是一名真正的“工匠”。同時，作者也是Linux開源社區RCU模塊的領導者和維護者。認真閱讀本書后，不得不欽佩于作者在并行編程方面的真知灼見和實踐能力。例如作者親自編寫了一個軟件用例，來考察CPU核之間原子操作和鎖的性能，得出一個結論，原子操作和鎖可能消耗超過1000個CPU時鐘周期；作者也編寫過另外一個關于全局變量的用例，其中一個CPU核遞增操作一個全局變量，同時在不同的CPU核上觀察所讀到的全局變量值。這個用例向讀者展示了多核系統令人驚奇的、反直覺的效果；作者對內存屏障的講解，特別是內存屏障傳遞性的講解，十分深入。這些深入的內容，難得一見，非大師不能為。
其次，這本書也得到Linux內核社區和應用軟件專家的一致推薦。這些推薦者既包括Linux社區大名鼎鼎的Ingo Molnar、Rusty Russel、Greg Kroah-Hartman、Maged M.Micheal，也包括國內活躍于社區的龐訓磊、Shawn Guo等開源貢獻者，還包括Linaro開源組織的領導和資深工程師，以及在BAT工作多年的高級應用軟件專家。
第三，這本書的內容比較全面。除了介紹常見的鎖以外，還重點介紹了RCU的使用及其原理，以及實現RCU的基礎：內存屏障。本書最后還介紹了并行軟件的驗證，以及并行實時計算等內容。實際上，其中每一部分都是并行編程的寶藏。由于篇幅和難度的原因，作者在當前版本中，將RCU部分作了大幅壓縮。對RCU感興趣的讀者可以閱讀早期原版著作。即使如此，本書對RCU的講解也非常深入。對于并行軟件的驗證，作者提出了不少獨特的觀點，這些觀點和作者多年的編程經驗息息相關，與常見的理論著作相比，有一定的新意。形式驗證部分，作者以實際的例子，一步一步講述驗證過程，很明顯，作者親自動手做過這種驗證。并行實時計算部分，是作者新增的內容，別具一格，值得讀者細讀。內存屏障部分，是本書一個難點，借助于作者在這方面的功力，需要讀者反復閱讀，才能真正理解。
第四，這本書講解得很深入。有些語句，需要讀者反復琢磨、推敲，甚至需要多次通讀本書才能領會作者的意思。也許，經典書籍的閱讀方法均是如此。剛剛開始接觸Linux內核的讀者，不太會喜歡閱讀《深入理解Linux內核》一書，覺得這本書不易理解。但是，如果你愿意花一年時間，將這本書反復閱讀三遍，則會有一種別樣的心情。本書也是如此，建議讀者在初次閱讀時，不要輕易放棄。本書實為并行編程方面不可多得的好書。舉兩個例子：第一，5.2.2節中有一句原文是“One way to provide per-thread variables is to allocate an array with one element perthread (presumably cache aligned and padded to avoid false sharing).”。譯者將其翻譯為“一種實現每線程變量的方法是分配一個數組，數組每個元素對應一個線程（假設已經對齊并且填充過了，這樣可以防止共享出現“假共享”）”。第一次閱讀本書，可能會不理解括號中那句話，有一種云里霧里的感覺。要真正理解這句話，需要讀者仔細閱讀本書后面關于MESI消息協議部分，參閱更多參考資料。要理解本句中“對齊”和“填充”兩個詞，也需要深厚的內核功底。第二，14.2.10.2節，“一個LOCK操作充當了一個單方面屏障的角色。它確保：對于系統中其他組件的角度來說，所有鎖操作后面的內存操作看起來發生在鎖操作之后。LOCK操作之前的內存操作可能發生在它完成之后。”這句話讀起來也比較繞，難于理解，似乎也相互矛盾。實際上，讀者需要琢磨“看起來”這個詞，它表示其他核看到內存操作的順序，并不代表內存操作的完成時機。
總之，如果你對并行編程或者操作系統內核有興趣，或者需要對項目進行深度性能優化，我強烈推薦這本并行編程的經典好書！
中興通訊操作系統產品部 鐘衛東
譯者序1
希望這本著作能夠成為經典！
20年前，當我正式成為一名軟件工程師的時候，就有一個夢想：開發一款操作系統。那時候，雖然知道Linux的存在，但是實在找不到一臺可以正常安裝使用Linux的PC。因此只能閱讀相關的源碼分析書籍而不能動手實踐。
我至今仍然清楚記得：大約10年前，中興通訊操作系統團隊的鐘衛東部長，可能被我對操作系統的熱情所感動，不顧我沒有上過大學的事實，冒著風險將我招聘到中興通訊成都研究所。面對100多種型號的單板，我既興奮又惶恐。這些單板涉及ARM、X86、PowerPC、MIPS、SH、Sparc等不同的CPU架構。從此，我開始了激動人心而有趣的內核之旅。
在之后的6年中，我對照Linux內核源碼，根據《深入理解Linux內核》、《深入理解Linux網絡內幕》、《深入理解Linux虛擬內存管理》，以及其他一些Linux內核文件系統、網絡協議棧方面的書籍，做了2200頁、87萬字的內核學習筆記，同時將相應的源碼注釋公布到網絡中供自由下載。
然而，這6年在看Linux內核代碼的過程中，以及在工程實踐中，總有一個幽靈般的陰影出現在我的腦海中：什么是內存屏障？2011年，我看過內核源碼目錄中的文檔以后，終于解決了標準內核和工具鏈一個關于內存屏障的故障。要復現這個故障，項目同事需要在整整一個房間里面擺滿單板和服務器，才能搭建一套復現環境，并且需要用多套這樣的環境，花費2個月時間才能復現一次相關故障。即使在解決了相關故障以后，我仍然覺得自己對內存屏障理解得不深刻。因為內核源碼目錄下的文檔，對內存屏障描述得仍然語焉不詳。那個幽靈仍然在腦海中盤旋：到底什么才是內存屏障？
直到有一天，我在辦公室晃悠的時候，突然在魯陽的辦公桌上發現一本特別的書——《Is Parallel Programming Hard, And, If So, What Can You Do About It?》。說它特別，是因為它是打印出來的。當我翻看了目錄看到里面包含內存屏障和RCU的時候，立即明白這就是我幾年來苦苦追尋而未得的書！并且，這本書里面花了濃重的筆墨來講述這兩個主題。還有比這更令人高興的事情嗎？
聰明的讀者一定知道接下來發生了什么事情。你猜得沒錯，我鼓動魯陽一起翻譯這本書，當時的目的純粹是為了學習，并且分享到網絡中。在此，我不得不向魯陽道歉：為了讓你堅持下去，我說過一些不留情面的話。這些話不過是云門禪宗棒喝之法而已。如果你早就忘記這些話，那就謝天謝地了！
為了翻譯好這本書，我特意去補了一下英語方面的課。最終，這本書能夠與讀者見面，大概有以下幾個原因。
1．魯陽和我都有一點Linux內核和并行編程基礎。
2．我們的熱情和有點自大的自信。
3．英語不算太難學。
4．家人的容忍。也許是我常常念叨：翻譯好這本書，工資可能漲一大截。
5．有一些值得感恩的網友，他們督促我們做好翻譯工作。
在終于完整地翻譯完本書之際，我整理出幾條理由，這些理由使得本書有成為經典的潛質。
1．深刻是本書的特點。本書從霍金提出的兩個理論物理限制為起點，站在硬件而不是軟件的角度，闡述并行編程的難題。讓人有一種“知其然并且知其所以然”的感覺。書中不少觀點，如內存屏障的傳遞性，是資深工程師也不容易理解的。但是，看過本書以后，讀者會有一種豁然開朗的感覺。
2．在并行編程方面，本書比較全面，并且包含豐富的示例。包括但不僅僅限于硬件基礎、緩存、并行設計、鎖、RCU、內存屏障、驗證及形式驗證、實時并行計算。
3．原著作者Paul是真正的大師。看過作者簡介，并且真正知道RCU在Linux內核中份量的朋友，不知道你們是否會在心里嘀咕：在Linux開源社區，有沒有人愿意試著去挖Paul的墻角，代替Paul把RCU維護起來？
4．Paul 在40年的職業生涯中，大部分時間都在編寫并行編程的代碼。當他扛著與奔馳車價值相當的雙核計算機往實驗室走的時候，我這個有20年編程經驗的程序員，還沒有上小學。
5．國內對并行計算和Linux內核的研究逐步深入，讀者期待一本深入講解并行編程的書籍。本書有并行編程的入門知識，更有值得細細回味、反復琢磨的金玉良言。
6．譯者多次核對校正，盡量做到符合原著本意，兩位譯者有多年Linux內核經驗，盡量做到不錯譯。
當然，由于譯者水平的原因，書中錯漏之處在所難免，熱忱歡迎讀者提出批評建議。
最后，譯者誠心感謝原著作者Paul給大家奉獻了一本好書；也感謝電子工業出版社符隆美編輯的辛勤工作；以及資深互聯網軟件工程師劉海平，感謝你熱心地向出版社推薦這本書；最真心的感謝留給同桌夫人巫緒萍及我們的兒子謝文韜，犧牲了大量陪伴你們的時間，謝謝你們的寬容！
謝寶友
2017年4月20日
于深圳
譯者序2
大概在6年前，那時我在中興通訊的操作系統部門工作。當時中興通訊希望加入Linux基金會，由于英語還不算差，操作系統部的鐘衛東部長讓我負責一些部門與開源社區的合作推進工作，所以除了編程工作以外，我時常密切關注Linux開源社區的最新動態。有一天我在LWN.net上瀏覽新聞，一條消息突然跳入了我的視線：Paul McKenney出了一本關于并行編程的書（原文鏈接在此，https://lwn.net/Articles/421425）。那時候我還不知道Paul是誰，但是書的內容很吸引人，于是我開始把書介紹給周圍的同事。過了一陣子，謝寶友找到我，問我有沒有興趣一起把這本書翻譯成中文，我們倆一拍即合，開始利用業余時間合力翻譯這本大部頭。
雖然當時本書的內容尚未完成，有一些章節只列了提綱，但是關于并行程序的設計思想、相關基礎知識、RCU和內存屏障方面的內容已經非常豐富，對于從事內核開發工作的我們來說，簡直就是寶庫，我們認為即使只翻譯這些內容，對其他中國讀者來說也很有幫助。
翻譯的過程遠遠比最初想象得困難，原著作者Paul是一位有近40年從業經驗的資深大牛，在書中大量使用了Linux內核的術語、并行編程的研究文獻，以及對復雜算法和示例代碼的解釋，在翻譯過程中需要字斟句酌，力求準確地傳達作者的原意，所以進度很慢。不過當時我還未婚，尚算自由，下班以后的空余時間幾乎全部用來做這件事，大概花了4個月的時間完成了第一個中文版本。
我們把中文版發布到了網上，也開始和Paul聯系，請他幫我們宣傳，希望能讓更多的中國開發者知道這件事。同年在南京舉行的CLK 2011（中國Linux內核開發者大會）上，我和寶友見到了Paul本人。這里有一個有趣的小插曲，由于會后找Paul提問和咨詢的人太多，Paul干脆在會場外席地而坐，逐一侃侃而談。不擺架子的大牛，是Paul給我留下的最深刻印象。
后來因為家庭的原因，我去了美國。生活充滿了新的挑戰，繼續更新內容的事情因此擱置。期間，寶友繼續翻譯了答案部分的內容，也有出版社聯系過我們，想出版本書的中文版，但因為種種原因，后來無疾而終。直到去年夏天，電子工業出版社正式從原著作者處獲得版權授權，邀請我和寶友將本書最新版翻譯成中文。于是我們再度合作，花了大半年時間，重新審閱翻譯稿，將內容更新到最新版本，完整地翻譯了所有附錄和小問題答案，同時修訂了很多錯誤。相較之前的翻譯稿，作者對這一版的內容有大幅改變：
第6章新增了對迷宮問題并行化解法的討論，
完全重寫了第7章鎖和第8章數據所有權的內容。
第9章新增了關于危險指針和順序鎖，更新了一些例子。
新增了第10章，如何將哈希表并行化。
新增了第11章，如何驗證并行算法的正確性。
新增了第13章綜合應用。
新增了第15章并行實時計算。
從這個列表可以看出，原著作者Paul對并行編程技術的思考一直沒有停止，還在不停地將這個經典領域的新問題和新進展加入到本書中。比如一些學者對常見數據結構哈希表的最新研究，使得本書不僅成為一部案頭必備的工具書，還是一個開拓新知識的出發點。
作者在書中數次強調設計的重要性。工作以來，我曾參與的項目有操作系統內核、瀏覽器內核，目前開發的是內存數據庫，都屬于系統軟件的范疇。這些項目都大量使用了多線程來充分利用硬件。在這些實踐中，我有一點體會，關于分割數據、分割時間、減少跨線程訪問、并行快速路徑、鎖的使用紀律這些設計思想，一旦應用到項目中，代碼就變得清晰易懂，很少有BUG。一旦違反，就帶來難以維護的代碼，隨之而來的是層出不窮的BUG。
書中還散落著許多寶貴的經驗法則，比如10.6.3節中如何通過重新排列數據結構順序來避免緩存行“顛簸”。這些前輩摸索出來的經驗能讓新一代的開發者少走很多彎路。
作者的行文十分幽默，我在翻譯過程中，經常忍俊不禁。希望能在中文版中，盡量將作者的幽默感保留下來。
去年我的兒子小魚兒降生，作為一個新爸爸，白天工作，晚上在照顧孩子之余還要加班翻譯文稿，真是分秒必爭。最后借這個機會，將最真心的感謝留給我的夫人盧靜，感謝你對家庭的付出，沒有你的幫助和理解，就沒有本書中文版的面世。
魯陽
2017年6月16日于Woburn，Massachusetts |
內容簡介：本書首先以霍金提出的兩個理論物理限制為引子，解釋了多核并行計算興起的原因，并從硬件的角度闡述并行編程的難題。接著，本書以常見的計數器為例，探討其不同的實現方法及適用場景。在這些實現方法中，除了介紹常見的鎖以外，本書還重點介紹了RCU的使用及其原理，以及實現RCU的基礎：內存屏障。最后，本書還介紹了并行軟件的驗證，以及并行實時計算等內容。本書適合于對并行編程有興趣的大學生、研究生，以及需要對項目進行深度性能優化的軟硬件工程師，特別值得一提的是，本書對操作系統內核工程師也很有價值。 |
目錄：第1章 如何使用本書 1
1.1 路線圖 1
1.2 小問題 2
1.3 除本書之外的選擇 3
1.4 示例源代碼 4
1.5 這本書屬于誰 4
第2章 簡介 6
2.1 導致并行編程困難的歷史原因 6
2.2 并行編程的目標 7
2.2.1 性能 8
2.2.2 生產率 9
2.2.3 通用性 9
2.3 并行編程的替代方案 11
2.3.1 串行應用的多個實例 11
2.3.2 使用現有的并行軟件 11
2.3.3 性能優化 12
2.4 是什么使并行編程變得復雜 12
2.4.1 分割任務 13
2.4.2 并行訪問控制 13
2.4.3 資源分割和復制 14
2.4.4 與硬件的交互 14
2.4.5 組合使用 14
2.4.6 語言和環境如何支持這些任務 14
2.5 本章的討論 15
第3章 硬件和它的習慣 16
3.1 概述 16
3.1.1 流水線CPU 16
3.1.2 內存引用 17
3.1.3 原子操作 18
3.1.4 內存屏障 19
3.1.5 高速緩存未命中 19
3.1.6 I/O操作 19
3.2 開銷 20
3.2.1 硬件體系結構 20
3.2.2 操作的開銷 21
3.3 硬件的免費午餐 23
3.3.1 3D集成 23
3.3.2 新材料和新工藝 24
3.3.3 是光，不是電子 24
3.3.4 專用加速器 24
3.3.5 現有的并行軟件 25
3.4 對軟件設計的啟示 25
第4章 辦事的家伙 27
4.1 腳本語言 27
4.2 POSIX多進程 28
4.2.1 POSIX進程創建和銷毀 28
4.2.2 POSIX線程創建和銷毀 30
4.2.3 POSIX鎖 31
4.2.4 POSIX讀/寫鎖 34
4.3 原子操作 37
4.4 Linux內核中類似POSIX的操作 38
4.5 如何選擇趁手的工具 39
第5章 計數 40
5.1 為什么并發計數不可小看 41
5.2 統計計數器 42
5.2.1 設計 43
5.2.2 基于數組的實現 43
5.2.3 最終結果一致的實現 44
5.2.4 基于每線程變量的實現 46
5.2.5 本節討論 48
5.3 近似上限計數器 48
5.3.1 設計 48
5.3.2 簡單的上限計數實現 50
5.3.3 關于簡單上限計數的討論 55
5.3.4 近似上限計數器的實現 55
5.3.5 關于近似上限計數器的討論 55
5.4 精確上限計數 56
5.4.1 原子上限計數的實現 56
5.4.2 關于原子上限計數的討論 62
5.4.3 Signal-Theft上限計數的設計 62
5.4.4 Signal-Theft上限計數的實現 63
5.4.5 關于Signal-Theft上限計數的討論 68
5.5 特殊場合的并行計數 68
5.6 關于并行計數的討論 69
5.6.1 并行計數的性能 70
5.6.2 并行計數的專門化 71
5.6.3 從并行計數中學到什么 71
第6章 對分割和同步的設計 73
6.1 分割練習 73
6.1.1 哲學家就餐問題 73
6.1.2 雙端隊列 75
6.1.3 關于分割問題示例的討論 81
6.2 設計準則 82
6.3 同步粒度 83
6.3.1 串行程序 84
6.3.2 代碼鎖 85
6.3.3 數據鎖 86
6.3.4 數據所有權 88
6.3.5 鎖粒度與性能 88
6.4 并行快速路徑 90
6.4.1 讀/寫鎖 91
6.4.2 層次鎖 91
6.4.3 資源分配器緩存 92
6.5 分割之外 97
6.5.1 使用工作隊列的迷宮問題并行解法 97
6.5.2 另一種迷宮問題的并行解法 100
6.5.3 性能比較I 102
6.5.4 另一種迷宮問題的串行解法 104
6.5.5 性能比較II 104
6.5.6 未來展望與本節總結 105
6.6 分割、并行化與優化 106
第7章 鎖 107
7.1 努力活著 108
7.1.1 死鎖 108
7.1.2 活鎖與饑餓 114
7.1.3 不公平的鎖 116
7.1.4 低效率的鎖 117
7.2 鎖的類型 117
7.2.1 互斥鎖 117
7.2.2 讀/寫鎖 118
7.2.3 讀/寫鎖之外 118
7.2.4 范圍鎖 119
7.3 鎖在實現中的問題 121
7.3.1 基于原子交換的互斥鎖實現示例 121
7.3.2 互斥鎖的其他實現 122
7.4 基于鎖的存在保證 124
7.5 鎖：是英雄還是惡棍 125
7.5.1 應用程序中的鎖：英雄 125
7.5.2 并行庫中的鎖：只是一個工具 126
7.5.3 并行化串行庫時的鎖：惡棍 128
7.6 總結 130
第8章 數據所有權 131
8.1 多進程 131
8.2 部分數據所有權和pthread線程庫 132
8.3 函數輸送 132
8.4 指派線程 132
8.5 私有化 133
8.6 數據所有權的其他用途 133
第9章 延后處理 134
9.1 引用計數 134
9.1.1 各種引用計數的實現 135
9.1.2 危險指針 140
9.1.3 支持引用計數的Linux原語 141
9.1.4 計數優化 142
9.2 順序鎖 142
9.3 讀-復制-修改（RCU） 145
9.3.1 RCU介紹 145
9.3.2 RCU基礎 147
9.3.3 RCU用法 155
9.3.4 Linux內核中的RCU API 166
9.3.5 “玩具式”的RCU實現 171
9.3.6 RCU練習 188
9.4 如何選擇 188
9.5 更新端怎么辦 190
第10章 數據結構 191
10.1 從例子入手 191
10.2 可分割的數據結構 192
10.2.1 哈希表的設計 192
10.2.2 哈希表的實現 192
10.2.3 哈希表的性能 195
10.3 讀側重的數據結構 197
10.3.1 受RCU保護的哈希表的實現 197
10.3.2 受RCU保護的哈希表的性能 199
10.3.3 對受RCU保護的哈希表的討論 201
10.4 不可分割的數據結構 201
10.4.1 可擴展哈希表的設計 202
10.4.2 可擴展哈希表的實現 203
10.4.3 可擴展哈希表的討論 210
10.4.4 其他可擴展的哈希表 211
10.5 其他數據結構 214
10.6 微優化 214
10.6.1 實例化 215
10.6.2 比特與字節 215
10.6.3 硬件層面的考慮 216
10.7 總結 217
第11章 驗證 218
11.1 簡介 218
11.1.1 BUG來自于何處 218
11.1.2 所需的心態 220
11.1.3 應該何時開始驗證 221
11.1.4 開源之路 221
11.2 跟蹤 222
11.3 斷言 223
11.4 靜態分析 224
11.5 代碼走查 224
11.5.1 審查 224
11.5.2 走查 225
11.5.3 自查 225
11.6 幾率及海森堡BUG 227
11.6.1 離散測試統計 228
11.6.2 濫用離散測試統計 229
11.6.3 持續測試統計 229
11.6.4 定位海森堡BUG 232
11.7 性能評估 235
11.7.1 性能基準 236
11.7.2 剖析 236
11.7.3 差分分析 237
11.7.4 微基準 237
11.7.5 隔離 237
11.7.6 檢測干擾 238
11.8 總結 242
第12章 形式驗證 244
12.1 通用目的的狀態空間搜索 244
12.1.1 Promela和Spin 244
12.1.2 如何使用 Promela 249
12.1.3 Promela 示例: 鎖 251
12.1.4 Promela 示例: QRCU 254
12.1.5 Promela初試牛刀：dynticks和可搶占RCU 260
12.1.6 驗證可搶占RCU和dynticks 264
12.2 特定目的的狀態空間搜索 288
12.2.1 解析Litmus測試 289
12.2.2 Litmus測試意味著什么 290
12.2.3 運行Litmus測試 291
12.2.4 PPCMEM討論 292
12.3 公理方法 293
12.4 SAT求解器 294
12.5 總結 295
第13章 綜合應用 296
13.1 計數難題 296
13.1.1 對更新進行計數 296
13.1.2 對查找進行計數 296
13.2 使用RCU拯救并行軟件性能 297
13.2.1 RCU和基于每CPU變量的統計計數 297
13.2.2 RCU及可插拔I/O設備的計數器 300
13.2.3 數組及長度 300
13.2.4 相關聯的字段 301
13.3 散列難題 302
13.3.1 相關聯的數據元素 302
13.3.2 更新友好的哈希表遍歷 303
第14章 高級同步 304
14.1 避免鎖 304
14.2 內存屏障 304
14.2.1 內存序及內存屏障 305
14.2.2 如果B在A后面，并且C在B后面，為什么C不在A后面 306
14.2.3 變量可以擁有多個值 307
14.2.4 能信任什么東西 308
14.2.5 鎖實現回顧 312
14.2.6 一些簡單的規則 313
14.2.7 抽象內存訪問模型 314
14.2.8 設備操作 315
14.2.9 保證 315
14.2.10 什么是內存屏障 316
14.2.11 鎖約束 325
14.2.12 內存屏障示例 326
14.2.13 CPU緩存的影響 328
14.2.14 哪里需要內存屏障 329
14.3 非阻塞同步 329
14.3.1 簡單NBS 330
14.3.2 NBS討論 331
第15章 并行實時計算 332
15.1 什么是實時計算 332
15.1.1 軟實時 332
15.1.2 硬實時 333
15.1.3 現實世界的實時 334
15.2 誰需要實時計算 336
15.3 誰需要并行實時計算 337
15.4 實現并行實時系統 337
15.4.1 實現并行實時操作系統 339
15.4.2 實現并行實時應用 349
15.5 實時VS.快速：如何選擇 351
第16章 易于使用 353
16.1 簡單是什么 353
16.2 API設計的Rusty準則 353
16.3 修整Mandelbrot集合 354
第17章 未來的沖突 357
17.1 曾經的CPU技術不代表未來 357
17.1.1 單處理器Uber Alles 358
17.1.2 多線程Mania 359
17.1.3 更多類似的場景 359
17.1.4 撞上內存墻 359
17.2 事務內存 360
17.2.1 外部世界 361
17.2.2 進程修改 364
17.2.3 同步 367
17.2.4 討論 370
17.3 硬件事務內存 371
17.3.1 HTM與鎖相比的優勢 372
17.3.2 HTM與鎖相比的劣勢 373
17.3.3 HTM與增強后的鎖機制相比的劣勢 379
17.3.4 HTM最適合的場合 380
17.3.5 潛在的攪局者 380
17.3.6 結論 382
17.4 并行函數式編程 383
附錄A 重要問題 385
A.1 “After”的含義是什么 385
A.2 “并發”和“并行”之間的差異是什么 388
A.3 現在是什么時間 389
附錄B 同步原語 391
B.1 組織和初始化 391
B.1.1 smp_init() 391
B.2 線程創建、銷毀及控制 392
B.2.1 create_thread() 392
B.2.2 smp_thread_id() 392
B.2.3 for_each_thread() 392
B.2.4 for_each_running_thread() 392
B.2.5 wait_thread() 393
B.2.6 wait_all_threads() 393
B.2.7 用法示例 393
B.3 鎖 394
B.3.1 spin_lock_init() 394
B.3.2 spin_lock() 394
B.3.3 spin_trylock() 394
B.3.4 spin_unlock() 394
B.3.5 用法示例 395
B.4 每線程變量 395
B.4.1 DEFINE_PER_THREAD() 395
B.4.2 DECLARE_PER_THREAD() 395
B.4.3 per_thread() 395
B.4.4 __get_thread_var() 396
B.4.5 init_per_thread() 396
B.4.6 用法示例 396
B.5 性能 396
附錄C 為什么需要內存屏障 397
C.1 緩存結構 397
C.2 緩存一致性協議 399
C.2.1 MESI狀態 399
C.2.2 MESI協議消息 400
C.2.3 MESI狀態圖 400
C.2.4 MESI協議示例 401
C.3 存儲導致不必要的停頓 402
C.3.1 存儲緩沖 403
C.3.2 存儲轉發 403
C.3.3 存儲緩沖區及內存屏障 404
C.4 存儲序列導致不必要的停頓 406
C.4.1 使無效隊列 406
C.4.2 使無效隊列及使無效應答 407
C.4.3 使無效隊列及內存屏障 407
C.5 讀和寫內存屏障 409
C.6 內存屏障示例 410
C.6.1 亂序體系結構 410
C.6.2 示例1 411
C.6.3 示例2 412
C.6.4 示例3 412
C.7 特定的內存屏障指令 413
C.7.1 Alpha 414
C.7.2 AMD64 417
C.7.3 ARMv7-A/R 417
C.7.4 IA64 418
C.7.5 PA-RISC 418
C.7.6 POWER / Power PC 418
C.7.7 SPARC RMO、PSO及TSO 419
C.7.8 x86 420
C.7.9 zSeries 421
C.8 內存屏障是永恒的嗎 421
C.9 對硬件設計者的建議 422
附錄D 小問題答案 423
D.1 如何使用本書 423
D.2 簡介 424
D.3 硬件和它的習慣 427
D.4 辦事的家伙 429
D.5 計數 433
D.6 對分割和同步的設計 445
D.7 鎖 449
D.8 數據所有權 455
D.9 延遲處理 456
D.10 數據結構 471
D.11 驗證 473
D.12 形式驗證 478
D.13 綜合應用 481
D.14 高級同步 483
D.15 并行實時計算 486
D.16 易于使用 487
D.17 未來的沖突 487
D.18 重要問題 490
D.19 同步原語 491
D.20 為什么需要內存屏障 491
附錄E 術語 495
附錄F 感謝 502
F.1 評審者 502
F.2 硬件提供者 502
F.3 原始出處 503
F.4 圖表作者 503
F.5 其他幫助 505 |
| 序： |
|
