Java Concurrency in Practice PDF

Advance praise for Java Concurrency in Practice I was fortunate indeed to have worked with a fantastic team on the design and implementation of the concurrency features added to the Java platform in Java 5.0 and Java 6. Now this same team provides the best explanation yet of these new features, and of concurrency in general. Concurrency is no longer a subject for advanced users only. Every Java developer should read this book. —Martin Buchholz JDK Concurrency Czar, Sun Microsystems For the past 30 years, computer performance has been driven by Moore’s Law; from now on, it will be driven by Amdahl’s Law. Writing code that effectively exploits multiple processors can be very challenging. Java Concurrency in Practice provides you with the concepts and techniques needed to write safe and scalable Java programs for today’s—and tomorrow’s—systems. —Doron Rajwan Research Scientist, Intel Corp This is the book you need if you’re writing—or designing, or debugging, or main- taining, or contemplating—multithreaded Java programs. If you’ve ever had to synchronize a method and you weren’t sure why, you owe it to yourself and your users to read this book, cover to cover. —Ted Neward Author of Effective Enterprise Java Brian addresses the fundamental issues and complexities of concurrency with uncommon clarity. This book is a must-read for anyone who uses threads and cares about performance. —Kirk Pepperdine CTO, JavaPerformanceTuning.com This book covers a very deep and subtle topic in a very clear and concise way, making it the perfect Java Concurrency reference manual. Each page is ﬁlled with the problems (and solutions!) that programmers struggle with every day. Effectively exploiting concurrency is becoming more and more important now that Moore’s Law is delivering more cores but not faster cores, and this book will show you how to do it. —Dr. Cliff Click Senior Software Engineer, Azul Systems I have a strong interest in concurrency, and have probably written more thread deadlocks and made more synchronization mistakes than most programmers. Brian’s book is the most readable on the topic of threading and concurrency in Java, and deals with this difﬁcult subject with a wonderful hands-on approach. This is a book I am recommending to all my readers of The Java Specialists’ Newsletter, because it is interesting, useful, and relevant to the problems facing Java developers today. —Dr. Heinz Kabutz The Java Specialists’ Newsletter I’ve focused a career on simplifying simple problems, but this book ambitiously and effectively works to simplify a complex but critical subject: concurrency. Java Concurrency in Practice is revolutionary in its approach, smooth and easy in style, and timely in its delivery—it’s destined to be a very important book. —Bruce Tate Author of Beyond Java Java Concurrency in Practice is an invaluable compilation of threading know-how for Java developers. I found reading this book intellectually exciting, in part be- cause it is an excellent introduction to Java’s concurrency API, but mostly because it captures in a thorough and accessible way expert knowledge on threading not easily found elsewhere. —Bill Venners Author of Inside the Java Virtual Machine Java Concurrency in Practice This page intentionally left blank Java Concurrency in Practice Brian Goetz with Tim Peierls Joshua Bloch Joseph Bowbeer David Holmes and Doug Lea Upper Saddle River, NJ Boston Indianapolis San Francisco New York Toronto Montreal London Munich Paris Madrid Capetown Sydney Tokyo Singapore Mexico City Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trade- marks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals. The authors and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein. The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding interests. For more information, please contact: U.S. Corporate and Government Sales (800) 382-3419 [email protected] For sales outside the United States, please contact: International Sales [email protected] Visit us on the Web: www.awprofessional.com This Book Is Safari Enabled The Safari® Enabled icon on the cover of your favorite technology book means the book is available through Safari Bookshelf. When you buy this book, you get free access to the online edition for 45 days. Safari Bookshelf is an electronic reference library that lets you easily search thousands of technical books, ﬁnd code samples, download chapters, and access technical information whenever and wherever you need it. To gain 45-day Safari Enabled access to this book: Go to http://www.awprofessional.com/safarienabled Complete the brief registration form Enter the coupon code UUIR-XRJG-JWWF-AHGM-137Z If you have difﬁculty registering on Safari Bookshelf or accessing the online edition, please e-mail customer-ser- [email protected]. Library of Congress Cataloging-in-Publication Data Goetz, Brian. Java Concurrency in Practice / Brian Goetz, with Tim Peierls... [et al.] p. cm. Includes bibliographical references and index. ISBN 0-321-34960-1 (pbk. : alk. paper) 1. Java (Computer program language) 2. Parallel programming (Computer science) 3. Threads (Computer programs) I. Title. QA76.73.J38G588 2006 005.13'3--dc22 2006012205 Copyright © 2006 Pearson Education, Inc. ISBN 0-321-34960-1 Text printed in the United States on recycled paper at Courier Stoughton in Stoughton, Massachusetts. 9th Printing March 2010 To Jessica This page intentionally left blank Contents Listings xii Preface xvii 1 Introduction 1 1.1 A (very) brief history of concurrency................... 1 1.2 Beneﬁts of threads............................. 3 1.3 Risks of threads............................... 5 1.4 Threads are everywhere.......................... 9 I Fundamentals 13 2 Thread Safety 15 2.1 What is thread safety?........................... 17 2.2 Atomicity................................... 19 2.3 Locking.................................... 23 2.4 Guarding state with locks......................... 27 2.5 Liveness and performance......................... 29 3 Sharing Objects 33 3.1 Visibility................................... 33 3.2 Publication and escape........................... 39 3.3 Thread conﬁnement............................ 42 3.4 Immutability................................. 46 3.5 Safe publication............................... 49 4 Composing Objects 55 4.1 Designing a thread-safe class....................... 55 4.2 Instance conﬁnement............................ 58 4.3 Delegating thread safety.......................... 62 4.4 Adding functionality to existing thread-safe classes.......... 71 4.5 Documenting synchronization policies.................. 74 ix x Contents 5 Building Blocks 79 5.1 Synchronized collections.......................... 79 5.2 Concurrent collections........................... 84 5.3 Blocking queues and the producer-consumer pattern......... 87 5.4 Blocking and interruptible methods................... 92 5.5 Synchronizers................................ 94 5.6 Building an efﬁcient, scalable result cache................ 101 II Structuring Concurrent Applications 111 6 Task Execution 113 6.1 Executing tasks in threads......................... 113 6.2 The Executor framework......................... 117 6.3 Finding exploitable parallelism...................... 123 7 Cancellation and Shutdown 135 7.1 Task cancellation.............................. 135 7.2 Stopping a thread-based service..................... 150 7.3 Handling abnormal thread termination................. 161 7.4 JVM shutdown............................... 164 8 Applying Thread Pools 167 8.1 Implicit couplings between tasks and execution policies....... 167 8.2 Sizing thread pools............................. 170 8.3 Conﬁguring ThreadPoolExecutor.................... 171 8.4 Extending ThreadPoolExecutor..................... 179 8.5 Parallelizing recursive algorithms.................... 181 9 GUI Applications 189 9.1 Why are GUIs single-threaded?...................... 189 9.2 Short-running GUI tasks.......................... 192 9.3 Long-running GUI tasks.......................... 195 9.4 Shared data models............................. 198 9.5 Other forms of single-threaded subsystems............... 202 III Liveness, Performance, and Testing 203 10 Avoiding Liveness Hazards 205 10.1 Deadlock................................... 205 10.2 Avoiding and diagnosing deadlocks................... 215 10.3 Other liveness hazards........................... 218 11 Performance and Scalability 221 11.1 Thinking about performance....................... 221 11.2 Amdahl’s law................................ 225 11.3 Costs introduced by threads........................ 229 11.4 Reducing lock contention......................... 232 Contents xi 11.5 Example: Comparing Map performance................. 242 11.6 Reducing context switch overhead.................... 243 12 Testing Concurrent Programs 247 12.1 Testing for correctness........................... 248 12.2 Testing for performance.......................... 260 12.3 Avoiding performance testing pitfalls.................. 266 12.4 Complementary testing approaches................... 270 IV Advanced Topics 275 13 Explicit Locks 277 13.1 Lock and ReentrantLock.......................... 277 13.2 Performance considerations........................ 282 13.3 Fairness.................................... 283 13.4 Choosing between synchronized and ReentrantLock......... 285 13.5 Read-write locks.............................. 286 14 Building Custom Synchronizers 291 14.1 Managing state dependence........................ 291 14.2 Using condition queues.......................... 298 14.3 Explicit condition objects.......................... 306 14.4 Anatomy of a synchronizer........................ 308 14.5 AbstractQueuedSynchronizer...................... 311 14.6 AQS in java.util.concurrent synchronizer classes......... 314 15 Atomic Variables and Nonblocking Synchronization 319 15.1 Disadvantages of locking......................... 319 15.2 Hardware support for concurrency.................... 321 15.3 Atomic variable classes........................... 324 15.4 Nonblocking algorithms.......................... 329 16 The Java Memory Model 337 16.1 What is a memory model, and why would I want one?........ 337 16.2 Publication.................................. 344 16.3 Initialization safety............................. 349 A Annotations for Concurrency 353 A.1 Class annotations.............................. 353 A.2 Field and method annotations....................... 353 Bibliography 355 Index 359 Listings 1 Bad way to sort a list. Don’t do this.................... xix 2 Less than optimal way to sort a list.................... xx 1.1 Non-thread-safe sequence generator................... 6 1.2 Thread-safe sequence generator...................... 7 2.1 A stateless servlet.............................. 18 2.2 Servlet that counts requests without the necessary synchroniza- tion. Don’t do this.............................. 19 2.3 Race condition in lazy initialization. Don’t do this........... 21 2.4 Servlet that counts requests using AtomicLong............. 23 2.5 Servlet that attempts to cache its last result without adequate atomicity. Don’t do this........................... 24 2.6 Servlet that caches last result, but with unnacceptably poor con- currency. Don’t do this............................ 26 2.7 Code that would deadlock if intrinsic locks were not reentrant.... 27 2.8 Servlet that caches its last request and result.............. 31 3.1 Sharing variables without synchronization. Don’t do this....... 34 3.2 Non-thread-safe mutable integer holder................. 36 3.3 Thread-safe mutable integer holder.................... 36 3.4 Counting sheep............................... 39 3.5 Publishing an object............................ 40 3.6 Allowing internal mutable state to escape. Don’t do this........ 40 3.7 Implicitly allowing the this reference to escape. Don’t do this.... 41 3.8 Using a factory method to prevent the this reference from escap- ing during construction.......................... 42 3.9 Thread conﬁnement of local primitive and reference variables.... 44 3.10 Using ThreadLocal to ensure thread conﬁnement........... 45 3.11 Immutable class built out of mutable underlying objects....... 47 3.12 Immutable holder for caching a number and its factors........ 49 3.13 Caching the last result using a volatile reference to an immutable holder object................................. 50 3.14 Publishing an object without adequate synchronization. Don’t do this...................................... 50 3.15 Class at risk of failure if not properly published............ 51 4.1 Simple thread-safe counter using the Java monitor pattern...... 56 4.2 Using conﬁnement to ensure thread safety............... 59 4.3 Guarding state with a private lock.................... 61 xii Listings xiii 4.4 Monitor-based vehicle tracker implementation............. 63 4.5 Mutable point class similar to java.awt.Point............. 64 4.6 Immutable Point class used by DelegatingVehicleTracker..... 64 4.7 Delegating thread safety to a ConcurrentHashMap........... 65 4.8 Returning a static copy of the location set instead of a “live” one.. 66 4.9 Delegating thread safety to multiple underlying state variables... 66 4.10 Number range class that does not sufﬁciently protect its invari- ants. Don’t do this.............................. 67 4.11 Thread-safe mutable point class...................... 69 4.12 Vehicle tracker that safely publishes underlying state......... 70 4.13 Extending Vector to have a put-if-absent method........... 72 4.14 Non-thread-safe attempt to implement put-if-absent. Don’t do this.. 72 4.15 Implementing put-if-absent with client-side locking.......... 73 4.16 Implementing put-if-absent using composition............. 74 5.1 Compound actions on a Vector that may produce confusing results. 80 5.2 Compound actions on Vector using client-side locking........ 81 5.3 Iteration that may throw ArrayIndexOutOfBoundsException..... 81 5.4 Iteration with client-side locking..................... 82 5.5 Iterating a List with an Iterator.................... 82 5.6 Iteration hidden within string concatenation. Don’t do this...... 84 5.7 ConcurrentMap interface.......................... 87 5.8 Producer and consumer tasks in a desktop search application.... 91 5.9 Starting the desktop search........................ 92 5.10 Restoring the interrupted status so as not to swallow the interrupt. 94 5.11 Using CountDownLatch for starting and stopping threads in timing tests...................................... 96 5.12 Using FutureTask to preload data that is needed later........ 97 5.13 Coercing an unchecked Throwable to a RuntimeException...... 98 5.14 Using Semaphore to bound a collection................. 100 5.15 Coordinating computation in a cellular automaton with Cyclic- Barrier.................................... 102 5.16 Initial cache attempt using HashMap and synchronization....... 103 5.17 Replacing HashMap with ConcurrentHashMap.............. 105 5.18 Memoizing wrapper using FutureTask................. 106 5.19 Final implementation of Memoizer.................... 108 5.20 Factorizing servlet that caches results using Memoizer......... 109 6.1 Sequential web server............................ 114 6.2 Web server that starts a new thread for each request.......... 115 6.3 Executor interface............................. 117 6.4 Web server using a thread pool...................... 118 6.5 Executor that starts a new thread for each task............ 118 6.6 Executor that executes tasks synchronously in the calling thread.. 119 6.7 Lifecycle methods in ExecutorService................. 121 6.8 Web server with shutdown support................... 122 6.9 Class illustrating confusing Timer behavior............... 124 6.10 Rendering page elements sequentially.................. 125 6.11 Callable and Future interfaces...................... 126 xiv Listings 6.12 Default implementation of newTaskFor in ThreadPoolExecutor... 126 6.13 Waiting for image download with Future................ 128 6.14 QueueingFuture class used by ExecutorCompletionService..... 129 6.15 Using CompletionService to render page elements as they be- come available................................ 130 6.16 Fetching an advertisement with a time budget............. 132 6.17 Requesting travel quotes under a time budget............. 134 7.1 Using a volatile ﬁeld to hold cancellation state............ 137 7.2 Generating a second’s worth of prime numbers............ 137 7.3 Unreliable cancellation that can leave producers stuck in a block- ing operation. Don’t do this......................... 139 7.4 Interruption methods in Thread...................... 139 7.5 Using interruption for cancellation.................... 141 7.6 Propagating InterruptedException to callers............. 143 7.7 Noncancelable task that restores interruption before exit....... 144 7.8 Scheduling an interrupt on a borrowed thread. Don’t do this..... 145 7.9 Interrupting a task in a dedicated thread................ 146 7.10 Cancelling a task using Future...................... 147 7.11 Encapsulating nonstandard cancellation in a Thread by overriding interrupt.................................. 149 7.12 Encapsulating nonstandard cancellation in a task with newTaskFor. 151 7.13 Producer-consumer logging service with no shutdown support... 152 7.14 Unreliable way to add shutdown support to the logging service... 153 7.15 Adding reliable cancellation to LogWriter................ 154 7.16 Logging service that uses an ExecutorService............. 155 7.17 Shutdown with poison pill......................... 156 7.18 Producer thread for IndexingService.................. 157 7.19 Consumer thread for IndexingService................. 157 7.20 Using a private Executor whose lifetime is bounded by a method call...................................... 158 7.21 ExecutorService that keeps track of cancelled tasks after shutdown.159 7.22 Using TrackingExecutorService to save unﬁnished tasks for later execution................................... 160 7.23 Typical thread-pool worker thread structure.............. 162 7.24 UncaughtExceptionHandler interface.................. 163 7.25 UncaughtExceptionHandler that logs the exception.......... 163 7.26 Registering a shutdown hook to stop the logging service....... 165 8.1 Task that deadlocks in a single-threaded Executor. Don’t do this... 169 8.2 General constructor for ThreadPoolExecutor.............. 172 8.3 Creating a ﬁxed-sized thread pool with a bounded queue and the caller-runs saturation policy........................ 175 8.4 Using a Semaphore to throttle task submission............. 176 8.5 ThreadFactory interface.......................... 176 8.6 Custom thread factory........................... 177 8.7 Custom thread base class......................... 178 8.8 Modifying an Executor created with the standard factories..... 179 8.9 Thread pool extended with logging and timing............ 180 Listings xv 8.10 Transforming sequential execution into parallel execution...... 181 8.11 Transforming sequential tail-recursion into parallelized recursion.. 182 8.12 Waiting for results to be calculated in parallel............. 182 8.13 Abstraction for puzzles like the “sliding blocks puzzle”........ 183 8.14 Link node for the puzzle solver framework............... 184 8.15 Sequential puzzle solver.......................... 185 8.16 Concurrent version of puzzle solver................... 186 8.17 Result-bearing latch used by ConcurrentPuzzleSolver........ 187 8.18 Solver that recognizes when no solution exists............. 188 9.1 Implementing SwingUtilities using an Executor.......... 193 9.2 Executor built atop SwingUtilities................... 194 9.3 Simple event listener............................ 194 9.4 Binding a long-running task to a visual component.......... 196 9.5 Long-running task with user feedback.................. 196 9.6 Cancelling a long-running task...................... 197 9.7 Background task class supporting cancellation, completion notiﬁ- cation, and progress notiﬁcation..................... 199 9.8 Initiating a long-running, cancellable task with BackgroundTask.. 200 10.1 Simple lock-ordering deadlock. Don’t do this.............. 207 10.2 Dynamic lock-ordering deadlock. Don’t do this............. 208 10.3 Inducing a lock ordering to avoid deadlock............... 209 10.4 Driver loop that induces deadlock under typical conditions..... 210 10.5 Lock-ordering deadlock between cooperating objects. Don’t do this. 212 10.6 Using open calls to avoiding deadlock between cooperating objects. 214 10.7 Portion of thread dump after deadlock................. 217 11.1 Serialized access to a task queue..................... 227 11.2 Synchronization that has no effect. Don’t do this............ 230 11.3 Candidate for lock elision......................... 231 11.4 Holding a lock longer than necessary.................. 233 11.5 Reducing lock duration.......................... 234 11.6 Candidate for lock splitting........................ 236 11.7 ServerStatus refactored to use split locks............... 236 11.8 Hash-based map using lock striping................... 238 12.1 Bounded buffer using Semaphore..................... 249 12.2 Basic unit tests for BoundedBuffer.................... 250 12.3 Testing blocking and responsiveness to interruption.......... 252 12.4 Medium-quality random number generator suitable for testing... 253 12.5 Producer-consumer test program for BoundedBuffer......... 255 12.6 Producer and consumer classes used in PutTakeTest......... 256 12.7 Testing for resource leaks......................... 258 12.8 Thread factory for testing ThreadPoolExecutor............ 258 12.9 Test method to verify thread pool expansion.............. 259 12.10 Using Thread.yield to generate more interleavings.......... 260 12.11 Barrier-based timer............................. 261 12.12 Testing with a barrier-based timer.................... 262 12.13 Driver program for TimedPutTakeTest................. 262 13.1 Lock interface................................ 277 xvi Listings 13.2 Guarding object state using ReentrantLock............... 278 13.3 Avoiding lock-ordering deadlock using tryLock............ 280 13.4 Locking with a time budget........................ 281 13.5 Interruptible lock acquisition....................... 281 13.6 ReadWriteLock interface.......................... 286 13.7 Wrapping a Map with a read-write lock................. 288 14.1 Structure of blocking state-dependent actions.............. 292 14.2 Base class for bounded buffer implementations............. 293 14.3 Bounded buffer that balks when preconditions are not met...... 294 14.4 Client logic for calling GrumpyBoundedBuffer.............. 294 14.5 Bounded buffer using crude blocking.................. 296 14.6 Bounded buffer using condition queues................. 298 14.7 Canonical form for state-dependent methods.............. 301 14.8 Using conditional notiﬁcation in BoundedBuffer.put......... 304 14.9 Recloseable gate using wait and notifyAll............... 305 14.10 Condition interface............................. 307 14.11 Bounded buffer using explicit condition variables........... 309 14.12 Counting semaphore implemented using Lock............. 310 14.13 Canonical forms for acquisition and release in AQS.......... 312 14.14 Binary latch using AbstractQueuedSynchronizer........... 313 14.15 tryAcquire implementation from nonfair ReentrantLock...... 315 14.16 tryAcquireShared and tryReleaseShared from Semaphore..... 316 15.1 Simulated CAS operation......................... 322 15.2 Nonblocking counter using CAS..................... 323 15.3 Preserving multivariable invariants using CAS............. 326 15.4 Random number generator using ReentrantLock........... 327 15.5 Random number generator using AtomicInteger........... 327 15.6 Nonblocking stack using Treiber’s algorithm (Treiber, 1986)..... 331 15.7 Insertion in the Michael-Scott nonblocking queue algorithm (Michael and Scott, 1996).......................... 334 15.8 Using atomic ﬁeld updaters in ConcurrentLinkedQueue....... 335 16.1 Insufﬁciently synchronized program that can have surprising re- sults. Don’t do this.............................. 340 16.2 Inner class of FutureTask illustrating synchronization piggybacking.343 16.3 Unsafe lazy initialization. Don’t do this.................. 345 16.4 Thread-safe lazy initialization....................... 347 16.5 Eager initialization............................. 347 16.6 Lazy initialization holder class idiom.................. 348 16.7 Double-checked-locking antipattern. Don’t do this........... 349 16.8 Initialization safety for immutable objects................ 350 Preface At this writing, multicore processors are just now becoming inexpensive enough for midrange desktop systems. Not coincidentally, many development teams are noticing more and more threading-related bug reports in their projects. In a recent post on the NetBeans developer site, one of the core maintainers observed that a single class had been patched over 14 times to ﬁx threading-related problems. Dion Almaer, former editor of TheServerSide, recently blogged (after a painful debugging session that ultimately revealed a threading bug) that most Java pro- grams are so rife with concurrency bugs that they work only “by accident”. Indeed, developing, testing and debugging multithreaded programs can be extremely difﬁcult because concurrency bugs do not manifest themselves pre- dictably. And when they do surface, it is often at the worst possible time—in production, under heavy load. One of the challenges of developing concurrent programs in Java is the mis- match between the concurrency features offered by the platform and how de- velopers need to think about concurrency in their programs. The language pro- vides low-level mechanisms such as synchronization and condition waits, but these mechanisms must be used consistently to implement application-level protocols or policies. Without such policies, it is all too easy to create programs that com- pile and appear to work but are nevertheless broken. Many otherwise excellent books on concurrency fall short of their goal by focusing excessively on low-level mechanisms and APIs rather than design-level policies and patterns. Java 5.0 is a huge step forward for the development of concurrent applica- tions in Java, providing new higher-level components and additional low-level mechanisms that make it easier for novices and experts alike to build concurrent applications. The authors are the primary members of the JCP Expert Group that created these facilities; in addition to describing their behavior and features, we present the underlying design patterns and anticipated usage scenarios that motivated their inclusion in the platform libraries. Our goal is to give readers a set of design rules and mental models that make it easier—and more fun—to build correct, performant concurrent classes and ap- plications in Java. We hope you enjoy Java Concurrency in Practice. Brian Goetz Williston, VT March 2006 xvii xviii Preface How to use this book To address the abstraction mismatch between Java’s low-level mechanisms and the necessary design-level policies, we present a simpliﬁed set of rules for writing concurrent programs. Experts may look at these rules and say “Hmm, that’s not entirely true: class C is thread-safe even though it violates rule R.” While it is possible to write correct programs that break our rules, doing so requires a deep understanding of the low-level details of the Java Memory Model, and we want developers to be able to write correct concurrent programs without having to master these details. Consistently following our simpliﬁed rules will produce correct and maintainable concurrent programs. We assume the reader already has some familiarity with the basic mecha- nisms for concurrency in Java. Java Concurrency in Practice is not an introduction to concurrency—for that, see the threading chapter of any decent introductory volume, such as The Java Programming Language (Arnold et al., 2005). Nor is it an encyclopedic reference for All Things Concurrency—for that, see Concurrent Programming in Java (Lea, 2000). Rather, it offers practical design rules to assist developers in the difﬁcult process of creating safe and performant concurrent classes. Where appropriate, we cross-reference relevant sections of The Java Pro- gramming Language, Concurrent Programming in Java, The Java Language Speciﬁcation (Gosling et al., 2005), and Effective Java (Bloch, 2001) using the conventions [JPL n.m], [CPJ n.m], [JLS n.m], and [EJ Item n]. After the introduction (Chapter 1), the book is divided into four parts: Fundamentals. Part I (Chapters 2-5) focuses on the basic concepts of con- currency and thread safety, and how to compose thread-safe classes out of the concurrent building blocks provided by the class library. A “cheat sheet” summa- rizing the most important of the rules presented in Part I appears on page 110. Chapters 2 (Thread Safety) and 3 (Sharing Objects) form the foundation for the book. Nearly all of the rules on avoiding concurrency hazards, constructing thread-safe classes, and verifying thread safety are here. Readers who prefer “practice” to “theory” may be tempted to skip ahead to Part II, but make sure to come back and read Chapters 2 and 3 before writing any concurrent code! Chapter 4 (Composing Objects) covers techniques for composing thread-safe classes into larger thread-safe classes. Chapter 5 (Building Blocks) covers the concurrent building blocks—thread-safe collections and synchronizers—provided by the platform libraries. Structuring Concurrent Applications. Part II (Chapters 6-9) describes how to exploit threads to improve the throughput or responsiveness of concurrent ap- plications. Chapter 6 (Task Execution) covers identifying parallelizable tasks and executing them within the task-execution framework. Chapter 7 (Cancellation and Shutdown) deals with techniques for convincing tasks and threads to ter- minate before they would normally do so; how programs deal with cancellation and shutdown is often one of the factors that separates truly robust concurrent applications from those that merely work. Chapter 8 (Applying Thread Pools) addresses some of the more advanced features of the task-execution framework. Preface xix Chapter 9 (GUI Applications) focuses on techniques for improving responsiveness in single-threaded subsystems. Liveness, Performance, and Testing. Part III (Chapters 10-12) concerns itself with ensuring that concurrent programs actually do what you want them to do and do so with acceptable performance. Chapter 10 (Avoiding Liveness Hazards) describes how to avoid liveness failures that can prevent programs from making forward progress. Chapter 11 (Performance and Scalability) covers techniques for improving the performance and scalability of concurrent code. Chapter 12 (Testing Concurrent Programs) covers techniques for testing concurrent code for both correctness and performance. Advanced Topics. Part IV (Chapters 13-16) covers topics that are likely to be of interest only to experienced developers: explicit locks, atomic variables, nonblocking algorithms, and developing custom synchronizers. Code examples While many of the general concepts in this book are applicable to versions of Java prior to Java 5.0 and even to non-Java environments, most of the code examples (and all the statements about the Java Memory Model) assume Java 5.0 or later. Some of the code examples may use library features added in Java 6. The code examples have been compressed to reduce their size and to high- light the relevant portions. The full versions of the code examples, as well as supplementary examples and errata, are available from the book’s website, http://www.javaconcurrencyinpractice.com. The code examples are of three sorts: “good” examples, “not so good” exam- ples, and “bad” examples. Good examples illustrate techniques that should be emulated. Bad examples illustrate techniques that should deﬁnitely not be em- ulated, and are identiﬁed with a “Mr. Yuk” icon1 to make it clear that this is “toxic” code (see Listing 1). Not-so-good examples illustrate techniques that are not necessarily wrong but are fragile, risky, or perform poorly, and are decorated with a “Mr. Could Be Happier” icon as in Listing 2. public task = taskExec.submit(r); try { task.get(timeout, unit); } catch (TimeoutException e) { // task will be cancelled below } catch (ExecutionException e) { // exception thrown in task; rethrow throw launderThrowable(e.getCause()); } finally { // Harmless if task already completed task.cancel(true); // interrupt if running } } Listing 7.10. Cancelling a task using Future. When Future.get throws InterruptedException or TimeoutExcep- tion and you know that the result is no longer needed by the program, cancel the task with Future.cancel. 7.1.6 Dealing with non-interruptible blocking Many blocking library methods respond to interruption by returning early and throwing InterruptedException, which makes it easier to build tasks that are responsive to cancellation. However, not all blocking methods or blocking mech- anisms are responsive to interruption; if a thread is blocked performing syn- chronous socket I/O or waiting to acquire an intrinsic lock, interruption has no effect other than setting the thread’s interrupted status. We can sometimes con- vince threads blocked in noninterruptible activities to stop by means similar to interruption, but this requires greater awareness of why the thread is blocked. 148 Chapter 7. Cancellation and Shutdown Synchronous socket I/O in java.io. The common form of blocking I/O in server applications is reading or writing to a socket. Unfortunately, the read and write methods in InputStream and OutputStream are not re- sponsive to interruption, but closing the underlying socket makes any threads blocked in read or write throw a SocketException. Synchronous I/O in java.nio. Interrupting a thread waiting on an Interrupt- ibleChannel causes it to throw ClosedByInterruptException and close the channel (and also causes all other threads blocked on the channel to throw ClosedByInterruptException). Closing an InterruptibleChannel causes threads blocked on channel operations to throw AsynchronousCloseExcep- tion. Most standard Channels implement InterruptibleChannel. Asynchronous I/O with Selector. If a thread is blocked in Selector.select (in java.nio.channels), calling close or wakeup causes it to return prema- turely. Lock acquisition. If a thread is blocked waiting for an intrinsic lock, there is nothing you can do to stop it short of ensuring that it eventually acquires the lock and makes enough progress that you can get its attention some other way. However, the explicit Lock classes offer the lockInterruptib- ly method, which allows you to wait for a lock and still be responsive to interrupts—see Chapter 13. ReaderThread in Listing 7.11 shows a technique for encapsulating nonstan- dard cancellation. ReaderThread manages a single socket connection, reading synchronously from the socket and passing any data received to processBuffer. To facilitate terminating a user connection or shutting down the server, Reader- Thread overrides interrupt to both deliver a standard interrupt and close the underlying socket; thus interrupting a ReaderThread makes it stop what it is do- ing whether it is blocked in read or in an interruptible blocking method. 7.1.7 Encapsulating nonstandard cancellation with newTaskFor The technique used in ReaderThread to encapsulate nonstandard cancellation can be reﬁned using the newTaskFor hook added to ThreadPoolExecutor in Java 6. When a Callable is submitted to an ExecutorService, submit returns a Future that can be used to cancel the task. The newTaskFor hook is a factory method that creates the Future representing the task. It returns a RunnableFuture, an interface that extends both Future and Runnable (and is implemented by FutureTask). Customizing the task Future allows you to override Future.cancel. Custom cancellation code can perform logging or gather statistics on cancellation, and can also be used to cancel activities that are not responsive to interruption. Read- erThread encapsulates cancellation of socket-using threads by overriding inter- rupt; the same can be done for tasks by overriding Future.cancel. CancellableTask in Listing 7.12 deﬁnes a CancellableTask interface that ex- tends Callable and adds a cancel method and a newTask factory method for 7.1. Task cancellation 149 public class ReaderThread extends Thread { private final Socket socket; private final InputStream in; public ReaderThread(Socket socket) throws IOException { this.socket = socket; this.in = socket.getInputStream(); } public void interrupt() { try { socket.close(); } catch (IOException ignored) { } finally { super.interrupt(); } } public void run() { try { byte[] buf = new byte[BUFSZ]; while (true) { int count = in.read(buf); if (count < 0) break; else if (count > 0) processBuffer(buf, count); } } catch (IOException e) { } } } Listing 7.11. Encapsulating nonstandard cancellation in a Thread by overriding interrupt. 150 Chapter 7. Cancellation and Shutdown constructing a RunnableFuture. CancellingExecutor extends ThreadPoolExec- utor, and overrides newTaskFor to let a CancellableTask create its own Future. SocketUsingTask implements CancellableTask and deﬁnes Future.cancel to close the socket as well as call super.cancel. If a SocketUsingTask is cancelled through its Future, the socket is closed and the executing thread is interrupted. This increases the task’s responsiveness to cancellation: not only can it safely call interruptible blocking methods while remaining responsive to cancellation, but it can also call blocking socket I/O methods. 7.2 Stopping a thread-based service Applications commonly create services that own threads, such as thread pools, and the lifetime of these services is usually longer than that of the method that creates them. If the application is to shut down gracefully, the threads owned by these services need to be terminated. Since there is no preemptive way to stop a thread, they must instead be persuaded to shut down on their own. Sensible encapsulation practices dictate that you should not manipulate a thread—interrupt it, modify its priority, etc.—unless you own it. The thread API has no formal concept of thread ownership: a thread is represented with a Thread object that can be freely shared like any other object. However, it makes sense to think of a thread as having an owner, and this is usually the class that created the thread. So a thread pool owns its worker threads, and if those threads need to be interrupted, the thread pool should take care of it. As with any other encapsulated object, thread ownership is not transitive: the application may own the service and the service may own the worker threads, but the application doesn’t own the worker threads and therefore should not attempt to stop them directly. Instead, the service should provide lifecycle methods for shutting itself down that also shut down the owned threads; then the application can shut down the service, and the service can shut down the threads. Executor- Service provides the shutdown and shutdownNow methods; other thread-owning services should provide a similar shutdown mechanism. Provide lifecycle methods whenever a thread-owning service has a lifetime longer than that of the method that created it. 7.2.1 Example: a logging service Most server applications use logging, which can be as simple as inserting println statements into the code. Stream classes like PrintWriter are thread-safe, so this simple approach would require no explicit synchronization.3 However, as 3. If you are logging multiple lines as part of a single log message, you may need to use additional client-side locking to prevent undesirable interleaving of output from multiple threads. If two threads logged multiline stack traces to the same stream with one println call per line, the results would be interleaved unpredictably, and could easily look like one large but meaningless stack trace. 7.2. Stopping a thread-based service 151 public interface CancellableTask extends Callable { void cancel(); RunnableFuture newTask(); } @ThreadSafe public class CancellingExecutor extends ThreadPoolExecutor {... protected RunnableFuture newTaskFor(Callable callable) { if (callable instanceof CancellableTask) return ((CancellableTask) callable).newTask(); else return super.newTaskFor(callable); } } public abstract class SocketUsingTask implements CancellableTask { @GuardedBy("this") private Socket socket; protected synchronized void setSocket(Socket s) { socket = s; } public synchronized void cancel() { try { if (socket != null) socket.close(); } catch (IOException ignored) { } } public RunnableFuture newTask() { return new FutureTask(this) { public boolean cancel(boolean mayInterruptIfRunning) { try { SocketUsingTask.this.cancel(); } finally { return super.cancel(mayInterruptIfRunning); } } }; } } Listing 7.12. Encapsulating nonstandard cancellation in a task with newTaskFor. 152 Chapter 7. Cancellation and Shutdown we’ll see in Section 11.6, inline logging can have some performance costs in high- volume applications. Another alternative is have the log call queue the log mes- sage for processing by another thread. LogWriter in Listing 7.13 shows a simple logging service in which the logging activity is moved to a separate logger thread. Instead of having the thread that produces the message write it directly to the output stream, LogWriter hands it off to the logger thread via a BlockingQueue and the logger thread writes it out. This is a multiple-producer, single-consumer design: any activity calling log is acting as a producer, and the background logger thread is the consumer. If the logger thread falls behind, the BlockingQueue eventually blocks the producers until the logger thread catches up. public class LogWriter { private final BlockingQueue queue; private final LoggerThread logger; public LogWriter(Writer writer) { this.queue = new LinkedBlockingQueue(CAPACITY); this.logger = new LoggerThread(writer); } public void start() { logger.start(); } public void log(String msg) throws InterruptedException { queue.put(msg); } private class LoggerThread extends Thread { private final PrintWriter writer;... public void run() { try { while (true) writer.println(queue.take()); } catch(InterruptedException ignored) { } finally { writer.close(); } } } } Listing 7.13. Producer-consumer logging service with no shutdown support. For a service like LogWriter to be useful in production, we need a way to terminate the logger thread so it does not prevent the JVM from shutting down 7.2. Stopping a thread-based service 153 normally. Stopping the logger thread is easy enough, since it repeatedly calls take, which is responsive to interruption; if the logger thread is modiﬁed to exit on catching InterruptedException, then interrupting the logger thread stops the service. However, simply making the logger thread exit is not a very satisfying shut- down mechanism. Such an abrupt shutdown discards log messages that might be waiting to be written to the log, but, more importantly, threads blocked in log because the queue is full will never become unblocked. Cancelling a producer- consumer activity requires cancelling both the producers and the consumers. In- terrupting the logger thread deals with the consumer, but because the producers in this case are not dedicated threads, cancelling them is harder. Another approach to shutting down LogWriter would be to set a “shutdown requested” ﬂag to prevent further messages from being submitted, as shown in Listing 7.14. The consumer could then drain the queue upon being notiﬁed that shutdown has been requested, writing out any pending messages and unblock- ing any producers blocked in log. However, this approach has race conditions that make it unreliable. The implementation of log is a check-then-act sequence: producers could observe that the service has not yet been shut down but still queue messages after the shutdown, again with the risk that the producer might get blocked in log and never become unblocked. There are tricks that reduce the likelihood of this (like having the consumer wait several seconds before declaring the queue drained), but these do not change the fundamental problem, merely the likelihood that it will cause a failure. public void log(String msg) throws InterruptedException { if (!shutdownRequested) queue.put(msg); else throw new IllegalStateException("logger is shut down"); } Listing 7.14. Unreliable way to add shutdown support to the logging service. The way to provide reliable shutdown for LogWriter is to ﬁx the race con- dition, which means making the submission of a new log message atomic. But we don’t want to hold a lock while trying to enqueue the message, since put could block. Instead, we can atomically check for shutdown and conditionally increment a counter to “reserve” the right to submit a message, as shown in Log- Service in Listing 7.15. 7.2.2 ExecutorService shutdown In Section 6.2.4, we saw that ExecutorService offers two ways to shut down: graceful shutdown with shutdown , and abrupt shutdown with shutdownNow. In an abrupt shutdown, shutdownNow returns the list of tasks that had not yet started after attempting to cancel all actively executing tasks. 154 Chapter 7. Cancellation and Shutdown public class LogService { private final BlockingQueue queue; private final LoggerThread loggerThread; private final PrintWriter writer; @GuardedBy("this") private boolean isShutdown; @GuardedBy("this") private int reservations; public void start() { loggerThread.start(); } public void stop() { synchronized (this) { isShutdown = true; } loggerThread.interrupt(); } public void log(String msg) throws InterruptedException { synchronized (this) { if (isShutdown) throw new IllegalStateException(...); ++reservations; } queue.put(msg); } private class LoggerThread extends Thread { public void run() { try { while (true) { try { synchronized (LogService.this) { if (isShutdown && reservations == 0) break; } String msg = queue.take(); synchronized (LogService.this) { --reservations; } writer.println(msg); } catch (InterruptedException e) { } } } finally { writer.close(); } } } } Listing 7.15. Adding reliable cancellation to LogWriter. 7.2. Stopping a thread-based service 155 The two different termination options offer a tradeoff between safety and re- sponsiveness: abrupt termination is faster but riskier because tasks may be in- terrupted in the middle of execution, and normal termination is slower but safer because the ExecutorService does not shut down until all queued tasks are proc- essed. Other thread-owning services should consider providing a similar choice of shutdown modes. Simple programs can get away with starting and shutting down a global Ex- ecutorService from main. More sophisticated programs are likely to encapsulate an ExecutorService behind a higher-level service that provides its own lifecycle methods, such as the variant of LogService in Listing 7.16 that delegates to an ExecutorService instead of managing its own threads. Encapsulating an Exec- utorService extends the ownership chain from application to service to thread by adding another link; each member of the chain manages the lifecycle of the services or threads it owns. public class LogService { private final ExecutorService exec = newSingleThreadExecutor();... public void start() { } public void stop() throws InterruptedException { try { exec.shutdown(); exec.awaitTermination(TIMEOUT, UNIT); } finally { writer.close(); } } public void log(String msg) { try { exec.execute(new WriteTask(msg)); } catch (RejectedExecutionException ignored) { } } } Listing 7.16. Logging service that uses an ExecutorService. 7.2.3 Poison pills Another way to convince a producer-consumer service to shut down is with a poison pill: a recognizable object placed on the queue that means “when you get this, stop.” With a FIFO queue, poison pills ensure that consumers ﬁnish the work on their queue before shutting down, since any work submitted prior to submitting the poison pill will be retrieved before the pill; producers should not submit any work after putting a poison pill on the queue. IndexingService in Listings 7.17, 7.18, and 7.19 shows a single-producer, single-consumer version of 156 Chapter 7. Cancellation and Shutdown public class IndexingService { private static final File POISON = new File(""); private final IndexerThread consumer = new IndexerThread(); private final CrawlerThread producer = new CrawlerThread(); private final BlockingQueue queue; private final FileFilter fileFilter; private final File root; class CrawlerThread extends Thread { } class IndexerThread extends Thread { } public void start() { producer.start(); consumer.start(); } public void stop() { producer.interrupt(); } public void awaitTermination() throws InterruptedException { consumer.join(); } } Listing 7.17. Shutdown with poison pill. the desktop search example from Listing 5.8 on page 91 that uses a poison pill to shut down the service. Poison pills work only when the number of producers and consumers is known. The approach in IndexingService can be extended to multiple producers by having each producer place a pill on the queue and having the consumer stop only when it receives Nproducers pills. It can be extended to multiple consumers by having each producer place Nconsumers pills on the queue, though this can get unwieldy with large numbers of producers and consumers. Poison pills work reliably only with unbounded queues. 7.2.4 Example: a one-shot execution service If a method needs to process a batch of tasks and does not return until all the tasks are ﬁnished, it can simplify service lifecycle management by using a private Executor whose lifetime is bounded by that method. (The invokeAll and in- vokeAny methods can often be useful in such situations.) The checkMail method in Listing 7.20 checks for new mail in parallel on a number of hosts. It creates a private executor and submits a task for each host: it then shuts down the executor and waits for termination, which occurs when all 7.2. Stopping a thread-based service 157 public class CrawlerThread extends Thread { public void run() { try { crawl(root); } catch (InterruptedException e) { } finally { while (true) { try { queue.put(POISON); break; } catch (InterruptedException e1) { } } } } private void crawl(File root) throws InterruptedException {... } } Listing 7.18. Producer thread for IndexingService. public class IndexerThread extends Thread { public void run() { try { while (true) { File file = queue.take(); if (file == POISON) break; else indexFile(file); } } catch (InterruptedException consumed) { } } } Listing 7.19. Consumer thread for IndexingService. 158 Chapter 7. Cancellation and Shutdown the mail-checking tasks have completed.4 boolean checkMail(Set hosts, long timeout, TimeUnit unit) throws InterruptedException { ExecutorService exec = Executors.newCachedThreadPool(); final AtomicBoolean hasNewMail = new AtomicBoolean(false); try { for (final String host : hosts) exec.execute(new Runnable() { public void run() { if (checkMail(host)) hasNewMail.set(true); } }); } finally { exec.shutdown(); exec.awaitTermination(timeout, unit); } return hasNewMail.get(); } Listing 7.20. Using a private Executor whose lifetime is bounded by a method call. 7.2.5 Limitations of shutdownNow When an ExecutorService is shut down abruptly with shutdownNow, it attempts to cancel the tasks currently in progress and returns a list of tasks that were sub- mitted but never started so that they can be logged or saved for later processing.5 However, there is no general way to ﬁnd out which tasks started but did not complete. This means that there is no way of knowing the state of the tasks in progress at shutdown time unless the tasks themselves perform some sort of checkpointing. To know which tasks have not completed, you need to know not only which tasks didn’t start, but also which tasks were in progress when the executor was shut down.6 TrackingExecutor in Listing 7.21 shows a technique for determining which tasks were in progress at shutdown time. By encapsulating an ExecutorSer- vice and instrumenting execute (and similarly submit , not shown) to remember 4. The reason an AtomicBoolean is used instead of a volatile boolean is that in order to access the hasNewMail ﬂag from the inner Runnable, it would have to be final, which would preclude modifying it. 5. The Runnable objects returned by shutdownNow might not be the same objects that were submitted to the ExecutorService: they might be wrapped instances of the submitted tasks. 6. Unfortunately, there is no shutdown option in which tasks not yet started are returned to the caller but tasks in progress are allowed to complete; such an option would eliminate this uncertain intermediate state. 7.2. Stopping a thread-based service 159 which tasks were cancelled after shutdown, TrackingExecutor can identify which tasks started but did not complete normally. After the executor terminates, get- CancelledTasks returns the list of cancelled tasks. In order for this technique to work, the tasks must preserve the thread’s interrupted status when they return, which well behaved tasks will do anyway. public class TrackingExecutor extends AbstractExecutorService { private final ExecutorService exec; private final Set tasksCancelledAtShutdown = Collections.synchronizedSet(new HashSet());... public List getCancelledTasks() { if (!exec.isTerminated()) throw new IllegalStateException(...); return new ArrayList(tasksCancelledAtShutdown); } public void execute(final Runnable runnable) { exec.execute(new Runnable() { public void run() { try { runnable.run(); } finally { if (isShutdown() && Thread.currentThread().isInterrupted()) tasksCancelledAtShutdown.add(runnable); } } }); } // delegate other ExecutorService methods to exec } Listing 7.21. ExecutorService that keeps track of cancelled tasks after shut- down. WebCrawler in Listing 7.22 shows an application of TrackingExecutor. The work of a web crawler is often unbounded, so if a crawler must be shut down we might want to save its state so it can be restarted later. CrawlTask provides a getPage method that identiﬁes what page it is working on. When the crawler is shut down, both the tasks that did not start and those that were cancelled are scanned and their URLs recorded, so that page-crawling tasks for those URLs can be added to the queue when the crawler restarts. TrackingExecutor has an unavoidable race condition that could make it yield false positives: tasks that are identiﬁed as cancelled but actually completed. This 160 Chapter 7. Cancellation and Shutdown public abstract class WebCrawler { private volatile TrackingExecutor exec; @GuardedBy("this") private final Set urlsToCrawl = new HashSet();... public synchronized void start() { exec = new TrackingExecutor( Executors.newCachedThreadPool()); for (URL url : urlsToCrawl) submitCrawlTask(url); urlsToCrawl.clear(); } public synchronized void stop() throws InterruptedException { try { saveUncrawled(exec.shutdownNow()); if (exec.awaitTermination(TIMEOUT, UNIT)) saveUncrawled(exec.getCancelledTasks()); } finally { exec = null; } } protected abstract List processPage(URL url); private void saveUncrawled(List uncrawled) { for (Runnable task : uncrawled) urlsToCrawl.add(((CrawlTask) task).getPage()); } private void submitCrawlTask(URL u) { exec.execute(new CrawlTask(u)); } private class CrawlTask implements Runnable { private final URL url;... public void run() { for (URL link : processPage(url)) { if (Thread.currentThread().isInterrupted()) return; submitCrawlTask(link); } } public URL getPage() { return url; } } } Listing 7.22. Using TrackingExecutorService to save unﬁnished tasks for later execution. 7.3. Handling abnormal thread termination 161 arises because the thread pool could be shut down between when the last instruc- tion of the task executes and when the pool records the task as complete. This is not a problem if tasks are idempotent (if performing them twice has the same ef- fect as performing them once), as they typically are in a web crawler. Otherwise, the application retrieving the cancelled tasks must be aware of this risk and be prepared to deal with false positives. 7.3 Handling abnormal thread termination It is obvious when a single-threaded console application terminates due to an uncaught exception—the program stops running and produces a stack trace that is very different from typical program output. Failure of a thread in a concur- rent application is not always so obvious. The stack trace may be printed on the console, but no one may be watching the console. Also, when a thread fails, the application may appear to continue to work, so its failure could go unno- ticed. Fortunately, there are means of both detecting and preventing threads from “leaking” from an application. The leading cause of premature thread death is RuntimeException. Because these exceptions indicate a programming error or other unrecoverable problem, they are generally not caught. Instead they propagate all the way up the stack, at which point the default behavior is to print a stack trace on the console and let the thread terminate. The consequences of abnormal thread death range from benign to disastrous, depending on the thread’s role in the application. Losing a thread from a thread pool can have performance consequences, but an application that runs well with a 50-thread pool will probably run ﬁne with a 49-thread pool too. But losing the event dispatch thread in a GUI application would be quite noticeable—the application would stop processing events and the GUI would freeze. OutOf- Time on page 124 showed a serious consequence of thread leakage: the service represented by the Timer is permanently out of commission. Just about any code can throw a RuntimeException. Whenever you call an- other method, you are taking a leap of faith that it will return normally or throw one of the checked exceptions its signature declares. The less familiar you are with the code being called, the more skeptical you should be about its behavior. Task-processing threads such as the worker threads in a thread pool or the Swing event dispatch thread spend their whole life calling unknown code through an abstraction barrier like Runnable, and these threads should be very skeptical that the code they call will be well behaved. It would be very bad if a service like the Swing event thread failed just because some poorly written event han- dler threw a NullPointerException. Accordingly, these facilities should call tasks within a try-catch block that catches unchecked exceptions, or within a try-finally block to ensure that if the thread exits abnormally the framework is informed of this and can take corrective action. This is one of the few times when you might want to consider catching RuntimeException—when you are calling unknown, untrusted code through an abstraction such as Runnable.7 7. There is some controversy over the safety of this technique; when a thread throws an unchecked 162 Chapter 7. Cancellation and Shutdown Listing 7.23 illustrates a way to structure a worker thread within a thread pool. If a task throws an unchecked exception, it allows the thread to die, but not before notifying the framework that the thread has died. The framework may then replace the worker thread with a new thread, or may choose not to because the thread pool is being shut down or there are already enough worker threads to meet current demand. ThreadPoolExecutor and Swing use this technique to ensure that a poorly behaved task doesn’t prevent subsequent tasks from execut- ing. If you are writing a worker thread class that executes submitted tasks, or calling untrusted external code (such as dynamically loaded plugins), use one of these approaches to prevent a poorly written task or plugin from taking down the thread that happens to call it. public void run() { Throwable thrown = null; try { while (!isInterrupted()) runTask(getTaskFromWorkQueue()); } catch (Throwable e) { thrown = e; } finally { threadExited(this, thrown); } } Listing 7.23. Typical thread-pool worker thread structure. 7.3.1 Uncaught exception handlers The previous section offered a proactive approach to the problem of unchecked exceptions. The Thread API also provides the UncaughtExceptionHandler fa- cility, which lets you detect when a thread dies due to an uncaught exception. The two approaches are complementary: taken together, they provide defense-in- depth against thread leakage. When a thread exits due to an uncaught exception, the JVM reports this event to an application-provided UncaughtExceptionHandler (see Listing 7.24); if no handler exists, the default behavior is to print the stack trace to System.err.8 exception, the entire application may possibly be compromised. But the alternative—shutting down the entire application—is usually not practical. 8. Before Java 5.0, the only way to control the UncaughtExceptionHandler was by subclassing ThreadGroup. In Java 5.0 and later, you can set an UncaughtExceptionHandler on a per-thread basis with Thread.setUncaughtExceptionHandler, and can also set the default UncaughtExceptionHand- ler with Thread.setDefaultUncaughtExceptionHandler. However, only one of these handlers is called—ﬁrst the JVM looks for a per-thread handler, then for a ThreadGroup handler. The default handler implementation in ThreadGroup delegates to its parent thread group, and so on up the chain until one of the ThreadGroup handlers deals with the uncaught exception or it bubbles up to the top- level thread group. The top-level thread group handler delegates to the default system handler (if one exists; the default is none) and otherwise prints the stack trace to the console. 7.3. Handling abnormal thread termination 163 public interface UncaughtExceptionHandler { void uncaughtException(Thread t, Throwable e); } Listing 7.24. UncaughtExceptionHandler interface. What the handler should do with an uncaught exception depends on your quality-of-service requirements. The most common response is to write an error message and stack trace to the application log, as shown in Listing 7.25. Handlers can also take more direct action, such as trying to restart the thread, shutting down the application, paging an operator, or other corrective or diagnostic action. public class UEHLogger implements Thread.UncaughtExceptionHandler { public void uncaughtException(Thread t, Throwable e) { Logger logger = Logger.getAnonymousLogger(); logger.log(Level.SEVERE, "Thread terminated with exception: " + t.getName(), e); } } Listing 7.25. UncaughtExceptionHandler that logs the exception. In long-running applications, always use uncaught exception handlers for all threads that at least log the exception. To set an UncaughtExceptionHandler for pool threads, provide a ThreadFac- tory to the ThreadPoolExecutor constructor. (As with all thread manipulation, only the thread’s owner should change its UncaughtExceptionHandler.) The stan- dard thread pools allow an uncaught task exception to terminate the pool thread, but use a try-finally block to be notiﬁed when this happens so the thread can be replaced. Without an uncaught exception handler or other failure notiﬁcation mechanism, tasks can appear to fail silently, which can be very confusing. If you want to be notiﬁed when a task fails due to an exception so that you can take some task-speciﬁc recovery action, either wrap the task with a Runnable or Callable that catches the exception or override the afterExecute hook in ThreadPoolEx- ecutor. Somewhat confusingly, exceptions thrown from tasks make it to the uncaught exception handler only for tasks submitted with execute ; for tasks submitted with submit , any thrown exception, checked or not, is considered to be part of the task’s return status. If a task submitted with submit terminates with an exception, it is rethrown by Future.get, wrapped in an ExecutionException. 164 Chapter 7. Cancellation and Shutdown 7.4 JVM shutdown The JVM can shut down in either an orderly or abrupt manner. An orderly shut- down is initiated when the last “normal” (nondaemon) thread terminates, some- one calls System.exit, or by other platform-speciﬁc means (such as sending a SIGINT or hitting Ctrl-C). While this is the standard and preferred way for the JVM to shut down, it can also be shut down abruptly by calling Runtime.halt or by killing the JVM process through the operating system (such as sending a SIGKILL ). 7.4.1 Shutdown hooks In an orderly shutdown, the JVM ﬁrst starts all registered shutdown hooks. Shut- down hooks are unstarted threads that are registered with Runtime.addShut- downHook. The JVM makes no guarantees on the order in which shutdown hooks are started. If any application threads (daemon or nondaemon) are still running at shutdown time, they continue to run concurrently with the shutdown process. When all shutdown hooks have completed, the JVM may choose to run ﬁnalizers if runFinalizersOnExit is true, and then halts. The JVM makes no attempt to stop or interrupt any application threads that are still running at shutdown time; they are abruptly terminated when the JVM eventually halts. If the shutdown hooks or ﬁnalizers don’t complete, then the orderly shutdown process “hangs” and the JVM must be shut down abruptly. In an abrupt shutdown, the JVM is not required to do anything other than halt the JVM; shutdown hooks will not run. Shutdown hooks should be thread-safe: they must use synchronization when accessing shared data and should be careful to avoid deadlock, just like any other concurrent code. Further, they should not make assumptions about the state of the application (such as whether other services have shut down already or all normal threads have completed) or about why the JVM is shutting down, and must therefore be coded extremely defensively. Finally, they should exit as quickly as possible, since their existence delays JVM termination at a time when the user may be expecting the JVM to terminate quickly. Shutdown hooks can be used for service or application cleanup, such as delet- ing temporary ﬁles or cleaning up resources that are not automatically cleaned up by the OS. Listing 7.26 shows how LogService in Listing 7.16 could register a shutdown hook from its start method to ensure the log ﬁle is closed on exit. Because shutdown hooks all run concurrently, closing the log ﬁle could cause trouble for other shutdown hooks who want to use the logger. To avoid this problem, shutdown hooks should not rely on services that can be shut down by the application or other shutdown hooks. One way to accomplish this is to use a single shutdown hook for all services, rather than one for each service, and have it call a series of shutdown actions. This ensures that shutdown actions execute sequentially in a single thread, thus avoiding the possibility of race conditions or deadlock between shutdown actions. This technique can be used whether or not you use shutdown hooks; executing shutdown actions sequentially rather than concurrently eliminates many potential sources of failure. In applications 7.4. JVM shutdown 165 public void start() { Runtime.getRuntime().addShutdownHook(new Thread() { public void run() { try { LogService.this.stop(); } catch (InterruptedException ignored) {} } }); } Listing 7.26. Registering a shutdown hook to stop the logging service. that maintain explicit dependency information among services, this technique can also ensure that shutdown actions are performed in the right order. 7.4.2 Daemon threads Sometimes you want to create a thread that performs some helper function but you don’t want the existence of this thread to prevent the JVM from shutting down. This is what daemon threads are for. Threads are divided into two types: normal threads and daemon threads. When the JVM starts up, all the threads it creates (such as garbage collector and other housekeeping threads) are daemon threads, except the main thread. When a new thread is created, it inherits the daemon status of the thread that created it, so by default any threads created by the main thread are also normal threads. Normal threads and daemon threads differ only in what happens when they exit. When a thread exits, the JVM performs an inventory of running threads, and if the only threads that are left are daemon threads, it initiates an orderly shutdown. When the JVM halts, any remaining daemon threads are abandoned— finally blocks are not executed, stacks are not unwound—the JVM just exits. Daemon threads should be used sparingly—few processing activities can be safely abandoned at any time with no cleanup. In particular, it is dangerous to use daemon threads for tasks that might perform any sort of I/O. Daemon threads are best saved for “housekeeping” tasks, such as a background thread that periodically removes expired entries from an in-memory cache. Daemon threads are not a good substitute for properly managing the life- cycle of services within an application. 7.4.3 Finalizers The garbage collector does a good job of reclaiming memory resources when they are no longer needed, but some resources, such as ﬁle or socket handles, must be explicitly returned to the operating system when no longer needed. To assist in 166 Chapter 7. Cancellation and Shutdown this, the garbage collector treats objects that have a nontrivial finalize method specially: after they are reclaimed by the collector, finalize is called so that persistent resources can be released. Since ﬁnalizers can run in a thread managed by the JVM, any state accessed by a ﬁnalizer will be accessed by more than one thread and therefore must be accessed with synchronization. Finalizers offer no guarantees on when or even if they run, and they impose a signiﬁcant performance cost on objects with nontriv- ial ﬁnalizers. They are also extremely difﬁcult to write correctly.9 In most cases, the combination of finally blocks and explicit close methods does a better job of resource management than ﬁnalizers; the sole exception is when you need to manage objects that hold resources acquired by native methods. For these reasons and others, work hard to avoid writing or using classes with ﬁnalizers (other than the platform library classes) [EJ Item 6]. Avoid ﬁnalizers. Summary End-of-lifecycle issues for tasks, threads, services, and applications can add com- plexity to their design and implementation. Java does not provide a preemptive mechanism for cancelling activities or terminating threads. Instead, it provides a cooperative interruption mechanism that can be used to facilitate cancellation, but it is up to you to construct protocols for cancellation and use them consistently. Using FutureTask and the Executor framework simpliﬁes building cancellable tasks and services. 9. See (Boehm, 2005) for some of the challenges involved in writing ﬁnalizers. Chapter 8 Applying Thread Pools Chapter 6 introduced the task execution framework, which simpliﬁes manage- ment of task and thread lifecycles and provides a simple and ﬂexible means for decoupling task submission from execution policy. Chapter 7 covered some of the messy details of service lifecycle that arise from using the task execution frame- work in real applications. This chapter looks at advanced options for conﬁguring and tuning thread pools, describes hazards to watch for when using the task exe- cution framework, and offers some more advanced examples of using Executor. 8.1 Implicit couplings between tasks and execution policies We claimed earlier that the Executor framework decouples task submission from task execution. Like many attempts at decoupling complex processes, this was a bit of an overstatement. While the Executor framework offers substantial ﬂexi- bility in specifying and modifying execution policies, not all tasks are compatible with all execution policies. Types of tasks that require speciﬁc execution policies include: Dependent tasks. The most well behaved tasks are independent: those that do not depend on the timing, results, or side effects of other tasks. When executing independent tasks in a thread pool, you can freely vary the pool size and conﬁguration without affecting anything but performance. On the other hand, when you submit tasks that depend on other tasks to a thread pool, you implicitly create constraints on the execution policy that must be carefully managed to avoid liveness problems (see Section 8.1.1). Tasks that exploit thread conﬁnement. Single-threaded executors make stronger promises about concurrency than do arbitrary thread pools. They guaran- tee that tasks are not executed concurrently, which allows you to relax the thread safety of task code. Objects can be conﬁned to the task thread, thus enabling tasks designed to run in that thread to access those objects without synchronization, even if those resources are not thread-safe. This forms an implicit coupling between the task and the execution policy—the tasks re- 167 168 Chapter 8. Applying Thread Pools quire their executor to be single-threaded.1 In this case, if you changed the Executor from a single-threaded one to a thread pool, thread safety could be lost. Response-time-sensitive tasks. GUI applications are sensitive to response time: users are annoyed at long delays between a button click and the correspond- ing visual feedback. Submitting a long-running task to a single-threaded executor, or submitting several long-running tasks to a thread pool with a small number of threads, may impair the responsiveness of the service managed by that Executor. Tasks that use ThreadLocal. ThreadLocal allows each thread to have its own pri- vate “version” of a variable. However, executors are free to reuse threads as they see ﬁt. The standard Executor implementations may reap idle threads when demand is low and add new ones when demand is high, and also re- place a worker thread with a fresh one if an unchecked exception is thrown from a task. ThreadLocal makes sense to use in pool threads only if the thread-local value has a lifetime that is bounded by that of a task; Thread- Local should not be used in pool threads to communicate values between tasks. Thread pools work best when tasks are homogeneous and independent. Mix- ing long-running and short-running tasks risks “clogging” the pool unless it is very large; submitting tasks that depend on other tasks risks deadlock unless the pool is unbounded. Fortunately, requests in typical network-based server applications—web servers, mail servers, ﬁle servers—usually meet these guide- lines. Some tasks have characteristics that require or preclude a speciﬁc exe- cution policy. Tasks that depend on other tasks require that the thread pool be large enough that tasks are never queued or rejected; tasks that exploit thread conﬁnement require sequential execution. Document these requirements so that future maintainers do not undermine safety or live- ness by substituting an incompatible execution policy. 8.1.1 Thread starvation deadlock If tasks that depend on other tasks execute in a thread pool, they can deadlock. In a single-threaded executor, a task that submits another task to the same executor and waits for its result will always deadlock. The second task sits on the work queue until the ﬁrst task completes, but the ﬁrst will not complete because it is 1. The requirement is not quite this strong; it would be enough to ensure only that tasks not exe- cute concurrently and provide enough synchronization so that the memory effects of one task are guaranteed to be visible to the next task—which is precisely the guarantee offered by newSingle- ThreadExecutor. 8.1. Implicit couplings 169 waiting for the result of the second task. The same thing can happen in larger thread pools if all threads are executing tasks that are blocked waiting for other tasks still on the work queue. This is called thread starvation deadlock, and can occur whenever a pool task initiates an unbounded blocking wait for some resource or condition that can succeed only through the action of another pool task, such as waiting for the return value or side effect of another task, unless you can guarantee that the pool is large enough. ThreadDeadlock in Listing 8.1 illustrates thread starvation deadlock. Render- PageTask submits two additional tasks to the Executor to fetch the page header and footer, renders the page body, waits for the results of the header and footer tasks, and then combines the header, body, and footer into the ﬁnished page. With a single-threaded executor, ThreadDeadlock will always deadlock. Similarly, tasks coordinating amongst themselves with a barrier could also cause thread starvation deadlock if the pool is not big enough. Whenever you submit to an Executor tasks that are not independent, be aware of the possibility of thread starvation deadlock, and document any pool sizing or conﬁguration constraints in the code or conﬁguration ﬁle where the Executor is conﬁgured. In addition to any explicit bounds on the size of a thread pool, there may also be implicit limits because of constraints on other resources. If your application uses a JDBC connection pool with ten connections and each task needs a database connection, it is as if your thread pool only has ten threads because tasks in excess of ten will block waiting for a connection. public class ThreadDeadlock { ExecutorService exec = Executors.newSingleThreadExecutor(); public class RenderPageTask implements Callable { public String call() throws Exception { Future header, footer; header = exec.submit(new LoadFileTask("header.html")); footer = exec.submit(new LoadFileTask("footer.html")); String page = renderBody(); // Will deadlock -- task waiting for result of subtask return header.get() + page + footer.get(); } } } Listing 8.1. Task that deadlocks in a single-threaded Executor. Don’t do this. 170 Chapter 8. Applying Thread Pools 8.1.2 Long-running tasks Thread pools can have responsiveness problems if tasks can block for extended periods of time, even if deadlock is not a possibility. A thread pool can become clogged with long-running tasks, increasing the service time even for short tasks. If the pool size is too small relative to the expected steady-state number of long- running tasks, eventually all the pool threads will be running long-running tasks and responsiveness will suffer. One technique that can mitigate the ill effects of long-running tasks is for tasks to use timed resource waits instead of unbounded waits. Most blocking meth- ods in the plaform libraries come in both untimed and timed versions, such as Thread.join, BlockingQueue.put, CountDownLatch.await, and Selector.sel- ect. If the wait times out, you can mark the task as failed and abort it or requeue it for execution later. This guarantees that each task eventually makes progress towards either successful or failed completion, freeing up threads for tasks that might complete more quickly. If a thread pool is frequently full of blocked tasks, this may also be a sign that the pool is too small. 8.2 Sizing thread pools The ideal size for a thread pool depends on the types of tasks that will be submit- ted and the characteristics of the deployment system. Thread pool sizes should rarely be hard-coded; instead pool sizes should be provided by a conﬁguration mechanism or computed dynamically by consulting Runtime.availableProc- essors. Sizing thread pools is not an exact science, but fortunately you need only avoid the extremes of “too big” and “too small”. If a thread pool is too big, then threads compete for scarce CPU and memory resources, resulting in higher memory usage and possible resource exhaustion. If it is too small, throughput suffers as processors go unused despite available work. To size a thread pool properly, you need to understand your computing envi- ronment, your resource budget, and the nature of your tasks. How many process- ors does the deployment system have? How much memory? Do tasks perform mostly computation, I/O, or some combination? Do they require a scarce re- source, such as a JDBC connection? If you have different categories of tasks with very different behaviors, consider using multiple thread pools so each can be tuned according to its workload. For compute-intensive tasks, an Ncpu -processor system usually achieves opti- mum utilization with a thread pool of Ncpu + 1 threads. (Even compute-intensive threads occasionally take a page fault or pause for some other reason, so an “ex- tra” runnable thread prevents CPU cycles from going unused when this happens.) For tasks that also include I/O or other blocking operations, you want a larger pool, since not all of the threads will be schedulable at all times. In order to size the pool properly, you must estimate the ratio of waiting time to compute time for your tasks; this estimate need not be precise and can be obtained through pro- ﬁling or instrumentation. Alternatively, the size of the thread pool can be tuned 8.3. Conﬁguring ThreadPoolExecutor 171 by running the application using several different pool sizes under a benchmark load and observing the level of CPU utilization. Given these deﬁnitions: Ncpu = number of CPUs Ucpu = target CPU utilization, 0 ≤ Ucpu ≤ 1 W = ratio of wait time to compute time C The optimal pool size for keeping the processors at the desired utilization is: W Nthreads = Ncpu ∗ Ucpu ∗ 1 + C You can determine the number of CPUs using Runtime : int N_CPUS = Runtime.getRuntime().availableProcessors(); Of course, CPU cycles are not the only resource you might want to manage using thread pools. Other resources that can contribute to sizing constraints are memory, ﬁle handles, socket handles, and database connections. Calculating pool size constraints for these types of resources is easier: just add up how much of that resource each task requires and divide that into the total quantity available. The result will be an upper bound on the pool size. When tasks require a pooled resource such as database connections, thread pool size and resource pool size affect each other. If each task requires a connec- tion, the effective size of the thread pool is limited by the connection pool size. Similarly, when the only consumers of connections are pool tasks, the effective size of the connection pool is limited by the thread pool size. 8.3 Conﬁguring ThreadPoolExecutor ThreadPoolExecutor provides the base implementation for the executors re- turned by the newCachedThreadPool, newFixedThreadPool, and newScheduled- ThreadExecutor factories in Executors. ThreadPoolExecutor is a ﬂexible, robust pool implementation that allows a variety of customizations. If the default execution policy does not meet your needs, you can instantiate a ThreadPoolExecutor through its constructor and customize it as you see ﬁt; you can consult the source code for Executors to see the execution policies for the default conﬁgurations and use them as a starting point. ThreadPoolExecutor has several constructors, the most general of which is shown in Listing 8.2. 8.3.1 Thread creation and teardown The core pool size, maximum pool size, and keep-alive time govern thread cre- ation and teardown. The core size is the target size; the implementation attempts to maintain the pool at this size even when there are no tasks to execute,2 and will 2. When a ThreadPoolExecutor is initially created, the core threads are not started immediately but instead as tasks are submitted, unless you call prestartAllCoreThreads. 172 Chapter 8. Applying Thread Pools public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue workQueue, ThreadFactory threadFactory, RejectedExecutionHandler handler) {... } Listing 8.2. General constructor for ThreadPoolExecutor. not create more threads than this unless the work queue is full.3 The maximum pool size is the upper bound on how many pool threads can be active at once. A thread that has been idle for longer than the keep-alive time becomes a candidate for reaping and can be terminated if the current pool size exceeds the core size. By tuning the core pool size and keep-alive times, you can encourage the pool to reclaim resources used by otherwise idle threads, making them available for more useful work. (Like everything else, this is a tradeoff: reaping idle threads incurs additional latency due to thread creation if threads must later be created when demand increases.) The newFixedThreadPool factory sets both the core pool size and the maxi- mum pool size to the requested pool size, creating the effect of inﬁnite timeout; the newCachedThreadPool factory sets the maximum pool size to Integer.MAX_- VALUE and the core pool size to zero with a timeout of one minute, creating the effect of an inﬁnitely expandable thread pool that will contract again when de- mand decreases. Other combinations are possible using the explicit ThreadPool- Executor constructor. 8.3.2 Managing queued tasks Bounded thread pools limit the number of tasks that can be executed concurrently. (The single-threaded executors are a notable special case: they guarantee that no tasks will execute concurrently, offering the possibility of achieving thread safety through thread conﬁnement.) We saw in Section 6.1.2 how unbounded thread creation could lead to insta- bility, and addressed this problem by using a ﬁxed-sized thread pool instead of creating a new thread for every request. However, this is only a partial solution; it is still possible for the application to run out of resources under heavy load, just harder. If the arrival rate for new requests exceeds

Java Concurrency in Practice PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue