C++ Concurrency in Action (Anthony Williams) (Z-Library)

📄 File Format: PDF

💾 File Size: 6.5 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

M A N N I N G SECOND EDITION Anthony Williams IN ACTION

📄 Page 2

Praise for the first edition “It’s not just the best current treatment of C++11’s threading facilities ... it’s likely to remain the best for some time to come.” —Scott Meyers, author of Effective C++ and More Effective C++ “Simplifies the dark art of C++ multithreading.” —Rick Wagner, Red Hat “Reading this made my brain hurt. But it’s a good hurt.” —Joshua Heyer, Ingersoll Rand “Anthony shows how to put concurrency into practice.” —Roger Orr, OR/2 Limited “A thoughtful, in-depth guide to the new concurrency standard for C++ straight from the mouth of one the horses.” —Neil Horlock, Director, Credit Suisse “Any serious C++ developers should understand the contents of this important book.” —Dr. Jamie Allsop, Development Director

📄 Page 3

(This page has no text content)

📄 Page 4

C++ Concurrency in Action Second Edition ANTHONY WILLIAMS M A N N I N G SHELTER ISLAND

📄 Page 5

For online information and ordering of this and other Manning books, please visit www.manning.com. The publisher offers discounts on this book when ordered in quantity. For more information, please contact Special Sales Department Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 Email: orders@manning.com ©2019 by Manning Publications Co. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps. Recognizing the importance of preserving what has been written, it is Manning’s policy to have the books we publish printed on acid-free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine. Manning Publications Co. Development editors: Cynthia Kane, Jennifer Stout 20 Baldwin Road Technical development editor: Alain Couniot PO Box 761 Review editor: Aleksandar Dragosavljević Shelter Island, NY 11964 Production editor: Janet Vail Copy editors: Safis Editing, Heidi Ward Proofreader: Melody Dolab Technical proofreader: Frédéric Flayol Typesetter: Dennis Dalinnik Cover designer: Marija Tudor ISBN: 9781617294693 Printed in the United States of America 1 2 3 4 5 6 7 8 9 10 – SP – 24 23 22 21 20 19

📄 Page 6

To Kim, Hugh, and Erin

📄 Page 7

vi brief contents 1 ■ Hello, world of concurrency in C++! 1 2 ■ Managing threads 16 3 ■ Sharing data between threads 36 4 ■ Synchronizing concurrent operations 72 5 ■ The C++ memory model and operations on atomic types 124 6 ■ Designing lock-based concurrent data structures 173 7 ■ Designing lock-free concurrent data structures 205 8 ■ Designing concurrent code 251 9 ■ Advanced thread management 300 10 ■ Parallel algorithms 327 11 ■ Testing and debugging multithreaded applications 339

📄 Page 8

contents preface xiii acknowledgments xv about this book xvii about the author xx about the cover illustration xxi 1 Hello, world of concurrency in C++! 1 1.1 What is concurrency? 2 Concurrency in computer systems 2 ■ Approaches to concurrency 4 ■ Concurrency vs. parallelism 6 1.2 Why use concurrency? 7 Using concurrency for separation of concerns 7 ■ Using concurrency for performance: task and data parallelism 8 When not to use concurrency 9 1.3 Concurrency and multithreading in C++ 10 History of multithreading in C++ 10 ■ Concurrency support in the C++11 standard 11 ■ More support for concurrency and parallelism in C++14 and C++17 12 ■ Efficiency in the C++ Thread Library 12 ■ Platform-specific facilities 13 1.4 Getting started 13 Hello, Concurrent World 14vii

📄 Page 9

