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