ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/CyclicBarrier.java
Revision: 1.12
Committed: Tue Aug 26 13:07:36 2003 UTC (20 years, 9 months ago) by dl
Branch: MAIN
Changes since 1.11: +63 -63 lines
Log Message: 
Style cleanups to COWList; CyclicBarrier broken barriers now Fast-fail

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     * from a previous {@link await}. will also leave abnormally via
88     * {@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     * @spec JSR-166
93 dl 1.12 * @revised $Date: 2003/08/25 22:32:40 $
94     * @editor $Author: dholmes $
95 brian 1.4 * @see CountDownLatch
96 tim 1.1 *
97 dl 1.5 * @author Doug Lea
98 tim 1.1 */
99     public class CyclicBarrier {
100 dl 1.5 /** The lock for guarding barrier entry */
101 dl 1.2 private final ReentrantLock lock = new ReentrantLock();
102 dl 1.5 /** Condition to wait on until tripped */
103 dl 1.2 private final Condition trip = lock.newCondition();
104 dl 1.5 /** The number of parties */
105 dl 1.2 private final int parties;
106 dl 1.5 /* The command to run when tripped */
107 dl 1.12 private final Runnable barrierCommand;
108 dl 1.2
109     /**
110 dl 1.12 * The generation number. Incremented upon barrier trip.
111     * Retracted upon reset.
112 dl 1.2 */
113 dl 1.12 private long generation;
114 dl 1.2
115     /**
116 dl 1.12 * Breakage indicator.
117 dl 1.2 */
118 dl 1.12 private boolean broken;
119 dl 1.2
120     /**
121     * Number of parties still waiting. Counts down from parties to 0
122     * on each cycle.
123     */
124     private int count;
125    
126     /**
127 dl 1.12 * Update state on barrier trip and wake up everyone.
128 dl 1.2 */
129     private void nextGeneration() {
130     count = parties;
131 dl 1.12 ++generation;
132     trip.signalAll();
133     }
134    
135     /**
136     * Set barrier as broken and wake up everyone
137     */
138     private void breakBarrier() {
139     broken = true;
140     trip.signalAll();
141 dl 1.2 }
142    
143 dl 1.5 /**
144 dl 1.7 * Main barrier code, covering the various policies.
145 dl 1.5 */
146 dholmes 1.11 private int dowait(boolean timed, long nanos)
147     throws InterruptedException, BrokenBarrierException, TimeoutException {
148 dl 1.2 lock.lock();
149     try {
150     int index = --count;
151 dl 1.12 long g = generation;
152 dl 1.2
153 dl 1.12 if (broken)
154 dl 1.2 throw new BrokenBarrierException();
155    
156     if (Thread.interrupted()) {
157 dl 1.12 breakBarrier();
158 dl 1.2 throw new InterruptedException();
159     }
160    
161     if (index == 0) { // tripped
162     nextGeneration();
163 dl 1.12 boolean ranAction = false;
164 dl 1.2 try {
165     if (barrierCommand != null)
166     barrierCommand.run();
167 dl 1.12 ranAction = true;
168 dl 1.2 return 0;
169 dl 1.12 } finally {
170     if (!ranAction)
171     breakBarrier();
172 dholmes 1.11 }
173 dl 1.2 }
174    
175 dl 1.12 for (;;) {
176 dl 1.2 try {
177     if (!timed)
178     trip.await();
179     else if (nanos > 0)
180     nanos = trip.awaitNanos(nanos);
181 dl 1.12 } catch (InterruptedException ie) {
182     breakBarrier();
183     throw ie;
184 dl 1.2 }
185    
186 dl 1.12 if (broken ||
187     g > generation) // true if a reset occurred while waiting
188     throw new BrokenBarrierException();
189    
190     if (g < generation)
191     return index;
192    
193 dl 1.2 if (timed && nanos <= 0) {
194 dl 1.12 breakBarrier();
195 dl 1.2 throw new TimeoutException();
196     }
197     }
198    
199 tim 1.9 } finally {
200 dl 1.2 lock.unlock();
201     }
202     }
203 tim 1.1
204     /**
205     * Create a new <tt>CyclicBarrier</tt> that will trip when the
206     * given number of parties (threads) are waiting upon it, and which
207     * will execute the given barrier action when the barrier is tripped.
208     *
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     * tripped.
213     *
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     * given number of parties (threads) are waiting upon it.
226     *
227     * <p>This is equivalent to <tt>CyclicBarrier(parties, null)</tt>.
228     *
229     * @param parties the number of threads that must invoke {@link #await}
230     * before the barrier is tripped.
231     *
232     * @throws IllegalArgumentException if <tt>parties</tt> is less than 1.
233     */
234     public CyclicBarrier(int parties) {
235 dl 1.2 this(parties, null);
236 tim 1.1 }
237    
238     /**
239     * Return the number of parties required to trip this barrier.
240     * @return the number of parties required to trip this barrier.
241     **/
242     public int getParties() {
243 dl 1.2 return parties;
244 tim 1.1 }
245    
246     /**
247     * Wait until all {@link #getParties parties} have invoked <tt>await</tt>
248     * on this barrier.
249     *
250     * <p>If the current thread is not the last to arrive then it is
251     * disabled for thread scheduling purposes and lies dormant until
252 dl 1.2 * one of following things happens:
253 tim 1.1 * <ul>
254     * <li>The last thread arrives; or
255     * <li>Some other thread {@link Thread#interrupt interrupts} the current
256     * thread; or
257     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
258     * other waiting threads; or
259 dl 1.2 * <li>Some other thread times out while waiting for barrier; or
260 tim 1.1 * <li>Some other thread invokes {@link #reset} on this barrier.
261     * </ul>
262     * <p>If the current thread:
263     * <ul>
264     * <li>has its interrupted status set on entry to this method; or
265     * <li>is {@link Thread#interrupt interrupted} while waiting
266     * </ul>
267     * then {@link InterruptedException} is thrown and the current thread's
268     * interrupted status is cleared.
269     *
270     * <p>If the barrier is {@link #reset} while any thread is waiting, or if
271     * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked
272     * 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     * will be propagated in the current thread.
285     *
286     * @return the arrival index of the current thread, where index
287     * <tt>{@link #getParties()} - 1</tt> indicates the first to arrive and
288     * zero indicates the last to arrive.
289     *
290     * @throws InterruptedException if the current thread was interrupted
291     * while waiting
292     * @throws BrokenBarrierException if <em>another</em> thread was
293     * interrupted while the current thread was waiting, or the barrier was
294 dl 1.12 * reset, or the barrier was broken when <tt>await</tt> was called,
295     * or the barrier action (if present) failed due an exception.
296 tim 1.1 */
297     public int await() throws InterruptedException, BrokenBarrierException {
298 dl 1.2 try {
299     return dowait(false, 0);
300 tim 1.9 } catch (TimeoutException toe) {
301 dl 1.2 throw new Error(toe); // cannot happen;
302     }
303     }
304    
305     /**
306     * Wait until all {@link #getParties parties} have invoked <tt>await</tt>
307     * on this barrier.
308     *
309     * <p>If the current thread is not the last to arrive then it is
310     * disabled for thread scheduling purposes and lies dormant until
311     * one of the following things happens:
312     * <ul>
313     * <li>The last thread arrives; or
314     * <li>The speceified timeout elapses; or
315     * <li>Some other thread {@link Thread#interrupt interrupts} the current
316     * thread; or
317     * <li>Some other thread {@link Thread#interrupt interrupts} one of the
318     * other waiting threads; or
319     * <li>Some other thread times out while waiting for barrier; or
320     * <li>Some other thread invokes {@link #reset} on this barrier.
321     * </ul>
322     * <p>If the current thread:
323     * <ul>
324     * <li>has its interrupted status set on entry to this method; or
325     * <li>is {@link Thread#interrupt interrupted} while waiting
326     * </ul>
327     * then {@link InterruptedException} is thrown and the current thread's
328     * interrupted status is cleared.
329     *
330     * <p>If the barrier is {@link #reset} while any thread is waiting, or if
331     * the barrier {@link #isBroken is broken} when <tt>await</tt> is invoked
332     * 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     * will be propagated in the current thread.
345     *
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     * the last reset; and <tt>false</tt> otherwise.
372 tim 1.1 */
373     public boolean isBroken() {
374 dl 1.2 lock.lock();
375     try {
376 dl 1.12 return broken;
377 tim 1.9 } finally {
378 dl 1.2 lock.unlock();
379     }
380 tim 1.1 }
381    
382     /**
383     * Reset the barrier to its initial state. If any parties are
384     * currently waiting at the barrier, they will return with a
385 dl 1.8 * {@link BrokenBarrierException}. Note that resets <em>after</em>
386 dl 1.12 * a breakage has occurred for other reasons can be complicated to
387     * carry out; threads need to re-synchronize in some other way,
388     * and choose one to perform the reset. It may be preferable to
389     * instead create a new barrier for subsequent use.
390 tim 1.1 */
391     public void reset() {
392 dl 1.2 lock.lock();
393     try {
394 dl 1.12 /*
395     * Retract generation number enough to cover threads
396     * currently waiting on current and still resuming from
397     * previous generation, plus similarly accommodating spans
398     * after the reset.
399     */
400     generation -= 4;
401     broken = false;
402 dl 1.2 trip.signalAll();
403 tim 1.9 } finally {
404 dl 1.2 lock.unlock();
405     }
406 tim 1.1 }
407    
408     /**
409     * Return the number of parties currently waiting at the barrier.
410     * This method is primarily useful for debugging and assertions.
411     *
412     * @return the number of parties currently blocked in {@link #await}
413     **/
414     public int getNumberWaiting() {
415 dl 1.2 lock.lock();
416     try {
417     return parties - count;
418 tim 1.9 } finally {
419 dl 1.2 lock.unlock();
420     }
421 tim 1.1 }
422    
423     }