深入理解並行編程 (Is parallel programming hard, and, if so, what can you do about it?) 深入理解并行编程

作者:（美）Paul E.Mckenney （保羅·E·麥肯尼）譯者:謝寶友
Paul是IBM Linux技術中心的傑出工程師，目前專註於高性能、可擴放性、實時響應和能源效率的挑戰，在無線電和因特網協議、系統管理、商務應用和實時系統方面有頗多成績。
謝寶友，畢業於四川省稅務學校稅收專業，現供職於中興微電子操作系統團隊，對操作系統內核有較強的興趣。專職於操作系統內核已經有八年時間。目標是利用十年時間，成為一名真正的“內核菜鳥”。個人主頁是http://xiebaoyou.blog.chinaunix.net。魯陽，2009年畢業於成都電子科技大學，曾供職於中興通訊操作系統部門和騰訊移動瀏覽器部門，後赴美留學，目前供職於分佈式內存數據庫（distributedin-memorydatabase）公司VoltDB。8年時間從系統內核做到上層應用，目標是做一名真正的“全棧工程師”。

目錄

第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變量可以擁有多個值