Concurrency with Modern C++

【实例截图】

【核心代码】

Contents
Reader Testimonials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Special Fonts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Special Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Special Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
Run the Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
How you should read the book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Personal Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
About Me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
My Special Circumstances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
A Quick Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Concurrency with Modern C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
C 11 and C 14: The Foundation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
C 17: Parallel Algorithms of the Standard Template Library . . . . . . . . . . . . . . . . . . 5
Execution Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
New Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
The Near Future: C 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
std::jthread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Atomic Smart Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Latches and Barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Calculating the Sum of a Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Thread-Safe Initialisation of a Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
CONTENTS
Ongoing Optimisation with CppMem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
The Future: C 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Executors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Extended futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Transactional Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Task Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Data-Parallel Vector Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Patterns and Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Concurrent Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Time Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
CppMem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
The Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Basics of the Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
What is a memory location? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
What happens if two threads access the same memory location? . . . . . . . . . . . . . 15
The Contract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
The Foundation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
The Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Atomics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Strong versus Weak Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
The Atomic Flag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
The Class Template std::atomic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
All Atomic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Free Atomic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
std::shared_ptr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
The Class Template std::atomic_ref (C 20) . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Specialisations of std::atomic_ref . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
The Synchronisation and Ordering Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 47
The Six Variants of Memory Orderings in C . . . . . . . . . . . . . . . . . . . . . . . . 47
Sequential Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Acquire-Release Semantic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
std::memory_order_consume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Relaxed Semantic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Fences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
CONTENTS
std::atomic_thread_fence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
std::atomic_signal_fence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Thread Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Thread Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Thread Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Shared Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Mutexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Thread-safe Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Thread-Local Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Condition Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
The Predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Lost Wakeup and Spurious Wakeup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
The Wait Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Tasks versus Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
std::async . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
std::packaged_task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
std::promise and std::future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
std::shared_future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Notifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Parallel Algorithms of the Standard Template Library . . . . . . . . . . . . . . . . . . . . . . . 161
Execution Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
Parallel and Vectorised Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Hazards of Data Races and Deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
The New Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
More overloads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
The functional Heritage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
The Near Future: C 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
A Cooperatively Interruptible Joining Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Automatically Joining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Interrupt a std::jthread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Stop Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Atomic Smart Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
CONTENTS
A thread-safe singly linked list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Latches and Barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
std::latch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
std::barrier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
A Generator Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
The Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
Calculating the Sum of a Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Single Threaded addition of a Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Multithreaded Summation with a Shared Variable . . . . . . . . . . . . . . . . . . . . . . 223
Thread-Local Summation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Summation of a Vector: The Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
Thread-Safe Initialisation of a Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Double-Checked Locking Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Performance Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Thread-Safe Meyers Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
std::lock_guard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
std::call_once with std::once_flag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Atomics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
Performance Numbers of the various Thread-Safe Singleton Implementations . . . . . 255
Ongoing Optimisation with CppMem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
CppMem: Non-Atomic Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
CppMem: Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
CppMem: Atomics with Sequential Consistency . . . . . . . . . . . . . . . . . . . . . . . 264
CppMem: Atomics with Acquire-Release Semantic . . . . . . . . . . . . . . . . . . . . . 272
CppMem: Atomics with Non-atomics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
CppMem: Atomics with Relaxed Semantic . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
The Future: C 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Executors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
A long Way . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
What is an Executor? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
First Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Goals of an Executor Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
Execution Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
A Prototype Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
Extended Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
CONTENTS
Concurrency TS v1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
Unified Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
Transactional Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
ACI(D) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Synchronized and Atomic Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
transaction_safe versus transaction_unsafe Code . . . . . . . . . . . . . . . . . . . . 308
Task Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Fork and Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
define_task_block versus define_task_block_restore_thread . . . . . . . . . . . . . 310
The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
The Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
Data-Parallel Vector Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
Data-Parallel Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
The Interface of the Data-Parallel Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Patterns and Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Invaluable Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Pattern versus Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Anti-Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Synchronisation Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
Dealing with Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
Copied Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
Thread-Specific Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
Dealing with Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
Scoped Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
Strategized Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
Thread-Safe Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Guarded Suspension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
Concurrent Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
Active Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
Further Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
Monitor Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
CONTENTS
Runtime behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
Further Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
Half-Sync/Half-Async . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
Reactor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
Proactor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
Further Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
Code Reviews . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
Minimise Sharing of Mutable Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
Minimise Waiting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
Prefer Immutable Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
Use pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
Look for the Right Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Use Static Code Analysis Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
Use Dynamic Enforcement Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Data Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
Condition Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
Promises and Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Don’t use volatile for synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Don’t program Lock Free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
If you program Lock-Free, use well-established patterns . . . . . . . . . . . . . . . . . . 410
Don’t build your abstraction, use guarantees of the language . . . . . . . . . . . . . . . 411
Don’t reinvent the wheel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
Lock-Based Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
General Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
Locking Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
Granularity of the Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
Typical Usage Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
Avoidance of Loopholes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
Contention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
CONTENTS
Concurrent Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
A Simplified Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
A Complete Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
Concurrent Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
Coarse-Grained Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
Fine-Grained Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
Lock-Free Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
Further Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
ABA Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
Blocking Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
Breaking of Program Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Data Races . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
Deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
False Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
Lifetime Issues of Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
Moving Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
Race Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
The Time Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
The Interplay of Time Point, Time Duration, and Clock . . . . . . . . . . . . . . . . . . . . . 481
Time Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
From Time Point to Calendar Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
Cross the valid Time Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
Time Duration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
Calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
Clocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
Accuracy and Steadiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
Epoch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
Sleep and Wait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
CppMem - An Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
The simplified Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
1. Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
2. Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
3. Display Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
4. Display Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
5. Model Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
The Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
CONTENTS
ACID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
CAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
Callable Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
Critical Section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
Eager Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
Executor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
Function Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
Lambda Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
Lazy evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
Lock-free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
Lost Wakeup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
Math Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
Memory Location . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
Modification Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
Monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
Non-blocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
Predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
RAII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
Release Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
Sequential Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
Sequence Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
Spurious Wakeup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
Total order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
TriviallyCopyable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
volatile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
wait-free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519