CONTENTSviii2 Managing threads 16 2.1 Basic thread management 17 Launching a thread 17 ■ Waiting for a thread to complete 20 Waiting in exceptional circumstances 20 ■ Running threads in the background 22 2.2 Passing arguments to a thread function 24 2.3 Transferring ownership of a thread 27 2.4 Choosing the number of threads at runtime 31 2.5 Identifying threads 34 3 Sharing data between threads 36 3.1 Problems with sharing data between threads 37 Race conditions 38 ■ Avoiding problematic race conditions 39 3.2 Protecting shared data with mutexes 40 Using mutexes in C++ 41 ■ Structuring code for protecting shared data 42 ■ Spotting race conditions inherent in interfaces 44 Deadlock: the problem and a solution 51 ■ Further guidelines for avoiding deadlock 53 ■ Flexible locking with std::unique_lock 59 ■ Transferring mutex ownership between scopes 61 ■ Locking at an appropriate granularity 62 3.3 Alternative facilities for protecting shared data 64 Protecting shared data during initialization 65 ■ Protecting rarely updated data structures 68 ■ Recursive locking 70 4 Synchronizing concurrent operations 72 4.1 Waiting for an event or other condition 73 Waiting for a condition with condition variables 74 Building a thread-safe queue with condition variables 76 4.2 Waiting for one-off events with futures 81 Returning values from background tasks 82 ■ Associating a task with a future 84 ■ Making (std::)promises 87 ■ Saving an exception for the future 89 ■ Waiting from multiple threads 90 4.3 Waiting with a time limit 93 Clocks 93 ■ Durations 94 ■ Time points 96 ■ Functions that accept timeouts 98

📄 Page 10

CONTENTS ix4.4 Using synchronization of operations to simplify code 99 Functional programming with futures 99 ■ Synchronizing operations with message passing 104 ■ Continuation-style concurrency with the Concurrency TS 108 ■ Chaining continuations 110 ■ Waiting for more than one future 114 Waiting for the first future in a set with when_any 115 Latches and barriers in the Concurrency TS 118 ■ A basic latch type: std::experimental::latch 118 ■ std::experimental::barrier: a basic barrier 120 ■ std::experimental::flex_barrier— std::experimental::barrier’s flexible friend 121 5 The C++ memory model and operations on atomic types 124 5.1 Memory model basics 125 Objects and memory locations 125 ■ Objects, memory locations, and concurrency 126 ■ Modification orders 127 5.2 Atomic operations and types in C++ 128 The standard atomic types 128 ■ Operations on std::atomic_flag 132 ■ Operations on std::atomic<bool> 134 Operations on std::atomic<T*>: pointer arithmetic 137 Operations on standard atomic integral types 138 The std::atomic<> primary class template 138 Free functions for atomic operations 140 5.3 Synchronizing operations and enforcing ordering 142 The synchronizes-with relationship 143 ■ The happens-before relationship 145 ■ Memory ordering for atomic operations 146 Release sequences and synchronizes-with 164 ■ Fences 166 Ordering non-atomic operations with atomics 168 ■ Ordering non-atomic operations 169 6 Designing lock-based concurrent data structures 173 6.1 What does it mean to design for concurrency? 174 Guidelines for designing data structures for concurrency 175 6.2 Lock-based concurrent data structures 176 A thread-safe stack using locks 176 ■ A thread-safe queue using locks and condition variables 179 ■ A thread-safe queue using fine-grained locks and condition variables 183 6.3 Designing more complex lock-based data structures 194 Writing a thread-safe lookup table using locks 194 ■ Writing a thread-safe list using locks 199

📄 Page 11

CONTENTSx7 Designing lock-free concurrent data structures 205 7.1 Definitions and consequences 206 Types of nonblocking data structures 206 ■ Lock-free data structures 207 ■ Wait-free data structures 208 ■ The pros and cons of lock-free data structures 208 7.2 Examples of lock-free data structures 209 Writing a thread-safe stack without locks 210 ■ Stopping those pesky leaks: managing memory in lock-free data structures 214 Detecting nodes that can’t be reclaimed using hazard pointers 218 Detecting nodes in use with reference counting 226 ■ Applying the memory model to the lock-free stack 232 ■ Writing a thread-safe queue without locks 236 7.3 Guidelines for writing lock-free data structures 248 Guideline: use std::memory_order_seq_cst for prototyping 248 Guideline: use a lock-free memory reclamation scheme 248 Guideline: watch out for the ABA problem 249 ■ Guideline: identify busy-wait loops and help the other thread 249 8 Designing concurrent code 251 8.1 Techniques for dividing work between threads 252 Dividing data between threads before processing begins 253 Dividing data recursively 254 ■ Dividing work by task type 258 8.2 Factors affecting the performance of concurrent code 260 How many processors? 261 ■ Data contention and cache ping-pong 262 ■ False sharing 264 ■ How close is your data? 265 ■ Oversubscription and excessive task switching 266 8.3 Designing data structures for multithreaded performance 266 Dividing array elements for complex operations 267 ■ Data access patterns in other data structures 269 8.4 Additional considerations when designing for concurrency 270 Exception safety in parallel algorithms 271 ■ Scalability and Amdahl’s law 277 ■ Hiding latency with multiple threads 279 Improving responsiveness with concurrency 280

