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 Theproducerconsumerproblem...................... 9
1.4 Thereaderswritersproblem ......................... 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 LamportsBakeryalgorithm ......................... 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