Synchronizers

The java.util.concurrent package contains several classes that help manage a set of collaborating threadssee Table 1-3. These mechanisms have "canned functionality" for common rendezvous patterns between threads. If you have a set of collaborating threads that follows one of these behavior patterns, you should simply reuse the appropriate library class instead of trying to come up with a handcrafted collection of locks.

Table 1-3. Synchronizers
Class	What It Does	When To Use
`CyclicBarrier`	Allows a set of threads to wait until a predefined count of them has reached a common barrier, and then optionally executes a barrier action.	When a number of threads need to complete before their results can be used.
`CountDownLatch`	Allows a set of threads to wait until a count has been decremented to 0.	When one or more threads need to wait until a specified number of results are available.
`Exchanger`	Allows two threads to exchange objects when both are ready for the exchange.	When two threads work on two instances of the same data structure, one by filling an instance and the other by emptying the other.
`SynchronousQueue`	Allows a thread to hand off an object to another thread.	To send an object from one thread to another when both are ready, without explicit synchronization.
`Semaphore`	Allows a set of threads to wait until permits are available for proceeding.	To restrict the total number of threads that can access a resource. If permit count is one, use to block threads until another thread gives permission.

Barriers

The CyclicBarrier class implements a rendezvous called a barrier. Consider a number of threads that are working on parts of a computation. When all parts are ready, the results need to be combined. When a thread is done with its part, we let it run against the barrier. Once all threads have reached the barrier, the barrier gives way and the threads can proceed.

Here are the details. First, construct a barrier, giving the number of participating threads:

 CyclicBarrier barrier = new CyclicBarrier(nthreads);

Each thread does some work and calls await on the barrier upon completion:

 public void run() {    doWork();    barrier.await();    . . . }

The await method takes an optional timeout parameter:

 barrier.await(100, TimeUnit.MILLISECONDS);

If any of the threads waiting for the barrier leaves the barrier, then the barrier breaks. (A thread can leave because it called await with a timeout or because it was interrupted.) In that case, the await method for all other threads throws a BrokenBarrierException. Threads that are already waiting have their await call terminated immediately.

You can supply an optional barrier action that is executed when all threads have reached the barrier:

 Runnable barrierAction = . . .; CyclicBarrier barrier = new CyclicBarrier(nthreads, barrierAction);

The action can harvest the result of the individual threads.

The barrier is called cyclic because it can be reused after all waiting threads have been released.

Countdown Latches

A CountDownLatch lets a set of threads wait until a count has reached zero. It differs from a barrier in these respects:

Not all threads need to wait for the latch until it can be opened.
The latch can be counted down by external events.
The countdown latch is one-time only. Once the count has reached 0, you cannot reuse it.

A useful special case is a latch with a count of 1. This implements a one-time gate. Threads are held at the gate until another thread sets the count to 0.

Imagine, for example, a set of threads that need some initial data to do their work. The worker threads are started and wait at the gate. Another thread prepares the data. When it is ready, it calls countDown, and all worker threads proceed.

Exchangers

An Exchanger is used when two threads are working on two instances of the same data buffer. Typically, one thread fills the buffer, and the other consumes its contents. When both are done, they exchange their buffers.

Synchronous Queues

A synchronous queue is a mechanism that pairs up producer and consumer threads. When a thread calls put on a SynchronousQueue, it blocks until another thread calls take, and vice versa. Unlike the case with an Exchanger, data are only transferred in one direction, from the producer to the consumer.

Even though the SynchronousQueue class implements the BlockingQueue interface, it is not conceptually a queue. It does not contain any elementsits size method always returns 0.

Semaphores

Conceptually, a semaphore manages a number of permits. To proceed past the semaphore, a thread requests a permit by calling acquire. Only a fixed number of permits are available, limiting the number of threads that are allowed to pass. Other threads may issue permits by calling release. There are no actual permit objects. The semaphore simply keeps a count. Moreover, a permit doesn't have to be released by the thread that acquires it. In fact, any thread can issue any number of permits. If it issues more than the maximum available, the semaphore is simply set to the maximum count. This generality makes semaphores both very flexible and potentially confusing.