📄 Page 12

CONTENTS xi8.5 Designing concurrent code in practice 282 A parallel implementation of std::for_each 282 ■ A parallel implementation of std::find 284 ■ A parallel implementation of std::partial_sum 290 9 Advanced thread management 300 9.1 Thread pools 301 The simplest possible thread pool 301 ■ Waiting for tasks submitted to a thread pool 303 ■ Tasks that wait for other tasks 307 ■ Avoiding contention on the work queue 310 Work stealing 311 9.2 Interrupting threads 315 Launching and interrupting another thread 316 ■ Detecting that a thread has been interrupted 318 ■ Interrupting a condition variable wait 318 ■ Interrupting a wait on std::condition_variable_any 321 ■ Interrupting other blocking calls 323 ■ Handling interruptions 324 Interrupting background tasks on application exit 325 10 Parallel algorithms 327 10.1 Parallelizing the standard library algorithms 327 10.2 Execution policies 328 General effects of specifying an execution policy 328 std::execution::sequenced_policy 330 std::execution::parallel_policy 330 std::execution::parallel_unsequenced_policy 331 10.3 The parallel algorithms from the C++ Standard Library 331 Examples of using parallel algorithms 334 Counting visits 336 11 Testing and debugging multithreaded applications 339 11.1 Types of concurrency-related bugs 340 Unwanted blocking 340 ■ Race conditions 341 11.2 Techniques for locating concurrency-related bugs 342 Reviewing code to locate potential bugs 342 ■ Locating concurrency-related bugs by testing 344 ■ Designing for testability 346 ■ Multithreaded testing techniques 347 Structuring multithreaded test code 350 ■ Testing the performance of multithreaded code 352

📄 Page 13

CONTENTSxiiappendix A Brief reference for some C++11 language features 354 appendix B Brief comparison of concurrency libraries 382 appendix C A message-passing framework and complete ATM example 384 appendix D C++ Thread Library reference 401 index 551

📄 Page 14

preface I encountered the concept of multithreaded code while working at my first job after I left college. We were writing a data processing application that had to populate a data- base with incoming data records. There was a lot of data, but each record was inde- pendent and required a reasonable amount of processing before it could be inserted into the database. To take full advantage of the power of our 10-CPU UltraSPARC, we ran the code in multiple threads, each thread processing its own set of incoming records. We wrote the code in C++, using POSIX threads, and made a fair number of mistakes—multithreading was new to all of us—but we got there in the end. It was also while working on this project that I first became aware of the C++ Standards Commit- tee and the freshly published C++ Standard. I have had a keen interest in multithreading and concurrency ever since. Where others saw it as difficult, complex, and a source of problems, I saw it as a powerful tool that could enable your code to take advantage of the available hardware to run faster. Later on, I would learn how it could be used to improve the responsiveness and per- formance of applications even on single-core hardware, by using multiple threads to hide the latency of time-consuming operations such as I/O. I also learned how it worked at the OS level and how Intel CPUs handled task switching. Meanwhile, my interest in C++ brought me in contact with the ACCU and then the C++ Standards panel at BSI, as well as Boost. I followed the initial development of the Boost Thread Library with interest, and when it was abandoned by the original devel- oper, I jumped at the chance to get involved. I was the primary developer and main- tainer of the Boost Thread Library for a number of years, though I have since handed that responsibility on.xiii

📄 Page 15

