ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/CyclicBarrier.java
Revision: 1.17
Committed: Sun Oct 5 23:00:18 2003 UTC (20 years, 8 months ago) by dl
Branch: MAIN
Changes since 1.16: +2 -1 lines
Log Message: 
added drainTo; clarified various exception specs

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 dl 1.17 * will execute the given barrier action when the barrier is tripped,
205     * performed by the last thread enetering the barrier.
206 tim 1.1 *
207     * @param parties the number of threads that must invoke {@link #await}
208     * before the barrier is tripped.
209     * @param barrierAction the command to execute when the barrier is
210 dl 1.15 * tripped, or <tt>null</tt> if there is no action.
211 tim 1.1 *
212     * @throws IllegalArgumentException if <tt>parties</tt> is less than 1.
213     */
214     public CyclicBarrier(int parties, Runnable barrierAction) {
215 dl 1.2 if (parties <= 0) throw new IllegalArgumentException();
216     this.parties = parties;
217     this.count = parties;
218     this.barrierCommand = barrierAction;
219 tim 1.1 }
220    
221     /**
222     * Create a new <tt>CyclicBarrier</tt> that will trip when the
223 dl 1.14 * given number of parties (threads) are waiting upon it, and
224     * does not perform a predefined action upon each barrier.
225 tim 1.1 *
226     * @param parties the number of threads that must invoke {@link #await}
227     * before the barrier is tripped.
228     *
229     * @throws IllegalArgumentException if <tt>parties</tt> is less than 1.
230     */
231     public CyclicBarrier(int parties) {
232 dl 1.2 this(parties, null);
233 tim 1.1 }
234    
235     /**
236     * Return the number of parties required to trip this barrier.
237     * @return the number of parties required to trip this barrier.
238     **/
239     public int getParties() {
240 dl 1.2 return parties;
241 tim 1.1 }
242    
243     /**
244     * Wait until all {@link #getParties parties} have invoked <tt>await</tt>
245     * on this barrier.
246     *
247     * <p>If the current thread is not the last to arrive then it is
248     * disabled for thread scheduling purposes and lies dormant until
249 dl 1.2 * one of following things happens:
250 tim 1.1 * <ul>
251     * <li>The last thread arrives; or
252     * <li>Some other thread {@link Thread#interrupt interrupts} the current
253     * thread; or
254     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
255     * other waiting threads; or
256 dl 1.2 * <li>Some other thread times out while waiting for barrier; or
257 tim 1.1 * <li>Some other thread invokes {@link #reset} on this barrier.
258     * </ul>
259     * <p>If the current thread:
260     * <ul>
261     * <li>has its interrupted status set on entry to this method; or
262     * <li>is {@link Thread#interrupt interrupted} while waiting
263     * </ul>
264     * then {@link InterruptedException} is thrown and the current thread's
265     * interrupted status is cleared.
266     *
267     * <p>If the barrier is {@link #reset} while any thread is waiting, or if
268 dholmes 1.13 * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked,
269 dl 1.16 * or while any thread is waiting,
270 tim 1.1 * then {@link BrokenBarrierException} is thrown.
271     *
272     * <p>If any thread is {@link Thread#interrupt interrupted} while waiting,
273     * then all other waiting threads will throw
274     * {@link BrokenBarrierException} and the barrier is placed in the broken
275     * state.
276     *
277     * <p>If the current thread is the last thread to arrive, and a
278     * non-null barrier action was supplied in the constructor, then the
279     * current thread runs the action before allowing the other threads to
280     * continue.
281     * If an exception occurs during the barrier action then that exception
282 dholmes 1.13 * will be propagated in the current thread and the barrier is placed in
283     * the broken state.
284 tim 1.1 *
285     * @return the arrival index of the current thread, where index
286     * <tt>{@link #getParties()} - 1</tt> indicates the first to arrive and
287     * zero indicates the last to arrive.
288     *
289     * @throws InterruptedException if the current thread was interrupted
290     * while waiting
291     * @throws BrokenBarrierException if <em>another</em> thread was
292     * interrupted while the current thread was waiting, or the barrier was
293 dl 1.12 * reset, or the barrier was broken when <tt>await</tt> was called,
294     * or the barrier action (if present) failed due an exception.
295 tim 1.1 */
296     public int await() throws InterruptedException, BrokenBarrierException {
297 dl 1.2 try {
298     return dowait(false, 0);
299 tim 1.9 } catch (TimeoutException toe) {
300 dl 1.2 throw new Error(toe); // cannot happen;
301     }
302     }
303    
304     /**
305     * Wait until all {@link #getParties parties} have invoked <tt>await</tt>
306     * on this barrier.
307     *
308     * <p>If the current thread is not the last to arrive then it is
309     * disabled for thread scheduling purposes and lies dormant until
310     * one of the following things happens:
311     * <ul>
312     * <li>The last thread arrives; or
313 dholmes 1.13 * <li>The specified timeout elapses; or
314 dl 1.2 * <li>Some other thread {@link Thread#interrupt interrupts} the current
315     * thread; or
316     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
317     * other waiting threads; or
318     * <li>Some other thread times out while waiting for barrier; or
319     * <li>Some other thread invokes {@link #reset} on this barrier.
320     * </ul>
321     * <p>If the current thread:
322     * <ul>
323     * <li>has its interrupted status set on entry to this method; or
324     * <li>is {@link Thread#interrupt interrupted} while waiting
325     * </ul>
326     * then {@link InterruptedException} is thrown and the current thread's
327     * interrupted status is cleared.
328     *
329     * <p>If the barrier is {@link #reset} while any thread is waiting, or if
330 dholmes 1.13 * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked,
331 dl 1.16 * or while any thread is waiting,
332 dl 1.2 * then {@link BrokenBarrierException} is thrown.
333     *
334     * <p>If any thread is {@link Thread#interrupt interrupted} while waiting,
335     * then all other waiting threads will throw
336     * {@link BrokenBarrierException} and the barrier is placed in the broken
337     * state.
338     *
339     * <p>If the current thread is the last thread to arrive, and a
340     * non-null barrier action was supplied in the constructor, then the
341     * current thread runs the action before allowing the other threads to
342     * continue.
343     * If an exception occurs during the barrier action then that exception
344 dholmes 1.13 * will be propagated in the current thread and the barrier is placed in
345     * the broken state.
346 dl 1.2 *
347 dl 1.5 * @param timeout the time to wait for the barrier
348     * @param unit the time unit of the timeout parameter
349 dl 1.2 * @return the arrival index of the current thread, where index
350     * <tt>{@link #getParties()} - 1</tt> indicates the first to arrive and
351     * zero indicates the last to arrive.
352     *
353     * @throws InterruptedException if the current thread was interrupted
354     * while waiting
355     * @throws TimeoutException if the specified timeout elapses.
356     * @throws BrokenBarrierException if <em>another</em> thread was
357     * interrupted while the current thread was waiting, or the barrier was
358 dl 1.12 * reset, or the barrier was broken when <tt>await</tt> was called,
359     * or the barrier action (if present) failed due an exception.
360 dl 1.2 */
361 dholmes 1.11 public int await(long timeout, TimeUnit unit)
362     throws InterruptedException,
363     BrokenBarrierException,
364     TimeoutException {
365 dl 1.2 return dowait(true, unit.toNanos(timeout));
366 tim 1.1 }
367    
368     /**
369     * Query if this barrier is in a broken state.
370     * @return <tt>true</tt> if one or more parties broke out of this
371 dl 1.2 * barrier due to interruption or timeout since construction or
372 dholmes 1.13 * the last reset, or a barrier action failed due to an exception;
373     * and <tt>false</tt> otherwise.
374 tim 1.1 */
375     public boolean isBroken() {
376 dl 1.2 lock.lock();
377     try {
378 dl 1.12 return broken;
379 tim 1.9 } finally {
380 dl 1.2 lock.unlock();
381     }
382 tim 1.1 }
383    
384     /**
385     * Reset the barrier to its initial state. If any parties are
386     * currently waiting at the barrier, they will return with a
387 dl 1.8 * {@link BrokenBarrierException}. Note that resets <em>after</em>
388 dl 1.12 * a breakage has occurred for other reasons can be complicated to
389     * carry out; threads need to re-synchronize in some other way,
390     * and choose one to perform the reset. It may be preferable to
391     * instead create a new barrier for subsequent use.
392 tim 1.1 */
393     public void reset() {
394 dl 1.2 lock.lock();
395     try {
396 dl 1.12 /*
397     * Retract generation number enough to cover threads
398     * currently waiting on current and still resuming from
399     * previous generation, plus similarly accommodating spans
400     * after the reset.
401     */
402     generation -= 4;
403     broken = false;
404 dl 1.2 trip.signalAll();
405 tim 1.9 } finally {
406 dl 1.2 lock.unlock();
407     }
408 tim 1.1 }
409    
410     /**
411     * Return the number of parties currently waiting at the barrier.
412     * This method is primarily useful for debugging and assertions.
413     *
414     * @return the number of parties currently blocked in {@link #await}
415     **/
416     public int getNumberWaiting() {
417 dl 1.2 lock.lock();
418     try {
419     return parties - count;
420 tim 1.9 } finally {
421 dl 1.2 lock.unlock();
422     }
423 tim 1.1 }
424    
425     }