多处理器编程的艺术

内容概要

Maurice Herlihy　哈佛大学的数学学士和麻省理工学院的计算机科学博士，目前为美国布朗大学计算机科学系教授，曾工作于卡内基-梅隆大学和DEC剑桥实验室。他是美国ACM会士，2003年分布式计算领域Dijkstra奖获得者。

Nir Shavit　以色列希伯来大学的计算机科学博士，目前为麻省理工学院电子工程和计算机科学系教授、以色列特拉维夫大学计算机科学系教授。1999~2011年期间，他担任Sun实验室的技术人员。

两位作者在2004年获得了理论计算机领域最高奖——哥德尔奖（G?del Prize），2012年他们共享了分布式计算领域的Edsger W. Dijkstra奖，40多年来他们一起合作，从事并行和分布式计算教学和研发工作。

书籍目录

出版者的话

译者序

前言

教学建议

第1章   引言
1

1.1   共享对象和同步
2

1.2   生活实例
4

1.2.1   互斥特性
6

1.2.2   道德
7

1.3   生产者-消费者问题
7

1.4   读者-写者问题
9

1.5   并行的困境
9

1.6   并行程序设计
11

1.7   本章注释
11

1.8   习题
11

第一部分   原       理

第2章   互斥
14

2.1   时间
14

2.2   临界区
14

2.3   双线程解决方案
16

2.3.1   LockOne类
16

2.3.2   LockTwo类
17

2.3.3   Peterson锁
18

2.4   过滤锁
19

2.5   公平性
21

2.6   Bakery算法
21

2.7   有界时间戳
23

2.8   存储单元数量的下界
25

2.9   本章注释
27

2.10   习题
28

第3章   并发对象
31

3.1   并发性与正确性
31

3.2   顺序对象
33

3.3   静态一致性
34

3.4   顺序一致性
35

3.5   可线性化性
38

3.5.1   可线性化点
38

3.5.2   评析
38

3.6   形式化定义
38

3.6.1   可线性化性
39

3.6.2   可线性化性的复合性
40

3.6.3   非阻塞特性
40

3.7   演进条件
41

3.8   Java存储器模型
43

3.8.1   锁和同步块
44

3.8.2   volatile域
44

3.8.3   final域
44

3.9   评析
45

3.10   本章注释
46

3.11   习题
46

第4章   共享存储器基础
50

4.1   寄存器空间
50

4.2   寄存器构造
54

4.2.1   MRSW安全寄存器
55

4.2.2   MRSW规则布尔寄存器
55

4.2.3   M-值MRSW规则寄存器
56

4.2.4   SRSW原子寄存器
57

4.2.5   MRSW原子寄存器
59

4.2.6   MRMW原子寄存器
60

4.3   原子快照
62

4.3.1   无障碍快照
63

4.3.2   无等待快照
64

4.3.3   正确性证明
66

4.4   本章注释
67

4.5   习题
67

第5章   同步原子操作的相对能力
70

5.1   一致数
70

5.2   原子寄存器
72

5.3   一致性协议
74

5.4   FIFO队列
74

5.5   多重赋值对象
77

5.6   读-改-写操作
79

5.7   Common2 RMW操作
80

5.8   compareAndSet()操作
81

5.9   本章注释
82

5.10   习题
83

第6章   一致性的通用性
87

6.1   引言
87

6.2   通用性
88

6.3   一种通用的无锁构造
88

6.4   一种通用的无等待构造
91

6.5   本章注释
95

6.6   习题
95

第二部分   实      践

第7章   自旋锁与争用
98

7.1   实际问题
98

7.2   测试-设置锁
100

7.3   再论基于TAS的自旋锁
102

7.4   指数后退
102

7.5   队列锁
104

7.5.1   基于数组的锁
104

7.5.2   CLH队列锁
106

7.5.3   MCS队列锁
107

7.6   时限队列锁
110

7.7   复合锁
112

7.8   层次锁
118

7.8.1   层次后退锁
118

7.8.2   层次CLH队列锁
119

7.9   由一个锁管理所有的锁
123

7.10   本章注释
123

7.11   习题
124

第8章   管程和阻塞同步
126

8.1   引言
126

8.2   管程锁和条件
126

8.2.1   条件
127

8.2.2   唤醒丢失问题
130

8.3   读者-写者锁
131

8.3.1   简单的读者-写者锁
131

8.3.2   公平的读者-写者锁
132

8.4   我们的可重入锁
134

8.5   信号量
135

8.6   本章注释
136

8.7   习题
136

第9章   链表：锁的作用
139

9.1   引言
139

9.2   基于链表的集合
140

9.3   并发推理
141

9.4   粗粒度同步
142

9.5   细粒度同步
143

9.6   乐观同步
146

9.7   惰性同步
149

9.8   非阻塞同步
153

9.9   讨论
157

9.10   本章注释
157

9.11   习题
158

第10章   并行队列和ABA问题
159

10.1   引言
159

10.2   队列
160

10.3   部分有界队列
160

10.4   完全无界队列
163

10.5   无锁的无界队列
164

10.6   内存回收和ABA问题
166

10.7   双重数据结构
170

10.8   本章注释
172

10.9   习题
172

