Java Concurrency in Practice / Edition 1

by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes

Overview

"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 maintaining, 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 filled 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 difficult 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 because 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

Threads are a fundamental part of the Java platform. As multicore processors become the norm, using concurrency effectively becomes essential for building high-performance applications. Java SE 5 and 6 are a huge step forward for the development of concurrent applications, with improvements to the Java Virtual Machine to support high-performance, highly scalable concurrent classes and a rich set of new concurrency building blocks. In Java Concurrency in Practice, the creators of these new facilities explain not only how they work and how to use them, but also the motivation and design patterns behind them.

However, developing, testing, and debugging multithreaded programs can still be very difficult; it is all too easy to create concurrent programs that appear to work, but fail when it matters most: in production, under heavy load. Java Concurrency in Practice arms readers with both the theoretical underpinnings and concrete techniques for building reliable, scalable, maintainable concurrent applications. Rather than simply offering an inventory of concurrency APIs and mechanisms, it provides design rules, patterns, and mental models that make it easier to build concurrent programs that are both correct and performant.

This book covers:

• Basic concepts of concurrency and thread safety
• Techniques for building and composing thread-safe classes
• Using the concurrency building blocks in java.util.concurrent
• Performance optimization dos and don'ts
• Testing concurrent programs
• Advanced topics such as atomic variables, nonblocking algorithms, and the Java Memory Model

Product Details

ISBN-13:	9780321349606
Publisher:	Pearson Education
Publication date:	05/09/2006
Pages:	432
Sales rank:	910,047
Product dimensions:	7.00(w) x 9.20(h) x 1.20(d)

About the Author

Brian Goetz is a software consultant with twenty years industry experience, with over 75 articles on Java development. He is one of the primary members of the Java Community Process JSR 166 Expert Group (Concurrency Utilities), and has served on numerous other JCP Expert Groups.

Tim Peierls is the very model of a modern multiprocessor, with BoxPop.biz, recording arts, and goings on theatrical. He is one of the primary members of the Java Community Process JSR 166 Expert Group (Concurrency Utilities), and has served on numerous other JCP Expert Groups.

Joshua Bloch is a principal engineer at Google and a Jolt Award-winner. He was previously a distinguished engineer at Sun Microsystems and a senior systems designer at Transarc. Josh led the design and implementation of numerous Java platform features, including JDK 5.0 language enhancements and the award-winning Java Collections Framework. He holds a Ph.D. in computer science from Carnegie Mellon University.

Joseph Bowbeer is a software architect at Vizrea Corporation where he specializes in mobile application development for the Java ME platform, but his fascination with concurrent programming began in his days at Apollo Computer. He served on the JCP Expert Group for JSR-166 (Concurrency Utilities).

David Holmes is director of DLTeCH Pty Ltd, located in Brisbane, Australia. He specializes in synchronization and concurrency and was a member of the JSR-166 expert group that developed the new concurrency utilities. He is also a contributor to the update of the Real-Time Specification for Java, and has spent the past few years working on an implementation of that specification.

Doug Lea is one of the foremost experts on object-oriented technology and software reuse. He has been doing collaborative research with Sun Labs for more than five years. Lea is Professor of Computer Science at SUNY Oswego, Co-director of the Software Engineering Lab at the New York Center for Advanced Technology in Computer Applications, and Adjunct Professor of Electrical and Computer Engineering at Syracuse University. In addition, he co-authored the book, Object-Oriented System Development (Addison-Wesley, 1993). He received his B.A., M.A., and Ph.D. from the University of New Hampshire.

Read an Excerpt

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 fix 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 programs are so rife with concurrency bugs that they work only "by accident". Indeed, developing, testing and debugging multithreaded programs can be extremely difficult because concurrency bugs do not manifest themselves predictably. 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 mismatch between the concurrency features offered by the platform and how developers need to think about concurrency in their programs. The language provides 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 compile 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 applications in Java, providingnew 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 applications in Java.

We hope you enjoy Java Concurrency in Practice.

Brian Goetz
Williston, VT
March 2006How to use this book

To address the abstraction mismatch between Java's low-level mechanisms and the necessary design-level policies, we present a simplified 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 simplified rules will produce correct and maintainable concurrent programs.

