ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/CyclicBarrier.java
Revision: 1.15
Committed: Sat Sep 13 18:51:11 2003 UTC (20 years, 8 months ago) by dl
Branch: MAIN
Changes since 1.14: +1 -1 lines
Log Message: 
Proofreading pass -- many minor adjustments

File Contents

# User Rev Content
1 dl 1.2 /*
2     * Written by Doug Lea with assistance from members of JCP JSR-166
3     * Expert Group and released to the public domain. Use, modify, and
4     * redistribute this code in any way without acknowledgement.
5     */
6    
7 tim 1.1 package java.util.concurrent;
8 dl 1.6 import java.util.concurrent.locks.*;
9 tim 1.1
10     /**
11 tim 1.10 * A synchronization aid that allows a set of threads to all wait for
12 brian 1.4 * each other to reach a common barrier point. CyclicBarriers are
13 dl 1.3 * useful in programs involving a fixed sized party of threads that
14 brian 1.4 * must occasionally wait for each other. The barrier is called
15 dl 1.3 * <em>cyclic</em> because it can be re-used after the waiting threads
16     * are released.
17 tim 1.1 *
18     * <p>A <tt>CyclicBarrier</tt> supports an optional {@link Runnable} command
19     * that is run once per barrier point, after the last thread in the party
20     * arrives, but before any threads are released.
21     * This <em>barrier action</em> is useful
22     * for updating shared-state before any of the parties continue.
23     *
24 brian 1.4 * <p><b>Sample usage:</b> Here is an example of
25 tim 1.1 * using a barrier in a parallel decomposition design:
26     * <pre>
27     * class Solver {
28     * final int N;
29     * final float[][] data;
30     * final CyclicBarrier barrier;
31     *
32     * class Worker implements Runnable {
33     * int myRow;
34     * Worker(int row) { myRow = row; }
35     * public void run() {
36     * while (!done()) {
37     * processRow(myRow);
38     *
39     * try {
40     * barrier.await();
41 tim 1.9 * } catch (InterruptedException ex) {
42     * return;
43     * } catch (BrokenBarrierException ex) {
44     * return;
45 tim 1.1 * }
46     * }
47     * }
48     * }
49     *
50     * public Solver(float[][] matrix) {
51     * data = matrix;
52     * N = matrix.length;
53     * barrier = new CyclicBarrier(N,
54     * new Runnable() {
55     * public void run() {
56     * mergeRows(...);
57     * }
58     * });
59     * for (int i = 0; i < N; ++i)
60     * new Thread(new Worker(i)).start();
61     *
62     * waitUntilDone();
63     * }
64     * }
65     * </pre>
66     * Here, each worker thread processes a row of the matrix then waits at the
67     * barrier until all rows have been processed. When all rows are processed
68     * the supplied {@link Runnable} barrier action is executed and merges the
69     * rows. If the merger
70     * determines that a solution has been found then <tt>done()</tt> will return
71     * <tt>true</tt> and each worker will terminate.
72     *
73     * <p>If the barrier action does not rely on the parties being suspended when
74     * it is executed, then any of the threads in the party could execute that
75     * action when it is released. To facilitate this, each invocation of
76     * {@link #await} returns the arrival index of that thread at the barrier.
77     * You can then choose which thread should execute the barrier action, for
78     * example:
79     * <pre> if (barrier.await() == 0) {
80     * // log the completion of this iteration
81     * }</pre>
82     *
83 dl 1.12 * <p>The <tt>CyclicBarrier</tt> uses a fast-fail all-or-none breakage
84     * model for failed synchronization attempts: If a thread leaves a
85     * barrier point prematurely because of interruption, failure, or
86     * timeout, all other threads, even those that have not yet resumed
87 dholmes 1.13 * from a previous {@link #await}. will also leave abnormally via
88 dl 1.12 * {@link BrokenBarrierException} (or <tt>InterruptedException</tt> if
89     * they too were interrupted at about the same time).
90 tim 1.1 *
91     * @since 1.5
92 brian 1.4 * @see CountDownLatch
93 tim 1.1 *
94 dl 1.5 * @author Doug Lea
95 tim 1.1 */
96     public class CyclicBarrier {
97 dl 1.5 /** The lock for guarding barrier entry */
98 dl 1.2 private final ReentrantLock lock = new ReentrantLock();
99 dl 1.5 /** Condition to wait on until tripped */
100 dl 1.2 private final Condition trip = lock.newCondition();
101 dl 1.5 /** The number of parties */
102 dl 1.2 private final int parties;
103 dl 1.5 /* The command to run when tripped */
104 dl 1.12 private final Runnable barrierCommand;
105 dl 1.2
106     /**
107 dl 1.12 * The generation number. Incremented upon barrier trip.
108     * Retracted upon reset.
109 dl 1.2 */
110 dl 1.12 private long generation;
111 dl 1.2
112     /**
113 dl 1.12 * Breakage indicator.
114 dl 1.2 */
115 dl 1.12 private boolean broken;
116 dl 1.2
117     /**
118     * Number of parties still waiting. Counts down from parties to 0
119     * on each cycle.
120     */
121     private int count;
122    
123     /**
124 dl 1.12 * Update state on barrier trip and wake up everyone.
125 dl 1.2 */
126     private void nextGeneration() {
127     count = parties;
128 dl 1.12 ++generation;
129     trip.signalAll();
130     }
131    
132     /**
133     * Set barrier as broken and wake up everyone
134     */
135     private void breakBarrier() {
136     broken = true;
137     trip.signalAll();
138 dl 1.2 }
139    
140 dl 1.5 /**
141 dl 1.7 * Main barrier code, covering the various policies.
142 dl 1.5 */
143 dholmes 1.11 private int dowait(boolean timed, long nanos)
144     throws InterruptedException, BrokenBarrierException, TimeoutException {
145 dl 1.2 lock.lock();
146     try {
147     int index = --count;
148 dl 1.12 long g = generation;
149 dl 1.2
150 dl 1.12 if (broken)
151 dl 1.2 throw new BrokenBarrierException();
152    
153     if (Thread.interrupted()) {
154 dl 1.12 breakBarrier();
155 dl 1.2 throw new InterruptedException();
156     }
157    
158     if (index == 0) { // tripped
159     nextGeneration();
160 dl 1.12 boolean ranAction = false;
161 dl 1.2 try {
162     if (barrierCommand != null)
163     barrierCommand.run();
164 dl 1.12 ranAction = true;
165 dl 1.2 return 0;
166 dl 1.12 } finally {
167     if (!ranAction)
168     breakBarrier();
169 dholmes 1.11 }
170 dl 1.2 }
171    
172 dl 1.12 for (;;) {
173 dl 1.2 try {
174     if (!timed)
175     trip.await();
176     else if (nanos > 0)
177     nanos = trip.awaitNanos(nanos);
178 dl 1.12 } catch (InterruptedException ie) {
179     breakBarrier();
180     throw ie;
181 dl 1.2 }
182    
183 dl 1.12 if (broken ||
184     g > generation) // true if a reset occurred while waiting
185     throw new BrokenBarrierException();
186    
187     if (g < generation)
188     return index;
189    
190 dl 1.2 if (timed && nanos <= 0) {
191 dl 1.12 breakBarrier();
192 dl 1.2 throw new TimeoutException();
193     }
194     }
195    
196 tim 1.9 } finally {
197 dl 1.2 lock.unlock();
198     }
199     }
200 tim 1.1
201     /**
202     * Create a new <tt>CyclicBarrier</tt> that will trip when the
203     * given number of parties (threads) are waiting upon it, and which
204     * will execute the given barrier action when the barrier is tripped.
205     *
206     * @param parties the number of threads that must invoke {@link #await}
207     * before the barrier is tripped.
208     * @param barrierAction the command to execute when the barrier is
209 dl 1.15 * tripped, or <tt>null</tt> if there is no action.
210 tim 1.1 *
211     * @throws IllegalArgumentException if <tt>parties</tt> is less than 1.
212     */
213     public CyclicBarrier(int parties, Runnable barrierAction) {
214 dl 1.2 if (parties <= 0) throw new IllegalArgumentException();
215     this.parties = parties;
216     this.count = parties;
217     this.barrierCommand = barrierAction;
218 tim 1.1 }
219    
220     /**
221     * Create a new <tt>CyclicBarrier</tt> that will trip when the
222 dl 1.14 * given number of parties (threads) are waiting upon it, and
223     * does not perform a predefined action upon each barrier.
224 tim 1.1 *
225     * @param parties the number of threads that must invoke {@link #await}
226     * before the barrier is tripped.
227     *
228     * @throws IllegalArgumentException if <tt>parties</tt> is less than 1.
229     */
230     public CyclicBarrier(int parties) {
231 dl 1.2 this(parties, null);
232 tim 1.1 }
233    
234     /**
235     * Return the number of parties required to trip this barrier.
236     * @return the number of parties required to trip this barrier.
237     **/
238     public int getParties() {
239 dl 1.2 return parties;
240 tim 1.1 }
241    
242     /**
243     * Wait until all {@link #getParties parties} have invoked <tt>await</tt>
244     * on this barrier.
245     *
246     * <p>If the current thread is not the last to arrive then it is
247     * disabled for thread scheduling purposes and lies dormant until
248 dl 1.2 * one of following things happens:
249 tim 1.1 * <ul>
250     * <li>The last thread arrives; or
251     * <li>Some other thread {@link Thread#interrupt interrupts} the current
252     * thread; or
253     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
254     * other waiting threads; or
255 dl 1.2 * <li>Some other thread times out while waiting for barrier; or
256 tim 1.1 * <li>Some other thread invokes {@link #reset} on this barrier.
257     * </ul>
258     * <p>If the current thread:
259     * <ul>
260     * <li>has its interrupted status set on entry to this method; or
261     * <li>is {@link Thread#interrupt interrupted} while waiting
262     * </ul>
263     * then {@link InterruptedException} is thrown and the current thread's
264     * interrupted status is cleared.
265     *
266     * <p>If the barrier is {@link #reset} while any thread is waiting, or if
267 dholmes 1.13 * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked,
268     * or whilst any thread is waiting,
269 tim 1.1 * then {@link BrokenBarrierException} is thrown.
270     *
271     * <p>If any thread is {@link Thread#interrupt interrupted} while waiting,
272     * then all other waiting threads will throw
273     * {@link BrokenBarrierException} and the barrier is placed in the broken
274     * state.
275     *
276     * <p>If the current thread is the last thread to arrive, and a
277     * non-null barrier action was supplied in the constructor, then the
278     * current thread runs the action before allowing the other threads to
279     * continue.
280     * If an exception occurs during the barrier action then that exception
281 dholmes 1.13 * will be propagated in the current thread and the barrier is placed in
282     * the broken state.
283 tim 1.1 *
284     * @return the arrival index of the current thread, where index
285     * <tt>{@link #getParties()} - 1</tt> indicates the first to arrive and
286     * zero indicates the last to arrive.
287     *
288     * @throws InterruptedException if the current thread was interrupted
289     * while waiting
290     * @throws BrokenBarrierException if <em>another</em> thread was
291     * interrupted while the current thread was waiting, or the barrier was
292 dl 1.12 * reset, or the barrier was broken when <tt>await</tt> was called,
293     * or the barrier action (if present) failed due an exception.
294 tim 1.1 */
295     public int await() throws InterruptedException, BrokenBarrierException {
296 dl 1.2 try {
297     return dowait(false, 0);
298 tim 1.9 } catch (TimeoutException toe) {
299 dl 1.2 throw new Error(toe); // cannot happen;
300     }
301     }
302    
303     /**
304     * Wait until all {@link #getParties parties} have invoked <tt>await</tt>
305     * on this barrier.
306     *
307     * <p>If the current thread is not the last to arrive then it is
308     * disabled for thread scheduling purposes and lies dormant until
309     * one of the following things happens:
310     * <ul>
311     * <li>The last thread arrives; or
312 dholmes 1.13 * <li>The specified timeout elapses; or
313 dl 1.2 * <li>Some other thread {@link Thread#interrupt interrupts} the current
314     * thread; or
315     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
316     * other waiting threads; or
317     * <li>Some other thread times out while waiting for barrier; or
318     * <li>Some other thread invokes {@link #reset} on this barrier.
319     * </ul>
320     * <p>If the current thread:
321     * <ul>
322     * <li>has its interrupted status set on entry to this method; or
323     * <li>is {@link Thread#interrupt interrupted} while waiting
324     * </ul>
325     * then {@link InterruptedException} is thrown and the current thread's
326     * interrupted status is cleared.
327     *
328     * <p>If the barrier is {@link #reset} while any thread is waiting, or if
329 dholmes 1.13 * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked,
330     * or whilst any thread is waiting,
331 dl 1.2 * then {@link BrokenBarrierException} is thrown.
332     *
333     * <p>If any thread is {@link Thread#interrupt interrupted} while waiting,
334     * then all other waiting threads will throw
335     * {@link BrokenBarrierException} and the barrier is placed in the broken
336     * state.
337     *
338     * <p>If the current thread is the last thread to arrive, and a
339     * non-null barrier action was supplied in the constructor, then the
340     * current thread runs the action before allowing the other threads to
341     * continue.
342     * If an exception occurs during the barrier action then that exception
343 dholmes 1.13 * will be propagated in the current thread and the barrier is placed in
344     * the broken state.
345 dl 1.2 *
346 dl 1.5 * @param timeout the time to wait for the barrier
347     * @param unit the time unit of the timeout parameter
348 dl 1.2 * @return the arrival index of the current thread, where index
349     * <tt>{@link #getParties()} - 1</tt> indicates the first to arrive and
350     * zero indicates the last to arrive.
351     *
352     * @throws InterruptedException if the current thread was interrupted
353     * while waiting
354     * @throws TimeoutException if the specified timeout elapses.
355     * @throws BrokenBarrierException if <em>another</em> thread was
356     * interrupted while the current thread was waiting, or the barrier was
357 dl 1.12 * reset, or the barrier was broken when <tt>await</tt> was called,
358     * or the barrier action (if present) failed due an exception.
359 dl 1.2 */
360 dholmes 1.11 public int await(long timeout, TimeUnit unit)
361     throws InterruptedException,
362     BrokenBarrierException,
363     TimeoutException {
364 dl 1.2 return dowait(true, unit.toNanos(timeout));
365 tim 1.1 }
366    
367     /**
368     * Query if this barrier is in a broken state.
369     * @return <tt>true</tt> if one or more parties broke out of this
370 dl 1.2 * barrier due to interruption or timeout since construction or
371 dholmes 1.13 * the last reset, or a barrier action failed due to an exception;
372     * and <tt>false</tt> otherwise.
373 tim 1.1 */
374     public boolean isBroken() {
375 dl 1.2 lock.lock();
376     try {
377 dl 1.12 return broken;
378 tim 1.9 } finally {
379 dl 1.2 lock.unlock();
380     }
381 tim 1.1 }
382    
383     /**
384     * Reset the barrier to its initial state. If any parties are
385     * currently waiting at the barrier, they will return with a
386 dl 1.8 * {@link BrokenBarrierException}. Note that resets <em>after</em>
387 dl 1.12 * a breakage has occurred for other reasons can be complicated to
388     * carry out; threads need to re-synchronize in some other way,
389     * and choose one to perform the reset. It may be preferable to
390     * instead create a new barrier for subsequent use.
391 tim 1.1 */
392     public void reset() {
393 dl 1.2 lock.lock();
394     try {
395 dl 1.12 /*
396     * Retract generation number enough to cover threads
397     * currently waiting on current and still resuming from
398     * previous generation, plus similarly accommodating spans
399     * after the reset.
400     */
401     generation -= 4;
402     broken = false;
403 dl 1.2 trip.signalAll();
404 tim 1.9 } finally {
405 dl 1.2 lock.unlock();
406     }
407 tim 1.1 }
408    
409     /**
410     * Return the number of parties currently waiting at the barrier.
411     * This method is primarily useful for debugging and assertions.
412     *
413     * @return the number of parties currently blocked in {@link #await}
414     **/
415     public int getNumberWaiting() {
416 dl 1.2 lock.lock();
417     try {
418     return parties - count;
419 tim 1.9 } finally {
420 dl 1.2 lock.unlock();
421     }
422 tim 1.1 }
423    
424     }