CONTENTS 4.4 Using synchronization of operations to simplify code 93 Functional programming with futures 93 Synchronizing operations with message passing 97 4.5 Summary 102 5 The C++memory model and operations on atomic types 103 5.1 Memory model basics 104 Objects and memory locations 104"Objects,memory locations, and concurrency 105.Modification orders 106 5.2 Atomic operations and types in C++107 The standard atomic types 107 Operations on std::atomic_flag 110"Operations on std::atomic<bool>112 Operations on std::atomic<T*>:pointer arithmetic 114 Operations on standard atomic integral types 116 The std::atomic<>primary class template 116 Free functions for atomic operations 117 5.3 Synchronizing operations and enforcing ordering 119 The synchronizes-with relationship 121The happens-before relationship 122Memory ordering for atomic operations 123 Release sequences and synchronizes-with 141"Fences 143 Ordering nonatomic operations with atomics 145 5.4 Summary 147 Designing lock-based concurrent data structures 148 6.1 What does it mean to design for concurrency?149 Guidelines for designing data structures for concurrency 149 6.2 Lock-based concurrent data structures 151 A thread-safe stack using locks 151"A thread-safe queue using locks and condition variables 154"A thread-safe queue using fine-grained locks and condition variables 158 6.3 Designing more complex lock-based data structures 169 Writing a thread-safe lookup table using locks 169"Writing a thread-safe list using locks 175 6.4 Summary 179 7 Designing lock-free concurrent data structures 180 7.1 Definitions and consequences 181 Types of nonblocking data structures 181"Lock-free data structures 182"Wait-free data structures 182 The pros and cons of lock-free data structures 183CONTENTS xi 4.4 Using synchronization of operations to simplify code 93 Functional programming with futures 93 ■ Synchronizing operations with message passing 97 4.5 Summary 102 5 The C++ memory model and operations on atomic types 103 5.1 Memory model basics 104 Objects and memory locations 104 ■ Objects, memory locations, and concurrency 105 ■ Modification orders 106 5.2 Atomic operations and types in C++ 107 The standard atomic types 107 ■ Operations on std::atomic_flag 110 ■ Operations on std::atomic<bool> 112 Operations on std::atomic<T*>: pointer arithmetic 114 Operations on standard atomic integral types 116 The std::atomic<> primary class template 116 ■ Free functions for atomic operations 117 5.3 Synchronizing operations and enforcing ordering 119 The synchronizes-with relationship 121 ■ The happens-before relationship 122 ■ Memory ordering for atomic operations 123 Release sequences and synchronizes-with 141 ■ Fences 143 Ordering nonatomic operations with atomics 145 5.4 Summary 147 6 Designing lock-based concurrent data structures 148 6.1 What does it mean to design for concurrency? 149 Guidelines for designing data structures for concurrency 149 6.2 Lock-based concurrent data structures 151 A thread-safe stack using locks 151 ■ A thread-safe queue using locks and condition variables 154 ■ A thread-safe queue using fine-grained locks and condition variables 158 6.3 Designing more complex lock-based data structures 169 Writing a thread-safe lookup table using locks 169 ■ Writing a thread-safe list using locks 175 6.4 Summary 179 7 Designing lock-free concurrent data structures 180 7.1 Definitions and consequences 181 Types of nonblocking data structures 181 ■ Lock-free data structures 182 ■ Wait-free data structures 182 The pros and cons of lock-free data structures 183