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

PrefaceAcknowledgmentsSuggestedwaystoteachtheartofmultiprocessorprogrammingCHAPTER 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