Semaphores were invented by Edsger Dijkstra in 1968, for use as a synchronization primitive. Dijkstra showed that semaphores can be efficiently implemented and that they are powerful enough to solve many common thread synchronization problems. In just about any operating systems textbook, you will find implementations of bounded queues using semaphores. Of course, application programmers shouldn't reinvent bounded queues. We suggest that you only use semaphores when their behavior maps well onto your synchronization problem, without your going through mental contortions.

For example, a semaphore with a permit count of 1 is useful as a gate that can be opened and closed by another thread. Imagine a program that does some work, then waits for a user to study the result and press a button to continue, then does the next unit of work. The worker thread calls acquire whenever it is ready to pause. The GUI thread calls release whenever the user clicks the Continue button.

What happens if the user clicks the button multiple times while the worker thread is ready? Because only one permit is available, the permit count stays at 1.

The program in Example 1-9 puts this idea to work. The program animates a sorting algorithm. A worker thread sorts an array, stopping periodically and waiting for the user to give permission to proceed. The user can admire a painting of the current state of the algorithm and press the Continue button to allow the worker thread to go to the next step.

We didn't want to bore you with the code for a sorting algorithm, so we simply call Arrays.sort. To pause the algorithm, we supply a Comparator object that waits for the semaphore. Thus, the animation is paused whenever the algorithm compares two elements. We paint the current values of the array and highlight the elements that are being compared (see Figure 1-7).

Example 1-9. AlgorithmAnimation.java

[View full width]

   1. import java.awt.*;   2. import java.awt.geom.*;   3. import java.awt.event.*;   4. import java.util.*;   5. import java.util.concurrent.*;   6. import javax.swing.*;   7.   8. /**   9.    This program animates a sort algorithm.  10. */  11. public class AlgorithmAnimation  12. {  13.    public static void main(String[] args)  14.    {  15.       JFrame frame = new AnimationFrame();  16.       frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);  17.       frame.setVisible(true);  18.    }  19. }  20.  21. /**  22.    This frame shows the array as it is sorted, together with buttons to single-step  the animation  23.    or to run it without interruption.  24. */  25. class AnimationFrame extends JFrame  26. {  27.    public AnimationFrame()  28.    {  29.       ArrayPanel panel = new ArrayPanel();  30.       add(panel, BorderLayout.CENTER);  31.  32.       Double[] values = new Double[VALUES_LENGTH];  33.       final Sorter sorter = new Sorter(values, panel);  34.  35.       JButton runButton = new JButton("Run");  36.       runButton.addActionListener(new  37.          ActionListener()  38.          {  39.             public void actionPerformed(ActionEvent event)  40.             {  41.                sorter.setRun();  42.             }  43.          });  44.  45.       JButton stepButton = new JButton("Step");  46.       stepButton.addActionListener(new  47.          ActionListener()  48.          {  49.             public void actionPerformed(ActionEvent event)  50.             {  51.                sorter.setStep();  52.             }  53.          });  54.  55.       JPanel buttons = new JPanel();  56.       buttons.add(runButton);  57.       buttons.add(stepButton);  58.       add(buttons, BorderLayout.NORTH);  59.       setSize(DEFAULT_WIDTH, DEFAULT_HEIGHT);  60.  61.       for (int i = 0; i < values.length; i++)  62.          values[i] = new Double(Math.random());  63.  64.       Thread t = new Thread(sorter);  65.       t.start();  66.    }  67.  68.    private static final int DEFAULT_WIDTH = 300;  69.    private static final int DEFAULT_HEIGHT = 300;  70.    private static final int VALUES_LENGTH = 30;  71. }  72.  73. /**  74.    This runnable executes a sort algorithm.  75.    When two elements are compared, the algorithm  76.    pauses and updates a panel.  77. */  78. class Sorter implements Runnable  79. {  80.    /**  81.       Constructs a Sorter.  82.       @param values the array to be sorted  83.       @param panel the panel on which to display the sorting progress  84.    */  85.    public Sorter(Double[] values, ArrayPanel panel)  86.    {  87.       this.values = values;  88.       this.panel = panel;  89.       this.gate = new Semaphore(1);  90.       this.run = false;  91.    }  92.  93.    /**  94.       Sets the sorter to "run" mode.  95.    */  96.    public void setRun()  97.    {  98.       run = true;  99.       gate.release(); 100.    } 101. 102.    /** 103.       Sets the sorter to "step" mode. 104.    */ 105.    public void setStep() 106.    { 107.       run = false; 108.       gate.release(); 109.    } 110. 111.    public void run() 112.    { 113.       Comparator<Double> comp = new 114.          Comparator<Double>() 115.          { 116.             public int compare(Double i1, Double i2) 117.             { 118.                panel.setValues(values, i1, i2); 119.                try 120.                { 121.                   if (run) 122.                      Thread.sleep(DELAY); 123.                   else 124.                      gate.acquire(); 125.                } 126.                catch (InterruptedException exception) 127.                { 128.                   Thread.currentThread().interrupt(); 129.                } 130.                return i1.compareTo(i2); 131.             } 132.          }; 133.       Arrays.sort(values, comp); 134.       panel.setValues(values, null, null); 135.    } 136. 137.    private Double[] values; 138.    private ArrayPanel panel; 139.    private Semaphore gate; 140.    private static final int DELAY = 100; 141.    private boolean run; 142. } 143. 144. /** 145.    This panel draws an array and marks two elements in the 146.    array. 147. */ 148. class ArrayPanel extends JPanel 149. { 150. 151.    public void paintComponent(Graphics g) 152.    { 153.       if (values == null) return; 154.       super.paintComponent(g); 155.       Graphics2D g2 = (Graphics2D) g; 156.       int width = getWidth() / values.length; 157.       for (int i = 0; i < values.length; i++) 158.       { 159.          double height = values[i] * getHeight(); 160.          Rectangle2D bar = new Rectangle2D.Double(width * i, 0, width, height); 161.          if (values[i] == marked1 || values[i] == marked2) 162.             g2.fill(bar); 163.          else 164.             g2.draw(bar); 165.       } 166.    } 167. 168.    /** 169.       Sets the values to be painted. 170.       @param values the array of values to display 171.       @param marked1 the first marked element 172.       @param marked2 the second marked element 173.    */ 174.    public void setValues(Double[] values, Double marked1, Double marked2) 175.    { 176.       this.values = values; 177.       this.marked1 = marked1; 178.       this.marked2 = marked2; 179.       repaint(); 180.    } 181. 182.    private Double marked1; 183.    private Double marked2; 184.    private Double[] values; 185. }

