多处理器编程的艺术 原书第2版

本书主要讨论共享存储通信方式下的多处理器并发程序设计。首先介绍基本原理，分析异步并发环境中的可计算问题，包括相关度量标准和方法。然后开展应用实践，侧重于并发程序的性能分析。每一章讨论一种特定的并发数据结构、程序设计模式或算法技巧。第2版对数据并行、事务性编程、存储管理等内容做了重点更新和扩充，并采用C++语言重构相关示例，更加关注底层机制。本书适合作为高等院校计算机相关专业的课程教材，也适合作为业界技术人员的参考书籍。

译者序
前言
第1章 导论1
1.1 共享对象和同步2
1.2 一则寓言故事4
1.2.1 互斥协议的特性6
1.2.2 故事的寓意7
1.3 生产者-消费者问题7
1.4 读者-写者问题9
1.5 并行化的严酷现实10
1.6 并行程序设计11
1.7 章节注释12
1.8 练习题12
第一部分 基本原理
第2章 互斥16
2.1 时间和事件16
2.2 临界区16
2.3 双线程解决方案19
2.3.1 LockOne类19
2.3.2 LockTwo类20
2.3.3 彼得森锁21
2.4 关于死锁的说明22
2.5 过滤锁23
2.6 公平性25
2.7 兰波特的面包房锁算法25
2.8 有界时间戳27
2.9 存储单元数量的下界29
2.10 章节注释32
2.11 练习题32
第3章 并发对象36
3.1 并发性和正确性36
3.2 串行对象38
3.3 顺序一致性39
3.3.1 顺序一致性与实时次序41
3.3.2 顺序一致性是非阻塞的41
3.3.3 可组合性42
3.4 线性一致性43
3.4.1 可线性化点43
3.4.2 线性一致性和顺序一致性43
3.5 静态一致性44
3.5.1 静态一致性的特性44
3.6 形式化定义44
3.6.1 历史记录45
3.6.2 线性一致性46
3.6.3 线性一致性满足可组合性47
3.6.4 线性一致性是非阻塞的47
3.7 内存一致性模型47
3.8 演进条件48
3.8.1 无等待性48
3.8.2 无锁性49
3.8.3 无阻塞性49
3.8.4 阻塞演进条件50
3.8.5 演进条件的特征描述50
3.9 评析51
3.10 章节注释52
3.11 练习题52
第4章 共享存储器基础57
4.1 寄存器空间58
4.2 寄存器构造62
4.2.1 MRSW安全寄存器63
4.2.2 MRSW常规布尔寄存器63
4.2.3 MRSW常规M-值寄存器64
4.2.4 SRSW原子寄存器65
4.2.5 MRSW原子寄存器67
4.2.6 MRMW原子寄存器69
4.3 原子快照71
4.3.1 无阻塞快照71
4.3.2 无等待快照73
4.3.3 正确性证明75
4.4 章节注释76
4.5 练习题77
第5章 同步操作原语的相对能力80
5.1 共识数80
5.1.1 状态和价81
5.2 原子寄存器82
5.3 共识性协议84
5.4 FIFO队列85
5.5 多重赋值对象87
5.6 读取-修改-写入操作90
5.7 Common2 RMW操作91
5.8 compareAndSet操作92
5.9 章节注释93
5.10 练习题94
第6章 共识性的通用性99
6.1 引言99
6.2 通用性99
6.3 无锁的通用构造100
6.4 无等待的通用构造103
6.5 章节注释107
6.6 练习题108
第二部分 应用实践
第7章 自旋锁和争用112
7.1 实际问题的研究112
7.2 易失性字段和原子对象114
7.3 测试-设置锁115
7.4 指数退避算法117
7.5 队列锁119
7.5.1 基于数组的锁119
7.5.2 CLH队列锁121
7.5.3 MCS队列锁123
7.6 时限队列锁125
7.7 层级锁127
7.7.1 层级退避锁128
7.7.2 同类群组锁129
7.7.3 同类群组锁的实现130
7.8 复合锁132
7.9 线程单独运行的快速路径137
7.10 锁的选择说明138
7.11 章节注释138
7.12 练习题139
第8章 管程和阻塞同步141
8.1 引言141
8.2 管程锁和条件141
8.2.1 条件142
8.2.2 唤醒丢失的问题145
8.3 读取-写入锁146
8.3.1 简单的读取-写入锁146
8.3.2 公平的读取-写入锁148
8.4 可重入锁150
8.5 信号量151
8.6 章节注释151
8.7 练习题152
第9章 链表：锁的作用155
9.1 引言155
9.2 基于链表的集合156
9.3 并发推理157
9.4 粗粒度同步159
9.5 细粒度同步160
9.6 乐观同步163
9.7 惰性同步167
9.8 非阻塞同步170
9.9 讨论175
9.10 章节注释176
9.11 练习题176
第10章 队列、内存管理和ABA问题178
10.1 引言178
10.2 队列179
10.3 有界部分队列179
10.4 无界接近队列183
10.5 无锁的无界队列184
10.6 内存回收和ABA问题187
10.6.1 简单的同步队列190
10.7 双重数据结构192
10.8 章节注释194
10.9 练习题194
第11章 栈和消除196
11.1 引言196
11.2 无锁的无界栈196
11.3 消除198
11.4 消除退避栈199
11.4.1 无锁交换机199
11.4.2 消除数组201
11.5 章节注释204
11.6 练习题204
第12章 计数、排序和分布式协作208
12.1 引言208
12.2 共享计数208
12.3 软件组合209
12.3.1 概述209
12.3.2 一个扩展的实例215
12.3.3 性能和健壮性216
12.4 静态一致池和计数器217
12.5 计数网络217
12.5.1 可计数网络218
12.5.2 双调计数网络219
12.5.3 性能和流水线227
12.6 衍射树228
12.7 并行排序231
12.8 排序网络231
12.8.1 设计一个排序网络232
12.9 样本排序234
12.10 分布式协作235
12.11 章节注释236
12.12 练习题237
第13章 并发哈希和固有并行240
13.1 引言240
13.2 封闭地址哈希集241
13.2.1 粗粒度哈希集243
13.2.2 带状哈希集244
13.2.3 可细化的哈希集246
13.3 无锁的哈希集249
13.3.1 递归有序拆分249
13.3.2 BucketList类252
13.3.3 LockFreeHashSet类253
13.4 开放地址哈希集255
13.4.1 布谷鸟哈希算法255
13.4.2 并发布谷鸟算法257
13.4.3 带状并发布谷鸟哈希算法261
13.4.4 可细化的并发布谷鸟哈希算法262
13.5 章节注释265
13.6 练习题265
第14章 跳跃链表和平衡查找266
14.1 引言266
14.2 顺序跳跃链表266
14.3 基于锁的并发跳跃链表268
14.3.1 概述268
14.3.2 算法269
14.4 无锁的并发跳跃链表275
14.4.1 概述275
14.4.2 算法277
14.5 并发跳跃链表283
14.6 章节注释284
14.7 练习题284
第15章 优先级队列286
15.1 引言286
15.1.1 并发优先级队列286
15.2 基于数组的有界优先级队列286
15.3 基于树的有界优先级队列287
15.4 基于堆的无界优先级队列290
15.4.1 顺序堆290
15.4.2 并发堆292
15.5 基于跳跃链表的无界优先级队列297
15.6 章节注释299
15.7 练习题300
第16章 调度和工作分配302
16.1 引言302
16.2 并行化分析308
16.3 多处理器的实际调度311
16.4 工作分配312
16.4.1 工作窃取312
16.4.2 让步和多道程序设计313
16.5 工作窃取双端队列314
16.5.1 有界工作窃取双端队列314
16.5.2 无界工作窃取双端队列318
16.5.3 工作交易321
16.6 章节注释322
16.7 练习题323
第17章 数据并行326
17.1 MapReduce328
17.1.1 MapReduce框架328
17.1.2 基于MapReduce的Word-Count应用程序330
17.1.3 基于MapReduce的KMeans应用程序331
17.1.4 MapReduce的实现332
17.2 流计算334
17.2.1 基于流的WordCount应用程序335
17.2.2 基于流的KMeans应用程序336
17.2.3 实现聚合运算的并行化338
17.3 章节注释340
17.4 练习题341
第18章 屏障347
18.1 引言347
18.2 屏障的实现348
18.3 语义反向屏障348
18.4 组合树屏障349
18.5 静态树屏障352
18.6 终止检测屏障353
18.7 章节注释356
18.8 练习题357
第19章 乐观主义和手动内存管理363
19.1 从Java过渡到C++363
19.2 乐观主义和显式回收364
19.3 保护挂起的操作365
19.4 用于管理内存的对象366
19.5 遍历链表367
19.6 风险指针369
19.7 基于周期的内存回收372
19.8 章节注释374
19.9 练习题375
第20章 事务性编程376
20.1 并发程序设计面临的挑战376
20.1.1 锁的问题376
20.1.2 明确预测的问题377
20.1.3 非阻塞算法的问题378
20.1.4 可组合性问题379
20.1.5 总结380
20.2 事务性编程380
20.2.1 事务性编程示例381
20.3 事务性编程的硬件支持382
20.3.1 硬件预测382
20.3.2 基本缓存一致性382
20.3.3 事务缓存一致性383
20.3.4 硬件支持的局限性384
20.4 事务性锁消除384
20.4.1 讨论386
20.5 事务性内存387
20.5.1 运行时调度388
20.5.2 显式自我中止388
20.6 软件事务389
20.6.1 使用所有权记录的事务390
20.6.2 基于值验证的事务394
20.7 硬件事务和软件事务的有机结合396
20.8 事务数据结构设计397
20.9 章节注释397
20.10 练习题398
附录A 软件基础399
附录B 硬件基础417
参考文献 428