| 作者 |
| [美]莫里斯·赫利希(Maurice Herlihy),[美]尼尔·沙维特(Nir Shavit),[美]维克多·卢昌科(Victor Luchangco),[美]迈克尔·斯皮尔(Michael Spear) |
| 丛书名 |
| 经典原版书库 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9787111695691 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 本书由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-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 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 |