ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/CyclicBarrier.java
Revision: 1.30
Committed: Thu Apr 21 23:56:09 2005 UTC (19 years, 1 month ago) by dl
Branch: MAIN
Changes since 1.29: +17 -20 lines
Log Message: 
Incorporate review suggestiosn from last change

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 dl 1.28 * arrives, but before any threads are released.
21 tim 1.1 * This <em>barrier action</em> is useful
22     * for updating shared-state before any of the parties continue.
23 dl 1.28 *
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 dl 1.28 *
32 tim 1.1 * 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 dl 1.28 * barrier.await();
41     * } 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 dl 1.28 * barrier = new CyclicBarrier(N,
54 tim 1.1 * new Runnable() {
55 dl 1.28 * public void run() {
56     * mergeRows(...);
57 tim 1.1 * }
58     * });
59 dl 1.28 * for (int i = 0; i < N; ++i)
60 tim 1.1 * new Thread(new Worker(i)).start();
61     *
62     * waitUntilDone();
63     * }
64     * }
65     * </pre>
66 dl 1.28 * Here, each worker thread processes a row of the matrix then waits at the
67 tim 1.1 * barrier until all rows have been processed. When all rows are processed
68 dl 1.28 * the supplied {@link Runnable} barrier action is executed and merges the
69 tim 1.1 * 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 dl 1.28 * You can then choose which thread should execute the barrier action, for
78 tim 1.1 * example:
79     * <pre> if (barrier.await() == 0) {
80     * // log the completion of this iteration
81     * }</pre>
82     *
83 dl 1.28 * <p>The <tt>CyclicBarrier</tt> uses an all-or-none breakage model
84     * for failed synchronization attempts: If a thread leaves a barrier
85     * point prematurely because of interruption, failure, or timeout, all
86     * other threads waiting at that barrier point will also leave
87     * abnormally via {@link BrokenBarrierException} (or
88     * <tt>InterruptedException</tt> if they too were interrupted at about
89     * 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.28 /**
98     * Each use of the barrier is represented as a generation instance.
99     * The generation changes whenever the barrier is tripped, or
100     * is reset. There can be many generations associated with threads
101     * using the barrier - due to the non-deterministic way the lock
102     * may be allocated to waiting threads - but only one of these
103     * can be active at a time (the one to which <tt>count</tt> applies)
104     * and all the rest are either broken or tripped.
105     * There need not be an active generation if there has been a break
106     * but no subsequent reset.
107     */
108     private static class Generation {
109     boolean broken = false;
110     boolean tripped = false;
111     }
112    
113 dl 1.5 /** The lock for guarding barrier entry */
114 dl 1.2 private final ReentrantLock lock = new ReentrantLock();
115 dl 1.5 /** Condition to wait on until tripped */
116 dl 1.21 private final Condition trip = lock.newCondition();
117 dl 1.5 /** The number of parties */
118 dl 1.2 private final int parties;
119 dl 1.5 /* The command to run when tripped */
120 dl 1.12 private final Runnable barrierCommand;
121 dl 1.28 /** The current generation */
122     private Generation generation = new Generation();
123 dl 1.2
124     /**
125     * Number of parties still waiting. Counts down from parties to 0
126 dl 1.28 * on each generation. This only has meaning for the current non-broken
127     * generation. It is reset to parties on each new generation.
128 dl 1.2 */
129 dl 1.28 private int count;
130 dl 1.2
131     /**
132 jsr166 1.29 * Updates state on barrier trip and wakes up everyone.
133 dl 1.28 * Called only while holding lock.
134     */
135 dl 1.2 private void nextGeneration() {
136 dl 1.28 // signal completion of last generation
137     generation.tripped = true;
138     trip.signalAll();
139     // set up next generation
140 dl 1.2 count = parties;
141 dl 1.28 generation = new Generation();
142 dl 1.12 }
143    
144     /**
145 jsr166 1.29 * Sets current barrier generation as broken and wakes up everyone.
146 dl 1.28 * Called only while holding lock.
147 dl 1.12 */
148     private void breakBarrier() {
149 dl 1.28 generation.broken = true;
150 dl 1.12 trip.signalAll();
151 dl 1.2 }
152    
153 dl 1.5 /**
154 dl 1.7 * Main barrier code, covering the various policies.
155 dl 1.5 */
156 dl 1.28 private int dowait(boolean timed, long nanos)
157     throws InterruptedException, BrokenBarrierException,
158     TimeoutException {
159 dl 1.20 final ReentrantLock lock = this.lock;
160 dl 1.2 lock.lock();
161     try {
162 dl 1.30 final Generation g = generation;
163 dl 1.2
164 dl 1.28 if (g.broken)
165 dl 1.2 throw new BrokenBarrierException();
166    
167     if (Thread.interrupted()) {
168 dl 1.12 breakBarrier();
169 dl 1.2 throw new InterruptedException();
170     }
171    
172 dl 1.30 int index = --count;
173     if (index == 0) { // tripped
174     boolean ranAction = false;
175     try {
176     if (barrierCommand != null)
177     barrierCommand.run();
178     ranAction = true;
179     nextGeneration();
180     return 0;
181     } finally {
182     if (!ranAction)
183     breakBarrier();
184     }
185     }
186 dl 1.2
187 dl 1.28 // loop until tripped, broken, interrupted, or timed out
188 dl 1.12 for (;;) {
189 dl 1.2 try {
190 dl 1.28 if (!timed)
191 dl 1.2 trip.await();
192 dl 1.23 else if (nanos > 0L)
193 dl 1.2 nanos = trip.awaitNanos(nanos);
194 dl 1.12 } catch (InterruptedException ie) {
195     breakBarrier();
196     throw ie;
197 dl 1.2 }
198 dl 1.28
199 dl 1.30 if (g.broken)
200 dl 1.12 throw new BrokenBarrierException();
201    
202 dl 1.28 if (g.tripped)
203 dl 1.12 return index;
204    
205 dl 1.23 if (timed && nanos <= 0L) {
206 dl 1.12 breakBarrier();
207 dl 1.2 throw new TimeoutException();
208     }
209     }
210 tim 1.9 } finally {
211 dl 1.2 lock.unlock();
212     }
213     }
214 tim 1.1
215     /**
216 dl 1.25 * Creates a new <tt>CyclicBarrier</tt> that will trip when the
217 tim 1.1 * given number of parties (threads) are waiting upon it, and which
218 dl 1.17 * will execute the given barrier action when the barrier is tripped,
219 dl 1.19 * performed by the last thread entering the barrier.
220 tim 1.1 *
221     * @param parties the number of threads that must invoke {@link #await}
222     * before the barrier is tripped.
223     * @param barrierAction the command to execute when the barrier is
224 dl 1.15 * tripped, or <tt>null</tt> if there is no action.
225 tim 1.1 *
226     * @throws IllegalArgumentException if <tt>parties</tt> is less than 1.
227     */
228     public CyclicBarrier(int parties, Runnable barrierAction) {
229 dl 1.2 if (parties <= 0) throw new IllegalArgumentException();
230 dl 1.28 this.parties = parties;
231 dl 1.2 this.count = parties;
232     this.barrierCommand = barrierAction;
233 tim 1.1 }
234    
235     /**
236 dl 1.25 * Creates a new <tt>CyclicBarrier</tt> that will trip when the
237 dl 1.14 * given number of parties (threads) are waiting upon it, and
238     * does not perform a predefined action upon each barrier.
239 tim 1.1 *
240     * @param parties the number of threads that must invoke {@link #await}
241     * before the barrier is tripped.
242     *
243     * @throws IllegalArgumentException if <tt>parties</tt> is less than 1.
244     */
245     public CyclicBarrier(int parties) {
246 dl 1.2 this(parties, null);
247 tim 1.1 }
248    
249     /**
250 dl 1.25 * Returns the number of parties required to trip this barrier.
251 tim 1.1 * @return the number of parties required to trip this barrier.
252     **/
253     public int getParties() {
254 dl 1.2 return parties;
255 tim 1.1 }
256    
257     /**
258 dl 1.25 * Waits until all {@link #getParties parties} have invoked <tt>await</tt>
259 tim 1.1 * on this barrier.
260     *
261     * <p>If the current thread is not the last to arrive then it is
262     * disabled for thread scheduling purposes and lies dormant until
263 dl 1.2 * one of following things happens:
264 tim 1.1 * <ul>
265     * <li>The last thread arrives; or
266     * <li>Some other thread {@link Thread#interrupt interrupts} the current
267     * thread; or
268     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
269     * other waiting threads; or
270 dl 1.24 * <li>Some other thread times out while waiting for barrier; or
271 tim 1.1 * <li>Some other thread invokes {@link #reset} on this barrier.
272     * </ul>
273     * <p>If the current thread:
274     * <ul>
275     * <li>has its interrupted status set on entry to this method; or
276     * <li>is {@link Thread#interrupt interrupted} while waiting
277     * </ul>
278     * then {@link InterruptedException} is thrown and the current thread's
279     * interrupted status is cleared.
280     *
281 dl 1.28 * <p>If the barrier is {@link #reset} while any thread is waiting, or if
282 dholmes 1.13 * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked,
283 dl 1.16 * or while any thread is waiting,
284 tim 1.1 * then {@link BrokenBarrierException} is thrown.
285     *
286     * <p>If any thread is {@link Thread#interrupt interrupted} while waiting,
287 dl 1.28 * then all other waiting threads will throw
288 tim 1.1 * {@link BrokenBarrierException} and the barrier is placed in the broken
289     * state.
290     *
291     * <p>If the current thread is the last thread to arrive, and a
292     * non-null barrier action was supplied in the constructor, then the
293 dl 1.28 * current thread runs the action before allowing the other threads to
294 tim 1.1 * continue.
295     * If an exception occurs during the barrier action then that exception
296 dholmes 1.13 * will be propagated in the current thread and the barrier is placed in
297     * the broken state.
298 tim 1.1 *
299     * @return the arrival index of the current thread, where index
300 dl 1.28 * <tt>{@link #getParties()} - 1</tt> indicates the first to arrive and
301 tim 1.1 * zero indicates the last to arrive.
302     *
303 dl 1.28 * @throws InterruptedException if the current thread was interrupted
304 jsr166 1.29 * while waiting.
305 tim 1.1 * @throws BrokenBarrierException if <em>another</em> thread was
306 dl 1.28 * interrupted or timed out while the current thread was waiting,
307     * or the barrier was reset, or the barrier was broken when
308     * <tt>await</tt> was called, or the barrier action (if present)
309     * failed due an exception.
310 tim 1.1 */
311     public int await() throws InterruptedException, BrokenBarrierException {
312 dl 1.2 try {
313 dl 1.23 return dowait(false, 0L);
314 tim 1.9 } catch (TimeoutException toe) {
315 dl 1.2 throw new Error(toe); // cannot happen;
316     }
317     }
318    
319     /**
320 dl 1.25 * Waits until all {@link #getParties parties} have invoked <tt>await</tt>
321 dl 1.2 * on this barrier.
322     *
323     * <p>If the current thread is not the last to arrive then it is
324     * disabled for thread scheduling purposes and lies dormant until
325     * one of the following things happens:
326     * <ul>
327     * <li>The last thread arrives; or
328 dholmes 1.13 * <li>The specified timeout elapses; or
329 dl 1.2 * <li>Some other thread {@link Thread#interrupt interrupts} the current
330     * thread; or
331     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
332     * other waiting threads; or
333 dl 1.24 * <li>Some other thread times out while waiting for barrier; or
334 dl 1.2 * <li>Some other thread invokes {@link #reset} on this barrier.
335     * </ul>
336     * <p>If the current thread:
337     * <ul>
338     * <li>has its interrupted status set on entry to this method; or
339     * <li>is {@link Thread#interrupt interrupted} while waiting
340     * </ul>
341     * then {@link InterruptedException} is thrown and the current thread's
342     * interrupted status is cleared.
343     *
344 dl 1.26 * <p>If the specified waiting time elapses then {@link TimeoutException}
345     * is thrown. If the time is less than or equal to zero, the
346     * method will not wait at all.
347     *
348 dl 1.28 * <p>If the barrier is {@link #reset} while any thread is waiting, or if
349 dholmes 1.13 * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked,
350 dl 1.16 * or while any thread is waiting,
351 dl 1.2 * then {@link BrokenBarrierException} is thrown.
352     *
353     * <p>If any thread is {@link Thread#interrupt interrupted} while waiting,
354 dl 1.28 * then all other waiting threads will throw
355 dl 1.2 * {@link BrokenBarrierException} and the barrier is placed in the broken
356     * state.
357     *
358     * <p>If the current thread is the last thread to arrive, and a
359     * non-null barrier action was supplied in the constructor, then the
360 dl 1.28 * current thread runs the action before allowing the other threads to
361 dl 1.2 * continue.
362     * If an exception occurs during the barrier action then that exception
363 dholmes 1.13 * will be propagated in the current thread and the barrier is placed in
364     * the broken state.
365 dl 1.2 *
366 dl 1.5 * @param timeout the time to wait for the barrier
367     * @param unit the time unit of the timeout parameter
368 dl 1.2 * @return the arrival index of the current thread, where index
369 jsr166 1.29 * <tt>{@link #getParties()} - 1</tt> indicates the first to arrive and
370 dl 1.2 * zero indicates the last to arrive.
371     *
372 dl 1.28 * @throws InterruptedException if the current thread was interrupted
373 jsr166 1.29 * while waiting.
374 dl 1.2 * @throws TimeoutException if the specified timeout elapses.
375     * @throws BrokenBarrierException if <em>another</em> thread was
376 dl 1.28 * interrupted or timed out while the current thread was waiting,
377     * or the barrier was reset, or the barrier was broken when
378     * <tt>await</tt> was called, or the barrier action (if present)
379     * failed due an exception.
380     */
381     public int await(long timeout, TimeUnit unit)
382     throws InterruptedException,
383     BrokenBarrierException,
384     TimeoutException {
385 dl 1.2 return dowait(true, unit.toNanos(timeout));
386 tim 1.1 }
387    
388     /**
389 dl 1.25 * Queries if this barrier is in a broken state.
390 tim 1.1 * @return <tt>true</tt> if one or more parties broke out of this
391 dl 1.2 * barrier due to interruption or timeout since construction or
392 dl 1.28 * the last reset, or a barrier action failed due to an exception;
393 jsr166 1.29 * <tt>false</tt> otherwise.
394 tim 1.1 */
395     public boolean isBroken() {
396 dl 1.20 final ReentrantLock lock = this.lock;
397 dl 1.2 lock.lock();
398     try {
399 dl 1.28 return generation.broken;
400 tim 1.9 } finally {
401 dl 1.2 lock.unlock();
402     }
403 tim 1.1 }
404    
405     /**
406 dl 1.25 * Resets the barrier to its initial state. If any parties are
407 tim 1.1 * currently waiting at the barrier, they will return with a
408 dl 1.8 * {@link BrokenBarrierException}. Note that resets <em>after</em>
409 dl 1.12 * a breakage has occurred for other reasons can be complicated to
410     * carry out; threads need to re-synchronize in some other way,
411     * and choose one to perform the reset. It may be preferable to
412     * instead create a new barrier for subsequent use.
413 tim 1.1 */
414     public void reset() {
415 dl 1.20 final ReentrantLock lock = this.lock;
416 dl 1.2 lock.lock();
417     try {
418 dl 1.28 breakBarrier(); // break the current generation
419     nextGeneration(); // start a new generation
420 tim 1.9 } finally {
421 dl 1.2 lock.unlock();
422     }
423 tim 1.1 }
424    
425     /**
426 dl 1.25 * Returns the number of parties currently waiting at the barrier.
427 tim 1.1 * This method is primarily useful for debugging and assertions.
428     *
429 jsr166 1.29 * @return the number of parties currently blocked in {@link #await}.
430 tim 1.1 **/
431     public int getNumberWaiting() {
432 dl 1.20 final ReentrantLock lock = this.lock;
433 dl 1.2 lock.lock();
434     try {
435 dl 1.30 return generation.broken ? 0 : parties - count;
436 tim 1.9 } finally {
437 dl 1.2 lock.unlock();
438     }
439 tim 1.1 }
440     }