多处理器编程的艺术PDF电子书下载

第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

第一部分 原理 13

第2章 互斥 13

2.1 时间 13

2.2 临界区 13

2.3 双线程解决方案 15

2.3.1 LockOne类 15

2.3.2 LockTwo类 16

2.3.3 Peterson锁 17

2.4 过滤锁 18

2.5 公平性 20

2.6 Bakery算法 20

2.7 有界时间戳 22

2.8 存储单元数量的下界 24

2.9 本章注释 26

2.10 习题 27

第3章 并发对象 30

3.1 并发性与正确性 30

3.2 顺序对象 32

3.3 静态一致性 33

3.4 顺序一致性 34

3.5 可线性化性 37

3.5.1 可线性化点 37

3.5.2 评析 37

3.6 形式化定义 37

3.6.1 可线性化性 38

3.6.2 可线性化性的复合性 39

3.6.3 非阻塞特性 39

3.7 演进条件 40

3.8 Java存储器模型 42

3.8.1 锁和同步块 43

3.8.2 volatile域 43

3.8.3 final域 43

3.9 评析 44

3.10 本章注释 45

3.11 习题 45

第4章 共享存储器基础 49

4.1 寄存器空间 49

4.2 寄存器构造 53

4.2.1 MRSW安全寄存器 54

4.2.2 MRSW规则布尔寄存器 54

4.2.3 M-值MRSW规则寄存器 55

4.2.4 SRSW原子寄存器 56

4.2.5 MRSW原子寄存器 58

4.2.6 MRMW原子寄存器 59

4.3 原子快照 61

4.3.1 无障碍快照 62

4.3.2 无等待快照 63

4.3.3 正确性证明 65

4.4 本章注释 66

4.5 习题 66

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

5.1 一致数 69

5.2 原子寄存器 71

5.3 一致性协议 73

5.4 FIFO队列 73

5.5 多重赋值对象 76

5.6 读-改-写操作 78

5.7 Common2 RMW操作 79

5.8 compareAndSet（）操作 80

5.9 本章注释 81

5.10 习题 82

第6章 一致性的通用性 86

6.1 引言 86

6.2 通用性 87

6.3 一种通用的无锁构造 87

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

6.5 本章注释 94

6.6 习题 94

第二部分 实践 97

第7章 自旋锁与争用 97

7.1 实际问题 97

7.2 测试-设置锁 99

7.3 再论基于TAS的自旋锁 101

7.4 指数后退 101

7.5 队列锁 103

7.5.1 基于数组的锁 103

7.5.2 CLH队列锁 105

7.5.3 MCS队列锁 106

7.6 时限队列锁 109

7.7 复合锁 111

7.8 层次锁 117

7.8.1 层次后退锁 117

7.8.2 层次CLH队列锁 118

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

7.10 本章注释 122

7.11 习题 123

第8章 管程和阻塞同步 125

8.1 引言 125

8.2 管程锁和条件 125

8.2.1 条件 126

8.2.2 唤醒丢失问题 129

8.3 读者-写者锁 130

8.3.1 简单的读者-写者锁 130

8.3.2 公平的读者-写者锁 131

8.4 我们的可重入锁 133

8.5 信号量 134

8.6 本章注释 135

8.7 习题 135

第9章 链表：锁的作用 138

9.1 引言 138

9.2 基于链表的集合 139

9.3 并发推理 140

9.4 粗粒度同步 141

9.5 细粒度同步 142

9.6 乐观同步 145

9.7 惰性同步 148

9.8 非阻塞同步 152

9.9 讨论 156

9.10 本章注释 156

9.11 习题 157

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

10.1 引言 158

10.2 队列 159

10.3 部分有界队列 159

10.4 完全无界队列 162

10.5 无锁的无界队列 163

10.6 内存回收和ABA问题 165

10.7 双重数据结构 169

10.8 本章注释 171

10.9 习题 171

第11章 并发栈和消除 173

11.1 引言 173

11.2 无锁的无界栈 173

11.3 消除 175

11.4 后退消除栈 175

11.4.1 无锁交换机 176

11.4.2 消除数组 178

11.5 本章注释 180

11.6 习题 180

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

12.1 引言 183

12.2 共享计数 183

12.3 软件组合 184

12.3.1 概述 184

12.3.2 一个扩展实例 189

12.3.3 性能和健壮性 190

12.4 静态一致池和计数器 191

12.5 计数网 191

12.5.1 可计数网 192

12.5.2 双调计数网 193

12.5.3 性能和流水线 200

12.6 衍射树 200

12.7 并行排序 203

12.8 排序网 203

12.9 样本排序 206

12.10 分布式协作 207

12.11 本章注释 207

12.12 习题 208

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

13.1 引言 211

13.2 封闭地址哈希集 212

13.2.1 粗粒度哈希集 213

13.2.2 空间分带哈希集 214

13.2.3 细粒度哈希集 216

13.3 无锁哈希集 218

13.3.1 递归有序划分 218

13.3.2 BucketList类 221

13.3.3 LockFreeHashSet〈T〉类 222

13.4 放地址哈希集 224

13.4.1 Cuckoo哈希 224

13.4.2 并发Cuckoo哈希 225

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

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

13.5 本章注释 232

13.6 习题 233

第14章 跳表和平衡查找 234

14.1 引言 234

14.2 顺序跳表 234

14.3 基于锁的并发跳表 235

14.3.1 简介 235

14.3.2 算法 237

14.4 无锁并发跳表 242

14.4.1 简介 242

14.4.2 算法细节 244

14.5 并发跳表 250

14.6 本章注释 250

14.7 习题 250

第15章 优先级队列 252

15.1 引言 252

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

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

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

15.4.1 顺序堆 255

15.4.2 并发堆 257

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

15.6 本章注释 263

15.7 习题 264

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

16.1 引言 265

16.2 并行分析 270

16.3 多处理器的实际调度 272

16.4 工作分配 274

16.4.1 工作窃取 274

16.4.2 屈从和多道程序设计 274

16.5 工作窃取双端队列 275

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

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

16.5.3 工作平衡 282

16.6 本章注释 283

16.7 习题 283

第17章 障碍 286

17.1 引言 286

17.2 障碍实现 287

17.3 语义换向障碍 287

17.4 组合树障碍 288

17.5 静态树障碍 290

17.6 终止检测障碍 292

17.7 本章注释 295

17.8 习题 295

第18章 事务内存 301

18.1 引言 301

18.1.1 关于锁的问题 301

18.1.2 关于compareAndSet（）的问题 302

18.1.3 关于复合性的问题 303

18.1.4 我们能做什么 304

18.2 事务和原子性 304

18.3 软事务内存 305

18.3.1 事务和事务线程 308

18.3.2 僵尸事务和一致性 309

18.3.3 原子对象 310

18.3.4 如何演进 310

18.3.5 争用管理器 311

18.3.6 原子对象的实现 313

18.3.7 无干扰原子对象 314

18.3.8 基于锁的原子对象 317

18.4 硬事务内存 322

18.4.1 缓存一致性 323

18.4.2 事务缓存一致性 323

18.4.3 引进 324

18.5 本章注释 324

18.6 习题 325

第三部分 附录 327

附录A 软件基础 327

附录B 硬件基础 339

参考文献 349