Java Concurrency in Practice - Summary - Part 3

This is part 3 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 4 - Composing objects

1. We often create thread-safe objects by composing together other thread-safe objects. In order to design a thread-safe class, we need to identify the object's state variables, establish invariants that constraint them and the post conditions associated with its method,  and then establish a policy for managing concurrent access to them.
1.  An object's state includes the state of other objects referenced from its state variables.  For eg: a LinkedList's state includes all the link node objects.
2. Synchronization policy - how an object uses immutability, thread-confinement, locking (how and which variables are guarded by which locks) to coordinate access to its state variable so that the invariants or post conditions are not violated.
3. Encapsulation enables us to determine that a class is thread-safe without having to examine the entire program, because all paths that use the data can be identified and made thread-safe.
1. Collection wrappers like synchronizedList make the underlying non-thread-safe ArrayList thread-safe by using encapsulation.
4. Java monitor pattern - object encapsulates all state and guards it with its own intrinsic lock.
1. Pro: Simplicity.
2. Con: External code can lock on the object's intrinsic lock and cause liveness problems that may require examining the whole program to debug.  This problem is avoided if a separate private object is used as the lock.
5. A composite object made of thread-safe components need not be thread-safe.  This is usually the case when there are constraints on the state of the components.
6. A state variable can be published if it is thread-safe, does not participate in any invariants that constrain its value and has no prohibited state transitions for any of its operations.
7. Re-use existing java thread-safe libraries whenever possible.  To add-functionality to an existing thread-safe class: 
1. The best option is to modify the source code of the class if available.  
1. Pro: details about synchronization policy are confined to one file, and is thus easier to maintain.
2. If modifying source code is not possible, the next best option is to extend the class, assuming it was designed for extension. 
1. Con: Fragile.  If base class changes synchronization policy (say which locks are used), then the extended class will silently fail.
3. Extension or source modification is not possible for collections wrapped in Collections.synchronized* wrappers, since the underlying wrapped class is unknown.  The solution is to use client-side locking - guard client code with the lock specified by the object's synchronization policy.  For Vector, the lock is the object itself.
4. Another option is Composition.  In a wrapper object, maintain a private internal copy of the object (say List) whose functionality we wish to extend.   Add the new functionality as a synchronized method of the wrapper.  Add synchronized methods for existing functionality of the wrapped object that simply delegate to the underlying object.
1. Pro: Less fragile
2. Con: Minor overhead due to double locking.
8. Document a class's thread-safety guarantees for users of the class; Document its synchronization policy for the class's maintainers.
1. Use @GuardedBy annotations to document the locks used to guard different state variables.
2. Since documentation for commonly used Java libraries is vague, we often have to guess whether a class is thread-safe or not.  For example, since a JDBC DataSource represents a pool of reusable database connections to be shared across multiple threads, we can assume that it is thread-safe.  However, individual JDBC Connection objects are intended to be used by a single thread, and are most likely not thread-safe.

Chapter 5: Building Blocks

