內容提要
《深入理解並行編程》首先以霍金提出的兩個理論物理限制為引子，解釋了多核並行計算興起的原因，並從硬體的角度闡述並行編程的難題。接著，《深入理解並行編程》以常見的計數器為例，探討其不同的實現方法及適用場景。在這些實現方法中，除了介紹常見的鎖以外，《深入理解並行編程》還重點介紹了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.13CPU快取的影響 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
