C++ Concurrency in Action

Introduction......Page 4
1.1.1 Concurrency in Computer Systems......Page 5
1.1.2 Approaches to Concurrency......Page 7
1.2.1 Using Concurrency for Separation of Concerns......Page 10
1.2.2 Using Concurrency for Performance......Page 11
1.2.3 When Not to use Concurrency......Page 12
1.3.1 History of multi-threading in C++......Page 13
1.3.2 Concurrency Support in the New Standard......Page 14
1.3.3 Efficiency in the C++ Thread Library......Page 15
1.4 Getting Started......Page 16
1.4.1 Hello Concurrent World......Page 17
1.5 Summary......Page 18
2.1.1 Launching a Thread......Page 19
2.1.2 Waiting for a Thread to Complete......Page 21
2.1.3 Running Threads in the Background......Page 24
2.2 Passing Arguments to a Thread Function......Page 26
2.3 Transferring Ownership of a Thread......Page 29
2.4 Choosing the Number of Threads at Runtime......Page 32
2.5 Identifying Threads......Page 35
2.6 Summary......Page 36
3.1 Problems with Sharing Data Between Threads......Page 38
3.1.1 Race Conditions......Page 41
3.2 Protecting Shared Data with Mutexes......Page 42
3.2.1 Using Mutexes in C++......Page 43
3.2.2 Structuring Code For Protecting Shared Data......Page 44
3.2.3 Spotting Race Conditions Inherent in Interfaces......Page 46
3.2.4 Deadlock: the Problem and a Solution......Page 54
3.2.5 Further Guidelines for Avoiding Deadlock......Page 56
3.2.6 Flexible Locking with std::unique_lock......Page 61
3.2.7 Transferring Mutex Ownership Between Scopes......Page 63
3.2.8 Locking at an Appropriate Granularity......Page 64
3.3.1 Protecting Shared Data During Initialization......Page 67
3.3.2 Protecting Rarely-Updated Data Structures......Page 71
3.4 Summary......Page 73
4.1 Waiting for an Event or other Condition......Page 74
4.1.1 Waiting for a Condition with Condition Variables......Page 76
4.1.2 Building a Thread-safe Queue with Condition Variables......Page 78
4.2 Waiting for One-off Events with Futures......Page 83
Packaged Tasks......Page 85
4.2.1 Associating a Task with a Future......Page 86
4.2.2 Making (std::)Promises......Page 87
4.2.3 Saving an Exception for the Future......Page 89
4.3 Using Synchronization of Operations to Simplify Code......Page 90
4.3.1 Functional Programming with Futures......Page 91
4.3.2 Synchronizing Operations with Message Passing......Page 93
4.4 Summary......Page 97
The C++ Memory Model and Operations on Atomic Types......Page 98
5.1.1 Objects and Memory Locations......Page 99
5.1.2 Objects, memory locations and concurrency......Page 100
5.2 Atomic Operations and Types in C++......Page 101
5.2.1 The Standard Atomic Types......Page 102
5.2.2 Operations on std::atomic_flag......Page 106
5.2.3 Operations on std::atomic_bool......Page 107
5.2.4 Operations on std::atomic_address......Page 110
5.2.5 Operations on Standard Atomic Integral Types......Page 111
5.2.6 The std::atomic class template......Page 112
5.2.7 Free functions for atomic operations......Page 113
5.3 Synchronizing Operations and Enforcing Ordering with Atomic Types......Page 115
5.3.1 The synchronizes-with relation......Page 117
5.3.2 The happens-before relation......Page 118
5.3.3 Memory Ordering for Atomic Operations......Page 119
5.3.4 Release Sequences and synchronizes-with......Page 135
5.3.5 Fences......Page 138
5.3.6 Ordering non-atomic operations with atomics......Page 140
5.4 Summary......Page 142
Designing Data Structures for Concurrency I: Lock-based Data Structures......Page 144
6.1.1 Guidelines for Designing Data Structures for Concurrency......Page 145
6.2.1 A Thread-safe Stack using Locks......Page 147
6.2.2 A Thread-Safe Queue Using Locks and Condition Variables......Page 150
6.2.3 A Thread-Safe Queue Using Fine-grained Locks and Condition Variables......Page 155
6.3.1 Writing a thread-safe Lookup Table Using Locks......Page 168
6.3.2 Writing a Thread-Safe List Using Locks......Page 174
6.4 Summary......Page 178
Designing Data Structures for Concurrency II: Lock-free Concurrent Data Structures......Page 179
7.1 The Pros and Cons of Lock-free Data Structures......Page 180
7.2.1 Writing a Thread-safe Stack without Locks......Page 181
7.2.2 Stopping those pesky leaks: managing memory in lock-free data structures......Page 185
7.2.3 Detecting nodes that can't be reclaimed using hazard pointers......Page 188
7.2.4 Detecting Nodes in Use with Reference Counting......Page 196
7.2.5 Applying the memory model to our lock-free stack......Page 201
7.2.6 Writing a thread-safe queue without locks......Page 206
7.3 Guidelines For Writing Lock-free Data Structures......Page 219
7.3.3 Guideline: Identify busy-wait loops and ?help? the other thread......Page 220
7.4 Summary......Page 221
8.1 Techniques for Dividing Work Between Threads......Page 222
8.1.1 Dividing Data Between Threads Before Processing Begins......Page 223
8.1.2 Dividing Data Recursively......Page 225
8.1.3 Dividing Work By Task Type......Page 229
8.2 Factors Affecting the Performance of Concurrent Code......Page 232
8.2.1 How many processors?......Page 233
8.2.2 Data Contention and Cache Ping Pong......Page 234
8.2.4 How Close is My Data?......Page 236
8.2.5 Over-subscription and Excessive Task Switching......Page 237
8.3.1 Dividing Array Elements for Complex Operations......Page 238
8.3.2 Data Access Patterns in Other Data Structures......Page 241
8.4 Additional Considerations when Designing Code for Concurrency......Page 242
8.4.1 Exception Safety in Parallel Algorithms......Page 243
8.4.2 Scalability and Amdahl's Law......Page 249
8.4.3 Hiding Latency with Multiple Threads......Page 251
8.4.4 Improving Responsiveness with Concurrency......Page 252
8.5.1 A parallel implementation of std::for_each......Page 254
8.5.2 A parallel implementation of std::find......Page 256
8.5.3 A parallel implementation of std::partial_sum......Page 260
8.6 Summary......Page 270
9.1 Thread Pools......Page 271
9.1.1 The Simplest Possible Thread Pool......Page 272
9.1.2 Waiting for Tasks Submitted to a Thread Pool......Page 274
9.1.3 Tasks that Wait for Other Tasks......Page 277
9.1.4 Avoiding Contention on the Work Queue......Page 280
9.1.5 Work-Stealing......Page 282
9.2 Interrupting Threads......Page 287
9.2.1 Launching and Interrupting Another Thread......Page 288
9.2.3 Interrupting a Condition Variable Wait......Page 290
9.2.4 Interrupting a Wait on std::condition_variable_any......Page 294
9.2.5 Interrupting other Blocking Calls......Page 296
9.2.6 Handling Interruptions......Page 297
9.2.7 Interrupting Background Tasks on Application Exit......Page 298
9.3 Summary......Page 300
10.1 Types of Concurrency-related Bugs......Page 301
10.1.2 Race Conditions......Page 302
10.2.1 Reviewing Code to Locate Potential Bugs......Page 304
10.2.2 Locating concurrency-related bugs by testing......Page 306
10.2.3 Designing for Testability......Page 308
10.2.4 Multi-threaded testing techniques......Page 309
10.3 Summary......Page 312
A.1 Rvalue References......Page 313
A.1.1 Move semantics......Page 314
A.2 Deleted Functions......Page 317
A.3 Defaulted Functions......Page 319
A.4 constexpr functions......Page 322
A.4.1 constexpr and user-defined types......Page 324
A.4.2 constexpr objects......Page 326
A.4.3 constexpr function requirements......Page 327
A.5 Lambda Functions......Page 328
A.5.1 Lambda functions that reference local variables......Page 330
A.6 Variadic Templates......Page 333
A.6.1 Expanding the parameter pack......Page 334
A.7 Summary......Page 337