We assume the reader already has some familiarity with the basic mechanisms 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 difficult process of creating safe and performant concurrent classes. Where appropriate, we cross-reference relevant sections of The Java Programming Language, Concurrent Programming in Java, The Java Language Specification (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 concurrency and thread safety, and how to compose thread-safe classes out of the concurrent building blocks provided by the class library. A "cheat sheet" summarizing 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 applications. 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 terminate 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.

Chapter 9 (GUI Applications) focuses on techniques for improving responsivenessin 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 highlight 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" examples, and "bad" examples. Good examples illustrate techniques that should be emulated. Bad examples illustrate techniques that should definitely not be emulated, and are identified with a "Mr. Yuk" icon to make it clear that this is "toxic" code. 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 BeHappier" icon.

Some readers may question the role of the "bad" examples in this book; after all, a book should show how to do things right, not wrong. The bad examples have two purposes. They illustrate common pitfalls, but more importantly they demonstrate how to analyze a program for thread safety—and the best way to do that is to see the ways in which thread safety is compromised.

Table of Contents

Listings xii
Preface xvii

Chapter 1: Introduction 1

1.1 A (very) brief history of concurrency 1
1.2 Benefits of threads 3
1.3 Risks of threads 5
1.4 Threads are everywhere 9

Part I: Fundamentals 13

Chapter 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

Chapter 3: Sharing Objects 33

3.1 Visibility 33
3.2 Publication and escape 39
3.3 Thread confinement 42
3.4 Immutability 46
3.5 Safepublication 49

Chapter 4: Composing Objects 55

4.1 Designing a thread-safe class 55
4.2 Instance confinement 58
4.3 Delegating thread safety 62
4.4 Adding functionality to existing thread-safe classes 71
4.5 Documenting synchronization policies 74

Chapter 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 efficient, scalable result cache 101

Part II: Structuring Concurrent Applications 111

Chapter 6: Task Execution 113

6.1 Executing tasks in threads 113
6.2 The Executor framework 117
6.3 Finding exploitable parallelism 123

Chapter 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

Chapter 8: Applying Thread Pools 167

8.1 Implicit couplings between tasks and execution policies 167
8.2 Sizing thread pools 170
8.3 Configuring ThreadPoolExecutor 171
8.4 Extending ThreadPoolExecutor 179
8.5 Parallelizing recursive algorithms 181

Chapter 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

Part III: Liveness, Performance, and Testing 203

Chapter 10: Avoiding Liveness Hazards 205

10.1 Deadlock 205
10.2 Avoiding and diagnosing deadlocks 215
10.3 Other liveness hazards 218

Chapter 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
11.5 Example: Comparing Map performance 242
11.6 Reducing context switch overhead 243

Chapter 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

Part IV: Advanced Topics 275

Chapter 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

Chapter 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

Chapter15: 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

Chapter 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

Appendix A: Annotations for Concurrency 353

A.1 Class annotations 353
A.2 Field andmethod annotations 353

Bibliography 355
Index 359

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 fix 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 programs are so rife with concurrency bugs that they work only 'by accident'. Indeed, developing, testing and debugging multithreaded programs can be extremely difficult because concurrency bugs do not manifest themselves predictably. 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 mismatch between the concurrency features offered by the platform and how developers need to think about concurrency in their programs. The language provides 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 compile 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 applications 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 applications in Java.

We hope you enjoy Java Concurrency in Practice.

Brian Goetz
Williston, VT
March 2006

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 simplified 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 simplified rules will produce correct and maintainable concurrent programs.

We assume the reader already has some familiarity with the basic mechanisms 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 difficult process of creating safe and performant concurrent classes. Where appropriate, we cross-reference relevant sections of The Java Programming Language, Concurrent Programming in Java, The Java Language Specification (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 concurrency and thread safety, and how to compose thread-safe classes out of the concurrent building blocks provided by the class library. A 'cheat sheet' summarizing 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 applications. 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 terminate 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.

Chapter 9 (GUI Applications) focuses on techniques for improving responsivenessin 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 highlight 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' examples, and 'bad' examples. Good examples illustrate techniques that should be emulated. Bad examples illustrate techniques that should definitely not be emulated, and are identified with a 'Mr. Yuk' icon to make it clear that this is 'toxic' code. 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 BeHappier' icon.

Some readers may question the role of the 'bad' examples in this book; after all, a book should show how to do things right, not wrong. The bad examples have two purposes. They illustrate common pitfalls, but more importantly they demonstrate how to analyze a program for thread safety—and the best way to do that is to see the ways in which thread safety is compromised.