The Art of Multiprocessor Programming
                                 Copyright 2007 Elsevier Inc. All rights reserved
                                    Maurice Herlihy       Nir Shavit
                                            October 3, 2007
                              DRAFT COPY
               2
               DRAFT COPY
                       Contents
                       1 Introduction                                                                13
                           1.1 SharedObjectsandSynchronization.............. 16
                           1.2 AFable.............................. 19
                                 1.2.1 PropertiesofMutualExclusion............. 21
                                 1.2.2 TheMoral......................... 22
                           1.3 TheProducer-ConsumerProblem................ 23
                           1.4 TheReaders/WritersProblem.................. 26
                           1.5 TheHarshRealitiesofParallelization ............. 27
                           1.6 Missive .............................. 29
                           1.7 ChapterNotes .......................... 30
                           1.8 Exercises ............................. 30
                       Principles                                                                    35
                       2 Mutual Exclusion                                                            37
                           2.1 Time................................ 37
                           2.2 CriticalSections ......................... 38
                           2.3 Two-ThreadSolutions...................... 41
                                 2.3.1  The LockOne Class.................... 41
                                 2.3.2  The LockTwo Class.................... 43
                                 2.3.3 ThePetersonLock.................... 44
                                    DRAFT COPY
                           2.4 TheFilterLock.......................... 46
                           2.5 Fairness.............................. 49
                           2.6 LamportsBakeryAlgorithm .................. 49
                           2.7   Bounded Timestamps . . . . . . ................ 51
                           2.8   Lower Bounds on Number of Locations . . . . . . . ...... 56
                           2.9 ChapterNotes .......................... 60
                           2.10Exercises ............................. 60
                                                               3
                                 4                                                                CONTENTS
                                 3 Concurrent Objects                                                        67
                                     3.1 ConcurrencyandCorrectness.................. 67
                                     3.2 SequentialObjects........................ 71
                                     3.3 QuiescentConsistency...................... 72
                                          3.3.1 Remarks.......................... 74
                                     3.4 SequentialConsistency...................... 75
                                          3.4.1 Remarks.......................... 76
                                     3.5  Linearizability . . ......................... 79
                                          3.5.1 LinearizationPoints ................... 79
                                          3.5.2 Remarks.......................... 79
                                     3.6 FormalDe“nitions ........................ 80
                                          3.6.1   Linearizability  . . . . .................. 81
                                          3.6.2   Linearizability is Compositional . . . . . ........ 82
                                          3.6.3 TheNon-BlockingProperty............... 83
                                     3.7 ProgressConditions ....................... 84
                                          3.7.1 DependentProgressConditions............. 85
                                     3.8 TheJavaMemoryModel .................... 86
                                          3.8.1 LocksandSynchronizedBlocks............. 88
                                          3.8.2 VolatileFields ...................... 88
                                          3.8.3 FinalFields........................ 89
                                     3.9 Remarks.............................. 90
                                     3.10ChapterNotes .......................... 91
                                     3.11Exercises ............................. 91
                                 4 Foundations of Shared Memory                                              97
                                     4.1 TheSpaceofRegisters...................... 98
                                     4.2 RegisterConstructions......................104
                                          4.2.1 MRSWSafeRegisters..................105
                                          4.2.2 ARegularBooleanMRSWRegister..........105
                                          4.2.3   Aregular M-valuedMRSWregister...........106
                                          4.2.4 AnAtomicSRSWRegister...............109
                                          4.2.5 AnAtomicMRSWRegister...............112
                                   DRAFT COPY
                                          4.2.6 AnAtomicMRMWRegister ..............115
                                     4.3 AtomicSnapshots ........................117
                                          4.3.1 AnObstruction-freeSnapshot..............117
                                          4.3.2 AWait-FreeSnapshot..................119
                                          4.3.3 CorrectnessArguments .................119
                                     4.4 ChapterNotes ..........................121
                                     4.5 Exercises .............................122