book

The Art of Multiprocessor Programming

by Maurice Herlihy, Nir Shavit

August 2011

Intermediate to advanced

528 pages

13h 45m

English

Morgan Kaufmann

Read now

Unlock full access

Copyright
Dedication
Acknowledgments
Preface
1. Introduction
1.1. Shared Objects and Synchronization1.2. A Fable1.2.1. Properties of Mutual Exclusion1.2.2. The Moral1.3. The Producer–Consumer Problem1.4. The Readers–Writers Problem1.5. The Harsh Realities of Parallelization1.6. Parallel Programming1.7. Chapter Notes1.8. Exercises
I. Principles
2. Mutual Exclusion
2.1. Time2.2. Critical Sections2.3. 2-Thread Solutions2.3.1. The LockOne Class2.3.2. The LockTwo Class2.3.3. The Peterson Lock2.4. The Filter Lock2.5. Fairness2.6. Lamport’s Bakery Algorithm2.7. Bounded Timestamps2.8. Lower Bounds on the Number of Locations2.9. Chapter Notes2.10. Exercises
3. Concurrent Objects
3.1. Concurrency and Correctness3.2. Sequential Objects3.3. Quiescent Consistency3.3.1. Remarks3.4. Sequential Consistency3.4.1. Remarks3.5. Linearizability3.5.1. Linearization Points3.5.2. Remarks3.6. Formal Definitions3.6.1. Linearizability3.6.2. Compositional Linearizability3.6.3. The Nonblocking Property3.7. Progress Conditions3.7.1. Dependent Progress Conditions3.8. The Java Memory Model3.8.1. Locks and Synchronized Blocks3.8.2. Volatile Fields3.8.3. Final Fields3.9. Remarks3.10. Chapter Notes3.11. Exercises
4. Foundations of Shared Memory
4.1. The Space of Registers4.2. Register Constructions4.2.1. MRSW Safe Registers4.2.2. A Regular Boolean MRSW Register4.2.3. A Regular M-Valued MRSW Register4.2.4. An Atomic SRSW Register4.2.5. An Atomic MRSW Register4.2.6. An Atomic MRMW Register4.3. Atomic Snapshots4.3.1. An Obstruction-Free Snapshot4.3.2. A Wait-Free Snapshot4.3.3. Correctness Arguments4.4. Chapter Notes4.5. Exercises
5. The Relative Power of Primitive Synchronization Operations
5.1. Consensus Numbers5.1.1. States and Valence5.2. Atomic Registers5.3. Consensus Protocols5.4. FIFO Queues5.5. Multiple Assignment Objects5.6. Read–Modify–Write Operations5.7. Common2 RMW Operations5.8. The compareAndSet() Operation5.9. Chapter Notes5.10. Exercises

