bca0●o0aoa0gg ++ Concurrency IN ACTION Practical Multithreading Anthony Williams MANNING
MANNING Anthony Williams Practical Multithreading IN ACTION
brief contents 1■Hello,.world of concurrency in C+！1 2·Managing threads 15 3Sharing data between threads 33 4Synchronizing concurrent operations 67 5The C++memory model and operations on atomic types 103 6Designing lock-based concurrent data structures 148 7Designing lock-free concurrent data structures 180 8Designing concurrent code 224 9Advanced thread management 273 10Testing and debugging multithreaded applications 300 vii
vii brief contents 1 ■ Hello, world of concurrency in C++! 1 2 ■ Managing threads 15 3 ■ Sharing data between threads 33 4 ■ Synchronizing concurrent operations 67 5 ■ The C++ memory model and operations on atomic types 103 6 ■ Designing lock-based concurrent data structures 148 7 ■ Designing lock-free concurrent data structures 180 8 ■ Designing concurrent code 224 9 ■ Advanced thread management 273 10 ■ Testing and debugging multithreaded applications 300
contents preface xv acknowledgments xvii about this book xix about the cover illustration xxii Hello,world of concurrency in C++!I 1.1 What is concurrency?2 Concurrency in computer systems 2 Approaches to concurrency 4 1.2 Why use concurrency?6 Using concurrency for separation of concerns 6 Using concurrency for performance 7.When not to use concurrency 8 1.3 Concurrency and multithreading in C++9 History of multithreading in C++10.Concurrency support in the new standard 10"Efficiency in the C++ Thread Library 11 Platform-specific facilities 12 1.4 Getting started 13 Hello,Concurrent World 13 1.5 Summary 14 ix
ix contents preface xv acknowledgments xvii about this book xix about the cover illustration xxii 1 Hello, world of concurrency in C++! 1 1.1 What is concurrency? 2 Concurrency in computer systems 2 Approaches to concurrency 4 1.2 Why use concurrency? 6 Using concurrency for separation of concerns 6 Using concurrency for performance 7 ■ When not to use concurrency 8 1.3 Concurrency and multithreading in C++ 9 History of multithreading in C++ 10 ■ Concurrency support in the new standard 10 ■ Efficiency in the C++ Thread Library 11 ■ Platform-specific facilities 12 1.4 Getting started 13 Hello, Concurrent World 13 1.5 Summary 14
CONTENTS 2 Managing threads 15 2.1 Basic thread management 16 Launching a thread 16"Waiting for a thread to complete 18 Waiting in exceptional circumstances 19"Running threads in the background 21 2.2 Passing arguments to a thread function 23 2.3 Transferring ownership of a thread 25 2.4 Choosing the number of threads at runtime 28 2.5 Identifying threads 31 2.6 Summary 32 3 Sharing data between threads 33 3.1 Problems with sharing data between threads 34 Race conditions 35"Avoiding problematic race conditions 36 3.2 Protecting shared data with mutexes 37 Using mutexes in C++38"Structuring code for protecting shared data 39 Spotting race conditions inherent in interfaces 40"Deadlock:the problem and a solution 47 Further guidelines for avoiding deadlock 49 Flexible locking with std::unique lock 54Transferring mutex ownership between scopes 55"Locking at an appropriate granularity 57 3.3 Alternative facilities for protecting shared data 59 Protecting shared data during initialization 59 Protecting rarely updated data structures 63"Recursive locking 64 3.4 Summary 65 4 Synchronizing concurrent operations 67 4.1 Waiting for an event or other condition 68 Waiting for a condition with condition variables 69 Building a thread-safe queue with condition variables 71 4.2 Waiting for one-off events with futures 76 Returning values from background tasks 77 Associating a task with a future 79.Making (std::)promises 81.Saving an exception for the future 83"Waiting from multiple threads 85 4.3 Waiting with a time limit 87 Clocks87·Durations88·Time points89 Functions that accept timeouts 91
x CONTENTS 2 Managing threads 15 2.1 Basic thread management 16 Launching a thread 16 ■ Waiting for a thread to complete 18 Waiting in exceptional circumstances 19 ■ Running threads in the background 21 2.2 Passing arguments to a thread function 23 2.3 Transferring ownership of a thread 25 2.4 Choosing the number of threads at runtime 28 2.5 Identifying threads 31 2.6 Summary 32 3 Sharing data between threads 33 3.1 Problems with sharing data between threads 34 Race conditions 35 ■ Avoiding problematic race conditions 36 3.2 Protecting shared data with mutexes 37 Using mutexes in C++ 38 ■ Structuring code for protecting shared data 39 ■ Spotting race conditions inherent in interfaces 40 ■ Deadlock: the problem and a solution 47 Further guidelines for avoiding deadlock 49 ■ Flexible locking with std::unique_lock 54 ■ Transferring mutex ownership between scopes 55 ■ Locking at an appropriate granularity 57 3.3 Alternative facilities for protecting shared data 59 Protecting shared data during initialization 59 ■ Protecting rarely updated data structures 63 ■ Recursive locking 64 3.4 Summary 65 4 Synchronizing concurrent operations 67 4.1 Waiting for an event or other condition 68 Waiting for a condition with condition variables 69 Building a thread-safe queue with condition variables 71 4.2 Waiting for one-off events with futures 76 Returning values from background tasks 77 ■ Associating a task with a future 79 ■ Making (std::)promises 81 ■ Saving an exception for the future 83 ■ Waiting from multiple threads 85 4.3 Waiting with a time limit 87 Clocks 87 ■ Durations 88 ■ Time points 89 Functions that accept timeouts 91
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 183
CONTENTS 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