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

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-basedsets20

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 Discussion225

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 class. 319 

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