深入理解并行编程

　　《深入理解并行编程》首先以霍金提出的两个理论物理限制为引子，解释了多核并行计算兴起的原因，并从硬件的角度阐述并行编程的难题。接着，《深入理解并行编程》以常见的计数器为例，探讨其不同的实现方法及适用场景。在这些实现方法中，除了介绍常见的锁以外，《深入理解并行编程》还重点介绍了RCU的使用及其原理，以及实现RCU的基础：内存屏障。最后，《深入理解并行编程》还介绍了并行软件的验证，以及并行实时计算等内容。

　　《深入理解并行编程》适合于对并行编程有兴趣的大学生、研究生，以及需要对项目进行深度性能优化的软硬件工程师，特别值得一提的是，《深入理解并行编程》对操作系统内核工程师也很有价值。

Paul E. McKenney is the core contributor of Linux kernel .

　　译者序1

　　希望这本著作能够成为经典！

　　20年前，当我正式成为一名软件工程师的时候，就有一个梦想：开发一款操作系统。那时候，虽然知道Linux的存在，但是实在找不到一台可以正常安装使用Linux的PC。因此只能阅读相关的源码分析书籍而不能动手实践。

　　我至今仍然清楚记得：大约10年前，中兴通讯操作系统团队的钟卫东部长，可能被我对操作系统的热情所感动，不顾我没有上过大学的事实，冒着风险将我招聘到中兴通讯成都研究所。面对100多种型号的单板，我既兴奋又惶恐。这些单板涉及ARM、X86、PowerPC、MIPS、SH、Sparc等不同的CPU架构。从此，我开始了激动人心而有趣的内核之旅。

　　在之后的6年中，我对照Linux内核源码，根据《深入理解Linux内核》、《深入理解Linux网络内幕》、《深入理解Linux虚拟内存管理》，以及其他一些Linux内核文件系统、网络协议栈方面的书籍，做了2200页、87万字的内核学习笔记，同时将相应的源码注释公布到网络中供自由下载。

　　然而，这6年在看Linux内核代码的过程中，以及在工程实践中，总有一个幽灵般的阴影出现在我的脑海中：什么是内存屏障？2011年，我看过内核源码目录中的文档以后，终于解决了标准内核和工具链一个关于内存屏障的故障。要复现这个故障，项目同事需要在整整一个房间里面摆满单板和服务器，才能搭建一套复现环境，并且需要用多套这样的环境，花费2个月时间才能复现一次相关故障。即使在解决了相关故障以后，我仍然觉得自己对内存屏障理解得不深刻。因为内核源码目录下的文档，对内存屏障描述得仍然语焉不详。那个幽灵仍然在脑海中盘旋：到底什么才是内存屏障？

　　直到有一天，我在办公室晃悠的时候，突然在鲁阳的办公桌上发现一本特别的书——《IsParallelProgrammingHard,And,IfSo,WhatCanYouDoAboutIt?》。说它特别，是因为它是打印出来的。当我翻看了目录看到里面包含内存屏障和RCU的时候，立即明白这就是我几年来苦苦追寻而未得的书！并且，这本书里面花了浓重的笔墨来讲述这两个主题。还有比这更令人高兴的事情吗？

　　聪明的读者一定知道接下来发生了什么事情。你猜得没错，我鼓动鲁阳一起翻译这本书，当时的目的纯粹是为了学习，并且分享到网络中。在此，我不得不向鲁阳道歉：为了让你坚持下去，我说过一些不留情面的话。这些话不过是云门禅宗棒喝之法而已。如果你早就忘记这些话，那就谢天谢地了！

　　为了翻译好这本书，我特意去补了一下英语方面的课。最终，这本书能够与读者见面，大概有以下几个原因。

　　1．鲁阳和我都有一点Linux内核和并行编程基础。

　　2．我们的热情和有点自大的自信。

　　3．英语不算太难学。

　　4．家人的容忍。也许是我常常念叨：翻译好这本书，工资可能涨一大截。

