Java Concurrency in Practice - Summary - Part 9

This is part 9 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it.

Chapter 13 - Explicit Locks

1. Unlike intrinsic locking, the Lock interface offers unconditional, polled, timed, and interruptible lock acquisition.
2. Lock implementations provide the same memory visibility guarantees as intrinsic locking.  They can vary in locking semantics, scheduling algorithms, ordering guarantees and performance.
3. ReentrantLock has same semantics as a synchronized block.
4. Why use explicit locks over intrinsic locks?
1. Unlike intrinsic locking, a thread waiting to acquire a ReentrantLock can be interrupted. 
2. ReentrantLock also supports timed lock acquisition.  
3. WIth intrinsic locks, a deadlock is fatal.
4. Intrinsic locks must be released in the same code block they are acquired in.  This makes non-blocking designs impossible.
5. ReentrantLock is much faster than intrinsic locking in Java 5.0
5. Lock objects are usually released in a finally block, to make sure that it is released if an exception is thrown.
6. lockInterruptibly() helps us build cancelable tasks.
7. tryLock() returns false if the lock cannot be acquired.  Timed tryLock() is also responsive to interruption.
8. ReentrantLock offers two fairness options
1. Fair - threads acquire locks in order of requesting.
2. Non-fair (default) - thread can acquire lock if it is available at the time of the lock request, even if earlier threads are waiting.  Non-fair locking is useful because it avoids the overhead of suspending/resuming a thread if the lock is available at time of the lock request.  
3. Fairness is usually not needed, and has a very high performance penalty (multiple orders of magnitude).
4. Fair locks work best when they are held for a relatively long time or when the mean time between lock requests is large.
9. When to use intrinsic locks?
1. synchronized blocks have a more concise syntax.  You can never forget to unlock a synchronized block.
2. Use ReentrantLock only when advanced features like timed, polled, interruptible lock acquisition, fairness or non-block structured locking are needed.
3. Harder to debug deadlock problems when using ReentrantLock because lock acquisition is not tied to a particular stack frame, and thus the stack dump is not very helpful.
4. synchronized is likely to have more performance improvements in the future (eg: lock coarsening) as it is part of the Java language spec.
10. Read-Write Lock - protected resource can be accessed by multiple readers or one writer at the same time.
1. offers readLock() and writeLock() methods which return a Lock object that must be acquired before doing the respective operations.
2.  More complex implementation.  Hence has lower performance except in read-heavy workloads.
11. Lock can only be released by thread that acquired it.

Chapter 14 - Building Custom Synchronizers

