1BListing and Image Index xi Listing 14.6.Bounded Buffer Using Condition Queues. 183 Listing 14.7.Canonical Form for State-dependent Methods. 184 Listing 14.8.Using Conditional Notification in BoundedBuffer.put. 186 Listing 14.9.Recloseable Gate Using wait and Notifyall 187 Listing 14.10.Condition Interface. 188 Listing 14.11.Bounded Buffer Using Explicit Condition Variables. 189 Listing 14.12.Counting Semaphore Implemented Using Lock. 190 Listing 14.13.Canonical Forms for Acquisition and Release in AQS. 191 Listing 14.14.Binary Latch Using AbstractQueuedsynchronizer. 192 Listing 14.15.tryacquire Implementation From Non-fair ReentrantLock. 193 Listing 14.16.tryacquireshared and tryreleaseshared from Semaphore. 193 Chapter 15.Atomic Variables and Non-blocking Synchronization 195 Listing 15.1.Simulated CAS Operation. 197 Listing 15.2.Non-blocking Counter Using CAS. 197 Listing 15.3.Preserving Multivariable Invariants Using CAS 199 Figure 15.1.Lock and AtomicInteger Performance Under High Contention. 200 Figure 15.2.Lock and AtomicInteger Performance Under Moderate Contention. 200 Listing 15.4.Random Number Generator Using ReentrantLock. 200 Listing 15.5.Random Number Generator Using Atomi cInteger. 201 Listing 15.6.Non-blocking Stack Using Treiber's Algorithm(Treiber,1986). 203 Figure 15.3.Queue with Two Elements in Quiescent State. 203 Figure 15.4.Queue in Intermediate State During Insertion. 204 Figure 15.5.Queue Again in Quiescent State After Insertion is Complete. 204 Listing 15.7.Insertion in the Michael-Scott Non-blocking Queue Algorithm (Michael and Scott,1996). 205 Listing 15.8.Using Atomic Field Updaters in ConcurrentLinkedQueue. 205 Chapter 16.The Jaya Memory Model 20Z Figure 16.1.Interleaving Showing Reordering in PossibleReordering. 208 Listing 16.1.Insufficiently Synchronized Program that can have Surprising Results.Don't Do this. 209 Figure 16.2.Illustration of Happens-before in the Java Memory Model. 210 Listing 16.2.Inner Class of FutureTask Illustrating Synchronization Piggybacking. 211 Listing 16.3.Unsafe Lazy Initialization.Don't Do this. 212 Listing 16.4.Thread-safe Lazy Initialization. 213 Listing 16.5.Eager Initialization. 213 Listing 16.6.Lazy Initialization Holder Class Idiom. 213 Listing 16.7.Double-checked-locking Anti-pattern.Don't Do this. 214 Listing 16.8.Initialization Safety for Immutable Objects. 215
1BListing and Image Index xi Listing 14.6. Bounded Buffer Using Condition Queues. 183 Listing 14.7. Canonical Form for StateͲdependent Methods. 184 Listing 14.8. Using Conditional Notification in BoundedBuffer.put. 186 Listing 14.9. Recloseable Gate Using Wait and Notifyall. 187 Listing 14.10. Condition Interface. 188 Listing 14.11. Bounded Buffer Using Explicit Condition Variables. 189 Listing 14.12. Counting Semaphore Implemented Using Lock. 190 Listing 14.13. Canonical Forms for Acquisition and Release in AQS. 191 Listing 14.14. Binary Latch Using AbstractQueuedSynchronizer. 192 Listing 14.15. tryAcquire Implementation From NonͲfair ReentrantLock. 193 Listing 14.16. tryacquireshared and tryreleaseshared from Semaphore. 193 Chapter 15. Atomic Variables and Non-blocking Synchronization 195 Listing 15.1. Simulated CAS Operation. 197 Listing 15.2. NonͲblocking Counter Using CAS. 197 Listing 15.3. Preserving Multivariable Invariants Using CAS. 199 Figure 15.1. Lock and AtomicInteger Performance Under High Contention. 200 Figure 15.2. Lock and AtomicInteger Performance Under Moderate Contention. 200 Listing 15.4. Random Number Generator Using ReentrantLock. 200 Listing 15.5. Random Number Generator Using AtomicInteger. 201 Listing 15.6. NonͲblocking Stack Using Treiber's Algorithm (Treiber, 1986). 203 Figure 15.3. Queue with Two Elements in Quiescent State. 203 Figure 15.4. Queue in Intermediate State During Insertion. 204 Figure 15.5. Queue Again in Quiescent State After Insertion is Complete. 204 Listing 15.7. Insertion in the MichaelͲScott NonͲblocking Queue Algorithm (Michael and Scott, 1996). 205 Listing 15.8. Using Atomic Field Updaters in ConcurrentLinkedQueue. 205 Chapter 16. The Java Memory Model 207 Figure 16.1. Interleaving Showing Reordering in PossibleReordering. 208 Listing 16.1. Insufficiently Synchronized Program that can have Surprising Results. Don't Do this. 209 Figure 16.2. Illustration of HappensͲbefore in the Java Memory Model. 210 Listing 16.2. Inner Class of FutureTask Illustrating Synchronization Piggybacking. 211 Listing 16.3. Unsafe Lazy Initialization. Don't Do this. 212 Listing 16.4. ThreadͲsafe Lazy Initialization. 213 Listing 16.5. Eager Initialization. 213 Listing 16.6. Lazy Initialization Holder Class Idiom. 213 Listing 16.7. DoubleͲcheckedͲlocking AntiͲpattern. Don't Do this. 214 Listing 16.8. Initialization Safety for Immutable Objects. 215
2BPreface xiii Preface At this writing,multi-core 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
2BPreface xiii Preface At this writing, multiͲcore 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
xiv Java Concurrency In Practice 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 Il,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 ll(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 separate 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 responsiveness in single-threaded subsystems. Liveness,Performance,and Testing.Part Ill (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,non-blocking 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(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.CouldBeHappier"icon as in Listing 2. [1]Mr.Yuk is a registered trademark of the Children's Hospital of Pittsburgh and appears by permission Listing 1.Bad Way to Sort a List.Don't Do this. public <T extends comparable<?super T>>void sort(List<T>list){ /Never returns the wrong answer! system.exit(O); 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
xiv Java Concurrency In Practice 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 separate 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 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, nonͲblocking 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[1] 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. CouldBeHappier" icon as in Listing 2. [1] Mr. Yuk is a registered trademark of the Children's Hospital of Pittsburgh and appears by permission. Listing 1. Bad Way to Sort a List. Don't Do this. public <T extends Comparable<? super T>> void sort(List<T> list) { // Never returns the wrong answer! System.exit(0); } 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.
2BPreface XV Listing 2.Less than Optimal Way to Sort a List. public <T.extends comparable<?super T>>void sort(List<T>list){ for (inti=0;i<1000000;i++) doNothingO; Collections.sort(list); Acknowledgments This book grew out of the development process for the java.util.concurrent package that was created by the Java Community Process JSR 166 for inclusion in Java 5.0.Many others contributed to JSR 166;in particular we thank Martin Buchholz for doing all the work related to getting the code into the JDK,and all the readers of the concurrency- interest mailing list who offered their suggestions and feedback on the draft APls. This book has been tremendously improved by the suggestions and assistance of a small army of reviewers,advisors, cheerleaders,and armchair critics.We would like to thank Dion Almaer,Tracy Bialik,Cindy Bloch,Martin Buchholz,Paul Christmann,Cliff Click,Stuart Halloway,David Hovemeyer,Jason Hunter,Michael Hunter,Jeremy Hylton,Heinz Kabutz, Robert Kuhar,Ramnivas Laddad,Jared Levy,Nicole Lewis,Victor Luchangco,Jeremy Manson,Paul Martin,Berna Massingill,Michael Maurer,Ted Neward,Kirk Pepperdine,Bill Pugh,Sam Pullara,Russ Rufer,Bill Scherer,Jeffrey Siegal, Bruce Tate,Gil Tene,Paul Tyma,and members of the Silicon Valley Patterns Group who,through many interesting technical conversations,offered guidance and made suggestions that helped make this book better. We are especially grateful to Cliff Biffle,Barry Hayes,Dawid Kurzyniec,Angelika Langer,Doron Rajwan,and Bill Venners, who reviewed the entire manuscript in excruciating detail,found bugs in the code examples,and suggested numerous improvements. We thank Katrina Avery for a great copy-editing job and Rosemary Simpson for producing the index under unreasonable time pressure.We thank Ami Dewar for doing the illustrations. Thanks to the whole team at Addison-Wesley who helped make this book a reality.Ann Sellers got the project launched and Greg Doench shepherded it to a smooth completion;Elizabeth Ryan guided it through the production process. We would also like to thank the thousands of software engineers who contributed indirectly by creating the software used to create this book,including TEX,LATEX,Adobe Acrobat,pic,grap,Adobe Illustrator,Perl,Apache Ant,IntelliJ IDEA,GNU emacs,Subversion,TortoiseSVN,and of course,the Java platform and class libraries
2BPreface xv Listing 2. Less than Optimal Way to Sort a List. public <T extends Comparable<? super T>> void sort(List<T> list) { for (int i=0; i<1000000; i++) doNothing(); Collections.sort(list); } Acknowledgments This book grew out of the development process for the java.util.concurrent package that was created by the Java Community Process JSR 166 for inclusion in Java 5.0. Many others contributed to JSR 166; in particular we thank Martin Buchholz for doing all the work related to getting the code into the JDK, and all the readers of the concurrencyinterest mailing list who offered their suggestions and feedback on the draft APIs. This book has been tremendously improved by the suggestions and assistance of a small army of reviewers, advisors, cheerleaders, and armchair critics. We would like to thank Dion Almaer, Tracy Bialik, Cindy Bloch, Martin Buchholz, Paul Christmann, Cliff Click, Stuart Halloway, David Hovemeyer, Jason Hunter, Michael Hunter, Jeremy Hylton, Heinz Kabutz, Robert Kuhar, Ramnivas Laddad, Jared Levy, Nicole Lewis, Victor Luchangco, Jeremy Manson, Paul Martin, Berna Massingill, Michael Maurer, Ted Neward, Kirk Pepperdine, Bill Pugh, Sam Pullara, Russ Rufer, Bill Scherer, Jeffrey Siegal, Bruce Tate, Gil Tene, Paul Tyma, and members of the Silicon Valley Patterns Group who, through many interesting technical conversations, offered guidance and made suggestions that helped make this book better. We are especially grateful to Cliff Biffle, Barry Hayes, Dawid Kurzyniec, Angelika Langer, Doron Rajwan, and Bill Venners, who reviewed the entire manuscript in excruciating detail, found bugs in the code examples, and suggested numerous improvements. We thank Katrina Avery for a great copyͲediting job and Rosemary Simpson for producing the index under unreasonable time pressure. We thank Ami Dewar for doing the illustrations. Thanks to the whole team at AddisonͲWesley who helped make this book a reality. Ann Sellers got the project launched and Greg Doench shepherded it to a smooth completion; Elizabeth Ryan guided it through the production process. We would also like to thank the thousands of software engineers who contributed indirectly by creating the software used to create this book, including TEX, LATEX, Adobe Acrobat, pic, grap, Adobe Illustrator, Perl, Apache Ant, IntelliJ IDEA, GNU emacs, Subversion, TortoiseSVN, and of course, the Java platform and class libraries
3BChapter 1-Introduction-10B1.1.A(Very)Brief History of Concurrency Chapter 1-Introduction Writing correct programs is hard;writing correct concurrent programs is harder.There are simply more things that can go wrong in a concurrent program than in a sequential one.So,why do we bother with concurrency?Threads are an inescapable feature of the Java language,and they can simplify the development of complex systems by turning complicated asynchronous code into simpler straight-line code.In addition,threads are the easiest way to tap the computing power of multiprocessor systems.And,as processor counts increase,exploiting concurrency effectively will only become more important
3BChapter 1Ͳ Introduction Ͳ 10B1.1. A (Very) Brief History of Concurrency 1 Chapter 1ǦIntroduction Writing correct programs is hard; writing correct concurrent programs is harder. There are simply more things that can go wrong in a concurrent program than in a sequential one. So, why do we bother with concurrency? Threads are an inescapable feature of the Java language, and they can simplify the development of complex systems by turning complicated asynchronous code into simpler straightͲline code. In addition, threads are the easiest way to tap the computing power of multiprocessor systems. And, as processor counts increase, exploiting concurrency effectively will only become more important.