Java Concurrency In Practice Brian Gδetz Tim Peierls Joshua Bloch Joseph Bowbeer David Holmes Doug Lea Addison-Wesley Professional 1SBN-10:0-321-34960-1 1SBN-13:978-0-321-34960-6
Java Concurrency In Practice Brian Göetz Tim Peierls Joshua Bloch Joseph Bowbeer David Holmes Doug Lea AddisonͲWesley Professional ISBNͲ10: 0Ͳ321Ͳ34960Ͳ1 ISBNͲ13: 978Ͳ0Ͳ321Ͳ34960Ͳ6
Java Concurrency In Practice Index Index ii Preface xiii How to Use this Book 诚 Code Examples xiv Acknowledaments Chapter 1-Introduction 1 1.1.A(Very)Brief History of Concurrency 2 1.2.Benefits of Threads 3 1.2:1Exploiting Multiple processors 12:2 Simplicity of Modelina 3 3 1.2.3.Simplified Handling of Asvnchronous Events 1.2.4.More Responsive User Interfaces 1.3.Risks of Threads 5 1.3.1.Safety.Hazards. 1.3.2.Liveness Hazards. 、 1.3.3.Performance Hazards 1.4.Threads are Everywhere 8 Part l:Fundamentals 10 Chapter 2.Thread Safety 11 2.1.What is Thread Safety? 12 2.2.Atomicity. 13 2.3.40 cking.… 2.4.Guarding State with Locks 6 19 2.5.Liveness and Performance …20 Chapter 3.Sharing Objects 23 3-visibility 23 3.2.Publication and Escape 2 3.3..Thread Confinement... .…28 3.4.Immutability 31 3.5.Safe Publication 33 Chapter 4.Composing Objects 37 4.1.Designing a Thread-safe Class. 37 4.2:.Instance confinement 39 4.3.Delegating Thread Safety 42 4.4.Adding Functionality to Existina.Thread-safe.Classes. 47 4.5.Documentina Synchronization policies 49 Chapter 5.Building Blocks 51 5.1.Svnchronized Collections. .51 5.2.Concurrent Collections 54 5.3.Blocking Queues and the Producer-consumer Pattern.. 55 5.4.Blocking and Interruptible Methods 5.5.Svnchron.ie...… 0 5.6.Building an Efficient,Scalable Result Cache 64 Summary of Part 1 .59
ii Java Concurrency In Practice Index Index ii Preface xiii How to Use this Book xiii Code Examples xiv Acknowledgments xv Chapter 1 - Introduction 1 1.1. A (Very) Brief History of Concurrency 2 1.2. Benefits of Threads 3 1.2.1. Exploiting Multiple Processors 3 1.2.2. Simplicity of Modeling 3 1.2.3. Simplified Handling of Asynchronous Events 3 1.2.4. More Responsive User Interfaces 4 1.3. Risks of Threads 5 1.3.1. Safety Hazards 5 1.3.2. Liveness Hazards 6 1.3.3. Performance Hazards 6 1.4. Threads are Everywhere 8 Part I: Fundamentals 10 Chapter 2. Thread Safety 11 2.1. What is Thread Safety? 12 2.2. Atomicity 13 2.3. Locking 16 2.4. Guardin g State with Locks 19 2.5. Liveness and Performance 20 Chapter 3. Sharing Objects 23 3.1. Visibility 23 3.2. Publication and Escape 26 3.3. Thread Confinement 28 3.4. Immutability 31 3.5. Safe Publication 33 Chapter 4. Composing Objects 37 4.1. Designin g a Thread Ͳsafe Class 37 4.2. Instance Confinement 39 4.3. Delegating Thread Safety 41 4.4. Adding Functionality to Existing Thread Ͳsafe Classes 47 4.5. Documenting Synchronization Policies 49 Chapter 5. Building Blocks 51 5.1. Synchronized Collections 51 5.2. Concurrent Collections 54 5.3. Blocking Queues an d the Producer Ͳconsumer Pattern 56 5.4. Blocking and Interruptible Methods 59 5.5. Synchronizers 60 5.6. Building an Efficient, Scalable Result Cache 64 Summary of Part I 69
<Index Part ll:Structuring Concurrent Applications 71 Chapter 6.Task Execution 72 6.1.Executing Tasks in.Threads 72 6.2.The Executor Framework. 74 6.3..Finding Exploitable Parallelism. 78 Summary. 83 Chapter 7.Cancellation and Shutdown 85 7.1.Task Cancellation 7.2 Stopping a Thread-based Service 85 7.3..Handling Abnormal.Thread Termination.. 23 .100 7.4.JVM Shutdown 102 Summary ..103 Chapter 8.Applying Thread Pools 104 8.1.Implicit Couplings Between Tasks and Execution Policies 104 ■■■■ 8.2.Sizing Thread Pools. .105 8.3.Configuring ThreadPoolExecutor ...1Q5 8.4.Extendina ThreadPoolExecutor. 111 8.5.Parallelizing Recursive Algorithms. .112 115 Chapter 2 GUL Applications 117 9.1.Why are GUls Single-threaded? 117 9.2:Short-running GUl Tasks... .…119 9.3.Long-runnina Gu Tasks 122 9.4.Shared Data Models.. ■■■ .123 9.5.Other Forms of Single-threaded Subsystems. 125 Summary......... .125 Partll:Liveness,Performance,and Testing 12Z Chapter 10.Avoiding Liveness Hazards 128 10.1.Deadlock .128 10.2.Avoiding and Diagnosing Deadlocks 133 10.3.Other Liveness Hazards 135 .136 Chapter 11.Performance and Scalability 137 11.1.Thinking about Performance. 137 11.2:Amdah!'s Law 139 11.3.Costs Introduced by Threads .142 11.4.Reducing Lock Contention. .144 ■■■■■■■ 11.5.Example:Comparing Map Performance. .150 11.6.Reducing Context Switch Overhead. 151 Summary 152 Chapter 12.Testing Concurrent Programs 153 12.1.Testing for Correctness... .153 12.2.Testing for Performance.. .160 12.3.Avoidina Performance Testing Pitfalls 165 12.4.Complementary Testing Approaches .167 Summary. 169 Part IV:Adyanced Topics 170 Chapter 13-Explicit Locks 171 13.1.Lock and Reentrantlock... .171 13.2.Performance Considerations .174 13.3.Fairnes5.… 175
<Index iii Part II: Structuring Concurrent Applications 71 Chapter 6. Task Execution 72 6.1. Executing Tasks in Threads 72 6.2. Th e Executor Framework 74 6.3. Finding Exploitable Parallelism 78 Summary 83 Chapter 7. Cancellation and Shutdown 85 7.1. Task Cancellation 85 7.2. Stopping a Thread Ͳbased Service 93 7.3. Handling Abnormal Thread Termination 100 7.4. JVM Shutdown 102 Summary 103 Chapter 8. Applying Thread Pools 104 8.1. Implicit Couplings Between Tasks and Execution Policies 104 8.2. Sizing Thread Pools 105 8.3. Configuring ThreadPoolExecutor 106 8.4. Extending ThreadPoolExecutor 111 8.5. Parallelizing Recursive Algorithms 112 Summary 116 Chapter 9. GUI Applications 117 9.1. Why are GUI s Single Ͳthreaded? 117 9.2. Short Ͳ running GUI Tasks 119 9.3. Long Ͳrunning GU I Tasks 121 9.4. Shared Data Models 123 9.5. Other Forms of Single Ͳthreaded Subsystems 125 Summary 126 Part III: Liveness, Performance, and Testing 127 Chapter 10. Avoiding Liveness Hazards 128 10.1. Deadlock 128 10.2. Avoiding and Diagnosing Deadlocks 133 10.3. Other Liveness Hazards 135 Summary 136 Chapter 11. Performance and Scalability 137 11.1. Thinking about Performance 137 11.2. Amdahl's Law 139 11.3. Costs Introduced by Threads 142 11.4. Reducing Lock Contention 144 11.5. Example: Comparing Map Performance 150 11.6. Reducing Context Switch Overhead 151 Summary 152 Chapter 12. Testing Concurrent Programs 153 12.1. Testing for Correctness 153 12.2. Testing for Performance 160 12.3. Avoiding Performanc e Testing Pitfalls 165 12.4. Complementary Testing Approaches 167 Summary 169 Part IV: Advanced Topics 170 Chapter 13 - Explicit Locks 171 13.1. Lock an d ReentrantLock 171 13.2. Performance Considerations 174 13.3. Fairness 175
iv Java Concurrency In Practice 13.4..Choosing.Between.Synchronized and ReentrantLock 175 135Read-writeLocks 175 Syma以.… 17 Chapter 14-Building Custom Synchronizers 179 14.1.Managing State Dependence 179 14.2.Using Condition Queues.. .183 14.3.Explicit Condition Objects 14.4.Anatomy of a Synchronizer... 188 189 14.5.AbstractQueuedSynchronizer. .190 14.6.AOS.in Jlava.util.concurrent Synchronizer Classes. .192 Summary. 194 Chapter 15.Atomic Variables and Non-blocking Synchronization 195 15.1.Disadvantages of Locking 195 15.2.Hardware Support for Concurrency. 195 15.3.Atomic Variable Classes. 198 15.4.Non-blocking Algorithms 201 Summa以.… 2Q5 Chapter 16.The Java Memory Model 207 16.1.What is a Memory Model,and Why would Want One? 207 16.2 Publication 211 225 Appendix A.Annotations for Concurrency 216 A1..Class Annotations. 216 A.2..Field and Method Annotations. 215 Bibliography 21Z
iv Java Concurrency In Practice 13.4. Choosing Between Synchronized and ReentrantLock 176 13.5. ReadͲwrite Locks 176 Summary 178 Chapter 14 - Building Custom Synchronizers 179 14.1. Managing State Dependence 179 14.2. Using Condition Queues 183 14.3. Explicit Condition Objects 188 14.4. Anatomy of a Synchronizer 189 14.5. AbstractQueuedSynchronizer 190 14.6. AQS in Java.util.concurrent Synchronizer Classes 192 Summary 194 Chapter 15. Atomic Variables and Non-blocking Synchronization 195 15.1. Disadvantages of Locking 195 15.2. Hardware Support for Concurrency 196 15.3. Atomic Variable Classes 198 15.4. NonͲblocking Algorithms 201 Summary 206 Chapter 16. The Java Memory Model 207 16.1. What is a Memory Model, and Why would I Want One? 207 16.2. Publication 211 Summary 215 Appendix A. Annotations for Concurrency 216 A.1. Class Annotations 216 A.2. Field and Method Annotations 216 Bibliography 217
1BListing and Image Index Listing and Image Index Preface Y Listing 1.Bad Way to Sort a List.Don't Do this. xiv Listing 2.Less than Optimal Way to Sort a List. y Chapter 1.Introduction 11 Listing 1.1.Non-thread-safe Sequence Generator 5 Figure 1.1.Unlucky Execution of Unsafesequence.Nextvalue. 5 Listing 1.2.Thread-safe Sequence Generator. 6 Chapter 2.Thread Safety 11 Listing 2.1.A Stateless Servlet. 13 Listing 2.2.Servlet that Counts Requests without the Necessary Synchronization.Don't Do this. 14 Listing 2.3.Race Condition in Lazy Initialization.Don't Do this. 15 Listing 2.4.Servlet that Counts Requests Using Atomi cLonq. 16 Listing 2.5.Servlet that Attempts to Cache its Last Result without Adequate Atomicity.Don't Do this. 17 Listing 2.6.Servlet that Caches Last Result,But with Unacceptably Poor Concurrency.Don't Do this. 18 Listing 2.7.Code that would Deadlock if Intrinsic Locks were Not Reentrant. 18 Figure 2.1.Poor Concurrency of SynchronizedFactorizer. 21 Listing 2.8.Servlet that Caches its Last Request and Result. 21 Chapter 3.Sharing Objects 23 Listing 3.1.Sharing Variables without Synchronization.Don't Do this. 23 Listing 3.2.Non-thread-safe Mutable Integer Holder. 24 Listing 3.3.Thread-safe Mutable Integer Holder. 24 Figure 3.1.Visibility Guarantees for Synchronization. 25 Listing 3.4.Counting Sheep. 26 Listing 3.5.Publishing an Object. 27 Listing 3.6.Allowing Internal Mutable State to Escape.Don't Do this. 21 Listing 3.7.Implicitly Allowing the this Reference to Escape.Don't Do this. 28 Listing 3.8.Using a Factory Method to Prevent the this Reference from Escaping During Construction. 28 Listing 3.9.Thread Confinement of Local Primitive and Reference Variables. 30 Listing 3.10.Using ThreadLocal to Ensure thread Confinement. 30 Listing 3.11.Immutable Class Built Out of Mutable Underlying Objects 32 Listing 3.12.Immutable Holder for Caching a Number and its Factors. 33 Listing 3.13.Caching the Last Result Using a Volatile Reference to an Immutable Holder Object. 33 Listing 3.14.Publishing an Object without Adequate Synchronization.Don't Do this. 33
1BListing and Image Index v Listing and Image Index Preface v Listing 1. Bad Way to Sort a List. Don't Do this. xiv Listing 2. Less than Optimal Way to Sort a List. xv Chapter 1. Introduction 11 Listing 1.1. NonͲthreadͲsafe Sequence Generator. 5 Figure 1.1. Unlucky Execution of UnsafeSequence.Nextvalue. 5 Listing 1.2. ThreadͲsafe Sequence Generator. 6 Chapter 2. Thread Safety 11 Listing 2.1. A Stateless Servlet. 13 Listing 2.2. Servlet that Counts Requests without the Necessary Synchronization. Don't Do this. 14 Listing 2.3. Race Condition in Lazy Initialization. Don't Do this. 15 Listing 2.4. Servlet that Counts Requests Using AtomicLong. 16 Listing 2.5. Servlet that Attempts to Cache its Last Result without Adequate Atomicity. Don't Do this. 17 Listing 2.6. Servlet that Caches Last Result, But with Unacceptably Poor Concurrency. Don't Do this. 18 Listing 2.7. Code that would Deadlock if Intrinsic Locks were Not Reentrant. 18 Figure 2.1. Poor Concurrency of SynchronizedFactorizer. 21 Listing 2.8. Servlet that Caches its Last Request and Result. 21 Chapter 3. Sharing Objects 23 Listing 3.1. Sharing Variables without Synchronization. Don't Do this. 23 Listing 3.2. NonͲthreadͲsafe Mutable Integer Holder. 24 Listing 3.3. ThreadͲsafe Mutable Integer Holder. 24 Figure 3.1. Visibility Guarantees for Synchronization. 25 Listing 3.4. Counting Sheep. 26 Listing 3.5. Publishing an Object. 27 Listing 3.6. Allowing Internal Mutable State to Escape. Don't Do this. 27 Listing 3.7. Implicitly Allowing the this Reference to Escape. Don't Do this. 28 Listing 3.8. Using a Factory Method to Prevent the this Reference from Escaping During Construction. 28 Listing 3.9. Thread Confinement of Local Primitive and Reference Variables. 30 Listing 3.10. Using ThreadLocal to Ensure thread Confinement. 30 Listing 3.11. Immutable Class Built Out of Mutable Underlying Objects. 32 Listing 3.12. Immutable Holder for Caching a Number and its Factors. 33 Listing 3.13. Caching the Last Result Using a Volatile Reference to an Immutable Holder Object. 33 Listing 3.14. Publishing an Object without Adequate Synchronization. Don't Do this. 33
vi Java Concurrency In Practice Listing 3.15.Class at Risk of Failure if Not Properly Published. 34 Chapter 4.Composing objects 31 Listing 4.1.Simple Thread-safe Counter Using the Java Monitor Pattern. 31 Listing 4.2.Using Confinement to Ensure Thread Safety. 9 Listing 4.3.Guarding State with a Private Lock. 40 Listing 4.4.Monitor-based Vehicle Tracker Implementation. 42 Listing 4.5.Mutable Point Class Similar to Java.awt.Point. 42 Listing 4.6.Immutable Point class used by DelegatingvehicleTracker. 42 Listing 4.7.Delegating Thread Safety to a ConcurrentHashMap. 43 Listing 4.8.Returning a Static Copy of the Location Set Instead of a"Live"One. 43 Listing 4.9.Delegating Thread Safety to Multiple Underlying State Variables. 44 Listing 4.10.Number Range Class that does Not Sufficiently Protect Its Invariants.Don't Do this. 45 Listing 4.11.Thread-safe Mutable Point Class. 45 Listing 4.12.Vehicle Tracker that Safely Publishes Underlying State. 46 Listing 4.13.Extending Vector to have a Put-if-absent Method. A7 Listing 4.14.Non-thread-safe Attempt to Implement Put-if-absent.Don't Do this. 48 Listing 4.15.Implementing Put-if-absent with Client-side Locking. 48 Listing 4.16.Implementing Put-if-absent Using Composition 49 Chapter 5.Building Blocks 51 Listing 5.1.Compound Actions on a vector that may Produce Confusing Results. 51 Figure 5.1.Interleaving of Getlast and Deletelast that throws ArrayIndexoutofBoundsException. 51 Listing 5.2.Compound Actions on Vector Using Client-side Locking. 52 Listing 5.3.Iteration that may Throw ArrayIndexoutofBoundsException. 52 Listing 5.4.Iteration with Client-side Locking. 52 Listing 5.5.Iterating a List with an Iterator. 53 Listing 5.6.Iteration Hidden within String Concatenation.Don't Do this. 54 Listing 5.7.ConcurrentMap Interface. 56 Listing 5.8.Producer and Consumer Tasks in a Desktop Search Application. 58 Listing 5.9.Starting the Desktop Search. 58 Listing 5.10.Restoring the Interrupted Status so as Not to Swallow the Interrupt. 60 Listing 5.11.Using CountDownLatch for Starting and Stopping Threads in Timing Tests. 61 Listing 5.12.Using FutureTask to Preload Data that is Needed Later. 62 Listing 5.13.Coercing an Unchecked Throwable to a RuntimeException. 62 Listing 5.14.Using Semaphore to Bound a Collection. 64
vi Java Concurrency In Practice Listing 3.15. Class at Risk of Failure if Not Properly Published. 34 Chapter 4. Composing Objects 37 Listing 4.1. Simple ThreadͲsafe Counter Using the Java Monitor Pattern. 37 Listing 4.2. Using Confinement to Ensure Thread Safety. 39 Listing 4.3. Guarding State with a Private Lock. 40 Listing 4.4. MonitorͲbased Vehicle Tracker Implementation. 42 Listing 4.5. Mutable Point Class Similar to Java.awt.Point. 42 Listing 4.6. Immutable Point class used by DelegatingVehicleTracker. 42 Listing 4.7. Delegating Thread Safety to a ConcurrentHashMap. 43 Listing 4.8. Returning a Static Copy of the Location Set Instead of a "Live" One. 43 Listing 4.9. Delegating Thread Safety to Multiple Underlying State Variables. 44 Listing 4.10. Number Range Class that does Not Sufficiently Protect Its Invariants. Don't Do this. 45 Listing 4.11. ThreadͲsafe Mutable Point Class. 46 Listing 4.12. Vehicle Tracker that Safely Publishes Underlying State. 46 Listing 4.13. Extending Vector to have a PutͲifͲabsent Method. 47 Listing 4.14. NonͲthreadͲsafe Attempt to Implement PutͲifͲabsent. Don't Do this. 48 Listing 4.15. Implementing PutͲifͲabsent with ClientͲside Locking. 48 Listing 4.16. Implementing PutͲifͲabsent Using Composition. 49 Chapter 5. Building Blocks 51 Listing 5.1. Compound Actions on a Vector that may Produce Confusing Results. 51 Figure 5.1. Interleaving of Getlast and Deletelast that throws ArrayIndexOutOfBoundsException. 51 Listing 5.2. Compound Actions on Vector Using ClientͲside Locking. 52 Listing 5.3. Iteration that may Throw ArrayIndexOutOfBoundsException. 52 Listing 5.4. Iteration with ClientͲside Locking. 52 Listing 5.5. Iterating a List with an Iterator. 53 Listing 5.6. Iteration Hidden within String Concatenation. Don't Do this. 54 Listing 5.7. ConcurrentMap Interface. 56 Listing 5.8. Producer and Consumer Tasks in a Desktop Search Application. 58 Listing 5.9. Starting the Desktop Search. 58 Listing 5.10. Restoring the Interrupted Status so as Not to Swallow the Interrupt. 60 Listing 5.11. Using CountDownLatch for Starting and Stopping Threads in Timing Tests. 61 Listing 5.12. Using FutureTask to Preload Data that is Needed Later. 62 Listing 5.13. Coercing an Unchecked Throwable to a RuntimeException. 62 Listing 5.14. Using Semaphore to Bound a Collection. 64
1BListing and Image Index Listing 5.15.Coordinating Computation in a Cellular Automaton with 64 Listing 5.16.Initial Cache Attempt Using HashMap and Synchronization. 66 Figure 5.2.Poor Concurrency of 66 Figure 5.3.Two Threads Computing the Same Value When Using 61 Listing 5.17.Replacing HashMap with ConcurrentHashMap. 61 Figure 5.4.Unlucky Timing that could Cause Memorizer3 to Calculate the Same Value Twice. 68 Listing 5.18.Memorizing Wrapper Using FutureTask. Listing 5.19.Final Implementation of Memorizer. 69 Listing 5.20.Factorizing Servlet that Caches Results Using Memorizer 69 Chapter 6,Task Execution 72 Listing 6.1.Sequential Web Server. 72 Listing 6.2.Web Server that Starts a New Thread for Each Request. 73 Listing 6.3.Executor Interface. 74 Listing 6.4.Web Server Using a Thread Pool. 75 Listing 6.5.Executor that Starts a New Thread for Each Task. 75 Listing 6.6.Executor that Executes Tasks Synchronously in the Calling Thread. 75 Listing 6.7.Lifecycle Methods in ExecutorService. 71 Listing 6.8.Web Server with Shutdown Support. 77 Listing 6.9.Class Illustrating Confusing Timer Behavior. 78 Listing 6.10.Rendering Page Elements Sequentially. 79 Listing 6.11.Callable and Future Interfaces. 80 Listing 6.12.Default Implementation of newTaskFor in ThreadPoolExecutor. 80 Listing 6.13.Waiting for Image Download with Future. 81 Listing 6.14.QueueingFuture Class Used By Executorcompletionservice 82 Listing 6.15.Using Completionservice to Render Page Elements as they Become Available. 82 Listing 6.16.Fetching an Advertisement with a Time Budget. 83 Listing 6.17.Requesting Travel Quotes Under a Time Budget. 84 Chapter 7.Cancellation and Shutdown 85 Listing 7.1.Using a Volatile Field to Hold Cancellation State. 86 Listing 7.2.Generating a Second's Worth of Prime Numbers. 86 Listing 7.3.Unreliable Cancellation that can Leave Producers Stuck in a Blocking Operation.Don't Do this. 8☑ Listing 7.4.Interruption Methods in Thread. 87 Listing 7.5.Using Interruption for Cancellation 88 Listing 7.6.Propagating InterruptedException to Callers. 89 Listing 7.7.Non-cancelable Task that Restores Interruption Before Exit. 90 Listing 7.8.Scheduling an Interrupt on a Borrowed Thread.Don't Do this. 90
1BListing and Image Index vii Listing 5.15. Coordinating Computation in a Cellular Automaton with 64 Listing 5.16. Initial Cache Attempt Using HashMap and Synchronization. 66 Figure 5.2. Poor Concurrency of 66 Figure 5.3. Two Threads Computing the Same Value When Using 67 Listing 5.17. Replacing HashMap with ConcurrentHashMap. 67 Figure 5.4. Unlucky Timing that could Cause Memorizer3 to Calculate the Same Value Twice. 68 Listing 5.18. Memorizing Wrapper Using FutureTask. 68 Listing 5.19. Final Implementation of Memorizer. 69 Listing 5.20. Factorizing Servlet that Caches Results Using Memorizer. 69 Chapter 6. Task Execution 72 Listing 6.1. Sequential Web Server. 72 Listing 6.2. Web Server that Starts a New Thread for Each Request. 73 Listing 6.3. Executor Interface. 74 Listing 6.4. Web Server Using a Thread Pool. 75 Listing 6.5. Executor that Starts a New Thread for Each Task. 75 Listing 6.6. Executor that Executes Tasks Synchronously in the Calling Thread. 75 Listing 6.7. Lifecycle Methods in ExecutorService. 77 Listing 6.8. Web Server with Shutdown Support. 77 Listing 6.9. Class Illustrating Confusing Timer Behavior. 78 Listing 6.10. Rendering Page Elements Sequentially. 79 Listing 6.11. Callable and Future Interfaces. 80 Listing 6.12. Default Implementation of newTaskFor in ThreadPoolExecutor. 80 Listing 6.13. Waiting for Image Download with Future. 81 Listing 6.14. QueueingFuture Class Used By ExecutorCompletionService. 82 Listing 6.15. Using CompletionService to Render Page Elements as they Become Available. 82 Listing 6.16. Fetching an Advertisement with a Time Budget. 83 Listing 6.17. Requesting Travel Quotes Under a Time Budget. 84 Chapter 7. Cancellation and Shutdown 85 Listing 7.1. Using a Volatile Field to Hold Cancellation State. 86 Listing 7.2. Generating a Second's Worth of Prime Numbers. 86 Listing 7.3. Unreliable Cancellation that can Leave Producers Stuck in a Blocking Operation. Don't Do this. 87 Listing 7.4. Interruption Methods in Thread. 87 Listing 7.5. Using Interruption for Cancellation. 88 Listing 7.6. Propagating InterruptedException to Callers. 89 Listing 7.7. NonͲcancelable Task that Restores Interruption Before Exit. 90 Listing 7.8. Scheduling an Interrupt on a Borrowed Thread. Don't Do this. 90
vili Java Concurrency In Practice Listing 7.9.Interrupting a Task in a Dedicated Thread. 91 Listing 7.10.Cancelling a Task Using Future. 92 Listing 7.11.Encapsulating Nonstandard Cancellation in a Thread by Overriding Interrupt. 93 Listing 7.12.Encapsulating Nonstandard Cancellation in a Task with Newtaskfor. 94 Listing 7.13.Producer-Consumer Logging Service with No Shutdown Support. 95 Listing 7.14.Unreliable Way to Add Shutdown Support to the Logging Service. 95 Listing 7.15.Adding Reliable Cancellation to Logwriter. 96 Listing 7.16.Logging Service that Uses an Executorservice. 97 Listing 7.17.Shutdown with Poison Pill 92 Listing 7.18.Producer Thread for IndexingService. 98 Listing 7.19.Consumer Thread for Indexingservice. 98 Listing 7.20.Using a Private Executor Whose Lifetime is Bounded by a Method Call. 98 Listing 7.21.Executorservice that Keeps Track of Cancelled Tasks After Shutdown 99 Listing 7.22.Using TRackingExecutorservice to Save Unfinished Tasks for Later Execution. 100 Listing 7.23.Typical Thread-pool Worker Thread Structure. 101 Listing 7.24.UncaughtExceptionHandler Interface. 101 Listing 7.25.UncaughtExceptionHandler that Logs the Exception. 101 Listing 7.26.Registering a Shutdown Hook to Stop the Logging Service. 103 Chapter 8.Applying Thread Pools 104 Listing 8.1.Task that Deadlocks in a Single-threaded Executor.Don't Do this. 105 Listing 8.2.General Constructor for ThreadPoolExecutor. 10Z Listing 8.3.Creating a Fixed-sized Thread Pool with a Bounded Queue and the Caller-runs Saturation Policy.109 Listing 8.4.Using a Semaphore to Throttle Task Submission. 109 Listing 8.5.ThreadFactory Interface. 109 Listing 8.6.Custom Thread Factory. 110 Listing 8.7.Custom Thread Base Class. 111 Listing 8.8.Modifying an Executor Created with the Standard Factories. 111 Listing 8.9.Thread Pool Extended with Logging and Timing. 112 Listing 8.10.Transforming Sequential Execution into Parallel Execution. 112 Listing 8.11.Transforming Sequential Tail-recursion into Parallelized Recursion. 113 Listing 8.12.Waiting for Results to be Calculated in Parallel. 113 Listing 8.13.Abstraction for Puzzles Like the "Sliding Blocks Puzzle". 113 Listing 8.14.Link Node for the Puzzle Solver Framework. 114 Listing 8.15.Sequential Puzzle Solver. 115 Listing 8.16.Concurrent Version of Puzzle Solver. 115 Listing 8.17.Result-bearing Latch Used by ConcurrentPuzzlesolver. 116
viii Java Concurrency In Practice Listing 7.9. Interrupting a Task in a Dedicated Thread. 91 Listing 7.10. Cancelling a Task Using Future. 92 Listing 7.11. Encapsulating Nonstandard Cancellation in a Thread by Overriding Interrupt. 93 Listing 7.12. Encapsulating Nonstandard Cancellation in a Task with Newtaskfor. 94 Listing 7.13. ProducerͲConsumer Logging Service with No Shutdown Support. 95 Listing 7.14. Unreliable Way to Add Shutdown Support to the Logging Service. 95 Listing 7.15. Adding Reliable Cancellation to LogWriter. 96 Listing 7.16. Logging Service that Uses an ExecutorService. 97 Listing 7.17. Shutdown with Poison Pill. 97 Listing 7.18. Producer Thread for IndexingService. 98 Listing 7.19. Consumer Thread for IndexingService. 98 Listing 7.20. Using a Private Executor Whose Lifetime is Bounded by a Method Call. 98 Listing 7.21. ExecutorService that Keeps Track of Cancelled Tasks After Shutdown. 99 Listing 7.22. Using TRackingExecutorService to Save Unfinished Tasks for Later Execution. 100 Listing 7.23. Typical ThreadͲpool Worker Thread Structure. 101 Listing 7.24. UncaughtExceptionHandler Interface. 101 Listing 7.25. UncaughtExceptionHandler that Logs the Exception. 101 Listing 7.26. Registering a Shutdown Hook to Stop the Logging Service. 103 Chapter 8. Applying Thread Pools 104 Listing 8.1. Task that Deadlocks in a SingleͲthreaded Executor. Don't Do this. 105 Listing 8.2. General Constructor for ThreadPoolExecutor. 107 Listing 8.3. Creating a FixedͲsized Thread Pool with a Bounded Queue and the CallerͲruns Saturation Policy. 109 Listing 8.4. Using a Semaphore to Throttle Task Submission. 109 Listing 8.5. ThreadFactory Interface. 109 Listing 8.6. Custom Thread Factory. 110 Listing 8.7. Custom Thread Base Class. 111 Listing 8.8. Modifying an Executor Created with the Standard Factories. 111 Listing 8.9. Thread Pool Extended with Logging and Timing. 112 Listing 8.10. Transforming Sequential Execution into Parallel Execution. 112 Listing 8.11. Transforming Sequential TailͲrecursion into Parallelized Recursion. 113 Listing 8.12. Waiting for Results to be Calculated in Parallel. 113 Listing 8.13. Abstraction for Puzzles Like the "Sliding Blocks Puzzle". 113 Listing 8.14. Link Node for the Puzzle Solver Framework. 114 Listing 8.15. Sequential Puzzle Solver. 115 Listing 8.16. Concurrent Version of Puzzle Solver. 115 Listing 8.17. ResultͲbearing Latch Used by ConcurrentPuzzleSolver. 116
1BListing and Image Index Listing 8.18.Solver that Recognizes when No Solution Exists. 116 Chapter 9 GUl Applications 11Z Figure 9.1.Control Flow of a Simple Button Click. 119 Listing 9.1.Implementing SwingUtilities Using an Executor. 120 Listing 9.2.Executor Built Atop SwingUtilities. 120 Listing 9.3.Simple Event Listener. 120 Figure 9.2.Control Flow with Separate Model and View Objects. 121 Listing 9.4.Binding a Long-running Task to a Visual Component. 121 Listing 9.5.Long-running Task with User Feedback. 122 Listing 9.6.Cancelling a Long-running Task. 122 Listing 9.7.Background Task Class Supporting Cancellation,Completion Notification,and Progress Notification. 124 Listing 9.8.Initiating a Long-running,Cancellable Task with BackgroundTask. 124 Chapter 10.Avoiding Liveness Hazards 128 Figure 10.1.Unlucky Timing in LeftRightDeadlock. 128 Listing 10.1.Simple Lock-ordering Deadlock.Don't Do this. 129 Listing 10.2.Dynamic Lock-ordering Deadlock.Don't Do this. 129 Listing 10.3.Inducing a Lock Ordering to Avoid Deadlock. 130 Listing 10.4.Driver Loop that Induces Deadlock Under Typical Conditions. 131 Listing 10.5.Lock-ordering Deadlock Between Cooperating Objects.Don't Do this. 132 Listing 10.6.Using Open Calls to Avoiding Deadlock Between Cooperating Objects. 133 Listing 10.7.Portion of Thread Dump After Deadlock. 135 Chapter 11.Performance and Scalability 13Z Figure 11.1.Maximum Utilization Under Amdahl's Law for Various Serialization Percentages. 140 Listing 11.1.Serialized Access to a Task Queue. 141 Figure 11.2.Comparing Queue Implementations. 141 Listing 11.2.Synchronization that has No Effect.Don't Do this. 142 Listing 11.3.Candidate for Lock Elision. 143 Listing 11.4.Holding a Lock Longer than Necessary. 145 Listing 11.5.Reducing Lock Duration. 145 Listing 11.6.Candidate for Lock Splitting. 146 Listing 11.7.Serverstatus Refactored to Use Split Locks. 145 Listing 11.8.Hash-based Map Using Lock Striping. 148 Figure 11.3.Comparing Scalability of Map Implementations. 150 Chapter 12.Testing Concurrent Programs 153 Listing 12.1.Bounded Buffer Using Semaphore. 154
1BListing and Image Index ix Listing 8.18. Solver that Recognizes when No Solution Exists. 116 Chapter 9. GUI Applications 117 Figure 9.1. Control Flow of a Simple Button Click. 119 Listing 9.1. Implementing SwingUtilities Using an Executor. 120 Listing 9.2. Executor Built Atop SwingUtilities. 120 Listing 9.3. Simple Event Listener. 120 Figure 9.2. Control Flow with Separate Model and View Objects. 121 Listing 9.4. Binding a LongͲrunning Task to a Visual Component. 121 Listing 9.5. LongͲrunning Task with User Feedback. 122 Listing 9.6. Cancelling a LongͲrunning Task. 122 Listing 9.7. Background Task Class Supporting Cancellation, Completion Notification, and Progress Notification. 124 Listing 9.8. Initiating a LongͲrunning, Cancellable Task with BackgroundTask. 124 Chapter 10. Avoiding Liveness Hazards 128 Figure 10.1. Unlucky Timing in LeftRightDeadlock. 128 Listing 10.1. Simple LockͲordering Deadlock. Don't Do this. 129 Listing 10.2. Dynamic LockͲordering Deadlock. Don't Do this. 129 Listing 10.3. Inducing a Lock Ordering to Avoid Deadlock. 130 Listing 10.4. Driver Loop that Induces Deadlock Under Typical Conditions. 131 Listing 10.5. LockͲordering Deadlock Between Cooperating Objects. Don't Do this. 132 Listing 10.6. Using Open Calls to Avoiding Deadlock Between Cooperating Objects. 133 Listing 10.7. Portion of Thread Dump After Deadlock. 135 Chapter 11. Performance and Scalability 137 Figure 11.1. Maximum Utilization Under Amdahl's Law for Various Serialization Percentages. 140 Listing 11.1. Serialized Access to a Task Queue. 141 Figure 11.2. Comparing Queue Implementations. 141 Listing 11.2. Synchronization that has No Effect. Don't Do this. 142 Listing 11.3. Candidate for Lock Elision. 143 Listing 11.4. Holding a Lock Longer than Necessary. 145 Listing 11.5. Reducing Lock Duration. 145 Listing 11.6. Candidate for Lock Splitting. 146 Listing 11.7. ServerStatus Refactored to Use Split Locks. 146 Listing 11.8. HashͲbased Map Using Lock Striping. 148 Figure 11.3. Comparing Scalability of Map Implementations. 150 Chapter 12. Testing Concurrent Programs 153 Listing 12.1. Bounded Buffer Using Semaphore. 154
Java Concurrency In Practice Listing 12.2.Basic Unit Tests for BoundedBuffer. 154 Listing 12.3.Testing Blocking and Responsiveness to Interruption. 156 Listing 12.4.Medium-quality Random Number Generator Suitable for Testing. 157 Listing 12.5.Producer-consumer Test Program for BoundedBuffer. 158 Listing 12.6.Producer and Consumer Classes Used in PutTakeTest. 158 Listing 12.7.Testing for Resource Leaks. 159 Listing 12.8.Thread Factory for Testing ThreadPoolExecutor. 160 Listing 12.9.Test Method to Verify Thread Pool Expansion. 160 Listing 12.10.Using Thread.yield to Generate More Interleavings. 160 Listing 12.11.Barrier-based Timer. 161 Figure 12.1.TimedPutTakeTest with Various Buffer Capacities. 162 Listing 12.12.Testing with a Barrier-based Timer. 162 Listing 12.13.Driver Program-for TimedPutTakeTest. 163 Figure 12.2.Comparing Blocking Queue Implementations. 163 Figure 12.3.Completion Time Histogram for TimedPutTakeTest with Default (Non-fair)and Fair Semaphores. 164 Figure 12.4.Completion Time Histogram for TimedPutTakeTest with Single-item Buffers. 164 Figure 12.5.Results Biased by Dynamic Compilation. 165 Chapter 13-Explicit Locks 171 Listing 13.1.Lock Interface. 171 Listing 13.2.Guarding Object State Using ReentrantLock. 171 Listing 13.3.Avoiding Lock-ordering Deadlock Using trylock. 173 Listing 13.4.Locking with a Time Budget. 173 Listing 13.5.Interruptible Lock Acquisition. 173 Figure 13.1.Intrinsic Locking Versus ReentrantLock Performance on Java 5.0 and Java 6. 174 Figure 13.2.Fair Versus Non-fair Lock Performance 175 Listing 13.6.ReadwriteLock Interface. 176 Listing 13.7.Wrapping a Map with a Read-write Lock. 178 Figure 13.3.Read-write Lock Performance. 178 Chapter 14-Building Custom Synchronizers 179 Listing 14.1.Structure of Blocking State-dependent Actions. 179 Listing 14.2.Base Class for Bounded Buffer Implementations. 180 Listing 14.3.Bounded Buffer that Balks When Preconditions are Not Met. 180 Listing 14.4.Client Logic for Calling GrumpyBoundedBuffer 181 Figure 14.1.Thread Oversleeping Because the Condition Became True Just After It Went to Sleep. 181 Listing 14.5.Bounded Buffer Using Crude Blocking. 182
x Java Concurrency In Practice Listing 12.2. Basic Unit Tests for BoundedBuffer. 154 Listing 12.3. Testing Blocking and Responsiveness to Interruption. 156 Listing 12.4. MediumͲquality Random Number Generator Suitable for Testing. 157 Listing 12.5. ProducerͲconsumer Test Program for BoundedBuffer. 158 Listing 12.6. Producer and Consumer Classes Used in PutTakeTest. 158 Listing 12.7. Testing for Resource Leaks. 159 Listing 12.8. Thread Factory for Testing ThreadPoolExecutor. 160 Listing 12.9. Test Method to Verify Thread Pool Expansion. 160 Listing 12.10. Using Thread.yield to Generate More Interleavings. 160 Listing 12.11. BarrierͲbased Timer. 161 Figure 12.1. TimedPutTakeTest with Various Buffer Capacities. 162 Listing 12.12. Testing with a BarrierͲbased Timer. 162 Listing 12.13. Driver ProgramͲfor TimedPutTakeTest. 163 Figure 12.2. Comparing Blocking Queue Implementations. 163 Figure 12.3. Completion Time Histogram for TimedPutTakeTest with Default (NonͲfair) and Fair Semaphores. 164 Figure 12.4. Completion Time Histogram for TimedPutTakeTest with SingleͲitem Buffers. 164 Figure 12.5. Results Biased by Dynamic Compilation. 165 Chapter 13 - Explicit Locks 171 Listing 13.1. Lock Interface. 171 Listing 13.2. Guarding Object State Using ReentrantLock. 171 Listing 13.3. Avoiding LockͲordering Deadlock Using trylock. 173 Listing 13.4. Locking with a Time Budget. 173 Listing 13.5. Interruptible Lock Acquisition. 173 Figure 13.1. Intrinsic Locking Versus ReentrantLock Performance on Java 5.0 and Java 6. 174 Figure 13.2. Fair Versus NonͲfair Lock Performance. 175 Listing 13.6. ReadWriteLock Interface. 176 Listing 13.7. Wrapping a Map with a ReadͲwrite Lock. 178 Figure 13.3. ReadͲwrite Lock Performance. 178 Chapter 14 - Building Custom Synchronizers 179 Listing 14.1. Structure of Blocking StateͲdependent Actions. 179 Listing 14.2. Base Class for Bounded Buffer Implementations. 180 Listing 14.3. Bounded Buffer that Balks When Preconditions are Not Met. 180 Listing 14.4. Client Logic for Calling GrumpyBoundedBuffer. 181 Figure 14.1. Thread Oversleeping Because the Condition Became True Just After It Went to Sleep. 181 Listing 14.5. Bounded Buffer Using Crude Blocking. 182