　　5．有一些值得感恩的网友，他们督促我们做好翻译工作。

　　在终于完整地翻译完本书之际，我整理出几条理由，这些理由使得本书有成为经典的潜质。

　　1．深刻是本书的特点。本书从霍金提出的两个理论物理限制为起点，站在硬件而不是软件的角度，阐述并行编程的难题。让人有一种“知其然并且知其所以然”的感觉。书中不少观点，如内存屏障的传递性，是资深工程师也不容易理解的。但是，看过本书以后，读者会有一种豁然开朗的感觉。

　　2．在并行编程方面，本书比较全面，并且包含丰富的示例。包括但不仅仅限于硬件基础、缓存、并行设计、锁、RCU、内存屏障、验证及形式验证、实时并行计算。

　　3．原著作者Paul是真正的大师。看过作者简介，并且真正知道RCU在Linux内核中份量的朋友，不知道你们是否会在心里嘀咕：在Linux开源社区，有没有人愿意试着去挖Paul的墙角，代替Paul把RCU维护起来？

　　4．Paul在40年的职业生涯中，大部分时间都在编写并行编程的代码。当他扛着与奔驰车价值相当的双核计算机往实验室走的时候，我这个有20年编程经验的程序员，还没有上小学。

　　5．国内对并行计算和Linux内核的研究逐步深入，读者期待一本深入讲解并行编程的书籍。本书有并行编程的入门知识，更有值得细细回味、反复琢磨的金玉良言。

　　6．译者多次核对校正，尽量做到符合原著本意，两位译者有多年Linux内核经验，尽量做到不错译。

　　当然，由于译者水平的原因，书中错漏之处在所难免，热忱欢迎读者提出批评建议。

　　最后，译者诚心感谢原著作者Paul给大家奉献了一本好书；也感谢电子工业出版社符隆美编辑的辛勤工作；以及资深互联网软件工程师刘海平，感谢你热心地向出版社推荐这本书；最真心的感谢留给同桌夫人巫绪萍及我们的儿子谢文韬，牺牲了大量陪伴你们的时间，谢谢你们的宽容！

　　谢宝友

　　2017年4月20日

　　于深圳

　　译者序2

　　大概在6年前，那时我在中兴通讯的操作系统部门工作。当时中兴通讯希望加入Linux基金会，由于英语还不算差，操作系统部的钟卫东部长让我负责一些部门与开源社区的合作推进工作，所以除了编程工作以外，我时常密切关注Linux开源社区的最新动态。有一天我在LWN.net上浏览新闻，一条消息突然跳入了我的视线：PaulMcKenney出了一本关于并行编程的书（原文链接在此，https://lwn.net/Articles/421425）。那时候我还不知道Paul是谁，但是书的内容很吸引人，于是我开始把书介绍给周围的同事。过了一阵子，谢宝友找到我，问我有没有兴趣一起把这本书翻译成中文，我们俩一拍即合，开始利用业余时间合力翻译这本大部头。

　　虽然当时本书的内容尚未完成，有一些章节只列了提纲，但是关于并行程序的设计思想、相关基础知识、RCU和内存屏障方面的内容已经非常丰富，对于从事内核开发工作的我们来说，简直就是宝库，我们认为即使只翻译这些内容，对其他中国读者来说也很有帮助。

　　翻译的过程远远比最初想象得困难，原著作者Paul是一位有近40年从业经验的资深大牛，在书中大量使用了Linux内核的术语、并行编程的研究文献，以及对复杂算法和示例代码的解释，在翻译过程中需要字斟句酌，力求准确地传达作者的原意，所以进度很慢。不过当时我还未婚，尚算自由，下班以后的空余时间几乎全部用来做这件事，大概花了4个月的时间完成了第一个中文版本。

　　我们把中文版发布到了网上，也开始和Paul联系，请他帮我们宣传，希望能让更多的中国开发者知道这件事。同年在南京举行的CLK2011（中国Linux内核开发者大会）上，我和宝友见到了Paul本人。这里有一个有趣的小插曲，由于会后找Paul提问和咨询的人太多，Paul干脆在会场外席地而坐，逐一侃侃而谈。不摆架子的大牛，是Paul给我留下的最深刻印象。

