Transcription
IN ACTIONPractical MultithreadingAnthony WilliamsMANNING
C Concurrency in Action
C Concurrencyin ActionPRACTICAL MULTITHREADINGANTHONY WILLIAMSMANNINGSHELTER ISLAND
For online information and ordering of this and other Manning books, please visitwww.manning.com. The publisher offers discounts on this book when ordered in quantity.For more information, please contactSpecial Sales DepartmentManning Publications Co.20 Baldwin RoadPO Box 261Shelter Island, NY 11964Email: orders@manning.com 2012 by Manning Publications Co. All rights reserved.No part of this publication may be reproduced, stored in a retrieval system, or transmitted, inany form or by means electronic, mechanical, photocopying, or otherwise, without prior writtenpermission of the publisher.Many of the designations used by manufacturers and sellers to distinguish their products areclaimed as trademarks. Where those designations appear in the book, and ManningPublications was aware of a trademark claim, the designations have been printed in initial capsor all caps.Recognizing the importance of preserving what has been written, it is Manning’s policy to havethe 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 booksare printed on paper that is at least 15 percent recycled and processed without the use ofelemental chlorine.Manning Publications Co.20 Baldwin RoadPO Box 261Shelter Island, NY 11964Development editor:Technical r designer:ISBN: 9781933988771Printed in the United States of America1 2 3 4 5 6 7 8 9 10 – MAL – 18 17 16 15 14 13 12Cynthia KaneJonathan WakelyLinda RecktenwaldKatie TennantDennis DalinnikMarija Tudor
To Kim, Hugh, and Erin
brief contents1 Hello, world of concurrency in C !12 Managing threads3 Sharing data between threads4 Synchronizing concurrent operations5 The C memory model and operations on atomic types6 Designing lock-based concurrent data structures 1487 Designing lock-free concurrent data structures 1808 Designing concurrent code 2249 Advanced thread management 27310 Testing and debugging multithreaded applications15vii3367300103
contentspreface xvacknowledgments xviiabout this book xixabout the cover illustration1xxiiHello, world of concurrency in C ! 11.1What is concurrency?2Concurrency in computer systemsApproaches to concurrency 41.2Why use concurrency?26Using concurrency for separation of concerns 6Using concurrency for performance 7 When notto use concurrency 8 1.3Concurrency and multithreading in C 9History of multithreading in C 10 Concurrency supportin the new standard 10 Efficiency in the C Thread Library 11 Platform-specific facilities 12 1.4Getting started 13Hello, Concurrent World1.5Summary 14ix13
CONTENTSx2Managing threads 152.1Basic thread management 16Launching a thread 16 Waiting for a thread to complete 18Waiting in exceptional circumstances 19 Running threadsin the background 21 2.22.32.42.52.63Passing arguments to a thread function 23Transferring ownership of a thread 25Choosing the number of threads at runtime 28Identifying threads 31Summary 32Sharing data between threads 333.1Problems with sharing data between threads 34Race conditions3.235 Avoiding problematic race conditionsProtecting shared data with mutexes3637Using mutexes in C 38 Structuring code for protectingshared data 39 Spotting race conditions inherentin interfaces 40 Deadlock: the problem and a solution 47Further guidelines for avoiding deadlock 49 Flexible lockingwith std::unique lock 54 Transferring mutex ownershipbetween scopes 55 Locking at an appropriate granularity 57 3.3Alternative facilities for protecting shared data59Protecting shared data during initialization 59 Protecting rarelyupdated data structures 63 Recursive locking 64 3.44Summary 65Synchronizing concurrent operations 674.1Waiting for an event or other condition68Waiting for a condition with condition variables 69Building a thread-safe queue with condition variables 714.2Waiting for one-off events with futures76Returning values from background tasks 77 Associating a taskwith a future 79 Making (std::)promises 81 Saving anexception for the future 83 Waiting from multiple threads 85 4.3Waiting with a time limit87Clocks 87 Durations 88 Time points 89Functions that accept timeouts 91
CONTENTS4.4xiUsing synchronization of operations to simplify codeFunctional programming with futuresoperations with message passing 974.5593 93SynchronizingSummary 102The C memory model and operations on atomic types 1035.1Memory model basics 104Objects and memory locations 104 Objects, memory locations,and concurrency 105 Modification orders 106 5.2Atomic operations and types in C 107The standard atomic types 107 Operations onstd::atomic flag 110 Operations on std::atomic bool 112Operations on std::atomic T* : pointer arithmetic 114Operations on standard atomic integral types 116The std::atomic primary class template 116 Free functionsfor atomic operations 117 5.3Synchronizing operations and enforcing ordering 119The synchronizes-with relationship 121 The happens-beforerelationship 122 Memory ordering for atomic operations 123Release sequences and synchronizes-with 141 Fences 143Ordering nonatomic operations with atomics 145 5.46Summary 147Designing lock-based concurrent data structures 1486.1What does it mean to design for concurrency?149Guidelines for designing data structures for concurrency6.2Lock-based concurrent data structures149151A thread-safe stack using locks 151 A thread-safe queue usinglocks and condition variables 154 A thread-safe queue usingfine-grained locks and condition variables 158 6.3Designing more complex lock-based data structuresWriting a thread-safe lookup table using locks 169thread-safe list using locks 1756.47 Writing aSummary 179Designing lock-free concurrent data structures 1807.1Definitions and consequences181Types of nonblocking data structures 181 Lock-freedata structures 182 Wait-free data structures 182The pros and cons of lock-free data structures 183 169
CONTENTSxii7.2Examples of lock-free data structures 184Writing a thread-safe stack without locks 184 Stopping thosepesky leaks: managing memory in lock-free data structures 188Detecting nodes that can’t be reclaimed using hazard pointers 193Detecting nodes in use with reference counting 200 Applying thememory model to the lock-free stack 205 Writing a thread-safequeue without locks 209 7.3Guidelines for writing lock-free data structures221Guideline: use std::memory order seq cst for prototyping 221Guideline: use a lock-free memory reclamation scheme 221Guideline: watch out for the ABA problem 222Guideline: identify busy-wait loops and help the other thread 2227.48Summary 223Designing concurrent code 2248.1Techniques for dividing work between threads225Dividing data between threads before processing begins 226Dividing data recursively 227 Dividing work by task type 231 8.2Factors affecting the performance of concurrent code 233How many processors? 234 Data contention and cacheping-pong 235 False sharing 237 How close isyour data? 238 Oversubscription and excessivetask switching 239 8.3Designing data structures for multithreadedperformance 239Dividing array elements for complex operations 240Data access patterns in other data structures 2428.4Additional considerations when designing forconcurrency 243Exception safety in parallel algorithms 243 Scalability andAmdahl’s law 250 Hiding latency with multiple threads 252Improving responsiveness with concurrency 253 8.5Designing concurrent code in practice255A parallel implementation of std::for each 255 A parallelimplementation of std::find 257 A parallel implementationof std::partial sum 263 8.6Summary 272
CONTENTS9xiiiAdvanced thread management 2739.1Thread pools274The simplest possible thread pool 274 Waiting for taskssubmitted to a thread pool 276 Tasks that wait for othertasks 280 Avoiding contention on the work queue 283Work stealing 284 9.2Interrupting threads289Launching and interrupting another thread 289 Detecting thata thread has been interrupted 291 Interrupting a conditionvariable wait 291 Interrupting a wait onstd::condition variable any 294 Interrupting otherblocking calls 296 Handling interruptions 297Interrupting background tasks on application exit 298 9.310Summary 299Testing and debugging multithreaded applications 30010.1Types of concurrency-related bugsUnwanted blocking 30110.2 301Race conditions302Techniques for locating concurrency-related bugsReviewing code to locate potential bugs 303Locating concurrency-related bugs by testing 305Designing for testability 307 Multithreaded testingtechniques 308 Structuring multithreaded test codeTesting the performance of multithreaded code 314303 10.3appendix Aappendix Bappendix Cappendix DSummary311314Brief reference for some C 11 language features 315Brief comparison of concurrency libraries 340A message-passing framework and complete ATM example 342C Thread Library reference 360resources 487index 489
prefaceI encountered the concept of multithreaded code while working at my first job after Ileft college. We were writing a data processing application that had to populate a database with incoming data records. There was a lot of data, but each record was independent and required a reasonable amount of processing before it could be insertedinto the database. To take full advantage of the power of our 10-CPU UltraSPARC, weran the code in multiple threads, each thread processing its own set of incomingrecords. We wrote the code in C , using POSIX threads, and made a fair number ofmistakes—multithreading was new to all of us—but we got there in the end. It was alsowhile working on this project that I first became aware of the C Standards Committee and the freshly published C Standard.I have had a keen interest in multithreading and concurrency ever since. Whereothers saw it as difficult, complex, and a source of problems, I saw it as a powerful toolthat 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 performance of applications even on single-core hardware, by using multiple threads to hidethe latency of time-consuming operations such as I/O. I also learned how it worked atthe OS level and how Intel CPUs handled task switching.Meanwhile, my interest in C brought me in contact with the ACCU and then theC Standards panel at BSI, as well as Boost. I followed the initial development ofthe Boost Thread Library with interest, and when it was abandoned by the originaldeveloper, I jumped at the chance to get involved. I have been the primary developerand maintainer of the Boost Thread Library ever since.xv
xviPREFACEAs the work of the C Standards Committee shifted from fixing defects in the existing standard to writing proposals for the next standard (named C 0x in the hopethat it would be finished by 2009, and now 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 bothfeet and authored or coauthored many of the multithreading and concurrencyrelated proposals that shaped this part of the new standard. I feel privileged to havehad the opportunity to combine two of my major computer-related interests—C and multithreading—in this way.This book draws on all my experience with both C and multithreading and aimsto teach other C developers how to use the C 11 Thread Library safely and efficiently. I also hope to impart some of my enthusiasm for the subject along the way.
acknowledgmentsI will start by saying a big “Thank you” to my wife, Kim, for all the love and support shehas given me while writing this book. It has occupied a significant part of my sparetime for the last four years, and without her patience, support, and understanding, Icouldn’t have managed it.Second, I would like to thank the team at Manning who have made this book possible: Marjan Bace, publisher; Michael Stephens, associate publisher; Cynthia Kane, mydevelopment editor; Karen Tegtmeyer, review editor; Linda Recktenwald, my copyeditor; Katie Tennant, my proofreader; and Mary Piergies, the production manager.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 Committeewho 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, DougLea, 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.Finally, I would like to thank the following people, whose suggestions have greatlyimproved this book: Dr. Jamie Allsop, Peter Dimov, Howard Hinnant, Rick Molloy,Jonathan Wakely, and Dr. Russel Winder, with special thanks to Russel for his detailedreviews and to Jonathan who, as technical proofreader, painstakingly checked all thecontent for outright errors in the final manuscript during production. (Any remainingxvii
xviiiACKNOWLEDGMENTSmistakes are of course all mine.) In addition I’d like to thank my panel of reviewers:Ryan Stephens, Neil Horlock, John Taylor Jr., Ezra Jivan, Joshua Heyer, Keith S. Kim,Michele Galli, Mike Tian-Jian Jiang, David Strong, Roger Orr, Wagner Rick, Mike Buksas,and Bas Vodde. Also, thanks to the readers of the MEAP edition who took the time topoint out errors or highlight areas that needed clarifying.
about this bookThis book is an in-depth guide to the concurrency and multithreading facilities from thenew C Standard, from the basic usage of std::thread, std::mutex, and std::async,to the complexities of atomic operations and the memory model.RoadmapThe first four chapters introduce the various library facilities provided by the libraryand show how they can be used.Chapter 5 covers the low-level nitty-gritty of the memory model and atomic operations, including how atomic operations can be used to impose ordering constraints onother code, and marks the end of the introductory chapters.Chapters 6 and 7 start the coverage of higher-level topics, with some examples ofhow to use the basic facilities to build more complex data structures—lock-based datastructures in chapter 6, and lock-free data structures in chapter 7.Chapter 8 continues the higher-level topics, with guidelines for designing multithreaded code, coverage of the issues that affect performance, and example implementations of various parallel algorithms.Chapter 9 covers thread management—thread pools, work queues, and interrupting operations.Chapter 10 covers testing and debugging—types of bugs, techniques for locatingthem, how to test for them, and so forth.The appendixes include a brief description of some of the new language facilities introduced with the new standard that are relevant to multithreading, thexix
ABOUT THIS BOOKxximplementation details of the message-passing library mentioned in chapter 4, and acomplete reference to the C 11 Thread Library.Who should read this bookIf you're writing multithreaded code in C , you should read this book. If you're usingthe new multithreading facilities from the C Standard Library, this book is an essential guide. If you’re using alternative thread libraries, the guidelines and techniquesfrom the later chapters should still prove useful.A good working knowledge of C is assumed, though familiarity with the new language features is not—these are covered in appendix A. Prior knowledge or experienceof multithreaded programming is not assumed, though it may be useful.How to use this bookIf you’ve never written multithreaded code before, I suggest reading this book sequentially from beginning to end, though possibly skipping the more detailed parts ofchapter 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’ve not used the new C 11 language facilities before, it might be worthskimming appendix A before you start to ensure that you’re up to speed with theexamples in the book. The uses of the new language facilities are highlighted inthe text, though, and you can always flip to the appendix if you encounter somethingyou’ve not seen before.If you have extensive experience with writing multithreaded code in other environments, the beginning chapters are probably still worth skimming so you can see howthe facilities you know map onto the new standard C ones. If you’re going to bedoing any low-level work with atomic variables, chapter 5 is a must. Chapter 8 is worthreviewing to ensure that you’re familiar with things like exception safety in multithreaded C . If you have a particular task in mind, the index and table of contentsshould help you find a relevant section quickly.Once you’re up to speed on the use of the C Thread Library, appendix D shouldcontinue to be useful, such as for looking up the exact details of each class and function call. You may also like to dip back into the main chapters from time to time torefresh your use of a particular construct or look at the sample code.Code conventions and downloadsAll source code in listings or in text is in a fixed-width font like this to separate itfrom ordinary text. Code annotations accompany many of the listings, highlightingimportant concepts. In some cases, numbered bullets link to explanations that followthe listing.Source code for all working examples in this book is available for download fromthe publisher’s website at www.manning.com/CPlusPlusConcurrencyinAction.
ABOUT THIS BOOKxxiSoftware requirementsTo use the code from this book unchanged, you’ll need a recent C compiler thatsupports the new C 11 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, g is the only compiler I’m aware of that ships with animplementation of the Standard Thread Library, although the Microsoft Visual Studio2011 preview also includes an implementation. The g implementation of theThread Library was first introduced in a basic form in g 4.3 and extended in subsequent releases. g 4.3 also introduced the first support for some of the new C 11language features; more of the new language features are supported in each subsequent release. See the g C 11 status page for details.1Microsoft Visual Studio 2010 provides some of the new C 11 language features,such as rvalue references and lambda functions, but doesn't ship with an implementation of the Thread Library.My company, Just Software Solutions Ltd, sells a complete implementation of theC 11 Standard Thread Library for Microsoft Visual Studio 2005, Microsoft VisualStudio 2008, Microsoft Visual Studio 2010, and various versions of g .2 This implementation has been used for testing the examples in this book.The Boost Thread Library3 provides an API that’s based on the C 11 StandardThread Library proposals and is portable to many platforms. Most of the examplesfrom the book can be modified to work with the Boost Thread Library by judiciousreplacement 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 havedifferent names (such as boost::unique future) in the Boost Thread Library.Author OnlinePurchase of C Concurrency in Action includes free access to a private web forum run byManning 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 andsubscribe to it, point your web browser to www.manning.com/CPlusPlusConcurrencyinAction. This page provides information on how to get on the forum once you’re registered, what kind of help is available, and the rules of conduct on the forum.Manning’s commitment to our readers is to provide a venue where a meaningfuldialogue between individual readers and between readers and the author can takeplace. It’s not a commitment to any specific amount of participation on the part of theauthor, whose contribution to the book’s forum remains voluntary (and unpaid). Wesuggest you try asking the author some challenging questions, lest his interest stray!The Author Online forum and the archives of previous discussions will be accessible from the publisher’s website as long as the book is in print.123GNU Compiler Collection C 0x/C 11 status page, http://gcc.gnu.org/projects/cxx0x.html.The just::thread implementation of the C Standard Thread Library, http://www.stdthread.co.uk.The Boost C library collection, http://www.boost.org.
about the cover illustrationThe illustration on the cover of C Concurrency in Action is captioned “Habit of aLady of Japan.” The image is taken from the four-volume Collection of the Dress ofDifferent Nations by Thomas Jefferys, published in London between 1757 and 1772. Thecollection includes beautiful hand-colored copperplate engravings of costumes fromaround the world and has influenced theatrical costume design since its publication.The diversity of the drawings in the compendium speaks vividly of the richness of thecostumes presented on the London stage over 200 years ago. The costumes, both historical and contemporaneous, offered a glimpse into the dress customs of people living in different times and in different countries, making them come alive for Londontheater audiences.Dress codes have changed in the last century and the diversity by region, so rich inthe past, has faded away. It’s now often hard to tell the inhabitant of one continentfrom another. Perhaps, trying to view it optimistically, we’ve traded a cultural andvisual diversity for a more varied personal life—or a more varied and interesting intellectual and technical life.We at Manning celebrate the inventiveness, the initiative, and the fun of the computer business with book covers based on the rich diversity of regional and theatricallife of two centuries ago, brought back to life by the pictures from this collection.xxii
Hello, world ofconcurrency in C !This chapter covers What is meant by concurrency andmultithreading Why you might want to use concurrency andmultithreading in your applications Some of the history of the support forconcurrency in C What a simple multithreaded C programlooks likeThese are exciting times for C users. Thirteen years after the original C Standard was published in 1998, the C Standards Committee is giving the languageand its supporting library a major overhaul. The new C Standard (referred to asC 11 or C 0x) was published in 2011 and brings with it a whole swathe ofchanges that will make working with C easier and more productive.One of the most significant new features in the C 11 Standard is the support ofmultithreaded programs. For the first time, the C Standard will acknowledge theexistence of multithreaded applications in the language and provide components inthe library for writing multithreaded applications. This will make it possible to write1
2CHAPTER 1Hello, world of concurrency in C !multithreaded C programs without relying on platform-specific extensions and thusallow writing portable multithreaded code with guaranteed behavior. It also comes at atime when programmers are increasingly looking to concurrency in general, and multithreaded programming in particular, to improve application performance.This book is about writing programs in C using multiple threads for concurrency and the C language features and library facilities that make that possible. I’llstart by explaining what I mean by concurrency and multithreading and why youwould want to use concurrency in your applications. After a quick detour into whyyou might not want to use it in your applications, I’ll give an overview of the concurrency support in C , and I’ll round off this chapter with a simple example of C concurrency in action. Readers experienced with developing multithreaded applications may wish to skip the early sections. In subsequent chapters I’ll cover moreextensive examples and look at the library facilities in more depth. The book will finish with an in-depth reference to all the C Standard Library facilities for multithreading and concurrency.So, what do I mean by concurrency and multithreading?1.1What is concurrency?At the simplest and most basic level, concurrency is about two or more separate activities happening at the same time. We encounter concurrency as a natural part of life;we can walk and talk at the same time or perform different actions with each hand,and of course we each go about our lives independently of each other—you can watchfootball while I go swimming, and so on.1.1.1Concurrency in computer systemsWhen we talk about concurrency in terms of computers, we mean a single system performing multiple independent activities in parallel, rather than sequentially, or oneafter the other. It isn’t a new phenomenon: multitasking operating systems that allowa single computer to run multiple applications at the same time through task switching have been commonplace for many years, and high-end server machines with multiple processors that enable genuine concurrency have been available for even longer.What is new is the increased prevalence of computers that can genuinely run multipletasks in parallel rather than just giving the illusion of doing so.Historically, most computers have had one processor, with a single processingunit or core, and this remains true for many desktop machines today. Such amachine can really only perform one task at a time, but it can switch between tasksmany times per second. By doing a bit of one task and then a bit of another and soon, it appears that the tasks are happening concurrently. This is called task switching.We still talk about concurrency with such systems; because the task switches are so fast,you can’t tell at which point a task may be suspended as the processor switches toanother one. The task switching provides an illusion of concurrency to both the userand the applications themselves. Because there is only an illusion of concurrency, the
What is concurrency?3behavior of applications may be subtly different when executing in a single-processortask-switching environment compared to when executing in an environment withtrue concurrency. In particular, incorrect assumptions about the memory model(covered in chapter 5) may not show up in such an environment. This is discussedin more depth in chapter 10.Computers containing multiple processors have been used for servers and highperformance computing tasks for a number of years, and now computers based onprocessors with more than one core on a single chip (multicore processors) are becoming increasingly common as desktop machines too. Whether they have multiple processors or multiple cores within a processor (or both), these computers are capable ofgenuinely running more than one task in parallel. We call this hardware concurrency.Figure 1.1 shows an idealized scenario of a computer with precisely two tasks to do,each divided into 10 equal-size chunks. On a dual-core machine (which has two processing cores), each task can execute on its own core. On a single-core machine doingtask switching, the chunks from each task are interleaved. But they are also spaced outa bit (in the diagram this is shown by the gray bars separating the chunks beingthicker than the separator bars shown for the dual-core machine); in order to do theinterleaving, the system has to perform a context switch every time it changes from onetask to another, and this takes time. In order to perform a context switch, the OS hasto save the CPU state and instruction pointer for the currently running task, work outwhich task to switch to, and reload the CPU state for the task being switched to. TheCPU will then potentially have to load the memory for the instructions and data forthe new task into cache, which can prevent the CPU from executing any instructions,causing further delay.Though the availability of concurrency in the hardware is most obvious with multiprocessor or multicore systems, some processors can execute multiple threads on asingle core. The important factor to consider is really the number of hardware threads:the measure of how many independent tasks the hardware can genuinely run concurrently. Even with a system that has genuine hardware concurrency, it’s easy to havemore tasks than the hardware can run in parallel, so task switching is still used in thesecases. For example, on a typical desktop computer there may be hundreds of tasksFigure 1.1 Two approaches to concurrency: parallel execution on a dual-coremachine versus task switching on a single-core machine
4CHAPTER 1Hello, world of concurrency in C !running, performing background operations, even when the computer is nominallyidle. It’s the task switching that allows these background tasks to run and allows you torun your word processor, compiler, editor, and web browser (or any combination ofapplications) all at once. Figure 1.2 shows task switching among four tasks on a dualcore machine, again for an idealized scenario with the tasks divided neatly into equalsize chunks. In practice, many issues will make the divisions uneven and the schedulingirregular. Some of these issues are covered in chapter 8 when we look at factors affecting the performance of concurrent code.All the
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
