132x Filetype PDF File size 0.54 MB Source: courses.csail.mit.edu
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
no reviews yet
Please Login to review.