- Forward


Concurrent Collections
in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • Some Observations:
    • Multi-threaded programs often make use of collections of various kinds
    • For performance reasons, collections are not, in general thread-safe
  • Fortunately:
    • Various syncrhonized collections have been implemented
  • Unfortunately:
    • They sometimes suffer from scalability problems because they can only be read from/written to by one thread at a time
Concurrent Collections
Back SMYC Forward
  • The Idea:
    • Provide coordination in other ways
  • The Approaches:
    • Copy-on-Write (COW)
    • Compare-and-Swap (CAS)
    • Fine-Grained-Lock (FGL)
Copy-on-Write Collections
Back SMYC Forward
  • The Approach:
    • The values in the collection are stored in an immutable array
    • A new copy of the collection is created every time it is modified
    • Snaphot iterators retain a reference to the backing array that was current at the start of iteration (which will never change)
  • Examples:
    • CopyOnWriteArrayList java.util.concurrent.CopyOnWriteArrayList
    • CopyOnWriteArraySet java.util.concurrent.CopyOnWriteArraySet
Compare-and-Swap Collections
Back SMYC Forward
  • The Approach:
    • Before updating, a local copy of the variable is made
    • Calculations are performed using the local copy
    • The local copy and the variable are compared - if they are the same the update is performed, otherwise it either gives up or tries again
    • Provide weakly consistent iterators that tolerate concurrent modification, traverse elements as they existed when the iterator was constructed, and may (but are not guaranteed to) reflect modifications to the collection after the construction of the iterator
  • Tradeoffs:
    • Eliminates many liveness defects
    • Can cause livelock
  • Examples:
    • ConcurrentLinkedQueue java.util.concurrent.ConcurrentLinkedQueue
    • ConcurrentLinkedDeque java.util.concurrent.ConcurrentLinkedDeque
    • ConcurrentSkipListMap java.util.concurrent.ConcurrentSkipListMap
Fine-Grained-Lock Collections
Back SMYC Forward
  • The Approach:
    • Use multiple (fine-grained) locks (e.g., lock striping) to make individual methods atomic without limiting access to all methods
    • Sometimes exploit details of the Java Memory Model to minimize the time that locks are held (or avoid acquiring locks)
  • Tradeoffs:
    • Multiple threads can access the collection at the same time
    • It is harder to implement methods that operate on the collection as a whole (e.g., size(), isEmpty()) since all of the locks would have to be acquired
  • Examples:
    • ConcurrentHashMap java.util.concurrent.ConcurrentHashMap
    • LinkedBlockingQueue java.util.concurrent.LinkedBlockingQueue
FGL (cont.) - ConcurrentHashMap
Back SMYC Forward
  • Objectives:
    • Full concurrency of retrievals
    • High expected concurrency of updates
    • Retrieval operations and update operations may overlap (i.e., an update for a key happens-before any non-null retrieval for that key)
  • Retrievals:
    • Usually do not block
    • Usually return the value inserted by the most recent completed insert operation and may return a value added by a concurrent insertion
  • Weakly Consistent Iterators:
    • Return each element once at most once
    • Never throw ConcurrentModificationException
    • May or may not reflect insertions or removals that occurred since the iterator was constructed
FGL (cont.) - ConcurrentHashMap (cont.)
Back SMYC Forward
  • Additional Atomic Methods (as per ConcurrentMap java.util.ConcurrentMap ):
    • putIfAbsent(k, v)
    • replace(k, v) and replace(k, v, n)
    • remove(k, v)
  • Computational Methods (as per ConcurrentMap java.util.ConcurrentMap ):
    • Examples - compute(), forEach()
    • Approach - use functional programming techniques
FGL (cont.) - LinkedBlockingQueue
Back SMYC Forward
  • Objective (as per the BlockingQueue java.util.concurrent.BlockingQueue interface):
    • First-in-first-out (possibly space-bounded) collection
    • Wait for the queue to become non-empty when retrieveing
    • Wait for the queue to have space when storing
  • Approach:
    • Separates the creation of work from its execution (e.g., using a "to do" list)
  • Method Summary:
    • Throws Exception Returns Special Blocks Until Times Out
      Insert add(e) offer(e) put(e) offer(e, time, timeunit)
      Remove remove() poll() take() poll(time, timeunit)
      Examine element() peek()
GLF (cont.) An Example of a LinkedBlockingQueue
Back SMYC Forward
  • The Setting:
    • In an application that dispatches emergency vehicles, a single Dispatcher is used by a DailyDispatchHandler and a RealTimeDispatchHandler, each of which executes in its own thread
  • The Previous Implementation:
    • The thread executing the dispatch() method enters the waiting state if no vehicles are available
    • The thread that executes makeVehicleAvailable() notifies the waiting threads
  • This Implementation:
    • The Dispatcher uses a LinkedBlockingQueue
An Example (cont.)
Back SMYC Forward
javaexamples/threads/v6b/Dispatcher.java
 
FGL (cont.) - Other Classes
Back SMYC Forward
  • ArrayBlockingQueue java.util.concurrent.ArrayBlockingQueue :
    • Bounded (because it is backed by a fixed-size array)
    • Supports a fairness policy that orders waiting producer and concumer threads in FIFO order (which decreases throughput but avoids starvation)
  • LinkedBlockingDeque java.util.concurrent.LinkedBlockingDeque (pronounced like "deck"):
    • Provides the capabilities of a doubly-ended queue (i.e., insertion/removal at/from both ends)
  • PriorityBlockingQueue java.util.concurrent.PriorityBlockingQueue
    • Elements are ordered either based on their natural ordering or a Comparator java.util.Comparator ; the head is the least element
There's Always More to Learn
Back -