Preface
Acknowledgments
Suggestedwaystoteachtheartofmultiprocessorprogramming
CHAPTER 1 Introduction 1
11 Sharedobjectsandsynchronization 3
12 Afable 6
121 Propertiesofamutualexclusionprotocol 8
122 Themoral 9
13 Theproducer�Cconsumerproblem 9
14 Thereaders�Cwritersproblem 11
15 Theharshrealitiesofparallelization 12
16 Parallelprogramming 14
17 Chapternotes 15
18 Exercises 15
PART 1 Principles
CHAPTER2 Mutual exclusion 21
21 Timeandevents 21
22 Criticalsections 22
23 Two-threadsolutions 25
231 TheLockOne class 25
232 TheLockTwo class 26
233 ThePetersonlock 27
24 Notesondeadlock 29
25 Thefilterlock 30
26 Fairness 33
27 Lamport��sBakeryalgorithm 34
28 Boundedtimestamps 35
29 Lowerboundsonthenumberoflocations 39
210Chapternotes 41
211 Exercises 42
CHAPTER 3 Concurrent objects 49
31 Concurrencyandcorrectness 49
32 Sequentialobjects 52
33 Sequentialconsistency 53
331 Sequentialconsistencyversusreal-timeorder 55
332 Sequentialconsistencyisnonblocking 56
333 Compositionality 57
34 Linearizability 58
341 Linearizationpoints 58
342 Linearizabilityversussequentialconsistency 59
35 Quiescentconsistency 59
351 Propertiesofquiescentconsistency 60
36 Formaldefinitions 60
361 Histories 60
362 Linearizability 61
363 Linearizabilityiscompositional 63
364 Linearizabilityisnonblocking 63
37 Memoryconsistencymodels 64
38 Progressconditions 64
381 Wait-freedom 65
382 Lock-freedom 65
383 Obstruction-freedom 66
384 Blockingprogressconditions 67
385 Characterizingprogressconditions 67
39 Remarks 68
310 Chapternotes 69
311 Exercises 70
CHAPTER 4 Foundations of shared memory 75
41 Thespaceofregisters 76
42 Registerconstructions 81
421 SafeMRSWregisters 82
422 AregularBooleanMRSWregister 83
423 AregularM-valuedMRSWregister 84
424 AnatomicSRSWregister 85
425 AnatomicMRSWregister 87
426 AnatomicMRMWregister 90
43 Atomicsnapshots 92
431 Anobstruction-freesnapshot 92
432