6. Universality of Consensus
6.1. Introduction6.2. Universality6.3. A Lock-Free Universal Construction6.4. A Wait-Free Universal Construction6.5. Chapter Notes6.6. Exercises
II. Practice
7. Spin Locks and Contention
7.1. Welcome to the Real World7.2. Test-And-Set Locks7.3. TAS-Based Spin Locks Revisited7.4. Exponential Backoff7.5. Queue Locks7.5.1. Array-Based Locks7.5.2. The CLH Queue Lock7.5.3. The MCS Queue Lock7.6. A Queue Lock with Timeouts7.7. A Composite Lock7.7.1. A Fast-Path Composite Lock7.8. Hierarchical Locks7.8.1. A Hierarchical Backoff Lock7.8.2. A Hierarchical CLH Queue Lock7.9. One Lock To Rule Them All7.10. Chapter Notes7.11. Exercises
8. Monitors and Blocking Synchronization
8.1. Introduction8.2. Monitor Locks and Conditions8.2.1. Conditions8.2.2. The Lost-Wakeup Problem8.3. Readers–Writers Locks8.3.1. Simple Readers–Writers Lock8.3.2. Fair Readers–Writers Lock8.4. Our Own Reentrant Lock8.5. Semaphores8.6. Chapter Notes8.7. Exercises
9. Linked Lists: The Role of Locking
9.1. Introduction9.2. List-Based Sets9.3. Concurrent Reasoning9.4. Coarse-Grained Synchronization9.5. Fine-Grained Synchronization9.6. Optimistic Synchronization9.7. Lazy Synchronization9.8. Non-Blocking Synchronization9.9. Discussion9.10. Chapter Notes9.11. Exercises
10. Concurrent Queues and the ABA Problem
10.1. Introduction10.2. Queues10.3. A Bounded Partial Queue10.4. An Unbounded Total Queue10.5. An Unbounded Lock-Free Queue10.6. Memory Reclamation and the ABA Problem10.6.1. A Naïve Synchronous Queue10.7. Dual Data Structures10.8. Chapter Notes10.9. Exercises
11. Concurrent Stacks and Elimination
11.1. Introduction11.2. An Unbounded Lock-Free Stack11.3. Elimination11.4. The Elimination Backoff Stack11.4.1. A Lock-Free Exchanger11.4.2. The Elimination Array11.5. Chapter Notes11.6. Exercises
12. Counting, Sorting, and Distributed Coordination
12.1. Introduction12.2. Shared Counting12.3. Software Combining12.3.1. OverviewIDLEFIRSTROOT12.3.2. An Extended Example12.3.3. Performance and Robustness12.4. Quiescently Consistent Pools and Counters12.5. Counting Networks12.5.1. Networks That Count12.5.2. The Bitonic Counting NetworkA Software Bitonic Counting NetworkProof of CorrectnessA Periodic Counting NetworkA Software Periodic Counting Network12.5.3. Performance and Pipelining12.6. Diffracting Trees12.7. Parallel Sorting12.8. Sorting Networks12.8.1. Designing a Sorting NetworkA Bitonic Sorting Algorithm12.9. Sample Sorting12.10. Distributed Coordination12.11. Chapter Notes12.12. Exercises
13. Concurrent Hashing and Natural Parallelism
13.1. Introduction13.2. Closed-Address Hash Sets13.2.1. A Coarse-Grained Hash Set13.2.2. A Striped Hash Set13.2.3. A Refinable Hash Set13.3. A Lock-Free Hash Set13.3.1. Recursive Split-Ordering13.3.2. The BucketList Class13.3.3. The LockFreeHashSet<T> Class13.4. An Open-Addressed Hash Set13.4.1. Cuckoo Hashing13.4.2. Concurrent Cuckoo Hashing13.4.3. Striped Concurrent Cuckoo Hashing13.4.4. A Refinable Concurrent Cuckoo Hash Set13.5. Chapter Notes13.6. Exercises
14. Skiplists and Balanced Search
14.1. Introduction14.2. Sequential Skiplists14.3. A Lock-Based Concurrent Skiplist14.3.1. A Bird’s-Eye View14.3.2. The Algorithm14.4. A Lock-Free Concurrent Skiplist14.4.1. A Bird’s-Eye View14.4.2. The Algorithm in Detail14.5. Concurrent Skiplists14.6. Chapter Notes14.7. Exercises
15. Priority Queues
15.1. Introduction15.1.1. Concurrent Priority Queues15.2. An Array-Based Bounded Priority Queue15.3. A Tree-Based Bounded Priority Queue15.4. An Unbounded Heap-Based Priority Queue15.4.1. A Sequential Heap15.4.2. A Concurrent HeapBird’s-Eye ViewIn Detail15.5. A Skiplist-Based Unbounded Priority Queue15.6. Chapter Notes15.7. Exercises
16. Futures, Scheduling, and Work Distribution
16.1. Introduction16.2. Analyzing Parallelism16.3. Realistic Multiprocessor Scheduling16.4. Work Distribution16.4.1. Work Stealing16.4.2. Yielding and Multiprogramming16.5. Work-Stealing Dequeues16.5.1. A Bounded Work-Stealing Dequeue16.5.2. An Unbounded Work-Stealing DEQueue16.5.3. Work Balancing16.6. Chapter Notes16.7. Exercises
17. Barriers
17.1. Introduction17.2. Barrier Implementations17.3. Sense-Reversing Barrier17.4. Combining Tree Barrier17.5. Static Tree Barrier17.6. Termination Detecting Barriers17.7. Chapter Notes17.8. Exercises
18. Transactional Memory
18.1. Introduction18.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 Atomicity18.3. Software Transactional Memory18.3.1. Transactions and Transactional Threads18.3.2. Zombies and Consistency18.3.3. Atomic Objects18.3.4. Dependent or Independent Progress?18.3.5. Contention Managers18.3.6. Implementing Atomic Objects18.3.7. An Obstruction-Free Atomic ObjectBird’s-Eye ViewWhy It WorksIn Detail18.3.8. A Lock-Based Atomic ObjectBird’s-Eye ViewWhy It WorksIn Detail18.4. Hardware Transactional Memory18.4.1. Cache Coherence18.4.2. Transactional Cache Coherence18.4.3. Enhancements18.5. Chapter Notes18.6. Exercises
III. Appendix
A. Software Basics
A.1. IntroductionA.2. JavaA.2.1. ThreadsA.2.2. MonitorsA.2.3. Yielding and SleepingA.2.4. Thread-Local ObjectsA.3. C#A.3.1. ThreadsA.3.2. MonitorsA.3.3. Thread-Local ObjectsA.4. PthreadsA.4.1. Thread-Local StorageA.5. Chapter Notes
B. Hardware Basics
B.1. Introduction (and a Puzzle)B.2. Processors and ThreadsB.3. InterconnectB.4. MemoryB.5. CachesB.5.1. CoherenceB.5.2. SpinningB.6. Cache-Conscious Programming, or the Puzzle SolvedB.7. Multi-Core and Multi-Threaded ArchitecturesB.7.1. Relaxed Memory ConsistencyB.8. Hardware Synchronization InstructionsB.9. Chapter NotesB.10. Exercises
Bibliography

Content preview from The Art of Multiprocessor Programming

Chapter 14. Skiplists and Balanced Search

Introduction

We have seen several concurrent implementations of sets based on linked lists and on hash tables. We now turn our attention to concurrent search structures with logarithmic depth. There are many concurrent logarithmic search structures in the literature. Here, we are interested in search structures intended for in-memory data, as opposed to data residing on outside storage such as disks.

Many popular sequential search structures, such as red-black trees or AVL-trees, require periodic rebalancing to maintain the structure’s logarithmic depth. Rebalancing works well for sequential tree-based search structures, but for concurrent structures, rebalancing may cause bottlenecks and contention. Instead, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

The Art of Multiprocessor Programming, Revised Reprint

Publisher Resources

ISBN: 9780123705914

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

The Art of Multiprocessor Programming

by Maurice Herlihy, Nir Shavit

Chapter 14. Skiplists and Balanced Search

Introduction

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.