PREFACExiv As the work of the C++ Standards Committee shifted from fixing defects in the existing standard to writing proposals for the C++11 standard (named C++0x in the hope that it would be finished by 2009, and then officially C++11, because it was finally published in 2011), I got more involved with BSI and started drafting proposals of my own. Once it became clear that multithreading was on the agenda, I jumped in with both feet and authored or co-authored many of the multithreading and concurrency- related proposals that shaped this part of the standard. I have continued to be involved with the concurrency group as we worked on the changes for C++17, the Concurrency TS, and proposals for the future. I feel privileged to have had the oppor- tunity to combine two of my major computer-related interests—C++ and multithread- ing—in this way. This book draws on all my experience with both C++ and multithreading and aims to teach other C++ developers how to use the C++17 Thread Library and Concurrency TS safely and efficiently. I also hope to impart some of my enthusiasm for the subject along the way.

📄 Page 16

acknowledgments I will start by saying a big “Thank you” to my wife, Kim, for all the love and support she has given me while writing this book. The first edition occupied a significant part of my spare time for the four years before publication, and the second edition has again required a significant investment of time, and without her patience, support, and understanding, I couldn’t have managed it. Second, I would like to thank the team at Manning who have made this book possi- ble: Marjan Bace, publisher; Michael Stephens, associate publisher; Cynthia Kane, my development editor; Aleksandar Dragosavljević, review editor; Safis Editing and Heidi Ward, my copyeditors; and Melody Dolab, my proofreader. Without their efforts you would not be reading this book right now. I would also like to thank the other members of the C++ Standards Committee who wrote committee papers on the multithreading facilities: Andrei Alexandrescu, Pete Becker, Bob Blainer, Hans Boehm, Beman Dawes, Lawrence Crowl, Peter Dimov, Jeff Garland, Kevlin Henney, Howard Hinnant, Ben Hutchings, Jan Kristofferson, Doug Lea, Paul McKenney, Nick McLaren, Clark Nelson, Bill Pugh, Raul Silvera, Herb Sutter, Detlef Vollmann, and Michael Wong, plus all those who commented on the papers, discussed them at the committee meetings, and otherwise helped shaped the multithreading and concurrency support in C++11, C++14, C++17, and the Concur- rency TS. Finally, I would like to thank the following people, whose suggestions have greatly improved this book: Dr. Jamie Allsop, Peter Dimov, Howard Hinnant, Rick Molloy, Jonathan Wakely, and Dr. Russel Winder, with special thanks to Russel for his detailedxv

📄 Page 17

ACKNOWLEDGMENTSxvireviews and to Frédéric Flayol, who, as technical proofreader, painstakingly checked all the content for outright errors in the final manuscript during production. (Any remaining mistakes are, of course, all mine.) In addition, I’d like to thank my panel of reviewers for the second edition: Al Norman, Andrei de Araújo Formiga, Chad Brewbaker, Dwight Wilkins, Hugo Filipe Lopes, Vieira Durana, Jura Shikin, Kent R. Spillner, Maria Gemini, Mateusz Malenta, Maurizio Tomasi, Nat Luengnaruemitchai, Robert C. Green II, Robert Trausmuth, Sanchir Kartiev, and Steven Parr. Also, thanks to the readers of the MEAP edition who took the time to point out errors or highlight areas that needed clarifying.

📄 Page 18

about this book This book is an in-depth guide to the concurrency and multithreading facilities from the new C++ Standard, from the basic usage of std::thread, std::mutex, and std:: async, to the complexities of atomic operations and the memory model. Roadmap The first four chapters introduce the various library facilities provided by the library and show how they can be used. Chapter 5 covers the low-level nitty-gritty of the memory model and atomic opera- tions, including how atomic operations can be used to impose ordering constraints on other code, and marks the end of the introductory chapters. Chapters 6 and 7 start the coverage of higher-level topics, with some examples of how to use the basic facilities to build more complex data structures—lock-based data structures in chapter 6, and lock-free data structures in chapter 7. Chapter 8 continues the higher-level topics, with guidelines for designing multi- threaded code, coverage of the issues that affect performance, and example imple- mentations of various parallel algorithms. Chapter 9 covers thread management—thread pools, work queues, and interrupt- ing operations. Chapter 10 covers the new parallelism support from C++17, which comes in the form of additional overloads for many of the Standard Library algorithms. Chapter 11 covers testing and debugging—types of bugs, techniques for locating them, how to test for them, and so forth.xvii

📄 Page 19

