• 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

• A Question:
  • Shouldn't somebody have done something about this?
• An Answer:
  • Various collections have been made thread-safe in various different ways

• The Idea:
  • Synchronize all of the methods in the class
• Implementation Details:
  • Use a factory method to decorate an existing collection object

• The Utility Class:
  • 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)

• 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

javaexamples/threads/v5b/Dispatcher.java

import java.util.*;


/**
 * Used to dispatch vehicles in a fleet (e.g., emergency
 * response vehicles).
 *
 * This version uses a synchronized LinkedList.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 5.0b
 */
public class Dispatcher
{
    protected int                    numberOfVehicles;
    protected List<Integer>          availableVehicles;
    

    /**
     * Construct a new Dispatcher
     *
     * @param n   The number of vehicles in the fleet
     */
    public Dispatcher(int n)
    {
       int     i;

       numberOfVehicles = n;
       availableVehicles = Collections.synchronizedList(new LinkedList<Integer>());

       for (i=0; i < n; i++)
       {
          makeVehicleAvailable(i);
       }
    }

    /**
     * Dispatch an available vehicle
     *
     * @param  task  The task to be handled
     * @return       true if a vehicle was dispatched
     */
    public boolean dispatch(String task)
    {
       boolean  ok;
       int      vehicle;
       Integer  v;

       try
       {
          v = availableVehicles.remove(0);
          vehicle = v.intValue();
          sendMessage(vehicle, task);
          ok = true;
       }
       catch (IndexOutOfBoundsException ioobe)
       {
           ok = false;           
       }
       return ok;
    }

    /**
     * Makes a vehicle available for future dispatching
     *
     * @param vehicle  The number of the vehicle
     */
    public void makeVehicleAvailable(int vehicle)
    {
       availableVehicles.add(new Integer(vehicle));
    }

    /**
     * Sends a message to a vehicle
     *
     * @param vehicle  The number of the vehicle
     * @param message  The message to send
     */
    private void sendMessage(int vehicle, String message)
    {

       // This method would normally transmit the message 
       // to the vehicle.  For simplicity, it now writes it 
       // to the screen instead.

       System.out.println(vehicle+"\t"+message+"\n");
       System.out.flush();       
    }
}
        

• 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)

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);
  }
  

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);
    }
  }
  

• 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

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);
  }
  

• One Fix:
  • Synchronize the iterating block on the underlying collection
• Another Fix:
  • Call toArray() and iterate over the array
• The Drawback of Both:
  • Performance

• An Important Issue:
  • Only one thread may access a synchronized collection at a time and this can cause scalability problems
• Other Approaches:
  • Concurrent collections