深入理解并发编程

【实例简介】深入理解并发编程

介绍了并发编程的精髓，特别是无锁的原理

【实例截图】

【核心代码】

深入理解并行编程
法律声明................................................................................................................ 3
前言........................................................................................................................ 4
1. 简介......................................................................................................... 16
1.1. 并行编程曾经的困难...................................................................... 16
1.2. 并行编程的目标.............................................................................. 18
1.2.1. 性能........................................................................................... 18
1.2.2. 生产率....................................................................................... 19
1.2.3. 通用性....................................................................................... 20
1.3. 并行编程的替代方案...................................................................... 23
1.3.1. 串行应用多实例化................................................................... 23
1.3.2. 使用现有的并行软件............................................................... 23
1.3.3. 对串行程序性能优化............................................................... 24
1.4. 是什么使并行编程变得困难？...................................................... 24
1.4.1. 工作分割................................................................................... 25
1.4.2. 并行访问控制........................................................................... 26
1.4.3. 资源分割和复制....................................................................... 26
1.4.4. 与硬件交互............................................................................... 27
1.4.5. 组合的能力............................................................................... 27
1.4.6. 语言和环境如何对这样的任务进行支持？........................... 27
1.5. 本书导读.......................................................................................... 28
1.5.1. 小问题....................................................................................... 28
1.5.2. 随书源码................................................................................... 28
2. 硬件的习性............................................................................................. 30
2.1. 概述.................................................................................................. 30
2.1.1. 流水线 CPU .............................................................................. 31
2.1.2. 内存引用................................................................................... 32
2.1.3. 原子操作................................................................................... 33
2.1.4. 内存屏障................................................................................... 34
2.1.5. 缓存失效................................................................................... 35
2.1.6. I/O 操作 .................................................................................... 36
2.2. 开销.................................................................................................. 37
2.2.1. 硬件体系结构........................................................................... 38
2.2.2. 操作的开销............................................................................... 39
2.3. 硬件的免费午餐? ............................................................................ 40
2.3.1. 3D 集成 ..................................................................................... 41
深入理解并行编程
2.3.2. 新材料和新工艺....................................................................... 42
2.3.3. 用光替换电子........................................................................... 42
2.3.4. 专用加速器............................................................................... 42
2.3.5. 现有的并行软件....................................................................... 43
2.4. 关于软件设计.................................................................................. 43
3. 工具......................................................................................................... 45
3.1. 脚本语言.......................................................................................... 45
3.2. POSIX 多进程 ................................................................................. 46
3.2.1. POSIX 进程创建和销毁 .......................................................... 46
3.2.2. POSIX 线程的创建和撤销 ...................................................... 48
3.2.3. POSIX 锁 .................................................................................. 49
3.2.4. POSIX 读写锁 .......................................................................... 53
3.3. 原子操作.......................................................................................... 56
3.4. Linux 内核中类似 POSIX 的操作 ................................................. 57
3.5. 趁手的工具——该如何选择？...................................................... 59
4. 计数......................................................................................................... 60
4.1. 为什么并发计数不可小看？.......................................................... 60
4.2. 统计计数器...................................................................................... 63
4.2.1. 设计........................................................................................... 63
4.2.2. 基于数组的实现....................................................................... 63
4.2.3. 结果一致的实现....................................................................... 64
4.2.4. 基于每线程变量的实现........................................................... 66
4.2.5. 讨论........................................................................................... 68
4.3. 近似上限计数器.............................................................................. 69
4.3.1. 设计........................................................................................... 69
4.3.2. 简单的上限计数器实现........................................................... 70
4.3.3. 关于简单上限计数器的讨论................................................... 75
4.3.4. 近似上限计数器的实现........................................................... 76
4.3.5. 关于近似上限计数器的讨论................................................... 76
4.4. 精确上限计数器.............................................................................. 77
4.4.1. 原子上限计数器的实现........................................................... 77
4.4.2. 关于原子上限计数器的讨论................................................... 84
4.4.3. Signal-Theft 上限计数器的设计 ............................................. 84
4.4.4. Signal-Theft 上限计数器的实现 ............................................. 85
4.4.5. Signal-Theft 上限计数器讨论 ................................................. 91
深入理解并行编程
4.5. 特殊的并行计数器.......................................................................... 92
4.6. 并行计数的讨论.............................................................................. 93
5. 分割和同步设计..................................................................................... 95
5.1. 分割练习.......................................................................................... 95
5.1.1. 哲学家就餐问题....................................................................... 95
5.1.2. 双端队列................................................................................... 97
5.1.3. 关于分割问题示例的讨论..................................................... 105
5.2. 设计准则........................................................................................ 105
5.3. 同步粒度........................................................................................ 107
5.3.1. 串行程序................................................................................. 108
5.3.2. 代码锁..................................................................................... 110
5.3.3. 数据锁..................................................................................... 111
5.3.4. 数据所有权............................................................................. 114
5.3.5. 锁粒度与性能......................................................................... 115
5.4. 并行快速路径................................................................................ 115
5.4.1. 读写锁..................................................................................... 116
5.4.2. 层级锁..................................................................................... 117
5.4.3. 资源分配器缓存..................................................................... 118
5.5. 性能总结........................................................................................ 124
6. 锁........................................................................................................... 125
6.1. 生存（staying alive） ................................................................... 126
6.1.1. 死锁......................................................................................... 126
6.1.2. 活锁......................................................................................... 129
6.1.3. 不公平..................................................................................... 130
6.1.4. 低效率..................................................................................... 130
6.2. 锁的类型........................................................................................ 130
6.2.1. 互斥锁..................................................................................... 130
6.2.2. 读写锁..................................................................................... 130
6.2.3. Beyond Reader-Writer Locks ................................................. 131
6.3. 基于锁的存在性保证.................................................................... 131
7. 数据所有者........................................................................................... 133
8. 延迟处理............................................................................................... 135
8.1. 屏障................................................................................................ 135
8.2. 引用计数........................................................................................ 135
8.2.1. 引用计数类型的实现............................................................. 136
深入理解并行编程
8.2.2. 支持引用计数的 Linux 原语 ................................................. 142
8.2.3. 计数器优化............................................................................. 143
8.3. Read-Copy Update（RCU）......................................................... 143
8.3.1. RCU 基础 ............................................................................... 143
8.3.2. RCU 用法 ............................................................................... 155
8.3.3. Linux 内核中的 RCU API...................................................... 168
8.3.4. “玩具式”的 RCU 实现 ...................................................... 174
8.3.5. RCU 练习 ............................................................................... 195
9. 使用 RCU ............................................................................................. 196
9.1. RCU 和基于每线程变量的统计计数器 ...................................... 196
9.1.1. 设计......................................................................................... 196
9.1.2. 实现......................................................................................... 196
9.1.3. 讨论......................................................................................... 199
9.2. RCU 和可移除 I/O 设备的计数器 ............................................... 199
10. 验证：调试及分析............................................................................... 201
11. 数据结构............................................................................................... 203
12. 高级同步............................................................................................... 205
12.1. 避免锁............................................................................................ 205
12.2. 内存屏障........................................................................................ 205
12.2.1. 内存序及内存屏障.......................................................... 205
12.2.2. 如果 B 在 A 后面, 并且 C 在 B 后面, 为什么 C 不在 A
后面？ 207
12.2.3. 变量可以拥有多个值...................................................... 208
12.2.4. 能信任什么东西? ............................................................ 209
12.2.5. 锁实现回顾...................................................................... 215
12.2.6. 一些简单的规则.............................................................. 216
12.2.7. 抽象内存访问模型.......................................................... 217
12.2.8. 设备操作.......................................................................... 219
12.2.9. 保证.................................................................................. 220
12.2.10. 什么是内存屏障? ............................................................ 221
12.2.11. 锁约束.............................................................................. 234
12.2.12. 内存屏障示例.................................................................. 235
12.2.13. CPU .................................................................................. 238
12.2.14. 哪里需要内存屏障? ........................................................ 239
12.3. 非阻塞同步.................................................................................... 240
深入理解并行编程
12.3.1. 简单 NBS ........................................................................ 240
12.3.2. 冒险指针.......................................................................... 240
12.3.3. 原子数据结构.................................................................. 240
12.3.4. ―Macho‖ NBS .................................................................. 240
13. 易于使用............................................................................................... 241
14. 未来的冲突........................................................................................... 242
14.1. CPU 技术日新月异 ....................................................................... 242
14.1.1. 单处理器 Uber Alles ....................................................... 244
14.1.2. 多线程 Mania .................................................................. 245
14.1.3. 在现有基础上进行一些改进.......................................... 245
14.1.4. 内存墙.............................................................................. 246
14.2. 事务内存........................................................................................ 247
14.2.1. I/O 操作 .......................................................................... 248
14.2.2. RPC 操作 ........................................................................ 249
14.2.3. 内存映射操作.................................................................. 250
14.2.4. 多线程事务...................................................................... 251
14.2.5. 外部的事务访问.............................................................. 252
14.2.6. 延时.................................................................................. 252
14.2.7. 锁...................................................................................... 253
14.2.8. 读者-写者锁 .................................................................... 253
14.2.9. 持久性.............................................................................. 254
14.2.10. 动态链接装载.................................................................. 255
14.2.11. 调试.................................................................................. 256
14.2.12. exec() 系统调用.............................................................. 257
14.2.13. RCU ................................................................................. 257
14.2.14. 讨论.................................................................................. 259
14.3. 硬件事务内存................................................................................ 259
14.3.1. HTM 与锁相比在写方面的优势 .................................... 260
14.3.2. HTM 与锁相比在写方面的劣势 .................................... 261
14.3.3. HTM 与改进后的锁机制相比，在写方面的劣势 ........ 267
14.3.4. HTM 最适合的场合 ........................................................ 267
14.3.5. 决定 HTM 潜力的几个因素 ........................................... 268
14.4. 共享内存并行编程........................................................................ 270
14.5. 基于任务的并行编程.................................................................... 270
A. 重要问题............................................................................................... 271
深入理解并行编程
A.1 ―after‖的含义是什么？ ................................................................. 271
A.2 现在是什么时间？........................................................................ 275
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 缓存结构........................................................................................ 284
C.2 缓存一致性协议............................................................................ 286
C.2.1 MESI 状态 ............................................................................. 286
C.2.2 MESI 协议消息 ..................................................................... 287
C.2.3 MESI 状态图 ......................................................................... 288
C.2.4 MESI 协议示例 ..................................................................... 290
C.3 不必要的存储延迟........................................................................ 291
深入理解并行编程
C.3.1 存储缓冲.......................................................................... 292
C.3.2 前向存储.......................................................................... 292
C.3.3 存储缓冲区及内存屏障.................................................. 294
C.4 连续存储导致不必要的延迟........................................................ 297
C.4.1 使无效队列...................................................................... 297
C.4.2 使无效队列及使无效应答.............................................. 297
C.4.3 使无效队列及内存屏障.................................................. 298
C.5 读和写内存屏障............................................................................ 301
C.6 内存屏障示例................................................................................ 301
C.6.1 乱序体系结构.................................................................. 302
C.6.2 示例 1 .............................................................................. 303
C.6.3 示例 2 .............................................................................. 303
C.6.4 示例 3 .............................................................................. 304
C.7 特定 CPUs 的内存屏障指令 ........................................................ 305
C.7.1 Alpha ....................................................................................... 307
C.7.2 AMD64 ................................................................................... 310
C.7.3 ARMv7-A/R ........................................................................... 310
C.7.4 IA64 ........................................................................................ 311
C.7.5 PA-RISC .................................................................................. 312
C.7.6 POWER / Power PC ............................................................... 312
C.7.7 SPARC RMO、PSO 及 TSO ................................................. 313
C.7.8 x86........................................................................................... 314
C.7.9 zSeries ..................................................................................... 315
C.8 内存屏障是永恒的？.................................................................... 315
C.9 对硬件设计者的建议.................................................................... 316
D. RCU 实现 ............................................................................................. 318
D.1 可睡眠 RCU 实现 ........................................................................ 318
D.1.1 SRCU 实现原理 .................................................................... 319
D.1.2 SRCU API 及其用法 .............................................................. 320
D.1.3 实现.................................................................................. 323
D.1.4 SRCU 概述 ............................................................................. 328
D.2 分级 RCU 概述 ............................................................................. 328
D.2.1 RCU 基础回顾 ....................................................................... 329
D.2.2 经典 RCU实现概要 ....................................................... 329
D.2.3 RCU 迫切要解决的问题 ....................................................... 330
深入理解并行编程
D.2.4 迈向可扩展 RCU实现 ................................................... 332
D.2.5 迈向不成熟的 RCU 实现 ............................................... 335
D.2.6 状态机.............................................................................. 336
D.2.7 用例.................................................................................. 338
D.2.8 测试.................................................................................. 342
D.2.9 结论.................................................................................. 347
D.3 分级 RCU代码走查 ..................................................................... 349
D.3.1 数据结构及内核参数...................................................... 349
D.3.2 外部接口.......................................................................... 357
D.3.3 初始化.............................................................................. 366
D.3.4 CPU 热插拨 ........................................................................... 371
D.3.5 杂项函数.......................................................................... 376
D.3.6 优雅周期检测函数.......................................................... 377
D.3.7 Dyntick-Idle 函数 ................................................................... 389
D.3.8 强制静止状态.................................................................. 395
D.3.9 CPU-延迟检测 ....................................................................... 402
D.3.10 可能的缺陷及变更.......................................................... 405
D.4 可抢占 RCU .................................................................................. 405
D.4.1 概念性 RCU .................................................................... 406
D.4.2 可抢占 RCU 算法概述 ................................................... 407
D.4.3 验证可抢占 RCU ............................................................ 424
E. LINUX 中的 RCU ................................................................................ 427
E.1 LINUX 中 RCU 的使用 ................................................................ 427
E.2 RCU 的演进 .................................................................................. 428
F. 形式验证............................................................................................... 434
F.1 什么是 Promela 和 Spin? .............................................................. 434
F.2 Promela 示例: 非原子性递增 ..................................................... 434
F.3 Promela 示例: 原子递增 ............................................................. 438
F.3.1 组合......................................................................................... 439
F.4 如何使用 Promela ........................................................................ 439
F.4.1 Promela 特性 ......................................................................... 440
F.4.2 Promela 编程技巧 .................................................................. 441
F.5 Promela 示例: 锁 ......................................................................... 442
F.6 Promela 示例: QRCU ................................................................... 445
F.6.1 运行 QRCU 示例 ................................................................. 450
深入理解并行编程
F.6.2 到底需要多少读者和写者? ................................................... 451
F.6.3 可选方法: 正确性校验 .......................................................... 451
F.6.4 可选方法: 更多工具 .............................................................. 451
F.6.5 可选方法: 分而治之 .............................................................. 452
F.7 Promela Parable: dynticks 和可抢占 RCU ................................. 452
F.7.1 可抢占 RCU 和 dynticks 介绍 ............................................... 453
F.7.2 验证可抢占 RCU 和 dynticks ................................................ 457
F.7.3 回顾......................................................................................... 478
F.8 简单的避免形式校验.................................................................... 479
F.8.1 简单 Dynticks 接口的状态变量 ........................................... 479
F.8.2 进入和退出 Dynticks-Idle 模式............................................ 480
F.8.3 从 Dynticks-Idle 模式进入 NMIs ......................................... 481
F.8.4 从 Dynticks-Idle 进入中断..................................................... 482
F.8.5 检查 Dynticks 静止状态 ....................................................... 483
F.8.6 讨论......................................................................................... 484
F.9 概要................................................................................................ 485
G. 问题答案............................................................................................... 486
G.1 第 1 章............................................................................................ 486
G.2 第 2 章............................................................................................ 491
G.3 第 3 章............................................................................................ 494
G.4 第 4 章............................................................................................ 498
G.5 第 5 章............................................................................................ 511
G.6 第 6 章............................................................................................ 515
G.7 第 7 章............................................................................................ 517
G.8 第 8 章............................................................................................ 517
G.9 第 9 章............................................................................................ 534
G.10 第 10 章.......................................................................................... 535
G.11 第 11 章 .......................................................................................... 535
G.12 第 12 章.......................................................................................... 535
G.13 第 13 章.......................................................................................... 538
G.14 第 14 章.......................................................................................... 538
G.15 附录 A ............................................................................................ 542
G.16 附录 B ............................................................................................ 543
G.17 附录 C ............................................................................................ 544
G.18 附录 D ............................................................................................ 548
深入理解并行编程
G.19 附录 F ............................................................................................ 566
H. 术语表................................................................................................... 572
I. 参考书目...................................................................................................... 579
J. 感谢....................................................................................................... 580