深入理解并行编程 PDF 高质量版

这书最先以史蒂芬霍金明确提出的2个理论物理限定为引子，表述了多核并行计算盛行的缘故，并从硬件配置的视角论述并行处理程序编写的难点。然后，这书以普遍的电子计数器为例，讨论其不一样的保持方式 及可用情景。在这种保持方式 中，除开详细介绍普遍的锁之外，这书还重中之重详细介绍了RCU的应用以及基本原理，及其保持RCU的基本：运行内存天然屏障。*后，这书还详细介绍了并行处理手机软件的认证，及其并行处理即时测算等內容。这书合适于对并行处理程序编写有兴趣爱好的在校大学生、硕士研究生，及其必须对新项目开展深层特性提升的硬件软件技术工程师，非常值得一提的是，这书对电脑操作系统核心技术工程师也很有使用价值。
Paul是IBM Linux研究中心的优秀技术工程师，现阶段致力于性能、可扩放性、即时没有响应和电力能源高效率的挑戰，在无线电话和互联网协议、管理信息系统、国际商务运用和即时系统软件层面有颇多考试成绩。

谢宝友，大学毕业于四川税收大学税款技术专业，现任职于中兴微电子电脑操作系统精英团队，对电脑操作系统核心有极强的兴趣爱好。职业于电脑操作系统核心早已有8年時间。总体目标是运用10年時间，变成一位真实的“核心小白”。个人中心是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 变量可以拥有多个值 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()