第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
· · · · · · (
收起)
