JMU
Synchronized Collections
in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
Motivation (cont.)
Synchronized Collections
Synchronized Collections (cont.)
An Example
An Example (cont.)
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();       
    }
}
        
An Important Limitation of Synchronized Collections
An Important Limitation (cont.)
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.)
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?
What About Iterators? (cont.)
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?
Going Further