　　后来因为家庭的原因，我去了美国。生活充满了新的挑战，继续更新内容的事情因此搁置。期间，宝友继续翻译了答案部分的内容，也有出版社联系过我们，想出版本书的中文版，但因为种种原因，后来无疾而终。直到去年夏天，电子工业出版社正式从原著作者处获得版权授权，邀请我和宝友将本书最新版翻译成中文。于是我们再度合作，花了大半年时间，重新审阅翻译稿，将内容更新到最新版本，完整地翻译了所有附录和小问题答案，同时修订了很多错误。相较之前的翻译稿，作者对这一版的内容有大幅改变：

　　第6章新增了对迷宫问题并行化解法的讨论，

　　完全重写了第7章锁和第8章数据所有权的内容。

　　第9章新增了关于危险指针和顺序锁，更新了一些例子。

　　新增了第10章，如何将哈希表并行化。

　　新增了第11章，如何验证并行算法的正确性。

　　新增了第13章综合应用。

　　新增了第15章并行实时计算。

　　从这个列表可以看出，原著作者Paul对并行编程技术的思考一直没有停止，还在不停地将这个经典领域的新问题和新进展加入到本书中。比如一些学者对常见数据结构哈希表的最新研究，使得本书不仅成为一部案头必备的工具书，还是一个开拓新知识的出发点。

　　作者在书中数次强调设计的重要性。工作以来，我曾参与的项目有操作系统内核、浏览器内核，目前开发的是内存数据库，都属于系统软件的范畴。这些项目都大量使用了多线程来充分利用硬件。在这些实践中，我有一点体会，关于分割数据、分割时间、减少跨线程访问、并行快速路径、锁的使用纪律这些设计思想，一旦应用到项目中，代码就变得清晰易懂，很少有BUG。一旦违反，就带来难以维护的代码，随之而来的是层出不穷的BUG。

　　书中还散落着许多宝贵的经验法则，比如10.6.3节中如何通过重新排列数据结构顺序来避免缓存行“颠簸”。这些前辈摸索出来的经验能让新一代的开发者少走很多弯路。

　　作者的行文十分幽默，我在翻译过程中，经常忍俊不禁。希望能在中文版中，尽量将作者的幽默感保留下来。

　　去年我的儿子小鱼儿降生，作为一个新爸爸，白天工作，晚上在照顾孩子之余还要加班翻译文稿，真是分秒必争。最后借这个机会，将最真心的感谢留给我的夫人卢静，感谢你对家庭的付出，没有你的帮助和理解，就没有本书中文版的面世。

　　鲁阳

　　2017年6月16日于Woburn，Massachusetts

第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 流水线CPU16

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 性能比较I102

6.5.4 另一种迷宫问题的串行解法104

6.5.5 性能比较II104

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 API166

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 几率及海森堡BUG227

11.6.1 离散测试统计228

11.6.2 滥用离散测试统计229

11.6.3 持续测试统计229

11.6.4 定位海森堡BUG232

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和Spin244

12.1.2 如何使用 Promela249

12.1.3 Promela 示例: 锁251

12.1.4 Promela 示例: QRCU254

12.1.5 Promela初试牛刀：dynticks和可抢占RCU260

12.1.6 验证可抢占RCU和dynticks264

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 简单NBS330

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 Alles358

17.1.2 多线程Mania359

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 示例1411

C.6.3 示例2412

C.6.4 示例3412

C.7 特定的内存屏障指令413

C.7.1 Alpha414

C.7.2 AMD64417

C.7.3 ARMv7-A/R417

C.7.4 IA64418

C.7.5 PA-RISC418

C.7.6 POWER / Power PC418

C.7.7 SPARC RMO、PSO及TSO419

C.7.8 x86420

C.7.9 zSeries421

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

计算机,编程,软件开发,计算机科学,并发,tt,parallel,2017_read