Machine generated contents note: 1.Introduction -- 1.1.Shared Objects and Synchronization -- 1.2.A Fable -- 1.2.1.Properties of Mutual Exclusion -- 1.2.2.The Moral -- 1.3.The Producer-Consumer Problem -- 1.4.The Readers-Writers Problem -- 1.5.The Harsh Realities of Parallelization -- 1.6.Parallel Programming -- 1.7.Chapter Notes -- 1.8.Exercises -- I.PRINCIPLES -- 2.Mutual Exclusion -- 2.1.Time -- 2.2.Critical Sections -- 2.3.2.Thread Solutions -- 2.3.1.The LockOne Class -- 2.3.2.The LockTwo Class -- 2.3.3.The Peterson Lock -- 2.4.The Filter Lock -- 2.5.Fairness -- 2.6.Lamport's Bakery Algorithm -- 2.7.Bounded Timestamps -- 2.8.Lower Bounds on the Number of Locations -- 2.9.Chapter Notes -- 2.10.Exercises -- 3.Concurrent Objects -- 3.1.Concurrency and Correctness -- 3.2.Sequential Objects -- 3.3.Quiescent Consistency -- 3.3.1.Remarks -- 3.4.Sequential Consistency -- 3.4.1.Remarks -- 3.5.Linearizability -- 3.5.1.Linearization Points -- 3.5.2.Remarks -- 3.6.Formal Definitions --

Contents note continued: 3.6.1.Linearizability -- 3.6.2.Compositional Linearizability -- 3.6.3.The Nonblocking Property -- 3.7.Progress Conditions -- 3.7.1.Dependent Progress Conditions -- 3.8.The Java Memory Model -- 3.8.1.Locks and Synchronized Blocks -- 3.8.2.Volatile Fields -- 3.8.3.Final Fields -- 3.9.Remarks -- 3.10.Chapter Notes -- 3.11.Exercises -- 4.Foundations of Shared Memory -- 4.1.The Space of Registers -- 4.2.Register Constructions -- 4.2.1.MRSW Safe Registers -- 4.2.2.A Regular Boolean MRSW Register -- 4.2.3.A Regular M-Valued MRSW Register -- 4.2.4.An Atomic SRSW Register -- 4.2.5.An Atomic MRSW Register -- 4.2.6.An Atomic MRMW Register -- 4.3.Atomic Snapshots -- 4.3.1.An Obstruction-Free Snapshot -- 4.3.2.A Wait-Free Snapshot -- 4.3.3.Correctness Arguments -- 4.4.Chapter Notes -- 4.5.Exercises -- 5.The Relative Power of Primitive Synchronization Operations -- 5.1.Consensus Numbers -- 5.1.1.States and Valence -- 5.2.Atomic Registers -- 5.3.Consensus Protocols --

Contents note continued: 5.4.FIFO Queues -- 5.5.Multiple Assignment Objects -- 5.6.Read-Modify-Write Operations -- 5.7.Common2 RMW Operations -- 5.8.The compareAndSet() Operation -- 5.9.Chapter Notes -- 5.10.Exercises -- 6.Universality of Consensus -- 6.1.Introduction -- 6.2.Universality -- 6.3.A Lock-Free Universal Construction -- 6.4.A Wait-Free Universal Construction -- 6.5.Chapter Notes -- 6.6.Exercises -- II.PRACTICE -- 7.Spin Locks and Contention -- 7.1.Welcome to the Real World -- 7.2.Test-And-Set Locks -- 7.3.TAS-Based Spin Locks Revisited -- 7.4.Exponential Backoff -- 7.5.Queue Locks -- 7.5.1.Array-Based Locks -- 7.5.2.The CLH Queue Lock -- 7.5.3.The MCS Queue Lock -- 7.6.A Queue Lock with Timeouts -- 7.7.A Composite Lock -- 7.7.1.A Fast-Path Composite Lock -- 7.8.Hierarchical Locks -- 7.8.1.A Hierarchical Backoff Lock -- 7.8.2.A Hierarchical CLH Queue Lock -- 7.9.One Lock To Rule Them All -- 7.10.Chapter Notes -- 7.11.Exercises --

