The Concurrency Specialist Course Outline

"Java Concurrency in Practice" in a four-day intensive course.

Java Concurrency Course 1 Introduction Welcome To The Course How we deal with questions Exercises with partial solutions Certificate of Training 1.1 History of concurrency Concurrent vs Parallel Programming Throughput vs Latency Hardware impact of concurrency 1.2 Benefits of threads Programming is easier Better throughput Simpler modeling More responsive programs 1.3 Risks of threads Safety vs liveness Safety hazards Using basic synchronized Caching of fields Code reordering Annotations for Concurrency Class annotations Field annotations 1.4 Threads are everywhere Concurrency is not an advanced feature Threads created by JVM Threads created by frameworks Timer Servlets and JavaServer Pages Remote Method Invocation (RMI) Swing and AWT 1.5 Short Java 7 Primer Underscores in integral literals Generic type inference I Fundamentals 2 Thread Safety Introduction to Thread Safety Multi-processing vs multi-threading Synchronization and shared data Your program has latent defects Object orientation and synchronization Example of a simple data race 2.1 What is thread safety? Definition of thread safety Stateless objects always thread-safe 2.2 Atomicity Byte code generated by simple count++ Demonstration of broken servlet Lazy initialization check-then-act Reordering of writes Compound actions Check-then-act Read-write-modify Using AtomicLong to keep state safe 2.3 Locking Mutexes in Java Atomics causing race conditions Intrinsic locks Effects of coarse-grained locking Reentrancy 2.4 Guarding state with locks Serialized access to critical code Examples of guards with compound actions Making compound actions atomic Danger of locking on non-final fields Locking on intrinsic lock Maintaining invariants Locking everything is not always enough 2.5 Liveness and performance Coarse-grained vs fine-grained locking Performance difference Simplicity vs performance 3 Sharing Objects 3.1 Visibility Synchronization and visibility Reason why changes are not visible Problems that state data can cause Non-atomic 64-bit numeric operations Making fields visible with volatile Volatile flushing Volatile vs synchronized Single-threaded write safety 3.2 Publication and escape Ways we might let object escape Publishing objects via fields Publishing objects as method returns Publishing objects to alien methods Implicit links to outer class 3.3 Thread confinement Unshared objects are safe Ad-hoc thread confinement Stack confinement ThreadLocal 3.4 Immutability Immutable is always thread safe Definition of immutable Immutable containing mutable object Final fields 3.5 Safe publication Making objects and their state visible Safe publication idioms "Effectively" immutable objects How to share objects safely 4 Composing Objects 4.1 Designing a thread-safe class Encapsulation Primitive vs object fields Thread-safe counter with invariant Post-conditions Pre-condition Waiting for pre-condition to become true 4.2 Instance confinement Encapsulation State guarded by private fields Split locks How instance confinement is good Java monitor pattern Lock confinement Example of fleet management 4.3 Delegating thread safety Using thread safe components Delegation with vehicle tracker Delegating safety to ConcurrentMap Independent fieldds Invariables and delegation Publishing underlying fields 4.4 Adding functionality to existing thread-safe classes Benefits of reuse Modifying existing code Subclassing to add functionality Using composition to add fiunctionality Client-side locking 4.5 Documenting synchronization policies Examples from the JDK What should be documented Synchronization policies Documentation checklist Interpreting vague documentation 5 Building Blocks 5.1 Synchronized containers Old Java 1.0 thread-safe containers Synchronized wrapper classes Locking with compound actions Adding functionality to thread-safe classes Exceptions with iteration Hidden iterators 5.2 Concurrent containers Scalability ConcurrentHashMap Additional atomic operations Java 8 ConcurrentHashMap CopyOnWriteCollections 5.3 Blocking queues and the producer-consumer pattern How BlockingQueues work Timed vs untimed methods Java implementations of BlockingQueue ArrayBlockingQueue Circular array lists LinkedBlockingQueue PriorityBlockingQueue DelayQueue SynchronousQueue TransferQueue Example of producer-consumer Deques ArrayDeque LinkedBlockingDeque ConcurrentLinkedDeque (Java 7) Work stealing 5.4 Blocking and interruptible methods Thread states during blocking Interrupting blocking methods Methods throwing InterruptedException 5.5 Synchronizers Coordinating flow of threads CountDownLatch FutureTask Semaphore CyclicBarrier Phaser (Java 7) 5.6 Building an efficient, scalable result cache Avoiding scalability bottlenecks Delaying computation until later Avoiding duplicate computation Using FutureTask for long computations 5.7 Summary II Structuring Concurrent Applications 6 Task Execution 6.1 Executing tasks in threads Identifying tasks Indepence of tasks Task boundaries Single-threaded vs multi-threaded Explicitely creating tasks Disadvantage of unbounded thread creation 6.2 The Executor framework Executor interface Motivation for using Executor Decoupling task submission from execution Execution policies Who will execute it? In which order? (FIFO, LIFO, by priority) Various sizing options for number of threads and queue length Thread pool structure Thread pool benefits Memory leaks with ThreadLocal Standard ExecutorService configurations ThreadPoolExecutor Executor lifecycle, state machine Shutdown() vs ShutdownNow() Delayed and periodic tasks Difference between java.util.Timer and ScheduledExecutor 6.3 Finding exploitable parallelism Breaking up a single client request Sequential vs parallel Callable and Future Callable controlling lifecycle Example showing page renderer with future Limitations of parallelizing heterogeneous tasks CompletionService Time limited tasks 7 Cancellation and Shutdown 7.1 Task cancellation Reasons for wanting to cancel a task Cooperative vs preemptive cancellation Using flags to signal cancellation Cancellation policies 7.1.1 Interruption WAITING state of thread Origins of interruptions How does interrupt work? Methods that put thread in WAITING state Policies in dealing with InterruptedException Thread.interrupted() method 7.1.2 Interruption policies Task vs Thread Different meanings of interrupt Preserving the interrupt status 7.1.3 Responding to interruption Letting the method throw the exception Restoring the interrupt and exiting Ignoring the interrupt status Saving the interrupt for later 7.1.4 Example: timed run Telling a long run to eventually give up Canceling busy jobs 7.1.5 Dealing with non-interruptible blocking Reactions of IO libraries to interrupts Interrupting locks 7.2 Stopping a thread-based service Graceful shutdown Providing lifecycle methods Example: A logging service Asynchronous logging caveats ExecutorService shutdown Poison pills One-shot execution service 7.3 Handling abnormal thread termination Using UncaughtExceptionHandler ThreadGroup for uncaught exceptions Dealing with exceptions in Swing 7.4 JVM shutdown Orderly shutdown Abrupt shutdown Shutdown hooks Daemon threads Finalizers 8 Applying Thread Pools 8.1 Tasks and Execution Policies Homogenous, independent and thread-agnostic tasks Thread starvation deadlock Long-running tasks 8.2 Sizing thread pools Danger of hardcoding worker number Problems when pool is too large or small Formula for calculating how many threads to use CPU-intensiv vs IO-intensive task sizing Examples of various pool sizes Mixing different types of tasks Determining the maximum allowed threads on your operating system 8.3 Configuring ThreadPoolExecutor corePoolSize maximumPoolSize keepAliveTime Using default Executors.new* methods Managing queued tasks PriorityBlockingQueue Saturation policies Abort Caller runs Discard Discard oldest Thread factories Customizing thread pool executor after construction 8.4 Extending ThreadPoolExecutor Using hooks for extension beforeExecute afterExecute terminate 8.5 Parallelizing recursive algorithms Converting sequential tasks to parallel Using Fork/Join to execute tasks 9 SwingWorker and Fork/Join 9.1 SwingWorker (Java 6) Single-threaded GUI frameworks Event Dispatcher Thread (EDT) Using SwingWorker to keep GUI responsive How to use SwingWorker SwingWorker - Who calls who? Demo of a SwingWorker in action The Good, the bad and the ugly 9.2 Fork/Join (Java 7) Breaking up work into chunks ForkJoinPool and ForkJoinTask Work-stealing in ForkJoinPool ForkJoinTask state machine RecursiveTask vs RecursiveAction Parallel Fibonacci Calculator Fork/Join vs. Compute Parallel merge sort Canceling a task Visibility guarantees with fork/join Use cases of fork/join III Liveness, Performance, and Testing 10 Avoiding Liveness Hazards 10.1 Deadlock The drinking philosophers Causing a deadlock amongst philosophers Resolving deadlocks Discovering deadlocks Lock-ordering deadlocks Defining a global ordering Dynamic lock order deadlocks Defining order on dynamic locks Checking whether locks are held Imposing a natural order Deadlock between cooperating objects Open calls and alien methods Example in Vector Resource deadlocks Thread-starvation deadlocks 10.2 Avoiding and diagnosing deadlocks Avoiding multiple locks Using open calls Unit testing for lock ordering deadlocks Adding a sleep to cause deadlocks Verifying thread deadlocks Timed lock attempts "TryLock" with synchronized Deadlock analysis with thread dumps Stopping deadlock victims DeadlockArbitrator 10.3 Other liveness hazards Starvation ReadWriteLock in Java 5 vs Java 6 Detecting thread starvation Poor responsiveness Livelock 11 Performance and Scalability 11.1 Thinking about performance Effects of serial sections and locking Performance vs scalability How fast vs how much Mistakes in traditional performance optimizations 2-tier vs multi-tier Evaluating performance tradeoffs 11.2 Amdahl's and Little's laws Formula for Amdahl's Law Utilization according to Amdahl Maximum useful cores Problems with Amdahl's law in practice Formula for Little's Law Applying Little's Law in practice How threading relates to Little's Law 11.3 Costs introduced by threads Context switching Cache invalidation Locking and unlocking Memory barriers Escape analysis and uncontended locks Lock elision Spinning before actual blocking 11.4 Reducing lock contention Exclusive locks Safety first! Narrowing lock scope Using ConcurrentHashMap Performance comparisons Reducing lock granularity Lock splitting Using CopyOnWrite collections Lock striping In ConcurrentHashMap In ConcurrentLinkedQueue Avoiding "hot fields" ReadWriteLock Immutable objects Atomic fields How to monitor CPU utilization Reasons why CPUs might not be loaded How to find "hot locks" Dangers of object pooling Hotspot options for lock performance 11.5 Example: Comparing Map performance ConcurrentSkipListMap Current ConcurrentHashMap Proposed Java 8 ConcurrentHashMap Cliff Click's NonBlockingHashMap 11.6 Reducing context switch overhead Atomic classes Volatile Unsafe 12 Testing Concurrent Programs 12.1 Testing for correctness Checking for data races Automatic tooling JChord JavaRaceFinder FindBugs IntelliJ IDEA False positives Memory requirements of automatic tools Testing through bulk updates Server HotSpot interference Testing pitfalls Controlling HotSpot and JIT Turning off optimizations Randomizing bulk operations Testing field visibility Single updates, with time delays Pros and cons of various approaches Examples of testing broken code Testing for deadlocks 12.2 Testing for performance HotSpot tricks Loop unrolling Useless code elimination Inlining of method calls Lock eliding Lock coarsening Eliminating object creation HotSpot interference in microbenchmarks HotSpot method call threshold HotSpot compile time Getting the fastest most optimized code Randomization Ensuring HotSpot does not overoptimize Math.random() vs ThreadLocalRandom Cost of remainder calculation Statistics Average and variance Value of the minimum Excluding warmup results Eliminating interference Length of timings Value of including standard deviation IV Advanced Topics 13 Explicit Locks 13.1 Lock and ReentrantLock Memory visibility semantics ReentrantLock implementation Using the explicit lock Using try-finally tryLock and timed locks Using try-lock to avoid deadlocks Interruptible locking Non-block-structured locking 13.2 Performance considerations Java 5 vs Java 6 performance Throughput on contended locks Uncontended performance Heavily contended locks 13.3 Fairness Standard non-fair mechanisms Round-robin by OS Barging Fair explicit locks in Java Throughput of fair locks 13.4 Synchronized vs ReentrantLock Memory semantics Ease of use Prefer synchronized 13.5 Read-write locks ReadWriteLock interface Understanding system to avoid starvation ReadWriteLock implementation options Release preference Reader barging Reentrancy Downgrading Upgrading 14 Building Custom Synchronizers 14.1 Managing state dependence Single-threaded vs multi-threaded Structure of blocking state-dependent actions Example using bounded queues Exceptions on pre-condition fails Crude blocking by polling and sleeping Introducing condition queues With intrinsic locks 14.2 Using condition queues State-dependence Condition predicate Lock Condition queue Waking up too soon Waiting for a specific timeout Conditional waits Missed signals InterruptedException notify() vs notifyAll() Encapsulating condition queues 14.3 Explicit condition objects Condition interface Benefits of explicit condition queues Timed conditions 14.4 AbstractQueuedSynchronizer (AQS) Basis for other synchronizers 14.5 Summary 15 Atomic Variables and Nonblocking Synchronization 15.1 Disadvantages of locking Elimination of uncontended intrinsic locks Volatile vs locking performance Priority inversion 15.2 Hardware support for concurrency Optimistic locking Compare-and-Swap (CAS) Compare-and-Set Managing conflicts with CAS Simulation of CAS Nonblocking counter CAS support in the JVM Shared cache lines Performance advantage of padding Using "Unsafe" to access memory directly 15.3 Atomic variable classes Optimistic locking classes Very fast when not too much contention Types of atomic classes How do atomics work? Atomic array classes Performance comparisons: Locks vs atomics Cost of atomic spin loops 15.4 Nonblocking algorithms Scalability problems with lock-based algorithms Definition of nonblocking and lock-free Nonblocking stack Doing speculative work Highly scalable hash table Atomic field updaters Using sun.misc.Unsafe Dangers Reasons why we need it The ABA problem AtomicStampedReference 15.5 Summary 16 Conclusion Tips on where to learn more Thank you! concurrency.vym 2012-01-12 vym 1.10.0