Figure 1-7. Animating a sort algorithm

 java.util.concurrent.CyclicBarrier 5.0

CyclicBarrier(int parties)
CyclicBarrier(int parties, Runnable barrierAction)
constructs a cyclic barrier for the given number of parties. The barrierAction is executed when all parties have called await on the barrier.
int await()
int await(long time, TimeUnit unit)
waits until all parties have called await on the barrier or until the timeout has been reached, in which case a TimeoutException is thrown. Upon success, returns the arrival index of this party. The first party has index parties - 1, and the last party has index 0.

 java.util.concurrent.CountDownLatch 5.0

CountdownLatch(int count)
constructs a countdown latch with the given count.
void await()
waits for this latch to count down to 0.
boolean await(long time, TimeUnit unit)
waits for this latch to count down to 0 or for the timeout to elapse. Returns true if the count is 0, false if the timeout elapsed.
public void countDown()
counts down the counter of this latch.

 java.util.concurrent.Exchanger<V> 5.0

V exchange(V item)
V exchange(V item, long time, TimeUnit unit)
blocks until another thread calls this method, and then exchanges the item with the other thread and returns the other thread's item. The second method throws a TimeoutException after the timeout has elapsed.

 java.util.concurrent.SynchronousQueue<V> 5.0

SynchronousQueue()
SynchronousQueue(boolean fair)
constructs a synchronous queue that allows threads to hand off items. If fair is true, the queue favors the longest-waiting threads.
void put(V item)
blocks until another thread calls take to take this item.
V take()
blocks until another thread calls put. Returns the item that the other thread provided.

 java.util.concurrent.Semaphore 5.0

Semaphore(int permits)
Semaphore(int permits, boolean fair)
construct a semaphore with the given maximum number of permits. If fair is TRue, the queue favors the longest-waiting threads.
void acquire()
waits to acquire a permit.
boolean tryAcquire()
tries to acquire a permit; returns false if none is available.
boolean tryAcquire(long time, TimeUnit unit)
tries to acquire a permit within the given time; returns false if none is available.
void release()
releases a permit.