ABOUT THIS BOOKxviii The appendixes include a brief description of some of the new language facilities introduced with the new standard that are relevant to multithreading, the implemen- tation details of the message-passing library mentioned in chapter 4, and a complete reference to the C++17 Thread Library. Who should read this book If you're writing multithreaded code in C++, you should read this book. If you're using the new multithreading facilities from the C++ Standard Library, this book is an essen- tial guide. If you’re using alternative thread libraries, the guidelines and techniques from the later chapters should still prove useful. A good working knowledge of C++ is assumed, though familiarity with the new lan- guage features is not—these are covered in appendix A. Prior knowledge or experi- ence of multithreaded programming is not assumed, though it may be useful. How to use this book If you’ve never written multithreaded code before, I suggest reading this book sequen- tially from beginning to end, though possibly skipping the more detailed parts of chapter 5. Chapter 7 relies heavily on the material in chapter 5, so if you skipped chapter 5, you should save chapter 7 until you’ve read it. If you haven’t used the new C++11 language facilities before, it might be worth skimming appendix A before you start to ensure that you’re up to speed with the examples in the book. The uses of the new language facilities are highlighted in the text, though, and you can always flip to the appendix if you encounter something you haven’t seen before. If you have extensive experience with writing multithreaded code in other environ- ments, the beginning chapters are probably still worth skimming so you can see how the facilities you know map onto the new standard C++ ones. If you’re going to be doing any low-level work with atomic variables, chapter 5 is a must. Chapter 8 is worth reviewing to ensure that you’re familiar with things like exception safety in multi- threaded C++. If you have a particular task in mind, the index and table of contents should help you find a relevant section quickly. Once you’re up to speed on the use of the C++ Thread Library, appendix D should continue to be useful, such as for looking up the exact details of each class and func- tion call. You may also like to dip back into the main chapters from time to time to refresh your memory on a particular construct or to look at the sample code. Code conventions and downloads All source code in listings or in text is in a fixed-width font like this to separate it from ordinary text. Code annotations accompany many of the listings, highlighting important concepts. In some cases, numbered bullets link to explanations that follow the listing.

📄 Page 20

ABOUT THIS BOOK xix Source code for all working examples in this book is available for download from the publisher’s website at www.manning.com/books/c-plus-plus-concurrency-in-action- second-edition. You may also download the source code from github at https://github .com/anthonywilliams/ccia_code_samples. Software requirements To use the code from this book unchanged, you’ll need a recent C++ compiler that supports the C++17 language features used in the examples (see appendix A), and you’ll need a copy of the C++ Standard Thread Library. At the time of writing, the latest versions of g++, clang++, and Microsoft Visual Stu- dio all ship with implementations of the C++17 Standard Thread Library. They also support most of the language features from the appendix, and those features that aren't supported are coming soon. My company, Just Software Solutions Ltd, sells a complete implementation of the C++11 Standard Thread Library for several older compilers, along with an implemen- tation of the Concurrency TS for newer versions of clang, gcc, and Microsoft Visual Studio.1 This implementation has been used for testing the examples in this book. The Boost Thread Library2 provides an API that’s based on the C++11 Standard Thread Library proposals and is portable to many platforms. Most of the examples from the book can be modified to work with the Boost Thread Library by judicious replacement of std:: with boost:: and use of the appropriate #include directives. There are a few facilities that are either not supported (such as std::async) or have different names (such as boost::unique_future) in the Boost Thread Library. Book forum Purchase of C++ Concurrency in Action, Second Edition includes free access to a pri- vate web forum run by Manning Publications where you can make comments about the book, ask technical questions, and receive help from the author and from other users. To access the forum, go to www.manning.com/books/c-plus-plus-concurrency- in-action-second-edition. You can also learn more about Manning’s forums and the rules of conduct at https://forums.manning.com/forums/about. Manning’s commitment to our readers is to provide a venue where a meaningful dialogue between individual readers and between readers and the author can take place. It’s not a commitment to any specific amount of participation on the part of the author, whose contribution to the book’s forum remains voluntary (and unpaid). We suggest you try asking the author some challenging questions, lest his interest stray! The forum and the archives of previous discussions will be accessible from the pub- lisher’s website as long as the book is in print. 1 The just::thread implementation of the C++ Standard Thread Library, http://www.stdthread.co.uk. 2 The Boost C++ library collection, http://www.boost.org.