第11章   并发栈和消除
174

11.1   引言
174

11.2   无锁的无界栈
174

11.3   消除
176

11.4   后退消除栈
176

11.4.1   无锁交换机
177

11.4.2   消除数组
179

11.5   本章注释
181

11.6   习题
181

第12章   计数、排序和分布式协作
184

12.1   引言
184

12.2   共享计数
184

12.3   软件组合
185

12.3.1   概述
185

12.3.2   一个扩展实例
190

12.3.3   性能和健壮性
191

12.4   静态一致池和计数器
192

12.5   计数网
192

12.5.1   可计数网
193

12.5.2   双调计数网
194

12.5.3   性能和流水线
201

12.6   衍射树
201

12.7   并行排序
204

12.8   排序网
204

12.9   样本排序
207

12.10   分布式协作
208

12.11   本章注释
208

12.12   习题
209

第13章   并发哈希和固有并行
212

13.1   引言
212

13.2   封闭地址哈希集
213

13.2.1   粗粒度哈希集
214

13.2.2   空间分带哈希集
215

13.2.3   细粒度哈希集
217

13.3   无锁哈希集
219

13.3.1   递归有序划分
219

13.3.2   BucketList类
222

13.3.3   LockFreeHashSet类
223

13.4   开放地址哈希集
225

13.4.1   Cuckoo哈希
225

13.4.2   并发Cuckoo哈希
226

13.4.3   空间分带的并发Cuckoo哈希
230

13.4.4   细粒度的并发Cuckoo哈希集
231

13.5   本章注释
233

13.6   习题
234

第14章   跳表和平衡查找
235

14.1   引言
235

14.2   顺序跳表
235

14.3   基于锁的并发跳表
236

14.3.1   简介
236

14.3.2   算法
238

14.4   无锁并发跳表
243

14.4.1   简介
243

14.4.2   算法细节
245

14.5   并发跳表
251

14.6   本章注释
251

14.7   习题
251

第15章   优先级队列
253

15.1   引言
253

15.2   基于数组的有界优先级队列
253

15.3   基于树的有界优先级队列
254

15.4   基于堆的无界优先级队列
256

15.4.1   顺序堆
256

15.4.2   并发堆
258

15.5   基于跳表的无界优先级队列
262

15.6   本章注释
264

15.7   习题
265

第16章   异步执行、调度和工作分配
266

16.1   引言
266

16.2   并行分析
271

16.3   多处理器的实际调度
273

16.4   工作分配
274

16.4.1   工作窃取
275

16.4.2   屈从和多道程序设计
275

16.5   工作窃取双端队列
276

16.5.1   有界工作窃取双端队列
276

16.5.2   无界工作窃取双端队列
279

16.5.3   工作平衡
282

16.6   本章注释
283

16.7   习题
284

第17章   障碍
287

17.1   引言
287

17.2   障碍实现
288

17.3   语义换向障碍
288

17.4   组合树障碍
289

17.5   静态树障碍
291

17.6   终止检测障碍
293

17.7   本章注释
295

17.8   习题
296

第18章   事务内存
302

18.1   引言
302

18.1.1   关于锁的问题
302

18.1.2   关于compareAndSet()的问题
303

18.1.3   关于复合性的问题
304

18.1.4   我们能做什么
305

18.2   事务和原子性
305

18.3   软事务内存
306

18.3.1   事务和事务线程
309

18.3.2   僵尸事务和一致性
310

18.3.3   原子对象
311

18.3.4   如何演进
311

18.3.5   争用管理器
312

18.3.6   原子对象的实现
314

18.3.7   无干扰原子对象
315

18.3.8   基于锁的原子对象
318

18.4   硬事务内存
323

18.4.1   缓存一致性
324

18.4.2   事务缓存一致性
324

18.4.3   改进
325

18.5   本章注释
325

18.6   习题
326

第三部分   附      录

附录A   软件基础
328

附录B   硬件基础
340

参考文献
350

索引
359

作者简介

工业界称为多核的多处理器机器正迅速地渗入计算的各个领域。多处理器编程要求理解新型计算原理、算法及编程工具，至今很少有人能够精通这门编程艺术。

现今，大多数工程技术人员都是通过艰辛的反复实践、求助有经验的朋友来学习多处理器编程技巧。这本最新的权威著作致力于改变这种状况，作者全面阐述了多处理器编程的指导原则，介绍了编制高效的多处理器程序所必备的算法技术。了解本书所涵盖的多处理器编程关键问题将使在校学生以及相关技术人员受益匪浅。

本书特色

本修订版结合2008年第1版出版以来课堂教学和读者反馈的勘误和修改意见，对全书进行了多方面的修订和更新。

循序渐进地讲述共享存储器多线程编程的基础知识。

详细解释当今多处理器硬件对并发程序设计的支持方式。

全面考察主流的并发数据结构及其关键设计要素。

从简单的锁机制到最新的事务内存系统，独立、完整地阐述了同步技术。

给出大量利用Java并发工具包编写的可完全执行的Java实例。

附录提供了采用其他程序设计语言和包（如C#、C及C++的Pthreads库）进行编程的相关背景知识以及硬件基础知识。

 多处理器编程的艺术下载