Contents note continued: 8.Monitors and Blocking Synchronization -- 8.1.Introduction -- 8.2.Monitor Locks and Conditions -- 8.2.1.Conditions -- 8.2.2.The Lost-Wakeup Problem -- 8.3.Readers-Writers Locks -- 8.3.1.Simple Readers-Writers Lock -- 8.3.2.Fair Readers-Writers Lock -- 8.4.Our Own Reentrant Lock -- 8.5.Semaphores -- 8.6.Chapter Notes -- 8.7.Exercises -- 9.Linked Lists: The Role of Locking -- 9.1.Introduction -- 9.2.List-Based Sets -- 9.3.Concurrent Reasoning -- 9.4.Coarse-Grained Synchronization -- 9.5.Fine-Grained Synchronization -- 9.6.Optimistic Synchronization -- 9.7.Lazy Synchronization -- 9.8.Non-Blocking Synchronization -- 9.9.Discussion -- 9.10.Chapter Notes -- 9.11.Exercises -- 10.Concurrent Queues and the ABA Problem -- 10.1.Introduction -- 10.2.Queues -- 10.3.A Bounded Partial Queue -- 10.4.An Unbounded Total Queue -- 10.5.An Unbounded Lock-Free Queue -- 10.6.Memory Reclamation and the ABA Problem -- 10.6.1.A Naive Synchronous Queue --

Contents note continued: 10.7.Dual Data Structures -- 10.8.Chapter Notes -- 10.9.Exercises -- 11.Concurrent Stacks and Elimination -- 11.1.Introduction -- 11.2.An Unbounded Lock-Free Stack -- 11.3.Elimination -- 11.4.The Elimination Backoff Stack -- 11.4.1.A Lock-Free Exchanger -- 11.4.2.The Elimination Array -- 11.5.Chapter Notes -- 11.6.Exercises -- 12.Counting, Sorting, and Distributed Coordination -- 12.1.Introduction -- 12.2.Shared Counting -- 12.3.Software Combining -- 12.3.1.Overview -- 12.3.2.An Extended Example -- 12.3.3.Performance and Robustness -- 12.4.Quiescently Consistent Pools and Counters -- 12.5.Counting Networks -- 12.5.1.Networks That Count -- 12.5.2.The Bitonic Counting Network -- 12.5.3.Performance and Pipelining -- 12.6.Diffracting Trees -- 12.7.Parallel Sorting -- 12.8.Sorting Networks -- 12.8.1.Designing a Sorting Network -- 12.9.Sample Sorting -- 12.10.Distributed Coordination -- 12.11.Chapter Notes -- 12.12.Exercises --

Contents note continued: 13.Concurrent Hashing and Natural Parallelism -- 13.1.Introduction -- 13.2.Closed-Address Hash Sets -- 13.2.1.A Coarse-Grained Hash Set -- 13.2.2.A Striped Hash Set -- 13.2.3.A Refinable Hash Set -- 13.3.A Lock-Free Hash Set -- 13.3.1.Recursive Split-Ordering -- 13.3.2.The Bucket List Class -- 13.3.3.The LockFreeHashSet<T>Class -- 13.4.An Open-Addressed Hash Set -- 13.4.1.Cuckoo Hashing -- 13.4.2.Concurrent Cuckoo Hashing -- 13.4.3.Striped Concurrent Cuckoo Hashing -- 13.4.4.A Refinable Concurrent Cuckoo Hash Set -- 13.5.Chapter Notes -- 13.6.Exercises -- 14.Skiplists and Balanced Search -- 14.1.Introduction -- 14.2.Sequential Skiplists -- 14.3.A Lock-Based Concurrent Skiplist -- 14.3.1.A Bird's-Eye View -- 14.3.2.The Algorithm -- 14.4.A Lock-Free Concurrent Skiplist -- 14.4.1.A Bird's-Eye View -- 14.4.2.The Algorithm in Detail -- 14.5.Concurrent Skiplists -- 14.6.Chapter Notes -- 14.7.Exercises -- 15.Priority Queues -- 15.1.Introduction --

