本书由Gödel奖得主领衔撰写，主要讨论共享存储通信方式下的多处理器并发程序设计。首先介绍基本原理，分析异步并发环境中的可计算问题，包括相关度量标准和方法。然后开展应用实践，侧重于并发程序的性能分析。每一章讨论一种特定的并发数据结构、程序设计模式或算法技巧。第2版对数据并行、事务性编程、存储管理等内容做了重点更新和扩充，并采用C++语言重构相关示例，更加关注底层机制。本书适合作为高等院校计算机相关专业的课程教材，也适合作为业界技术人员的参考书籍。
WU
计算机\并行计算
本书由G?del奖（理论计算机领域最高荣誉）得主领衔撰写，第1版被世界各地的大学选作教材，同时成为技术人员的重要参考书。第2版紧跟技术趋势，涉及大量前沿研究成果，涵盖当前主流算法，可进一步帮助读者实现或改进并行算法，解决大数据时代的海量计算难题。
本书主要讨论共享存储通信方式下的多处理器并发程序设计。首先介绍基本原理，分析异步并发环境中的可计算问题，包括相关度量标准和方法。然后开展应用实践，侧重于并发程序的性能分析。每一章讨论一种特定的并发数据结构、程序设计模式或算法技巧，深入剖析锁问题，进而将其应用到不同的多处理器系统设计中。
第2版对数据并行、事务性编程、存储管理等内容做了重点更新和扩充，并采用C++语言重构相关示例，更加关注底层机制。
作者简介
莫里斯·赫利希（Maurice Herlihy） 布朗大学计算机科学教授，曾任职于卡内基·梅隆大学和DEC公司剑桥实验室。他获得了包括Edsger W. Dijkstra奖（2003，2012）、ACM/EATCS G?del奖（2004）、IEEE Wallace McDowell奖（2013）和Fulbright杰出讲席（2012）在内的众多荣誉。他是ACM会士，美国国家发明家科学院、美国国家工程院以及美国艺术与科学院院士。他拥有麻省理工学院计算机科学博士学位。
尼尔·沙维特（Nir Shavit） 麻省理工学院计算机科学教授，特拉维夫大学计算机科学教授，曾任职于Sun实验室和Oracle实验室。他与Maurice Herlihy分享了Edsger W. Dijkstra奖（2012）和ACM/EATCS G?del奖（2004）。他拥有希伯来大学计算机科学博士学位。
维克多·卢昌科（Victor Luchangco） Algorand公司高级算法研究员，曾任职于Sun实验室和Oracle实验室。他拥有麻省理工学院计算机科学博士学位。
迈克尔·斯皮尔（Michael Spear） 理海大学计算机科学教授。他拥有罗切斯特大学计算机科学博士学位。
[美]莫里斯·赫利希(Maurice Herlihy),[美]尼尔·沙维特(Nir Shavit),[美]维克多·卢昌科(Victor Luchangco),[美]迈克尔·斯皮尔(Michael Spear) 著：莫里斯·赫利希（Maurice Herlihy） 布朗大学计算机科学教授，曾任职于卡内基·梅隆大学和DEC公司剑桥实验室。他获得了包括Edsger W. Dijkstra奖（2003，2012）、ACM/EATCS Gödel奖（2004）、IEEE Wallace McDowell奖（2013）和Fulbright杰出讲席（2012）在内的众多荣誉。他是ACM会士，美国国家发明家科学院、美国国家工程院以及美国艺术与科学院院士。他拥有麻省理工学院计算机科学博士学位。
尼尔·沙维特（Nir Shavit） 麻省理工学院计算机科学教授，特拉维夫大学计算机科学教授，曾任职于Sun实验室和Oracle实验室。他与Maurice Herlihy分享了Edsger W. Dijkstra奖（2012）和ACM/EATCS Gödel奖（2004）。他拥有希伯来大学计算机科学博士学位。
维克多·卢昌科（Victor Luchangco） Algorand公司高级算法研究员，曾任职于Sun实验室和Oracle实验室。他拥有麻省理工学院计算机科学博士学位。
迈克尔·斯皮尔（Michael Spear） 理海大学计算机科学教授。他拥有罗切斯特大学计算机科学博士学位。
Preface
Acknowledgments
Suggestedwaystoteachtheartofmultiprocessorprogramming
CHAPTER 1 Introduction .................................... 1
1.1 Sharedobjectsandsynchronization .................... 3
1.2 Afable ......................................... 6
1.2.1 Propertiesofamutualexclusionprotocol .......... 8
1.2.2 Themoral .................................. 9
1.3 Theproducer–consumerproblem...................... 9
1.4 Thereaders–writersproblem ......................... 11
1.5 Theharshrealitiesofparallelization.................... 12
1.6 Parallelprogramming .............................. 14
1.7 Chapternotes..................................... 15
1.8 Exercises........................................ 15
PART 1 Principles
CHAPTER2 Mutual exclusion ............................... 21
2.1 Timeandevents................................... 21
2.2 Criticalsections................................... 22
2.3 Two-threadsolutions ............................... 25
2.3.1 TheLockOne class ............................ 25
2.3.2 TheLockTwo class ............................ 26
2.3.3 ThePetersonlock ............................ 27
2.4 Notesondeadlock ................................. 29
2.5 Thefilterlock .................................... 30
2.6 Fairness......................................... 33
2.7 Lamport’sBakeryalgorithm ......................... 34
2.8 Boundedtimestamps ............................... 35
2.9 Lowerboundsonthenumberoflocations ............... 39
2.10Chapternotes..................................... 41
2.11 Exercises........................................ 42
CHAPTER 3 Concurrent objects ............................. 49
3.1 Concurrencyandcorrectness ......................... 49
3.2 Sequentialobjects ................................. 52
3.3 Sequentialconsistency.............................. 53
3.3.1 Sequentialconsistencyversusreal-timeorder ....... 55
3.3.2 Sequentialconsistencyisnonblocking............. 56
3.3.3 Compositionality............................. 57
3.4 Linearizability .................................... 58
3.4.1 Linearizationpoints .......................... 58
3.4.2 Linearizabilityversussequentialconsistency ........ 59
3.5 Quiescentconsistency .............................. 59
3.5.1 Propertiesofquiescentconsistency ............... 60
3.6 Formaldefinitions ................................. 60
3.6.1 Histories ................................... 60
3.6.2 Linearizability............................... 61
3.6.3 Linearizabilityiscompositional.................. 63
3.6.4 Linearizabilityisnonblocking ................... 63
3.7 Memoryconsistencymodels ......................... 64
3.8 Progressconditions ................................ 64
3.8.1 Wait-freedom ............................... 65
3.8.2 Lock-freedom ............................... 65
3.8.3 Obstruction-freedom .......................... 66
3.8.4 Blockingprogressconditions ................... 67
3.8.5 Characterizingprogressconditions ............... 67
3.9 Remarks ........................................ 68
3.10 Chapternotes..................................... 69
3.11 Exercises........................................ 70
CHAPTER 4 Foundations of shared memory ................. 75
4.1 Thespaceofregisters .............................. 76
4.2 Registerconstructions .............................. 81
4.2.1 SafeMRSWregisters ......................... 82
4.2.2 AregularBooleanMRSWregister ............... 83
4.2.3 AregularM-valuedMRSWregister .............. 84
4.2.4 AnatomicSRSWregister ...................... 85
4.2.5 AnatomicMRSWregister ..................... 87
4.2.6 AnatomicMRMWregister..................... 90
4.3 Atomicsnapshots ................................. 92
4.3.1 Anobstruction-freesnapshot.................... 92
4.3.2 Await-freesnapshot .......................... 93
4.3.3 Correctnessarguments ........................ 97
4.4 Chapternotes..................................... 98
4.5 Exercises........................................ 99
CHAPTER 5 The relative power of primitive synchronization operations ..................... 103
5.1 Consensusnumbers ................................ 104
5.1.1 Statesandvalence............................ 105
5.2 Atomicregisters .................................. 106
5.3 Consensusprotocols ............................... 109
5.4 FIFOqueues ..................................... 110
5.5 Multipleassignmentobjects.......................... 113
5.6 Read–modify–writeoperations ....................... 116
5.7 Common2RMWoperations ......................... 117
5.8 ThecompareAndSet operation ......................... 119
5.9 Chapternotes..................................... 120
5.10 Exercises........................................ 121
CHAPTER 6 Universality of consensus ....................... 129
6.1 Introduction...................................... 129
6.2 Universality...................................... 130
6.3 Alock-freeuniversalconstruction ..................... 130
6.4 Await-freeuniversalconstruction ..................... 134
6.5 Chapternotes..................................... 140
6.6 Exercises........................................ 141
PART 2 Practice
CHAPTER 7 Spin locks and contention ....................... 147
7.1 Welcometotherealworld ........................... 147
7.2 Volatilefieldsandatomicobjects ...................... 150
7.3 Test-and-setlocks ................................. 150
7.4 Exponentialback-off ............................... 154
7.5 Queuelocks...................................... 156
7.5.1 Array-basedlocks ............................ 156
7.5.2 TheCLHqueuelock.......................... 159
7.5.3 TheMCSqueuelock.......................... 161
7.6 Aqueuelockwithtimeouts .......................... 163
7.7 Hierarchicallocks ................................. 166
7.7.1 Ahierarchicalback-offlock .................... 167
7.7.2 Cohortlocks ................................ 167
7.7.3 Acohortlockimplementation ................... 170
7.8 Acompositelock.................................. 171
7.9 Afastpathforthreadsrunningalone ................... 178
7.10 Onelocktorulethemall ............................ 180
7.11 Chapternotes..................................... 180
7.12 Exercises........................................ 181
CHAPTER 8 Monitors and blocking synchronization .......... 183
8.1 Introduction...................................... 183
8.2 Monitorlocksandconditions......................... 183
8.2.1 Conditions ................................. 185
8.2.2 Thelost-wakeupproblem ...................... 187
8.3 Readers–writerslocks .............................. 189
8.3.1 Simplereaders–writerslock .................... 190
8.3.2 Fairreaders–writerslock ....................... 192
8.4Ourownreentrantlock.............................194
8.5Semaphores......................................19
8.6Chapternotes.....................................19
8.7Exercises........................................197
CHAPTER9 Linkedlists:Theroleoflocking.................201
9.1 Introduction......................................201
9.2 List-basedsets....................................20
9.3 Concurrentreasoning...............................204
9.4 Coarse-grainedsynchronization.......................20
9.5 Fine-grainedsynchronization.........................207
9.6 Optimisticsynchronization..........................211
9.7 Lazysynchronization...............................215
9.8 Nonblockingsynchronization.........................22
9.9 Discussion.......................................225
9.10 Chapternotes.....................................226
9.11 Exercises........................................226
CHAPTER 10 Queues, memory management, and the ABA problem ............... 229
10.1 Introduction...................................... 229
10.2 Queues ......................................... 230
10.3 Aboundedpartialqueue ............................ 230
10.4 Anunboundedtotalqueue ........................... 235
10.5 Alock-freeunboundedqueue ........................ 236
10.6 MemoryreclamationandtheABAproblem .............. 240
10.6.1Ana.vesynchronousqueue..................... 244
10.7 Dualdatastructures ................................ 244
10.8 Chapternotes..................................... 248
10.9 Exercises........................................ 248
CHAPTER 11 Stacks and elimination ......................... 251
11.1 Introduction...................................... 251
11.2 Anunboundedlock-freestack ........................ 251
11.3 Elimination ...................................... 254
11.4 Theeliminationback-offstack........................ 255
11.4.1Alock-freeexchanger......................... 255
11.4.2Theeliminationarray ......................... 257
11.5 Chapternotes..................................... 260
11.6 Exercises........................................ 261
CHAPTER 12 Counting, sorting, and distributed coordination ... 265
12.1 Introduction...................................... 265
12.2 Sharedcounting................................... 265
12.3 Softwarecombining................................ 266
12.3.1Overview .................................. 267
12.3.2Anextendedexample ......................... 274
12.3.3Performanceandrobustness .................... 275
12.4 Quiescentlyconsistentpoolsandcounters ............... 276
12.5 Countingnetworks................................. 276
12.5.1Networksthatcount .......................... 276
12.5.2Thebitoniccountingnetwork ................... 279
12.5.3Performanceandpipelining..................... 287
12.6 Diffractingtrees................................... 288
12.7 Parallelsorting ................................... 292
12.8 Sortingnetworks .................................. 293
12.8.1Designingasortingnetwork .................... 294
12.9 Samplesorting.................................... 296
12.10 Distributedcoordination ............................ 298
12.11 Chapternotes..................................... 299
12.12 Exercises........................................ 300
CHAPTER13 Concurrent hashing and natural parallelism ...... 305
13.1 Introduction...................................... 305
13.2 Closed-addresshashsets ............................ 306
13.2.1 Acoarse-grainedhashset ...................... 308
13.2.2 Astripedhashset ............................ 310
13.2.3 Arefinablehashset........................... 311
13.3 Alock-freehashset ................................ 315
13.3.1 Recursivesplit-ordering ....................... 315
13.3.2 TheBucketList class.......................... 318
13.3.3 TheLockFreeHashSet
13.4 Anopen-addresshashset............................ 323
13.4.1Cuckoohashing ............................. 323
13.4.2Concurrentcuckoohashing ..................... 324
13.4.3Stripedconcurrentcuckoohashing ............... 329
13.4.4Arefinableconcurrentcuckoohashset ............ 331
13.5 Chapternotes..................................... 332
13.6 Exercises........................................ 334
CHAPTER 14 Skiplists and balanced search ................... 335
14.1 Introduction...................................... 335
14.2 Sequentialskiplists ................................ 335
14.3 Alock-basedconcurrentskiplist ...................... 337
14.3.1 Abird’s-eyeview ............................ 337
14.3.2 Thealgorithm ............................... 339
14.4 Alock-freeconcurrentskiplist ........................ 345
14.4.1 Abird’s-eyeview ............................ 345
14.4.2 Thealgorithmindetail ........................ 348
14.5 Concurrentskiplists ................................ 355
14.6 Chapternotes..................................... 356
14.7 Exercises........................................ 356
CHAPTER 15 Priority queues ................................. 359
15.1 Introduction...................................... 359
15.1.1Concurrentpriorityqueues ..................... 359
15.2 Anarray-basedboundedpriorityqueue ................. 360
15.3 Atree-basedboundedpriorityqueue ................... 361
15.4 Anunboundedheap-basedpriorityqueue................ 363
15.4.1Asequentialheap ............................ 363
15.4.2Aconcurrentheap............................ 365
15.5 Askiplist-basedunboundedpriorityqueue............... 371
15.6 Chapternotes..................................... 374
15.7 Exercises........................................ 375
CHAPTER 16 Scheduling and work distribution ................ 377
16.1 Introduction...................................... 377
16.2 Analyzingparallelism .............................. 384
16.3 Realisticmultiprocessorscheduling .................... 387
16.4 Workdistribution.................................. 389
16.4.1 Workstealing ............................... 389
16.4.2 Yieldingandmultiprogramming ................. 390
16.5 Work-stealingdeques............................... 390
16.5.1 Aboundedwork-stealingdeque ................. 391
16.5.2 Anunboundedwork-stealingdeque............... 395
16.5.3 Workdealing ............................... 397
16.6 Chapternotes..................................... 400
16.7 Exercises........................................ 401
CHAPTER 17 Data parallelism ............................... 405
17.1 MapReduce ...................................... 407
17.1.1 TheMapReduce framework ...................... 408
17.1.2 AMapReduce-basedWordCount application .......... 410
17.1.3 AMapReduce-basedKMeans application............. 411
17.1.4 TheMapReduce implementation .................. 411
17.2 Streamcomputing ................................. 414
17.2.1 Astream-basedWordCount application ............. 416
17.2.2 Astream-basedKMeans application ............... 417
17.2.3 Makingaggregateoperationsparallel ............. 419
17.3 Chapternotes..................................... 422
17.4 Exercises........................................ 423
CHAPTER 18 Barriers ....................................... 431
18.1 Introduction...................................... 431
18.2 Barrierimplementations............................. 432
18.3 Sensereversingbarrier.............................. 433
18.4 Combiningtreebarrier.............................. 434
18.5 Statictreebarrier .................................. 436
18.6 Terminationdetectionbarriers ........................ 438
18.7 Chapternotes..................................... 442
18.8 Exercises........................................ 443
CHAPTER 19 Optimism and manual memory management ...... 451
19.1 TransitioningfromJavatoC++ ....................... 451
19.2 Optimismandexplicitreclamation..................... 451
19.3 Protectingpendingoperations ........................ 454
19.4 Anobjectformanagingmemory ...................... 455
19.5 Traversingalist ................................... 456
19.6 Hazardpointers ................................... 458
19.7 Epoch-basedreclamation ............................ 462
19.8 Chapternotes..................................... 465
19.9 Exercises........................................ 466
CHAPTER 20 Transactional programming ..................... 467
20.1 Challengesinconcurrentprogramming ................. 467
20.1.1 Problemswithlocking......................... 467
20.1.2 Problemswithexplicitspeculation ............... 468
20.1.3 Problemswithnonblockingalgorithms ............ 470
20.1.4 Problemswithcompositionality ................. 471
20.1.5 Summary .................................. 472
20.2 Transactionalprogramming .......................... 472
20.2.1 Anexampleoftransactionalprogramming.......... 473
20.3 Hardwaresupportfortransactionalprogramming.......... 475
20.3.1 Hardwarespeculation ......................... 475
20.3.2 Basiccachecoherence......................... 475
20.3.3 Transactionalcachecoherence................... 476
20.3.4 Limitationsofhardwaresupport ................. 477
20.4 Transactionallockelision ........................... 478
20.4.1 Discussion ................................. 480
20.5 Transactionalmemory .............................. 481
20.5.1 Run-timescheduling .......................... 482
20.5.2 Explicitself-abort ............................ 483
20.6 Softwaretransactions............................... 483
20.6.1 Transactionswithownershiprecords .............. 485
20.6.2 Transactionswithvalue-basedvalidation........... 490
20.7 Combininghardwareandsoftwaretransactions ........... 492
20.8 Transactionaldatastructuredesign..................... 493
20.9 Chapternotes..................................... 494
20.10 Exercises........................................ 494
APPENDIX A Software basics ............................. 497
A.1 Introduction...................................... 497
A.2 Java............................................ 497
A.2.1 Threads.................................... 497
A.2.2 Monitors................................... 498
A.2.3 Yieldingandsleeping ......................... 501
A.2.4 Thread-localobjects .......................... 502
A.2.5 Randomization .............................. 503
A.3 TheJavamemorymodel ............................ 504
A.3.1 Locksandsynchronizedblocks .................. 505
A.3.2 Volatilefields ............................... 506
A.3.3 Finalfields ................................. 506
A.4 C++............................................ 508
A.4.1 ThreadsinC++.............................. 508
A.4.2 LocksinC++ ............................... 509
A.4.3 Conditionvariables ........................... 510
A.4.4 Atomicvariables............................. 512
A.4.5 Thread-localstorage .......................... 513
A.5 C# ............................................. 514
A.5.1 Threads.................................... 514
A.5.2 Monitors................................... 515
A.5.3 Thread-localobjects .......................... 517
A.6 Appendixnotes ................................... 518
APPENDIX B Hardware basics .............................. 519
B.1 Introduction(andapuzzle) .......................... 519
B.2 Processorsandthreads.............................. 522
B.3 Interconnect...................................... 522
B.4 Memory ........................................ 523
B.5 Caches.......................................... 523
B.5.1 Coherence.................................. 524
B.5.2 Spinning ................................... 526
B.6 Cache-consciousprogramming,orthepuzzlesolved ....... 526
B.7 Multicoreandmultithreadedarchitectures ............... 527
B.7.1 Relaxedmemoryconsistency ................... 528
B.8 Hardwaresynchronizationinstructions.................. 529
B.9 Appendixnotes ................................... 530
B.10 Exercises........................................ 531
Bibliography.................................................. 533
Index ....................................................... 541