1. Java offers a wide variety of thread-safe classes that can serve as building blocks for large concurrent programs.  
2. External locking is still required for thread-safe classes in order to provide a 'reasonable' behavior.  
3. Unreliable Iteration is one example where additional synchronization is required.  For example, using getLast() and deleteLast() on a thread-safe List requires additional synchronization.  If getLast() determines the index of the last element to be L and the element at L is deleted by deleteLast() before getLast() accesses it, an ArrayOutOfBoundsException will be thrown.   Otherwise, an ArrayOutOfBounds exception may be thrown if the last element of the list is deleted after getLast() determined the index of the last element to be returned.  Note that the data in the List is never corrupted, we just get unexpected behavior.
1. Java Iterators throw an unchecked ConcurrentModificationException if it detects that the underlying collection has changed during iteration. This is not reliable as the counters used to track whether the underlying collection has changed are not thread-safe.
2. Iterators can sometimes be hidden - For eg: an iterator is used if a collection object is passed to a log statement which tries to get its string representation.
3. Unreliable iteration can be solved by client-side locking.  When using the synchronized wrappers provided by Java, we can use the underlying collection as the lock for composite actions. Con: Decreases scalability.
4. Another option to avoid concurrent modification exception is to clone the collection as a local copy.  The lock on the collection must be held while cloning.  Con: Can be very expensive to clone large collections.
5. To avoid client-side locking during iteration, use the Concurrent collections offered by Java.  This improves scalability as multiple threads can now access the collections simultaneously without blocking
4. ConcurrentHashMap
1. HashMap uses a single lock to synchronize all its operations.
2. ConcurrentHashMap uses lock-striping.  Supports concurrent non-blocking access by infinite number of readers, and a limited number of writers.
3. Iterators do not throw ConcurrentModificationException.
4. size() and isEmpty() are approximate.  These methods are not useful in concurrent environments anyway.
5. Cannot lock the entire map for synchronized access, needed in rare cases where multiple map entries need to be added atomically.
6. Cannot use client-side mapping while adding new atomic operations.  If these are needed, you most likely need ConcurrentMap instead of ConcurrentHashMap.
5. CopyOnWriteArrayList 
1. Thread-safety derived from the immutability of underlying list.  Mutability is provided by creating and republishing a new copy of the list on every change.  Iterators point to the list at the time the iterator was created.
2. Copying large lists can be expensive.  Hence mainly useful when iteration is the more common operation rather than addition - for eg: when using a list of event listeners.
6. Some more concurrent collections - CopyOnWriteArraySet, ConcurrentLinkedQueue, ConcurrentSkipListMap - concurrent replacement for synchronized SortedMap, ConcurrentSkipListSet - concurrent replacement for synchronized SortedSets
7. Java offers multiple Queue implementations (esp. BlockingQueue) that can be very useful to implement producer-consumer designs.  Queues can be blocking or non-blocking.  For non-blocking queues, .retrieval operations return null if queue is empty.
8. BlockingQueue
1. blocking methods : take, put (blocking happens only if queue is bounded)
2. non-blocking methods: offer, poll
3. Use bounded blocking queues for reliable resource management.  Otherwise, if consumers are slow, producers can keeping adding to the queue till the JVM runs out of heap space.  Do this early in design; hard to retrofit later.
4. We can use offer() to check if the item will be accepted by the queue.  If the queue is full, the item can be discarded in application specific ways (for eg: simply drop it or save it to local disk for later usage)
5. BlockingQueue implementations - contain sufficient internal synchronization to safely publish objects from a producer thread to a consumer thread
1. LinkedBlockingQueue
2. ArrayBlockingQueue
3. PriorityBlockingQueue
4. SynchronousQueue - Not really a queue as it does not maintain storage space for elements.  Just maintains a list of queued threads waiting to enqueue or dequeue an element.  Directly transfers item from producer to consumer - more efficient.  Direct handoff also informs producer that consumer has taken responsibility for the item.  take() and put() will block if no thread is waiting to participate in the handoff.  Mainly used when there are always enough consumer threads.
9. Deque and BlockingDeque - allows efficient insertion and removal from head and tail.
1. Enables Work Stealing designs - In producer-consumer design, there is a single queue that is shared across all threads.  This causes lots of contention.  In work stealing,  each consumer has its own deque, from the head of which it consumes items. If its deque is empty, it can steal objects from the tail of some other consumer's deque. Most of the time, a consumer takes objects from the head of its own deque, thereby avoiding contention.  Even when it steals, there is little contention as it steals from the tail rather than the head.  Work stealing is well-suited for applications where producers are also consumers.
10. Interruption
1. Thread.interrupt() interrupts a thread.
2. Interruption is a cooperative mechanism, i.e.,  One thread cannot force another to stop what it is doing.  Thread.interrupt() merely requests a thread to stop at a convenient stopping point.
3. If a method is marked to throw an InterruptedException, it means that the method is blocking and that it will attempt to stop blocking early if interrupted.
4. No language specification about how to deal with interrupts.  Most natural option is to cancel whatever the thread is currently doing. Blocking methods that are interruptible make it easy to cancel long-running tasks when necessary.
5. One common option to handle the InterruptedException is to propagate it to your caller.  This can be done by not catching it at all, or by catching and rethrowing it after performing some local cleanup.
6. In cases where you cannot throw an InterruptedException (for eg: inside Runnabe.run()), you must catch the InterruptedException and restore the interrupted status by calling Thread.currentThread().interrupt() on the current thread.  This allows  code higher up in the call stack to see that the thread was interrupted.
7. Never catch an InterruptedException and ignore it - except when extending Thread (and therefore controlling all code higher up in the call stack).
11. Synchronizers - an object that coordinates the control flow of threads based on its state.  BlockingQueue is one example of a synchronizer.  Latch, FutureTask, Semaphores and Barriers are other examples of synchronizers.
1. Latch - a synchronizer that can block threads until it reaches its terminal state.  A latch acts as a gate.  Once open, it remains open forever.
1. Eg usage: Ensure that a computation cannot proceed until the resources needed by it have been initialized, Wait until all players in a multi-player game have finished their moves.
2. CountDownLatch - initialized with positive integer.Threads call await(), which blocks till counter becomes 0.  Other threads call countDown() which decreases the count.
2. FutureTask - mainly used to represent long running or async computation (for eg: by the Executor framework)
1. The computation is encapsulated in a Callable (result-bearing equivalent of Runnable).
2. FutureTask.get() returns result immediately if computation is done, or if exception is thrown or if cancelled; otherwise blocks till done.  Result obtained from get() is safely published.
3. Once complete, it stays in completed state forever.
4. Future.get() can throw an ExecutionException if the Callable.run() throws one. Check all known exceptions when calling get().  Other exceptions are generally rethrown.
3. Semaphores
1. Counting semaphores are used to control the number of threads that can simultaneously access a resource.  A thread wishing to use the resource must acquire() a virtual permit and release() it when done.  acquire() blocks if no permits are available.
2. A binary semaphore is a mutex with non-reentrant locking, unlike the intrinsic java object lock which is reentrant.
3. Can be used to turn any collection into a bounded blocking collection.
4. Barriers
1. Similar to latches, but all threads must come together at the barrier point at the same time in order to proceed.
2. CyclicBarrier allows a fixed number of threads to rendezvous repeatedly.  Useful in parallel iterative algorithms.
3. If a thread blocked on await() is interrupted or an await() times out, then BrokenBarrierException is thrown.
4. When barrier is successfully passed, await() returns with a  unique arrival index per thread, which can be used for leader election amongst the threads.
5. Also supports barrier action - a Runnable to be executed when barrier is successfully passed but before threads are released.
12. For building an efficient scalable result cache, use a ConcurrentHashMap> putIfAbsent()

