73
《深入理解並行編程》中文版
原文的下載地址：https://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html
中文版下載地址：深入理解並行編程V1.0 （4.1M）
本書是linux內核大牛paul的力作，和魯陽同學一起，花了兩個月時間進行翻譯。
目前沒有翻譯問答部分，主要是時間不夠，也擔心不能將這部分翻譯準確。
對內核深度發燒的同學可以看看。
本書目錄
1. 簡介…………………………………………………………………………………………… 14
1.1. 導致並行編程困難的曆史原因……………………………………………… 14
1.2. 並行編程的目標…………………………………………………………………… 15
1.2.1. 性能………………………………………………………………………………. 16
1.2.2. 生產率…………………………………………………………………………… 17
1.2.3. 通用性…………………………………………………………………………… 18
1.3. 並行編程的替代方案……………………………………………………………. 20
1.3.1. 順序應用多實例化…………………………………………………………. 20
1.3.2.使用現有的並行軟件……………………………………………………… 21
1.3.3. 性能優化……………………………………………………………………….. 21
1.4. 是什麼使並行編程變得複雜？……………………………………………… 22
1.4.1. 工作分割……………………………………………………………………….. 22
1.4.2. 並行訪問控製………………………………………………………………… 23
1.4.3. 資源分割和複製…………………………………………………………….. 24
1.4.4. 與硬件交互……………………………………………………………………. 24
1.4.5. 組合使用……………………………………………………………………….. 24
1.4.6. 語言和環境如何對這樣的任務進行支持？……………………… 25
1.5. 本書導讀……………………………………………………………………………… 25
1.5.1. 小問題…………………………………………………………………………… 25
1.5.2. 隨書源碼……………………………………………………………………….. 26
2. 硬件的習性………………………………………………………………………………… 28
2.1. 概述…………………………………………………………………………………….. 28
2.1.1. CPU流水線 …………………………………………………………………… 29
2.1.2. 內存引用……………………………………………………………………….. 30
2.1.3. 原子操作……………………………………………………………………….. 31
2.1.4. 內存屏障……………………………………………………………………….. 32
2.1.5. Cache Miss …………………………………………………………………….. 33
2.1.6. I/O操作 ………………………………………………………………………… 34
2.2. 開銷…………………………………………………………………………………….. 35
2.2.1. 硬件體係結構………………………………………………………………… 36
2.2.2. 操作的開銷……………………………………………………………………. 37
2.3. 硬件的免費午餐? …………………………………………………………………. 38
2.3.1. 3D集成 …………………………………………………………………………. 39
2.3.2. 新材料和新工藝…………………………………………………………….. 39
2.3.3. 專用加速器……………………………………………………………………. 39
2.3.4. 現有的並行軟件…………………………………………………………….. 40
2.4. 軟件設計Implication ……………………………………………………………. 40
3. 工具…………………………………………………………………………………………… 43
3.1. 腳本語言……………………………………………………………………………… 43
3.2. POSIX多進程 ……………………………………………………………………… 44
3.2.1. POSIX進程創建和撤銷 …………………………………………………. 44
3.2.2. POSIX線程的創建和撤銷 ……………………………………………… 46
3.2.3. POSIX鎖 ………………………………………………………………………. 48
3.2.4. POSIX讀寫鎖 ……………………………………………………………….. 52
3.3. 原子操作……………………………………………………………………………… 55
3.4. Linux內核中類似POSIX的操作 …………………………………………. 56
3.5. 趁手的工具——該如何選擇？……………………………………………… 58
4. 計數…………………………………………………………………………………………… 59
4.1. 為什麼並發計數不可小看？…………………………………………………. 60
4.2. 統計計數器………………………………………………………………………….. 62
4.2.1. 設計………………………………………………………………………………. 62
4.2.2. 基於數組的實現…………………………………………………………….. 62
4.2.3. 結果一致的實現…………………………………………………………….. 64
4.2.4. 基於每線程變量的實現………………………………………………….. 66
4.2.5. 討論………………………………………………………………………………. 69
4.3. 近似上限計數器…………………………………………………………………… 69
4.3.1. 設計………………………………………………………………………………. 69
4.3.2. 簡單的上限計數器實現………………………………………………….. 70
4.3.3. 關於簡單上限計數器的討論…………………………………………… 76
4.3.4. 近似上限計數器的實現………………………………………………….. 76
4.3.5. 關於近似上限計數器的討論…………………………………………… 77
4.4. 精確上限計數器…………………………………………………………………… 77
4.4.1. 原子上限計數器的實現………………………………………………….. 77
4.4.2. 關於原子上限計數器的討論…………………………………………… 86
4.4.3. Signal-Theft上限計數器的設計 ……………………………………… 86
4.4.4. Signal-Theft上限計數器的實現 ……………………………………… 87
4.4.5. Signal-Theft上限計數器討論 …………………………………………. 94
4.5. 特殊的並行計數器……………………………………………………………….. 95
4.6. 並行計數的討論…………………………………………………………………… 96
5. 分割和同步設計……………………………………………………………………….. 100
5.1. 分割練習……………………………………………………………………………. 100
5.1.1. 哲學家就餐問題…………………………………………………………… 100
5.1.2. 雙端隊列……………………………………………………………………… 102
5.1.3. 關於分割問題示例的討論…………………………………………….. 111
5.2. 設計準則……………………………………………………………………………. 111
5.3. 同步粒度……………………………………………………………………………. 113
5.3.1. 串行程序……………………………………………………………………… 114
5.3.2. 代碼鎖…………………………………………………………………………. 116
5.3.3. 數據鎖…………………………………………………………………………. 117
5.3.4. 數據所有權………………………………………………………………….. 120
5.3.5. 鎖粒度與性能………………………………………………………………. 121
5.4. 並行快速路徑…………………………………………………………………….. 121
5.4.1. 讀寫鎖…………………………………………………………………………. 122
5.4.2. 層級鎖…………………………………………………………………………. 123
5.4.3. 資源分配器緩存…………………………………………………………… 125
5.5. 性能總結……………………………………………………………………………. 131
6. 鎖…………………………………………………………………………………………….. 132
6.1. 生存（staying alive） …………………………………………………………. 133
6.1.1. 死鎖…………………………………………………………………………….. 133
6.1.2. 活鎖…………………………………………………………………………….. 136
6.1.3. 不公平…………………………………………………………………………. 137
6.1.4. 低效率…………………………………………………………………………. 137
6.2. 鎖的類型……………………………………………………………………………. 137
6.2.1. 互斥鎖…………………………………………………………………………. 138
6.2.2. 讀寫鎖…………………………………………………………………………. 138
6.2.3. Beyond Reader-Writer Locks …………………………………………. 138
6.3. 基於鎖的存在擔保（existence guarantee） ………………………….. 138
7. 數據所有者………………………………………………………………………………. 140
8. 延遲處理………………………………………………………………………………….. 142
8.1. 屏障…………………………………………………………………………………… 142
8.2. 引用計數……………………………………………………………………………. 142
8.2.1. 引用計數類型的實現……………………………………………………. 143
8.2.2. 支持引用計數的Linux原語 …………………………………………. 150
8.2.3. 計數器優化………………………………………………………………….. 151
8.3. Read-Copy Update（RCU）………………………………………………… 151
8.3.1. RCU基礎 ……………………………………………………………………. 151
8.3.2. RCU用法 ……………………………………………………………………. 163
8.3.3. Linux內核中的RCU API……………………………………………… 176
8.3.4. “玩具式”的RCU實現 ……………………………………………… 183
8.3.5. RCU練習 ……………………………………………………………………. 206
9. 使用RCU ………………………………………………………………………………… 207
9.1. RCU和基於每線程變量的統計計數器 ……………………………….. 207
9.1.1. 設計…………………………………………………………………………….. 207
9.1.2. 實現…………………………………………………………………………….. 207
9.1.3. 討論…………………………………………………………………………….. 211
9.2. RCU和可移除I/O設備的計數器 ……………………………………….. 211
10. 驗證：調試及分析……………………………………………………………………. 214
11. 數據結構………………………………………………………………………………….. 216
12. 高級同步………………………………………………………………………………….. 218
12.1. 避免鎖……………………………………………………………………………….. 218
12.2. 內存屏障……………………………………………………………………………. 218
12.2.1. 內存序及內存屏障…………………………………………………. 218
12.2.2. 如果B在A後麵, 並且C在B後麵, 為什麼C不在A後麵? 220
12.2.3. 變量可以擁有多個值……………………………………………… 221
12.2.4. 能信任什麼東西? …………………………………………………… 222
12.2.5. 鎖實現回顧……………………………………………………………. 229
12.2.6. 一些簡單的規則…………………………………………………….. 230
12.2.7. 抽象內存訪問模型…………………………………………………. 230
12.2.8. 設備操作……………………………………………………………….. 233
12.2.9. 保證………………………………………………………………………. 233
12.2.10. 什麼是內存屏障? …………………………………………………… 234
12.2.11. 鎖約束…………………………………………………………………… 247
12.2.12. 內存屏障示例………………………………………………………… 248
12.2.13. CPU ………………………………………………………………………. 251
12.2.14. 哪裏需要內存屏障? ……………………………………………….. 253
12.3. 非阻塞同步………………………………………………………………………… 253
12.3.1. 簡單 NBS ……………………………………………………………… 253
12.3.2. 冒險指針……………………………………………………………….. 253
12.3.3. 原子數據結構………………………………………………………… 253
12.3.4. “Macho” NBS………………………………………………………… 253
13. 易於使用………………………………………………………………………………….. 254
13.1. Rusty Scale for API Design ………………………………………………….. 254
13.2. Shaving the Mandelbrot Set ………………………………………………….. 255
14. 時間管理………………………………………………………………………………….. 258
15. 未來的衝突………………………………………………………………………………. 259
15.1. 可交易內存………………………………………………………………………… 259
15.1.1. I/O 操作 ……………………………………………………………….. 260
15.1.2. RPC 操作 ……………………………………………………………… 260
15.1.3. 內存映射操作………………………………………………………… 261
15.1.4. 多線程事務……………………………………………………………. 262
15.1.5. 外部的事務訪問…………………………………………………….. 263
15.1.6. 延時………………………………………………………………………. 264
15.1.7. 鎖………………………………………………………………………….. 264
15.1.8. 讀者-寫者鎖 ………………………………………………………….. 265
15.1.9. 持續性…………………………………………………………………… 266
TM如何提供類似的持續性功能？……………………………………………………….. 266
15.1.10. 動態鏈接裝載………………………………………………………… 266
15.1.11. 調試………………………………………………………………………. 267
15.1.12. exec() 係統調用…………………………………………………….. 268
15.1.13. RCU ……………………………………………………………………… 268
15.1.14. 討論………………………………………………………………………. 270
15.2. 共享內存並行編程……………………………………………………………… 270
15.3. 基於任務的並行編程………………………………………………………….. 270
A. 重要問題………………………………………………………………………………….. 271
A.1 “after“的含義是什麼? …………………………………………………………. 271
B. 同步原語………………………………………………………………………………….. 277
B.1 初始化……………………………………………………………………………….. 277
B.1.1 smp_init() …………………………………………………………………….. 277
B.2 線程創建、銷毀及控製………………………………………………………. 278
B.2.1 create_thread() ……………………………………………………………… 278
B.2.2 smp_thread_id() ……………………………………………………………. 278
B.2.3 for_each_thread() ………………………………………………………….. 278
B.2.4 for_each_running_thread() …………………………………………….. 279
B.2.5 wait_thread() ………………………………………………………………… 279 深入理解並行編程
B.2.6 wait_all_threads() …………………………………………………………. 279
B.2.7 用法示例……………………………………………………………….. 279
B.3 鎖………………………………………………………………………………………. 280
B.3.1 spin_lock_init() …………………………………………………………….. 280
B.3.2 spin_lock() …………………………………………………………………… 280
B.3.3 spin_trylock() ……………………………………………………………….. 281
B.3.4 spin_unlock() ……………………………………………………………….. 281
B.3.5 用法示例……………………………………………………………….. 281
B.4 每線程變量………………………………………………………………………… 281
B.4.1 DEFINE_PER_THREAD() ……………………………………………. 282
B.4.2 DECLARE_PER_THREAD() ………………………………………… 282
B.4.3 per_thread() ………………………………………………………………….. 282
B.4.4 __get_thread_var() ………………………………………………………… 282
B.4.5 init_per_thread() …………………………………………………………… 282
B.4.6 用法示例……………………………………………………………….. 282
B.5 性能…………………………………………………………………………………… 283
C. 為什麼使用內存屏障………………………………………………………………… 284
C.1 Cache 結構………………………………………………………………………… 284
C.2 緩存一致性協議…………………………………………………………………. 286
C.2.1 MESI 狀態 ………………………………………………………………….. 286
C.2.2 MESI 協議消息 …………………………………………………………… 287
C.2.3 MESI狀態圖 ……………………………………………………………….. 288
C.2.4 MESI 協議示例 …………………………………………………………… 289
C.3 不必要的存儲延遲……………………………………………………………… 291
C.3.1 Store Buffers ………………………………………………………………… 291
C.3.2 Store Forwarding ………………………………………………………….. 292
C.3.3 存儲緩衝區及內存屏障………………………………………….. 293
C.4 不必要的存儲延遲……………………………………………………………… 296
C.4.1 無效隊列……………………………………………………………….. 296
C.4.2 使無效隊列及使無效應答………………………………………. 296
C.4.3 無效隊列及內存屏障……………………………………………… 297
C.5 讀和寫內存屏障…………………………………………………………………. 300
C.6 內存屏障示例…………………………………………………………………….. 300
C.6.1 亂序體係結構………………………………………………………… 300
C.6.2 示例 1 …………………………………………………………………… 301 深入理解並行編程
C.6.3 示例 2 …………………………………………………………………… 302
C.6.4 示例 3 …………………………………………………………………… 303
C.7 特定CPUs的內存屏障指令 ……………………………………………….. 304
C.7.1 Alpha …………………………………………………………………………… 306
C.7.2 AMD64 ……………………………………………………………………….. 308
C.7.3 ARMv7-A/R ………………………………………………………………… 309
6 ISB();………………………………………………………………………………………………… 309
C.7.4 IA64 ……………………………………………………………………………. 309
C.7.5 PA-RISC ………………………………………………………………………. 310
C.7.6 POWER / Power PC ……………………………………………………… 310
C.7.7 SPARC RMO, PSO, and TSO ………………………………………… 311
C.7.8 x86………………………………………………………………………………. 312
C.7.9 zSeries …………………………………………………………………………. 313
C.8 內存屏障是永恒的? ……………………………………………………………. 313
C.9 對硬件設計者的建議………………………………………………………….. 314
D. RCU實現 ………………………………………………………………………………… 315
D.1 可睡眠 RCU 實現 ……………………………………………………………… 315
D.1.1 SRCU 實現原理 ………………………………………………………….. 316
D.1.2 SRCU API 及用法 ……………………………………………………….. 317
D.1.3 實現………………………………………………………………………. 320
D.1.4 SRCU 概述 …………………………………………………………………. 326
D.2 分級 RCU 概述 ………………………………………………………………… 326
D.2.1 RCU 基礎回顧 ……………………………………………………………. 326
D.2.2 經典 RCU 實現概要 ……………………………………………… 327
D.2.3 RCU 迫切要解決的問題 ………………………………………………. 328
D.2.4 可擴展RCU 實現 ………………………………………………….. 329
D.2.5 邁向不成熟的RCU 實現 ……………………………………….. 332
D.2.6 狀態機…………………………………………………………………… 334
D.2.7 用例………………………………………………………………………. 335
D.2.8 測試………………………………………………………………………. 340
D.2.9 結論………………………………………………………………………. 345
D.3 分級 RCU代碼走查 …………………………………………………………… 346
D.3.1 數據結構及內核參數……………………………………………… 346
D.3.2 外部接口……………………………………………………………….. 354
D.3.3 初始化…………………………………………………………………… 362 深入理解並行編程
D.3.4 CPU 熱插撥 ………………………………………………………………… 367
D.3.5 雜項函數……………………………………………………………….. 372
D.3.6 Grace-Period檢測函數 …………………………………………………. 373
D.3.7 Dyntick-Idle 函數 ………………………………………………………… 385
D.3.8 強製靜止狀態………………………………………………………… 390
D.3.9 CPU-延遲檢測 …………………………………………………………….. 397
D.3.10 可能的缺陷及變更…………………………………………………. 400
D.4 可搶占 RCU ……………………………………………………………………… 400
D.4.1 RCU概念 ……………………………………………………………………. 401
D.4.2 可搶占RCU算法概述 …………………………………………… 402
D.4.3 驗證可搶占 RCU …………………………………………………… 419
E. 形式驗證………………………………………………………………………………….. 422
E.1 什麼是 Promela 和 Spin? ………………………………………………….. 422
E.2 Promela 示例: 非原子性遞增 …………………………………………….. 423
E.3 Promela 示例: 原子遞增 ……………………………………………………. 426
E.3.1 組合…………………………………………………………………………….. 427
E.4 如何使用 Promela ……………………………………………………………… 428
E.4.1 Promela 特性 ………………………………………………………………. 428
E.4.2 Promela編程技巧 ………………………………………………………… 429
E.5 Promela 示例: 鎖 ………………………………………………………………. 430
E.6 Promela 示例: QRCU …………………………………………………………. 433
E.6.1 運行 QRCU 示例 ……………………………………………………….. 438
E.6.2 到底需要多少讀者和寫者? …………………………………………… 439
E.6.3 可選方法: 正確性校驗 …………………………………………………. 439
E.6.4 可選方法: 更多工具 …………………………………………………….. 440
E.6.5 可選方法: 分而治之 …………………………………………………….. 440
E.7 Promela Parable: dynticks 和可搶占 RCU …………………………… 440
E.7.1 可搶占 RCU 和 dynticks介紹 …………………………………….. 441
E.7.2 驗證可搶占RCU和dynticks ………………………………………… 445
E.7.3 回顧…………………………………………………………………………….. 466
E.8 簡單的避免形式校驗………………………………………………………….. 467
E.8.1 簡單Dynticks 接口的狀態變量 ……………………………………. 467
E.8.2 進入和退出Dynticks-Idle 模式…………………………………….. 468
E.8.3 從Dynticks-Idle 模式進入NMIs ………………………………….. 469
E.8.4 Interrupts From Dynticks-Idle Mode ……………………………….. 470
E.8.5 檢查Dynticks 靜止狀態 ………………………………………………. 471
E.8.6 討論…………………………………………………………………………….. 473
E.9 概要…………………………………………………………………………………… 473
F. 問題答案………………………………………………………………………………….. 474
G. 術語表……………………………………………………………………………………… 475
H. 感謝…………………………………………………………………………………………. 476
文章轉自 並發編程網-ifeve.com
最後更新：2017-05-22 17:31:50