Preface                                            xv
Acknowledgments                                    xvii
About This Book                                    xix
About The Cover Illustration                       xxii
1 Hello, World Of Concurrency In C++!              1   (14)
  1.1 What is concurrency?                         2   (4)
    Concurrency in computer systems                2   (2)
    Approaches to concurrency                      4   (2)
  1.2 Why use concurrency?                         6   (3)
    Using concurrency for separation of concerns   6   (1)
    Using concurrency for performance              7   (1)
    When not to use concurrency                    8   (1)
  1.3 Concurrency and multithreading in C++        9   (4)
    History of multithreading in C++               10  (1)
    Concurrency support in the new standard        10  (1)
    Efficiency in the C++ Thread Library           11  (1)
    Platform-specific facilities                   12  (1)
  1.4 Getting started                              13  (1)
    Hello, Concurrent World                        13  (1)
  1.5 Summary                                      14  (1)
2 Managing threads                                 15  (18)
  2.1 Basic thread management                      16  (7)
    Launching a thread                             16  (2)
    Waiting for a thread to complete               18  (1)
    Waiting in exceptional circumstances           19  (2)
    Running threads in the background              21  (2)
  2.2 Passing arguments to a thread function       23  (2)
  2.3 Transferring ownership of a thread           25  (3)
  2.4 Choosing the number of threads at runtime    28  (3)
  2.5 Identifying threads                          31  (1)
  2.6 Summary                                      32  (1)
3 Sharing data between threads                     33  (34)
  3.1 Problems with sharing data between threads   34  (3)
    Race conditions                                35  (1)
    Avoiding problematic race conditions           36  (1)
  3.2 Protecting shared data with mutexes          37  (22)
    Using mutexes in C++                           38  (1)
    Structuring code for protecting shared data    39  (1)
    Spotting race conditions inherent in           40  (7)
    interfaces
    Deadlock: the problem and a solution           47  (2)
    Further guidelines for avoiding deadlock       49  (5)
    Flexible locking with std:: unique lock        54  (1)
    Transferring mutex ownership between scopes    55  (2)
    Locking at an appropriate granularity          57  (2)
  3.3 Alternative facilities for protecting        59  (6)
  shared data
    Protecting shared data during initialization   59  (4)
    Protecting rarely updated data structures      63  (1)
    Recursive locking                              64  (1)
  3.4 Summary                                      65  (2)
4 Synchronizing concurrent operations              67  (36)
  4.1 Waiting for an event or other condition      68  (8)
    Waiting for a condition with condition         69  (2)
    variables
    Building a thread-safe queue with condition    71  (5)
    variables
  4.2 Waiting for one-off events with futures      76  (11)
    Returning values from background tasks         77  (2)
    Associating a task with a future               79  (2)
    Making (std::)promises                         81  (2)
    Saving an exception for the future             83  (2)
    Waiting from multiple threads                  85  (2)
  4.3 Waiting with a time limit                    87  (6)
    Clocks                                         87  (1)
    Durations                                      88  (1)
    Time points                                    89  (2)
    Functions that accept timeouts                 91  (2)
  4.4 Using synchronization of operations to       93  (9)
  simplify code
    Functional programming with futures            93  (4)
    Synchronizing operations with message          97  (5)
    passing
  4.5 Summary                                      102 (1)
5 The C++ memory model and operations on atomic    103 (45)
types
  5.1 Memory model basics                          104 (3)
    Objects and memory locations                   104 (1)
    Objects, memory locations, and concurrency     105 (1)
    Modification orders                            106 (1)
  5.2 Atomic operations and types in C++           107 (12)
    The standard atomic types                      107 (3)
    Operations on std::atomic_flag                 110 (2)
    Operations on std::atomic<bool>          112 (2)
    Operations on std::atomic<T>: pointer    114 (2)
    arithmetic
    Operations on standard atomic integral types   116 (1)
    The std::atomic<> primary class          116 (1)
    template
    Free functions for atomic operations           117 (2)
  5.3 Synchronizing operations and enforcing       119 (28)
  ordering
    The synchronizes-with relationship             121 (1)
    The happens-before relationship                122 (1)
    Memory ordering for atomic operations          123 (18)
    Release sequences and synchronizes-with        141 (2)
    Fences                                         143 (2)
    Ordering nonatomic operations with atomics     145 (2)
  5.4 Summary                                      147 (1)