Java Concurrency in Practice - Summary - Part 2

This is part 2 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 3 - Sharing Objects

1. Synchronization (for example, by using synchronized blocks) is not just about atomic execution of code blocks, it also influences memory visibility - i.e., ensures that a thread can see the changes made in another thread.  Without synchronization, the Java memory model does not guarantee that a value written by a thread will be seen by another thread on a timely basis or even at all.   For example,  if proper synchronization is not used, a thread X that relies on a control variable that is set in thread Y may NEVER see any updates to it that are written in thread Y.  In most cases, thread X will incorrectly loop for ever.
2. If synchronization is not used, reordering of operations done by multi-processor CPUs for improving performance, can cause a thread to see an incorrect or partial value written by another thread.  Without synchronization, the data can be stale.  If thread first sets variable x to 1 and then y to 2, another thread may see y set to 2 while x is still unset.  This can lead to bugs that are very hard to debug.
3. Always use synchronization whenever data is shared across threads.
4. Out-of-thin-air safety - A thread always sees the value of a variable that was written by some thread; not some random value pulled out of thin air.  Unless declared as volatile, 64-bit numeric variables (long and double) do not have out-of-thin-air safety, because the JVM treats 64-bit operations as two 32-bit operations.
5. Volatile variables provide a weaker form of synchronization.  
1. Volatile variables are specially treated by the compiler (for eg: not cached in registers). So a read of a volatile variable always returns the latest value written by some thread.
2. When thread A writes to a volatile variable and subsequently thread B reads that same variable, the values of all variables visible to A prior to writing the volatile variable become visible to B after reading the volatile variable.
3. Don't overuse volatile, and in tricky ways.  Synchronized blocks are still necessary for atomic operations.  
4. Volatile is commonly used for a control variable that determines when a thread should exit an infinite loop.
5. Locking guarantees visibility and atomicity; volatile variables guarantee only visibility.
6. Use volatile variables only when all the following conditions are satisfied:
1. Writes to the variable do not depend on its current value, or if it is guaranteed that only a single thread writes to the variable.
2. The variable does not participate in invariants with other state variables.
3. Locking is not required for any other reason while the variable is being accessed.
6. For server applications, always specify the -server JVM command line argument even while developing and testing, since the JVM does more drastic optimizations in server mode. Some concurrency bugs arise only under these optimizations.
7. Publishing an object means making it available to code outside of its current scope.
1. This can be done by:
1. storing a reference to it somewhere where other code can find it, say a public static field or in a publicly accessible HashMap.
2. returning it from a non-private method.
3. passing it to an alien method
1. a method in other classes
2. an overridable method in the same class
4. publishing an inner class instance (this automatically exposes the enclosing instance)
2. Sometimes we do not want to publish an object since that will break encapsulation.  An object that is published when it should not have been is said to have escaped.
3. Do not allow the this reference to escape during construction.  This commonly happens when the constructor registers some inner class with external event listeners or starts a thread.  Even if this is the last statement in the constructor, it is possible that a reference to the object may escape before it is fully constructed.  Other threads can see the partially constructed object and react incorrectly.  Use a separate start() method to start a thread created in the constructor, or to register event listeners created in the constructor.  Alternatively, to do it one step, use a newInstance() factory method that calls the constructor and then automatically calls start() before returning the newly created object.
4. Calling an overriden instance method from the constructor also allows this to escape before being fully constructed.
8. Thread confinement, i.e., make sure data is accessed only from one thread, is the easiest way to achieve thread safety.
1. Swing UI framework & JDBC connection objects use thread confinement extensively.
2. Thread confinement options:
1. Ad-hoc thread confinement - programmer entirely responsible to confine object to thread - no language features used. Not recommended due to fragility.
2. Stack confinement - Object can be reached only through local variables
1. Primitive types are always stack confined.
2. Care should be taken that object references do not escape.
3. ThreadLocal - provides get and set methods that maintain a separate copy of a value for each thread. Used as: new ThreadLocal() { public T initialValue() {...}}
9. Immutability - Immutable objects are always thread-safe.
1. Even if all fields of an object are final, it may still not be immutable as some of its final fields can refer to mutable objects.
2. Final fields provide initialization safety as they have special semantics under the Java Memory Model.  Make all fields of a class final unless they really need to be mutable 
3. When a group of related data items must be processed atomically, consider creating an immutable holder class.   When an immutable holder class, we may be able to avoid a synchronized block.
10. Safe publication
1. Simply storing a reference to an object into a public field is not safe, as it could lead to other threads seeing the object in a partially constructed state (due to reordering).
2. Immutable objects can be published through any mechanism; no synchronization necessary.
3. Others must be safely published, i.e., both the reference to the object and the object's state must be made visible to other threads at the same time.  A properly constructed object can be safely published by:
1. Initializing an object reference from a static initializer.  This is often the easiest way; static initializers are executed by the JVM at class initialization time which has JVM-internal synchronization.
2. Storing a reference to it in a volatile field or AtomicReference.
3. Storing a reference to it into a final field of a properly constructed object
4. Storing a reference to it into a field that is properly guarded by a lock, like thread-safe collections like Vector or synchronizedList.
4. Effectively immutable objects must be safely published.
1. Objects that are not technically immutable, but whose state will not be modified after publication are called effectively immutable.  Safely published effectively immutable objects can be safely used by any thread without additional synchronization.  For example, the Date object is often used as an effectively immutable object although it is technically mutable.
5. Mutable objects must be safely published, AND must be either thread-safe or guarded by a lock.