Contents note continued: 15.1.1.Concurrent Priority Queues -- 15.2.An Array-Based Bounded Priority Queue -- 15.3.A Tree-Based Bounded Priority Queue -- 15.4.An Unbounded Heap-Based Priority Queue -- 15.4.1.A Sequential Heap -- 15.4.2.A Concurrent Heap -- 15.5.A Skiplist-Based Unbounded Priority Queue -- 15.6.Chapter Notes -- 15.7.Exercises -- 16.Futures, Scheduling, and Work Distribution -- 16.1.Introduction -- 16.2.Analyzing Parallelism -- 16.3.Realistic Multiprocessor Scheduling -- 16.4.Work Distribution -- 16.4.1.Work Stealing -- 16.4.2.Yielding and Multiprogramming -- 16.5.Work-Stealing Dequeues -- 16.5.1.A Bounded Work-Stealing Dequeue -- 16.5.2.An Unbounded Work-Stealing DEQueue -- 16.5.3.Work Balancing -- 16.6.Chapter Notes -- 16.7.Exercises -- 17.Barriers -- 17.1.Introduction -- 17.2.Barrier Implementations -- 17.3.Sense-Reversing Barrier -- 17.4.Combining Tree Barrier -- 17.5.Static Tree Barrier -- 17.6.Termination Detecting Barriers -- 17.7.Chapter Notes --

Contents note continued: 17.8.Exercises -- 18.Transactional Memory -- 18.1.Introduction -- 18.1.1.What is Wrong with Locking? -- 18.1.2.What is Wrong with compareAndSet()? -- 18.1.3.What is Wrong with Compositionality? -- 18.1.4.What can We Do about It? -- 18.2.Transactions and Atomicity -- 18.3.Software Transactional Memory -- 18.3.1.Transactions and Transactional Threads -- 18.3.2.Zombies and Consistency -- 18.3.3.Atomic Objects -- 18.3.4.Dependent or Independent Progress? -- 18.3.5.Contention Managers -- 18.3.6.Implementing Atomic Objects -- 18.3.7.An Obstruction-Free Atomic Object -- 18.3.8.A Lock-Based Atomic Object -- 18.4.Hardware Transactional Memory -- 18.4.1.Cache Coherence -- 18.4.2.Transactional Cache Coherence -- 18.4.3.Enhancements -- 18.5.Chapter Notes -- 18.6.Exercises -- III.APPENDIX -- A.Software Basics -- A.1.Introduction -- A.2.Java -- A.2.1.Threads -- A.2.2.Monitors -- A.2.3.Yielding and Sleeping -- A.2.4.Thread-Local Objects -- A.3.C# -- A.3.1.Threads --

Contents note continued: A.3.2.Monitors -- A.3.3.Thread-Local Objects -- A.4.Pthreads -- A.4.1.Thread-Local Storage -- A.5.Chapter Notes -- B.Hardware Basics -- B.1.Introduction (and a Puzzle) -- B.2.Processors and Threads -- B.3.Interconnect -- B.4.Memory -- B.5.Caches -- B.5.1.Coherence -- B.5.2.Spinning -- B.6.Cache-Conscious Programming, or the Puzzle Solved -- B.7.Multi-Core and Multi-Threaded Architectures -- B.7.1.Relaxed Memory Consistency -- B.8.Hardware Synchronization Instructions -- B.9.Chapter Notes -- B.10.Exercises.