6 Designing lock-based concurrent data             148 (32)
structures
  6.1 What does it mean to design for              149 (2)
  concurrency?
    Guidelines for designing data structures       149 (2)
    for concurrency
  6.2 Lock-based concurrent data structures        151 (18)
    A thread-safe stack using locks                151 (3)
    A thread-safe queue using locks and            154 (4)
    condition variables
    A thread-safe queue using fine-grained         158 (11)
    locks and condition variables
  6.3 Designing more complex lock-based data       169 (10)
  structures
    Writing a thread-safe lookup table using       169 (6)
    locks
    Writing a thread-safe list using locks         175 (4)
  6.4 Summary                                      179 (1)
7 Designing lock-free concurrent data structures   180 (44)
  7.1 Definitions and consequences                 181 (3)
    Types of nonblocking data structures           181 (1)
    Lock-free data structures                      182 (1)
    Wait-free data structures                      182 (1)
    The pros and cons of lock-free data            183 (1)
    structures
  7.2 Examples of lock-free data structures        184 (37)
    Writing a thread-safe stack without locks      184 (4)
    Stopping those pesky leaks: managing memory    188 (5)
    in lock-free data structures
    Detecting nodes that can't be reclaimed        193 (7)
    using hazard pointers
    Detecting nodes in use with reference          200 (5)
    counting
    Applying the memory model to the lock-free     205 (4)
    stack
    Writing a thread-safe queue without locks      209 (12)
  7.3 Guidelines for writing lock-free data        221 (2)
  structures
    Guideline: use std::memory_order_seq_cst       221 (1)
    for prototyping
    Guideline: use a lock-free memory              221 (1)
    reclamation scheme
    Guideline: watch out for the ABA problem       222 (1)
    Guideline: identify busy-wait loops and        222 (1)
    help the other thread
  7.4 Summary                                      223 (1)
8 Designing concurrent code                        224 (49)
  8.1 Techniques for dividing work between         225 (8)
  threads
    Dividing data between threads before           226 (1)
    processing begins
    Dividing data recursively                      227 (4)
    Dividing work by task type                     231 (2)
  8.2 Factors affecting the performance of         233 (6)
  concurrent code
    How many processors?                           234 (1)
    Data contention and cache ping-long            235 (2)
    False sharing                                  237 (1)
    How close is your data?                        238 (1)
    Oversubscription and excessive task            239 (1)
    switching
  8.3 Designing data structures for                239 (4)
  multithreaded performance
    Dividing array elements for complex            240 (2)
    operations
    Data access patterns in other data             242 (1)
    structures
  8.4 Additional considerations when designing     243 (12)
  for concurrency
    Exception safety in parallel algorithms        243 (7)
    Scalability and Amdahl's law                   250 (2)
    Hiding latency with multiple threads           252 (1)
    Improving responsiveness with concurrency      253 (2)
  8.5 Designing concurrent code in practice        255 (17)
    A parallel implementation of std: for each     255 (2)
    A parallel implementation of std: find         257 (6)
    A parallel implementation of std::partial      263 (9)
    sum
  8.6 Summary                                      272 (1)
9 Advanced thread management                       273 (27)
  9.1 Thread pools                                 274 (15)
    The simplest possible thread pool              274 (2)
    Waiting for tasks submitted to a thread pool   276 (4)
    Tasks that wait for other tasks                280 (3)
    Avoiding contention on the work queue          283 (1)
    Work stealing                                  284 (5)
  9.2 Interrupting threads                         289 (10)
    Launching and interrupting another thread      289 (2)
    Detecting that a thread has been interrupted   291 (1)
    Interrupting a condition variable wait         291 (3)
    Interrupting a wait on                         294 (2)
    std::condition_variable_any
    Interrupting other blocking calls              296 (1)
    Handling interruptions                         297 (1)
    Interrupting background tasks on               298 (1)
    application exit
  9.3 Summary                                      299 (1)
10 Testing and debugging multithreaded             300 (15)
applications
  10.1 Types of concurrency-related bugs           301 (2)
    Unwanted blocking                              301 (1)
    Race conditions                                302 (1)
  10.2 Techniques for locating                     303 (11)
  concurrency-related bugs
    Reviewing code to locate potential bugs        303 (2)
    Locating concurrency-related bugs by testing   305 (2)
    Designing for testability                      307 (1)
    Multithreaded testing techniques               308 (3)
    Structuring multithreaded test code            311 (3)
    Testing the performance of multithreaded       314 (1)
    code
  10.3 Summary                                     314 (1)
Appendix A Brief reference for some C++11          315 (25)
language features
Appendix B Brief comparison of concurrency         340 (2)
libraries
Appendix C A message-passing framework and         342 (18)
complete ATM example
Appendix D C++ Thread Library reference            360 (127)
Resources                                          487 (2)
Index                                              489