Use java.util.concurrent collections and classes including CyclicBarrier and CopyOnWriteArrayList

Back>

ExecutorService framework encapsulates the thread lifecycle management in a set of interfaces and implementing classes.

thread safe collection

Concurrent Collection framework encapsulates the state variable management in a set of interfaces and optimized implementing classes. We don't have to write custom synchronized code for accessing shared objects, we store them in concurrent collections, life is easier because of responsibility delegate.

Most of the interfaces we need to know for OCPJP about Concurrent Collections have already been covered in topic Create and use ArrayList, TreeSet, TreeMap, and ArrayDeque objects, here we introduce a few more interfaces: ConcurrentMap, BlockingQueue and BlockingDeque. After that we go through the 4 categories of implementations:

1. ConcurrentHashMap, ConcurrentLinkedQueue, ConcurrentLinkedDeque, ConcurrentSkipListSet, ConcurrentSkipListMap
2. CopyOnWriteArrayList, CopyOnWriteArraySet
3. LinkedBlockingQueue, LinkedBlockingDeque
4. synchronizedCollection(Collection<T> c)

Performance vise, the SynchronizedCollection is the slowest, because the wrapper has to lock the whole collection to achieve thread-safety. At anytime, only one thread is able to access the collection, the performance is no better than single thread.

Concurrent collections, on the other hand, never locks the whole collection, they use advanced and sophisticated techniques like lock stripping. One example lock stripping technique is to divide the whole collection into several segments, a thread only lock the segment relevant to its access, so the other segments can still be accessed by other threads. By using lock stripping, Concurrent collections has much better performance than Synchronized Collections.

CopyOnWrite collections achieve the thread-safety differently. It creates an immutable copy of the object under protection, so that multiple-threads can read it simultaneously. Once a write happens, the immutable copy is replaced with a new one. CopyOnWrite collection's thread-safety is achieved through immutable objects, no lock is involved. Their performance beat Concurrent collections when the read is far more frequent than write.

ConcurrentMap

public interface ConcurrentMap<K, V> extends Map<K, V>

ConcurrentMap and Map have the same methods. The only difference is, ConcurrentMap emphasis that it is a Map providing thread safety and atomicity guarantees.

ConcurrentHashMap, ConcurrentSkipListMap implements ConcurrentMap.

BlockingQueue

public interface BlockingQueue<E> extends Queue<E>

LinkedBlockingQueue implements the BlockingQueue interface.

A Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element.

BlockingQueue methods are those from Queue and two extra timed waiting methods:

boolean	offer(E e, long timeout, TimeUnit unit) Inserts the specified element into this queue, waiting up to the specified wait time if necessary for space to become available. Returns true if successful, false if timeout.
E	poll(long timeout, TimeUnit unit) Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available. Returns the head of the queue if available, null if timeout.

BlockingDeque

public interface BlockingDeque<E> extends Deque<E>, Deque<E>

A Deque that additionally supports blocking operations that wait for the deque to become non-empty when retrieving an element, and wait for space to become available in the deque when storing an element.

Linked BlockingDeque directly implements the BlockingDeque interface.

BlockingDeque methods are those from BlockingQueue and Deque plus 4 timed waiting methods:

boolean	offerFirst(E e, long timeout, TimeUnit unit) Inserts the specified element at the front of this deque, waiting up to the specified wait time if necessary for space to become available.
boolean	offerLast(E e, long timeout, TimeUnit unit) Inserts the specified element at the end of this deque, waiting up to the specified wait time if necessary for space to become available.
E	pollFirst(long timeout, TimeUnit unit) Retrieves and removes the first element of this deque, waiting up to the specified wait time if necessary for an element to become available.
E	pollLast(long timeout, TimeUnit unit) Retrieves and removes the last element of this deque, waiting up to the specified wait time if necessary for an element to become available.

General purpose implementations

Comparison of Implementations
+ means fast O(1)
* means normal O(log n)
- means slow O(n)

Class	Interface	Ordered	Sorted	Performance
ConcurrentHashMap	ConcurrentMap	No	No	modify +, retrieve +
ConcurrentSkipListMap	ConcurrentMap, SortedMap, NavigableMap	Yes	Yes	modify *, retrieve *
ConcurrentSkipListSet	SortedSet, NavigableSet	Yes	Yes	modify *, retrieve *
ConcurrentLinkedDeque	Deque	Yes	No	modify +, retrieve -
ConcurrentLinkedQueue	Queue	Yes	No	modify +, retrieve -

CopyOnWriteArrayList and CopyOnWriteArraySet

Thread safe implementations of List and Set, in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.

This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. 

The iterator will not reflect additions, removals, or changes to the list since the iterator was created.

Synchronized Collections

Concurrency API also includes static methods for obtaining synchronized versions of existing non-concurrent collection objects.

static <T> Collection<T>	synchronizedCollection(Collection<T> c) Returns a synchronized (thread-safe) collection backed by the specified collection.
static <T> List<T>	synchronizedList(List<T> list) Returns a synchronized (thread-safe) list backed by the specified list.
static <K,V> Map<K,V>	synchronizedMap(Map<K,V> m) Returns a synchronized (thread-safe) map backed by the specified map.
static <K,V> NavigableMap<K,V>	synchronizedNavigableMap(NavigableMap<K,V> m) Returns a synchronized (thread-safe) navigable map backed by the specified navigable map.
static <T> NavigableSet<T>	synchronizedNavigableSet(NavigableSet<T> s) Returns a synchronized (thread-safe) navigable set backed by the specified navigable set.
static <T> Set<T>	synchronizedSet(Set<T> s) Returns a synchronized (thread-safe) set backed by the specified set.
static <K,V> SortedMap<K,V>	synchronizedSortedMap(SortedMap<K,V> m) Returns a synchronized (thread-safe) sorted map backed by the specified sorted map.
static <T> SortedSet<T>	synchronizedSortedSet(SortedSet<T> s) Returns a synchronized (thread-safe) sorted set backed by the specified sorted set.

It is imperative that the user manually synchronize on the returned collection when traversing it via Iterator, Spliterator or Stream:

Collection c = Collections.synchronizedCollection(myCollection);
     ...
  synchronized (c) {
      Iterator i = c.iterator(); // Must be in the synchronized block
      while (i.hasNext())
         foo(i.next());
  }

CyclicBarrier

CyclicBarrier A synchronization aid that allows a set of threads to all wait for each other to reach a common barrier point. CyclicBarriers are useful in programs involving a fixed sized party of threads that must occasionally wait for each other. The barrier is called cyclic because it can be re-used after the waiting threads are released.