|
|
|
本書由G?del獎得主領銜撰寫，主要討論共用存儲通信方式下的多處理器併發程式設計。首先介紹基本原理，分析非同步併發環境中的可計算問題，包括相關度量標準和方法。然後開展應用實踐，側重於併發程式的性能分析。每一章討論一種特定的併發資料結構、程式設計模式或演算法技巧。第2版對資料並行、事務性程式設計、存儲管理等內容做了重點 新和擴充，並採用C++語言重構相關示例， 加關注底層機制。
本書適合作為高等院校電腦相關專業的課程教材，也適合作為業界技術人員的參考書籍。
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 ............................ 48
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