Java Concurrency in Practice - Summary - Part 1

This is part 1 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 1 - Introduction

1. Writing correct concurrent programs is very hard.
2. Threads are the easiest way to effectively use multi-processor systems, which are now ubiquitous.
3. When writing multi-threaded programs, we must pay attention to the following:
1. Safety - Nothing  bad ever happens, i.e. program correctness is guaranteed irrespective of interleaved execution.
2. Liveness - Something good eventually happens.  For eg: no deadlock.
3. Performance - Something good happens fast enough. For eg: no excessive context switches.
4. Many Java frameworks (GUI toolkits, RMI, Timers, etc) internally use threads.  So your code must be thread-safe even if you do not explicitly use threads.

Chapter 2 - Thread Safety

1. Writing concurrent programs is all about correctly managing access to shared, mutable state.  Threads are just one kind of mechanism.
1. An object's state = any data that can affect its externally visible behavior.  
2. An object's mutable state needs to be protected from uncontrolled concurrent access from multiple threads.
2. A class is thread-safe if it continues to behave correctly when accessed from multiple threads, with no additional synchronization or coordination required of the calling code.  In the absence of formal specifications (i.e., invariants constraining an object's fields, postconditions defining the effect of operations on the object etc), we assume that the single-threaded behavior of a class is its correct behavior (after verification, of course!).
1. It is much easier to design a class to be thread-safe than to retrofit thread-safety into it later.
2. It is easier to make a class thread-safe if its state is private.  In other words, follow good OO practices.
3. Thread-safe classes encapsulate any needed synchronization so that calling code need not provide their own.
3. Stateless objects are always thread-safe.
4. The most common race condition is associated with check-then-act sequences.  Lazy initialization of expensive objects is a common place where check-then-act is used.
5. Race condition != data race.  Data race happens when a thread writes a variable without synchronization and another thread tries to read it - the reading thread may see partial or completely incorrect data.
6. If all you need is a thread-safe counter, just use java.util.concurrent.atomic.AtomicLong.  If multiple pieces of state are involved, this is not sufficient - further synchronization is necessary.
7. synchronized block - Java's built-in locking mechanism for enforcing atomicity
1. synchronized block is associated with an object that serves as the lock, and a block of code to be guarded.  
2. Every java object can act as a lock for a synchronized block.  These built-in locks are called intrinsic or monitor locks.
3. Intrinsic locks are mutexes; i.e., only one thread can own it at a time.
4. Intrinsic locks are reentrant - a thread can immediately acquire a lock that it is currently holding.
8. Each mutable variable that is read/written from multiple threads must be guarded by synchronization with the SAME lock object EVERY TIME it is read/written.
1. Use @GuardedBy("lockobject") annotation on each mutable shared variable to document the locking strategy.
9. For every invariant that involves more than one variable, all the variables involved in the invariant must be guarded by the same lock.