1. State-dependent classes - blocking operations can proceed only if state-precondition becomes true (for example, you cannot retrieve result of FutureTask if computation has not yet finished).
2. Try to use existing state-dependent classes whenever possible. 
3. Condition queue - allows a group of threads (called wait set) to wait for a specific condition to become true.
4. Intrinsic condition queues - Any java object can act as a condition queue via the Object.wait(), notify() and notifyAll() functions.
1. Must hold intrinsic lock on an object before you can call wait(), notify() or notifyAll().   
2. Calling Object.wait() atomically releases lock and suspends the current thread.  It reacquires the lock upon waking up, just before returning from the wait() function call.   wait() blocks till thread is awakened by a notification, a specified timeout expires or the thread is interrupted.
3. In order to use condition queues, we must first identify and document the pre-condition that makes an operation state-dependent.  The state variables involved in the condition must be protected by the same lock object as the one we wait() on.
4. A single intrinsic condition queue can be used with more than one condition predicate.  This means that when a thread is awakened by a notifyAll, the condition it was waiting on need not be true.  wait() can even return spuriously without any notify().  The condition can also become false by the time wait() reacquires the lock after waking up.  Hence when waking up from wait(), the condition predicate must be tested again and we must go back to waiting if it is false.  Hence, call wait() in a loop: synchronized(lockObj) { while(!conditionPredicate()) { lock.wait();} // object is in desired state now
5. Notifications are not sticky - i.e. a thread won't know about notifications that occurred before it called wait().
6. In order to call notify() or notifyAll() on an object, you must hold the intrinsic lock on that object.  Unlike wait(), the lock is not automatically released.  The lock must be manually released soon as none of the woken up threads can make progress without acquiring the lock.
7. Use notifyAll() instead of notify().  If multiple threads are waiting on the same condition  queue for different condition predicates, calling notify() instead of notifyAll() can lead to missed signals, as only the wrong thread may be woken up.
1. However using notifyAll() can be very inefficient, as multiple threads are woken up and contend for the lock where only one of them can usually make progress.
2. notify() can be used only if 
1. The same condition predicate is associated with the condition queue and each thread executes the same logic on returning from wait().
2. A notification on the condition queue enables at most one thread to proceed.
8. A bounded buffer implementation needs to call notify only when moving away from the empty state or full states.  Such conditional notifications are efficient, but makes the code hard to get right.  Hence, avoid unless necessary as an optimization.
9. A state dependent class should either fully document its waiting/notification protocols to sub-classes or prevent sub-classes from participating in them at all.
10. Encapsulate condition queue objects in order to avoid external code from incorrectly calling wait() or notify() on them.  This often implies the usage of a private lock object instead of using the main object itself.
11. Explicit Condition objects - Condition 
1. Each intrinsic lock can have only one associated condition queue.  Hence multiple threads may wait on same condition queue for different condition predicates.
2. A Condition is associated with a single Lock object.   A Condition is created by calling Lock.newCondition().  You can create multiple Condition objects per Lock.
3. Equivalents of wait(), notify() and notifyAll() for Condition are await(), signal() and signalAll().  Since Condition is an Object, wait() and notify() are also available. Do not confuse them.
4. Explicit Condition objects make it easier to use signal() instead of signalAll().
12. Synchronizers
1. Both Semaphore and ReentrantLock extend AbstractQueuedSynchronzer (AQS) class.
2. AQS is a framework for building locks and synchronizers.
3. When using AQS, there is only one point of contention.
4. Acquisition - state dependent operation that can block.
5. Release - allows some threads blocked in acquire to proceed.  Not-blocking
13. AQS manages a single integer of state for the synchronizer class. It can be accessed with getState(), setState() and compareAndSetState() methods.  The integer can represent arbitrary semantics.  For example, FutureTask uses it to represent the state (running, completed, canceled) of the task.  Semaphore uses it to track the number of permits remaining.
1. Synchronizers track additional state variables themselves.
2. Synchronizers override tryAcquire, tryRelease, isHeldExclusively, tryAcquireShared and tryReleaseShared.  The acquire, release, etc methods of AQS call the appropriate try methods,

Java Concurrency in Practice - Summary - Part 8

This is part 8 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 11 - Performance and Scalability

1. Avoid premature optimization - first make it right, then make it fast, if not fast enough already (as indicated by actual performance measurements)
2. Tuning for scalability is often different from tuning for performance, and are often contradictory.
3. Amdahl's Law : Speedup <= 1/( F + (1-F)/N) where F is the fraction of computation that must be executed serially, and N is the number of processors.
4. A shared work queue adds some (often overlooked) serial processing.  Result handling is another form of serialization hidden inside otherwise seemingly 100% concurrent programs.
5. Costs of using threads
1. context switches - managing shared data structures in OS and JVM take memory and CPU. Can also cause flurry of processor cache misses on a thread context switch.
2. When a thread blocks on a lock, it is switched out by JVM before reaching its full scheduled CPU quantum, leading to more overhead.
6. Context switching costs 5000-10000 clock cycles (few microseconds).  Use vmstat to find % of time program spent in the kernel. High % can indicate high context switching.
7. synchronized and volatile result in the use of special CPU instructions called memory barriers that involve flushing/invalidating CPU caches, stalling execution pipelines, flushing hardware write buffers, and inhibit compiler optimizations as operations cannot be reordered.
8. Performance of contended and uncontended synchronization are very different.  synchronized is optimized for the uncontended scenario (20 to 250 clock cycles).  volatile is always uncontended. 
9. Modern JVMs can optimize away locking code that can be proven to never contend.
10. Modern JVMs perform escape analysis to identify thread-confined objects and avoid locking them.
11. Modern JVMs can do lock coarsening to merge multiple adjacent locks into a larger lock to avoid multiple lock/unlocks.
12. Synchronization by one thread affects performance of other threads due to traffic on the shared memory bus.
13. Uncontended synchronization can be handled entirely in JVM.  Contended synchronization involves OS activity - OS needs to suspend the thread that loses the contention.  
14. Blocking can implemented by spin-waiting or by suspending the thread via the OS.  spin-waiting is preferred for short waits.  JVM decides what to use based on profiling past performance.
15. Reducing lock contention
1. reduce duration for which locks are held.
2. reduce frequency at which locks are requested. Coarsen lock granularity by lock splitting (for moderately contended locks) and lock striping (for heavily contended locks).
3. replace exclusive locks with coordination mechanisms that permit greater concurrency.
16. Lock striping - ConcurrentHashMap uses 16 locks - bucket N is guarded by lock N % 16.  Locking for exclusive access to entire collection is hard when lock striping is used.
17. Avoid hot fields like cached values - for eg: size is cached for a Map, in order to convert an O(n) operation to a O(1) operation.  Use striped counters or atomic variables.
18. Alternatives to exclusive locks - concurrent collections, read-write locks, immutable objects, atomic variables.
19. Do not use object pools.  Object allocation and GC were slow in earlier versions of Java.  Now object allocation is faster than a C malloc - only 10 machine instructions.  Object pools also introduce synchronization overheads

Chapter 12 - Testing Concurrent Programs

1. Every test must wait till all the threads created by it terminate.  It should then report any failures in tearDown().
2. Testing blocking operations need some way to unblock a thread that has blocked as expected.  This is usually done by doing the blocking operation in a new thread and interrupting it after waiting for some time.  An InterruptedException is thrown if the operation blocked as expected.
3. Thread.getState() should not be used for concurrency control or testing.  Useful only for debugging.
4. One approach to test producer-consumer programs is to check that everything that is put into a queue or buffer eventually comes out of it, and nothing else does.  
1. For single producer-single consumer designs, use order sensitive checksum of elements that are added, and verify them when the element is removed.  Do not use a synchronized shadow list to track the elements as that will introduce artificial serialization.
2. For multiple producer-consumer designs, use an order insensitive checksum that can be combined at the end of the test to verify that all enqueued elements have been dequeued.
1. Make sure that the checksums are not guessable by the compiler (for eg: consecutive integers), so that they are not precomputed.  Use a simple random number generator like  xorShift(int y) { y ^= (y << 6); y ^= (y >>> 21); y ^= (y << 7); return y;}
5. Test on multi-processor machines with fewer processors than active threads.
6. Generate more thread interleaving by using Thread.yield() to encourage more context switches during operations that access shared state.  
7. Always include some basic functionality testing when doing performance testing to make sure that you are not measuring performance of broken code.
8. Non-fair semaphores provide better throughput, while fair semaphores provide lower variance in responsiveness.
9. Avoiding performance testing pitfalls
1. Ensure that garbage collection does not run at all during your test (check this using the -verbose:gc flag) OR ensure that garbage collection runs a number of times during the test (need to run test for a long time).
2. Your tests should run only after all code has been compiled; no point measuring performance of interpreted byte code.  Dynamic compilation takes CPU resources.  Compiled code executes much faster.
1. Code may be decompiled/recompiled multiple times during execution - for eg: if some previous assumption made by JVM is invalidated, or to compile with better optimization flags based on recently gathered performance statistics.
2. Run program long enough (several minutes) so that compilation and interpreted execution represent a small fraction of the results and do not bias it.
3. Or have an unmeasured warm-up run before starting to collect performance statistics.
4. Run JVM with -XX:+PrintCompilation so that we know when dynamic compilation happens.
3. When running multiple unrelated computationally intensive tests in a single JVM, place explicit pauses between tests in order to give the JVM a chance to catch up with its background tasks.  Don't do this when measuring multiple related activities, since omitting CPU required by background tasks gives unrealistic results.
4. In order to obtain realistic results, concurrent performance tests should approximate the thread-local computation done by a typical application.  Otherwise, there will be unrealistic contention.
5. Make sure that compilers do not optimize away benchmarking code.  
1. Trick to make sure that benchmarking calculation is not optimized away:  if (fox.hashCode() == System.nanoTime()) System.out.print(" ");
10. Complementary Testing Approaches
1. Code Review
2. Static analysis tools: FindBugs has detectors for:
1. Inconsistent synchronization.
2. Invoking Thread.run (Thread.start() is what is usually invoked, not Thread.run())
3. Unreleased lock
4. Empty synchronized block
5. Double-checked locking
6. Starting a thread from a constructor
7. Notification errors
8. Condition wait errors: Object.wait() or Condition.await() should be called in a loop with the appropriate lock held after testing some state predicate.
9. Misuse of Lock and Condition
10. Sleeping or waiting while holding a lock.
11. Spin loops

Java Concurrency in Practice - Summary - Part 7

This is part 7 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 9 - GUI Applications

1. Almost all GUI toolkits, including Swing, are implemented as a single-threaded subsystem.  All GUI activity is confined to a single dedicated event dispatch thread.  Attempts at multi-threaded GUIs suffered from deadlocks and race conditions.  User actions manifest as events that bubble up from the GUI component to the application.  Application initiated actions bubble down from the application code to the GUI components.  Hence, GUI components are often accessed in opposite order, creating ripe conditions for deadlocks.
2. Tasks that execute in the event thread must complete quickly.  Otherwise the UI will hang.
3. In Swing, GUI objects are kept consistent not by synchronization, but by thread confinement.  They must NOT be accessed from any other thread.
4. A few Swing methods are thread-safe:
1. SwingUtilities.isEventDispatchThread
2. SwingUtilities.invokeLater - schedules a Runnable to be executed on the event thread.
3. SwingUtilities.invokeAndWait - callable only from a non-GUI thread.  Schedules Runnable to be executed on GUI thread and waits for it complete
4. methods to enqueue a repaint or revalidate request on the event queue.
5. methods for adding/removing event listeners.
5. Short-running tasks can be run directly on the GUI thread.  For long running tasks, use Executors.newCachedThreadPool().
6. Use Future, so that tasks can be easily cancelled.  The task must be coded so that it is responsive to interruption.
7. SwingWorker class provides support for cancellation, progress indication, completion notification.  So, we don't have to implement our own using FutureTask and Executor.
8. Data models must be thread-safe if they are to be accessed from the GUI thread.
9. A program that has both a presentation-domain and an application domain data model is said to have a split-model design.
1. presentation data model is confined to event thread.  Application domain data model is thread-safe and is shared between the application and GUI threads.
2. presentation model registers listeners with the application model so that it can be notified of updates.  Presentation model can be updated from the application model by sending a snapshot of the current state or via incremental updates.

Chapter 10 - Avoiding Liveness Hazards

1. Unlike database systems, JVM does not do deadlock detection or recovery
2. A program will be free of lock-ordering deadlocks if all threads acquire the needed locks in a fixed global order.
1. The order of locks acquired by a thread may depend on external input. Hence static analysis alone is not sufficient to avoid lock-ordering deadlocks.
2. An alternative is to induce an ordering on locks by using System.identityHashCode.  Order lock acquisition by the hash code of the lock object.
1. In the extremely unlike scenario where the hash codes of two lock objects are equal, acquire a third "tie" lock before trying to acquire the original two locks.  The tie lock can be a global lock.  Since hash collisions are infrequent, the tie lock won't introduce a concurrency bottleneck.
3. If the lock objects (say bank Accounts) have a unique key, lock acquisition can be ordered by the key, and there is no need for the tie-lock.
4. Multiple locks may not always acquired in the same method.  Hence, it is not easy to detect lock-ordering deadlocks.  Watch out for invocation of alien methods while holding a lock.
3. Calling a method with no locks held is called an open call.  Liveness of a program can be more easily analyzed if all calls are open.
4. Use synchronized blocks within methods to guard shared state, instead of making the entire method synchronized.
1. In cases where loss of atomicity of the synchronized method is unacceptable, we need to construct application level protocols.  For example, when shutting down a service, lock for just long enough to mark the service as shutting down, and wait for existing tasks to complete without holding the lock. Since the service is marked as shutting down, no new tasks will start.
5. In addition to deadlocking waiting for locks, threads can also deadlock waiting for resources like database connections.
6. If you must acquire multiple locks, lock ordering must be part of your design. Minimize number of locks needed.  Document ordering policy.
7. Timed locks offered by the Lock class are another option for detecting and recovering from deadlocks.  The tryLock() method returns failure if timeout expires.  It can return failure even if no deadlock occurred, but the thread just took a long time due to some other reason.
8. JVM prints out deadlock information in thread dumps.  To trigger a thread dump, send SIGQUIT (kill -3) to the JVM.  Explicit Lock objects are not clearly shown in a thread dump.
9. Starvation - a thread is perpetually denied access to needed resources.
1. CPU cycle starvation can be caused by inappropriate use of thread priorities, or by executing infinite loops with locks held.
2. Avoid setting thread priorities as they are platform-dependent and can cause liveness issues.  Set lower priorities only for truly background tasks, that can improve the responsiveness of foreground tasks.
10. Livelock - thread is not blocked, but cannot make progress because it keeps retrying an operation that will always fail.  For example, when a code bug is triggered when processing a particular input, and that input is re-queued for processing by over-eager error handling code.  An unrecoverable error is being mistakenly being treated as a recoverable one.  Solution for some forms for livelocks is to introduce randomness into the retry.