您现在的位置: 首页 / 产品中心/ 华章分社/ 多处理器编程的艺术(英文版·原书第2版 )

多处理器编程的艺术(英文版·原书第2版 )

ISBN:978-7-111-69569-1

作者:(美)莫里斯·赫利希(Maurice Herlihy)等著

定价:¥199.00

本站图书均由机械工业出版社旗下电子商务网站提供

图书详情
内容提要
目录
CIP
本书由G?del奖(理论计算机领域最高荣誉)得主领衔撰写,第1版被世界各地的大学选作教材,同时成为技术人员的重要参考书。第2版紧跟技术趋势,涉及大量前沿研究成果,涵盖当前主流算法,可进一步帮助读者实现或改进并行算法,解决大数据时代的海量计算难题。
本书主要讨论共享存储通信方式下的多处理器并发程序设计。首先介绍基本原理,分析异步并发环境中的可计算问题,包括相关度量标准和方法。然后开展应用实践,侧重于并发程序的性能分析。每一章讨论一种特定的并发数据结构、程序设计模式或算法技巧,深入剖析锁问题,进而将其应用到不同的多处理器系统设计中。
第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<T> 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 
图书在版编目(CIP)数据
多处理器编程的艺术:英文版·原书第2版 / (美)莫里斯·赫利希(Maurice Herlihy)等著. --北京:机械工业出版社,2022.1
(经典原版书库)
书名原文:The Art of Multiprocessor Programming,Second Edition
ISBN 978-7-111-69569-1
I. ①多… II. ①莫… III. ①微处理器-程序设计-英文 IV. ①TP332
中国版本图书馆CIP数据核字(2021)第230810号
相关图书
浏览此书同时浏览过的图书