ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/CyclicBarrier.java
Revision: 1.22
Committed: Sat Dec 27 19:26:25 2003 UTC (20 years, 5 months ago) by dl
Branch: MAIN
Changes since 1.21: +2 -2 lines
Log Message: 
Headers reference Creative Commons

File Contents

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