- Forward


Synchronized Collections
in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • Some Observations:
    • Multi-threaded programs often make use of collections of various kinds
    • For performance reasons, collections are not, in general thread-safe
  • An Important Implication:
    • Multi-threaded programs that use collections often need to provide thread-safety
Motivation (cont.)
Back Forward
  • A Question:
    • Shouldn't somebody have done something about this?
  • An Answer:
    • Various collections have been made thread-safe in various different ways
Synchronized Collections
Back Forward
  • The Idea:
    • Synchronize all of the methods in the class
  • Implementation Details:
    • Use a factory method to decorate an existing collection object
Synchronized Collections (cont.)
Back Forward
  • The Utility Class:
    • Collections java.util.Collections
  • The Static Factory Methods:
    • List<T> synchronizedList(List<T> list)
    • Map<K, V> synchronizedMap(Map<K, V> map)
    • Set<T> synchronizedSet(Set<T> set)
An Example
Back 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 Dispatcher had synchronized dispatch() and makeVehicleAvailable() methods
  • This Implementation:
    • The Dispatcher uses a synchronized List
An Example (cont.)
Back Forward
javaexamples/threads/v5b/Dispatcher.java
 
An Important Limitation of Synchronized Collections
Back Forward
  • Remember:
    • Each method is synchronized
  • The Implication:
    • Individual methods are effectively atomic
  • However:
    • Sequences of method invokations are not atomic (which is sometimes called conditional thread safety)
An Important Limitation (cont.)
Back Forward
The Following Fragments have Race Conditions
List list = Collections.synchronizedList(new ArrayList<String>()); String element; if (list.size() > 0) { element = list.remove(0); }
Map map = Collections.synchronizedMap(new HashMap<String, Account>()); if (!map.containsKey(key)) { map.put(key, value); }
An Important Limitation (cont.)
Back Forward
Synchronizing
List list = Collections.synchronizedList(new ArrayList<String>()); String element; synchronized(list) { if (list.size() > 0) { element = list.remove(0); } }
Map map = Collections.synchronizedMap(new HashMap<String, Account>()); synchronized(map) { if (!map.containsKey(key)) { map.put(key, value); } }
What about Iterators?
Back Forward
  • The Question:
    • What happens if the underlying Collection is changed while using an Iterator (or a for-each loop)?
  • The Answer:
    • The next call to the Iterator object's hasNext() or next() method will throw a ConcurrentModificationException
  • Terminology:
    • The Iterator objects are said to fail-fast
What About Iterators? (cont.)
Back Forward
Using an Iterator
List list = Collections.synchronizedList(new ArrayList<String>()); Iterator<String> i = list.iterator(); while (i.hasNext()) // Might throw ConcurrentModificationException { element = i.next(i); // Might throw ConcurrentModificationException }
Traditional Iteration is also NOT Thread-Safe
List list = Collections.synchronizedList(new ArrayList<String>()); for (int i=0; i<list.size(); i++) { // list might be changed in another thread element = list.get(i); }
What about Iterators?
Back Forward
  • One Fix:
    • Synchronize the iterating block on the underlying collection
  • Another Fix:
    • Call toArray() and iterate over the array
  • The Drawback of Both:
    • Performance
Going Further
Back Forward
  • An Important Issue:
    • Only one thread may access a synchronized collection at a time and this can cause scalability problems
  • Other Approaches:
    • Concurrent collections
There's Always More to Learn
Back -