jaroslav@1890: /* jaroslav@1890: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. jaroslav@1890: * jaroslav@1890: * This code is free software; you can redistribute it and/or modify it jaroslav@1890: * under the terms of the GNU General Public License version 2 only, as jaroslav@1890: * published by the Free Software Foundation. Oracle designates this jaroslav@1890: * particular file as subject to the "Classpath" exception as provided jaroslav@1890: * by Oracle in the LICENSE file that accompanied this code. jaroslav@1890: * jaroslav@1890: * This code is distributed in the hope that it will be useful, but WITHOUT jaroslav@1890: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or jaroslav@1890: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License jaroslav@1890: * version 2 for more details (a copy is included in the LICENSE file that jaroslav@1890: * accompanied this code). jaroslav@1890: * jaroslav@1890: * You should have received a copy of the GNU General Public License version jaroslav@1890: * 2 along with this work; if not, write to the Free Software Foundation, jaroslav@1890: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. jaroslav@1890: * jaroslav@1890: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA jaroslav@1890: * or visit www.oracle.com if you need additional information or have any jaroslav@1890: * questions. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * This file is available under and governed by the GNU General Public jaroslav@1890: * License version 2 only, as published by the Free Software Foundation. jaroslav@1890: * However, the following notice accompanied the original version of this jaroslav@1890: * file: jaroslav@1890: * jaroslav@1890: * Written by Doug Lea with assistance from members of JCP JSR-166 jaroslav@1890: * Expert Group and released to the public domain, as explained at jaroslav@1890: * http://creativecommons.org/publicdomain/zero/1.0/ jaroslav@1890: */ jaroslav@1890: jaroslav@1890: package java.util.concurrent; jaroslav@1890: jaroslav@1890: import java.util.concurrent.TimeUnit; jaroslav@1890: import java.util.concurrent.TimeoutException; jaroslav@1890: import java.util.concurrent.atomic.AtomicReference; jaroslav@1890: import java.util.concurrent.locks.LockSupport; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * A reusable synchronization barrier, similar in functionality to jaroslav@1890: * {@link java.util.concurrent.CyclicBarrier CyclicBarrier} and jaroslav@1890: * {@link java.util.concurrent.CountDownLatch CountDownLatch} jaroslav@1890: * but supporting more flexible usage. jaroslav@1890: * jaroslav@1890: *

Registration. Unlike the case for other barriers, the jaroslav@1890: * number of parties registered to synchronize on a phaser jaroslav@1890: * may vary over time. Tasks may be registered at any time (using jaroslav@1890: * methods {@link #register}, {@link #bulkRegister}, or forms of jaroslav@1890: * constructors establishing initial numbers of parties), and jaroslav@1890: * optionally deregistered upon any arrival (using {@link jaroslav@1890: * #arriveAndDeregister}). As is the case with most basic jaroslav@1890: * synchronization constructs, registration and deregistration affect jaroslav@1890: * only internal counts; they do not establish any further internal jaroslav@1890: * bookkeeping, so tasks cannot query whether they are registered. jaroslav@1890: * (However, you can introduce such bookkeeping by subclassing this jaroslav@1890: * class.) jaroslav@1890: * jaroslav@1890: *

Synchronization. Like a {@code CyclicBarrier}, a {@code jaroslav@1890: * Phaser} may be repeatedly awaited. Method {@link jaroslav@1890: * #arriveAndAwaitAdvance} has effect analogous to {@link jaroslav@1890: * java.util.concurrent.CyclicBarrier#await CyclicBarrier.await}. Each jaroslav@1890: * generation of a phaser has an associated phase number. The phase jaroslav@1890: * number starts at zero, and advances when all parties arrive at the jaroslav@1890: * phaser, wrapping around to zero after reaching {@code jaroslav@1890: * Integer.MAX_VALUE}. The use of phase numbers enables independent jaroslav@1890: * control of actions upon arrival at a phaser and upon awaiting jaroslav@1890: * others, via two kinds of methods that may be invoked by any jaroslav@1890: * registered party: jaroslav@1890: * jaroslav@1890: *

Arrival. Methods {@link #arrive} and jaroslav@1890: * {@link #arriveAndDeregister} record arrival. These methods jaroslav@1890: * do not block, but return an associated arrival phase jaroslav@1890: * number; that is, the phase number of the phaser to which jaroslav@1890: * the arrival applied. When the final party for a given phase jaroslav@1890: * arrives, an optional action is performed and the phase jaroslav@1890: * advances. These actions are performed by the party jaroslav@1890: * triggering a phase advance, and are arranged by overriding jaroslav@1890: * method {@link #onAdvance(int, int)}, which also controls jaroslav@1890: * termination. Overriding this method is similar to, but more jaroslav@1890: * flexible than, providing a barrier action to a {@code jaroslav@1890: * CyclicBarrier}. jaroslav@1890: * jaroslav@1890: *
Waiting. Method {@link #awaitAdvance} requires an jaroslav@1890: * argument indicating an arrival phase number, and returns when jaroslav@1890: * the phaser advances to (or is already at) a different phase. jaroslav@1890: * Unlike similar constructions using {@code CyclicBarrier}, jaroslav@1890: * method {@code awaitAdvance} continues to wait even if the jaroslav@1890: * waiting thread is interrupted. Interruptible and timeout jaroslav@1890: * versions are also available, but exceptions encountered while jaroslav@1890: * tasks wait interruptibly or with timeout do not change the jaroslav@1890: * state of the phaser. If necessary, you can perform any jaroslav@1890: * associated recovery within handlers of those exceptions, jaroslav@1890: * often after invoking {@code forceTermination}. Phasers may jaroslav@1890: * also be used by tasks executing in a {@link ForkJoinPool}, jaroslav@1890: * which will ensure sufficient parallelism to execute tasks jaroslav@1890: * when others are blocked waiting for a phase to advance. jaroslav@1890: * jaroslav@1890: *

jaroslav@1890: * jaroslav@1890: *

Termination. A phaser may enter a termination jaroslav@1890: * state, that may be checked using method {@link #isTerminated}. Upon jaroslav@1890: * termination, all synchronization methods immediately return without jaroslav@1890: * waiting for advance, as indicated by a negative return value. jaroslav@1890: * Similarly, attempts to register upon termination have no effect. jaroslav@1890: * Termination is triggered when an invocation of {@code onAdvance} jaroslav@1890: * returns {@code true}. The default implementation returns {@code jaroslav@1890: * true} if a deregistration has caused the number of registered jaroslav@1890: * parties to become zero. As illustrated below, when phasers control jaroslav@1890: * actions with a fixed number of iterations, it is often convenient jaroslav@1890: * to override this method to cause termination when the current phase jaroslav@1890: * number reaches a threshold. Method {@link #forceTermination} is jaroslav@1890: * also available to abruptly release waiting threads and allow them jaroslav@1890: * to terminate. jaroslav@1890: * jaroslav@1890: *

Tiering. Phasers may be tiered (i.e., jaroslav@1890: * constructed in tree structures) to reduce contention. Phasers with jaroslav@1890: * large numbers of parties that would otherwise experience heavy jaroslav@1890: * synchronization contention costs may instead be set up so that jaroslav@1890: * groups of sub-phasers share a common parent. This may greatly jaroslav@1890: * increase throughput even though it incurs greater per-operation jaroslav@1890: * overhead. jaroslav@1890: * jaroslav@1890: *

In a tree of tiered phasers, registration and deregistration of jaroslav@1890: * child phasers with their parent are managed automatically. jaroslav@1890: * Whenever the number of registered parties of a child phaser becomes jaroslav@1890: * non-zero (as established in the {@link #Phaser(Phaser,int)} jaroslav@1890: * constructor, {@link #register}, or {@link #bulkRegister}), the jaroslav@1890: * child phaser is registered with its parent. Whenever the number of jaroslav@1890: * registered parties becomes zero as the result of an invocation of jaroslav@1890: * {@link #arriveAndDeregister}, the child phaser is deregistered jaroslav@1890: * from its parent. jaroslav@1890: * jaroslav@1890: *

Monitoring. While synchronization methods may be invoked jaroslav@1890: * only by registered parties, the current state of a phaser may be jaroslav@1890: * monitored by any caller. At any given moment there are {@link jaroslav@1890: * #getRegisteredParties} parties in total, of which {@link jaroslav@1890: * #getArrivedParties} have arrived at the current phase ({@link jaroslav@1890: * #getPhase}). When the remaining ({@link #getUnarrivedParties}) jaroslav@1890: * parties arrive, the phase advances. The values returned by these jaroslav@1890: * methods may reflect transient states and so are not in general jaroslav@1890: * useful for synchronization control. Method {@link #toString} jaroslav@1890: * returns snapshots of these state queries in a form convenient for jaroslav@1890: * informal monitoring. jaroslav@1890: * jaroslav@1890: *

Sample usages: jaroslav@1890: * jaroslav@1890: *

A {@code Phaser} may be used instead of a {@code CountDownLatch} jaroslav@1890: * to control a one-shot action serving a variable number of parties. jaroslav@1890: * The typical idiom is for the method setting this up to first jaroslav@1890: * register, then start the actions, then deregister, as in: jaroslav@1890: * jaroslav@1890: *

 {@code
jaroslav@1890:  * void runTasks(List tasks) {
jaroslav@1890:  *   final Phaser phaser = new Phaser(1); // "1" to register self
jaroslav@1890:  *   // create and start threads
jaroslav@1890:  *   for (final Runnable task : tasks) {
jaroslav@1890:  *     phaser.register();
jaroslav@1890:  *     new Thread() {
jaroslav@1890:  *       public void run() {
jaroslav@1890:  *         phaser.arriveAndAwaitAdvance(); // await all creation
jaroslav@1890:  *         task.run();
jaroslav@1890:  *       }
jaroslav@1890:  *     }.start();
jaroslav@1890:  *   }
jaroslav@1890:  *
jaroslav@1890:  *   // allow threads to start and deregister self
jaroslav@1890:  *   phaser.arriveAndDeregister();
jaroslav@1890:  * }}

jaroslav@1890: * jaroslav@1890: *

One way to cause a set of threads to repeatedly perform actions jaroslav@1890: * for a given number of iterations is to override {@code onAdvance}: jaroslav@1890: * jaroslav@1890: *

 {@code
jaroslav@1890:  * void startTasks(List tasks, final int iterations) {
jaroslav@1890:  *   final Phaser phaser = new Phaser() {
jaroslav@1890:  *     protected boolean onAdvance(int phase, int registeredParties) {
jaroslav@1890:  *       return phase >= iterations || registeredParties == 0;
jaroslav@1890:  *     }
jaroslav@1890:  *   };
jaroslav@1890:  *   phaser.register();
jaroslav@1890:  *   for (final Runnable task : tasks) {
jaroslav@1890:  *     phaser.register();
jaroslav@1890:  *     new Thread() {
jaroslav@1890:  *       public void run() {
jaroslav@1890:  *         do {
jaroslav@1890:  *           task.run();
jaroslav@1890:  *           phaser.arriveAndAwaitAdvance();
jaroslav@1890:  *         } while (!phaser.isTerminated());
jaroslav@1890:  *       }
jaroslav@1890:  *     }.start();
jaroslav@1890:  *   }
jaroslav@1890:  *   phaser.arriveAndDeregister(); // deregister self, don't wait
jaroslav@1890:  * }}

jaroslav@1890: * jaroslav@1890: * If the main task must later await termination, it jaroslav@1890: * may re-register and then execute a similar loop: jaroslav@1890: *

 {@code
jaroslav@1890:  *   // ...
jaroslav@1890:  *   phaser.register();
jaroslav@1890:  *   while (!phaser.isTerminated())
jaroslav@1890:  *     phaser.arriveAndAwaitAdvance();}

jaroslav@1890: * jaroslav@1890: *

Related constructions may be used to await particular phase numbers jaroslav@1890: * in contexts where you are sure that the phase will never wrap around jaroslav@1890: * {@code Integer.MAX_VALUE}. For example: jaroslav@1890: * jaroslav@1890: *

 {@code
jaroslav@1890:  * void awaitPhase(Phaser phaser, int phase) {
jaroslav@1890:  *   int p = phaser.register(); // assumes caller not already registered
jaroslav@1890:  *   while (p < phase) {
jaroslav@1890:  *     if (phaser.isTerminated())
jaroslav@1890:  *       // ... deal with unexpected termination
jaroslav@1890:  *     else
jaroslav@1890:  *       p = phaser.arriveAndAwaitAdvance();
jaroslav@1890:  *   }
jaroslav@1890:  *   phaser.arriveAndDeregister();
jaroslav@1890:  * }}

jaroslav@1890: * jaroslav@1890: * jaroslav@1890: *

To create a set of {@code n} tasks using a tree of phasers, you jaroslav@1890: * could use code of the following form, assuming a Task class with a jaroslav@1890: * constructor accepting a {@code Phaser} that it registers with upon jaroslav@1890: * construction. After invocation of {@code build(new Task[n], 0, n, jaroslav@1890: * new Phaser())}, these tasks could then be started, for example by jaroslav@1890: * submitting to a pool: jaroslav@1890: * jaroslav@1890: *

 {@code
jaroslav@1890:  * void build(Task[] tasks, int lo, int hi, Phaser ph) {
jaroslav@1890:  *   if (hi - lo > TASKS_PER_PHASER) {
jaroslav@1890:  *     for (int i = lo; i < hi; i += TASKS_PER_PHASER) {
jaroslav@1890:  *       int j = Math.min(i + TASKS_PER_PHASER, hi);
jaroslav@1890:  *       build(tasks, i, j, new Phaser(ph));
jaroslav@1890:  *     }
jaroslav@1890:  *   } else {
jaroslav@1890:  *     for (int i = lo; i < hi; ++i)
jaroslav@1890:  *       tasks[i] = new Task(ph);
jaroslav@1890:  *       // assumes new Task(ph) performs ph.register()
jaroslav@1890:  *   }
jaroslav@1890:  * }}

jaroslav@1890: * jaroslav@1890: * The best value of {@code TASKS_PER_PHASER} depends mainly on jaroslav@1890: * expected synchronization rates. A value as low as four may jaroslav@1890: * be appropriate for extremely small per-phase task bodies (thus jaroslav@1890: * high rates), or up to hundreds for extremely large ones. jaroslav@1890: * jaroslav@1890: *

Implementation notes: This implementation restricts the jaroslav@1890: * maximum number of parties to 65535. Attempts to register additional jaroslav@1890: * parties result in {@code IllegalStateException}. However, you can and jaroslav@1890: * should create tiered phasers to accommodate arbitrarily large sets jaroslav@1890: * of participants. jaroslav@1890: * jaroslav@1890: * @since 1.7 jaroslav@1890: * @author Doug Lea jaroslav@1890: */ jaroslav@1890: public class Phaser { jaroslav@1890: /* jaroslav@1890: * This class implements an extension of X10 "clocks". Thanks to jaroslav@1890: * Vijay Saraswat for the idea, and to Vivek Sarkar for jaroslav@1890: * enhancements to extend functionality. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Primary state representation, holding four bit-fields: jaroslav@1890: * jaroslav@1890: * unarrived -- the number of parties yet to hit barrier (bits 0-15) jaroslav@1890: * parties -- the number of parties to wait (bits 16-31) jaroslav@1890: * phase -- the generation of the barrier (bits 32-62) jaroslav@1890: * terminated -- set if barrier is terminated (bit 63 / sign) jaroslav@1890: * jaroslav@1890: * Except that a phaser with no registered parties is jaroslav@1890: * distinguished by the otherwise illegal state of having zero jaroslav@1890: * parties and one unarrived parties (encoded as EMPTY below). jaroslav@1890: * jaroslav@1890: * To efficiently maintain atomicity, these values are packed into jaroslav@1890: * a single (atomic) long. Good performance relies on keeping jaroslav@1890: * state decoding and encoding simple, and keeping race windows jaroslav@1890: * short. jaroslav@1890: * jaroslav@1890: * All state updates are performed via CAS except initial jaroslav@1890: * registration of a sub-phaser (i.e., one with a non-null jaroslav@1890: * parent). In this (relatively rare) case, we use built-in jaroslav@1890: * synchronization to lock while first registering with its jaroslav@1890: * parent. jaroslav@1890: * jaroslav@1890: * The phase of a subphaser is allowed to lag that of its jaroslav@1890: * ancestors until it is actually accessed -- see method jaroslav@1890: * reconcileState. jaroslav@1890: */ jaroslav@1890: private volatile long state; jaroslav@1890: jaroslav@1890: private static final int MAX_PARTIES = 0xffff; jaroslav@1890: private static final int MAX_PHASE = Integer.MAX_VALUE; jaroslav@1890: private static final int PARTIES_SHIFT = 16; jaroslav@1890: private static final int PHASE_SHIFT = 32; jaroslav@1890: private static final int UNARRIVED_MASK = 0xffff; // to mask ints jaroslav@1890: private static final long PARTIES_MASK = 0xffff0000L; // to mask longs jaroslav@1890: private static final long TERMINATION_BIT = 1L << 63; jaroslav@1890: jaroslav@1890: // some special values jaroslav@1890: private static final int ONE_ARRIVAL = 1; jaroslav@1890: private static final int ONE_PARTY = 1 << PARTIES_SHIFT; jaroslav@1890: private static final int EMPTY = 1; jaroslav@1890: jaroslav@1890: // The following unpacking methods are usually manually inlined jaroslav@1890: jaroslav@1890: private static int unarrivedOf(long s) { jaroslav@1890: int counts = (int)s; jaroslav@1890: return (counts == EMPTY) ? 0 : counts & UNARRIVED_MASK; jaroslav@1890: } jaroslav@1890: jaroslav@1890: private static int partiesOf(long s) { jaroslav@1890: return (int)s >>> PARTIES_SHIFT; jaroslav@1890: } jaroslav@1890: jaroslav@1890: private static int phaseOf(long s) { jaroslav@1890: return (int)(s >>> PHASE_SHIFT); jaroslav@1890: } jaroslav@1890: jaroslav@1890: private static int arrivedOf(long s) { jaroslav@1890: int counts = (int)s; jaroslav@1890: return (counts == EMPTY) ? 0 : jaroslav@1890: (counts >>> PARTIES_SHIFT) - (counts & UNARRIVED_MASK); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The parent of this phaser, or null if none jaroslav@1890: */ jaroslav@1890: private final Phaser parent; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The root of phaser tree. Equals this if not in a tree. jaroslav@1890: */ jaroslav@1890: private final Phaser root; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Heads of Treiber stacks for waiting threads. To eliminate jaroslav@1890: * contention when releasing some threads while adding others, we jaroslav@1890: * use two of them, alternating across even and odd phases. jaroslav@1890: * Subphasers share queues with root to speed up releases. jaroslav@1890: */ jaroslav@1890: private final AtomicReference evenQ; jaroslav@1890: private final AtomicReference oddQ; jaroslav@1890: jaroslav@1890: private AtomicReference queueFor(int phase) { jaroslav@1890: return ((phase & 1) == 0) ? evenQ : oddQ; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns message string for bounds exceptions on arrival. jaroslav@1890: */ jaroslav@1890: private String badArrive(long s) { jaroslav@1890: return "Attempted arrival of unregistered party for " + jaroslav@1890: stateToString(s); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns message string for bounds exceptions on registration. jaroslav@1890: */ jaroslav@1890: private String badRegister(long s) { jaroslav@1890: return "Attempt to register more than " + jaroslav@1890: MAX_PARTIES + " parties for " + stateToString(s); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Main implementation for methods arrive and arriveAndDeregister. jaroslav@1890: * Manually tuned to speed up and minimize race windows for the jaroslav@1890: * common case of just decrementing unarrived field. jaroslav@1890: * jaroslav@1890: * @param deregister false for arrive, true for arriveAndDeregister jaroslav@1890: */ jaroslav@1890: private int doArrive(boolean deregister) { jaroslav@1890: int adj = deregister ? ONE_ARRIVAL|ONE_PARTY : ONE_ARRIVAL; jaroslav@1890: final Phaser root = this.root; jaroslav@1890: for (;;) { jaroslav@1890: long s = (root == this) ? state : reconcileState(); jaroslav@1890: int phase = (int)(s >>> PHASE_SHIFT); jaroslav@1890: int counts = (int)s; jaroslav@1890: int unarrived = (counts & UNARRIVED_MASK) - 1; jaroslav@1890: if (phase < 0) jaroslav@1890: return phase; jaroslav@1890: else if (counts == EMPTY || unarrived < 0) { jaroslav@1890: if (root == this || reconcileState() == s) jaroslav@1890: throw new IllegalStateException(badArrive(s)); jaroslav@1890: } jaroslav@1895: else if (compareAndSwapLong(s, s-=adj)) { jaroslav@1890: if (unarrived == 0) { jaroslav@1890: long n = s & PARTIES_MASK; // base of next state jaroslav@1890: int nextUnarrived = (int)n >>> PARTIES_SHIFT; jaroslav@1890: if (root != this) jaroslav@1890: return parent.doArrive(nextUnarrived == 0); jaroslav@1890: if (onAdvance(phase, nextUnarrived)) jaroslav@1890: n |= TERMINATION_BIT; jaroslav@1890: else if (nextUnarrived == 0) jaroslav@1890: n |= EMPTY; jaroslav@1890: else jaroslav@1890: n |= nextUnarrived; jaroslav@1890: n |= (long)((phase + 1) & MAX_PHASE) << PHASE_SHIFT; jaroslav@1895: compareAndSwapLong(s, n); jaroslav@1890: releaseWaiters(phase); jaroslav@1890: } jaroslav@1890: return phase; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Implementation of register, bulkRegister jaroslav@1890: * jaroslav@1890: * @param registrations number to add to both parties and jaroslav@1890: * unarrived fields. Must be greater than zero. jaroslav@1890: */ jaroslav@1890: private int doRegister(int registrations) { jaroslav@1890: // adjustment to state jaroslav@1890: long adj = ((long)registrations << PARTIES_SHIFT) | registrations; jaroslav@1890: final Phaser parent = this.parent; jaroslav@1890: int phase; jaroslav@1890: for (;;) { jaroslav@1890: long s = state; jaroslav@1890: int counts = (int)s; jaroslav@1890: int parties = counts >>> PARTIES_SHIFT; jaroslav@1890: int unarrived = counts & UNARRIVED_MASK; jaroslav@1890: if (registrations > MAX_PARTIES - parties) jaroslav@1890: throw new IllegalStateException(badRegister(s)); jaroslav@1890: else if ((phase = (int)(s >>> PHASE_SHIFT)) < 0) jaroslav@1890: break; jaroslav@1890: else if (counts != EMPTY) { // not 1st registration jaroslav@1890: if (parent == null || reconcileState() == s) { jaroslav@1890: if (unarrived == 0) // wait out advance jaroslav@1890: root.internalAwaitAdvance(phase, null); jaroslav@1895: else if (compareAndSwapLong( s, s + adj)) jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: else if (parent == null) { // 1st root registration jaroslav@1890: long next = ((long)phase << PHASE_SHIFT) | adj; jaroslav@1895: if (compareAndSwapLong(s, next)) jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: else { jaroslav@1890: synchronized (this) { // 1st sub registration jaroslav@1890: if (state == s) { // recheck under lock jaroslav@1890: parent.doRegister(1); jaroslav@1890: do { // force current phase jaroslav@1890: phase = (int)(root.state >>> PHASE_SHIFT); jaroslav@1890: // assert phase < 0 || (int)state == EMPTY; jaroslav@1895: } while (!compareAndSwapLong jaroslav@1895: (state, jaroslav@1890: ((long)phase << PHASE_SHIFT) | adj)); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return phase; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Resolves lagged phase propagation from root if necessary. jaroslav@1890: * Reconciliation normally occurs when root has advanced but jaroslav@1890: * subphasers have not yet done so, in which case they must finish jaroslav@1890: * their own advance by setting unarrived to parties (or if jaroslav@1890: * parties is zero, resetting to unregistered EMPTY state). jaroslav@1890: * However, this method may also be called when "floating" jaroslav@1890: * subphasers with possibly some unarrived parties are merely jaroslav@1890: * catching up to current phase, in which case counts are jaroslav@1890: * unaffected. jaroslav@1890: * jaroslav@1890: * @return reconciled state jaroslav@1890: */ jaroslav@1890: private long reconcileState() { jaroslav@1890: final Phaser root = this.root; jaroslav@1890: long s = state; jaroslav@1890: if (root != this) { jaroslav@1890: int phase, u, p; jaroslav@1890: // CAS root phase with current parties; possibly trip unarrived jaroslav@1890: while ((phase = (int)(root.state >>> PHASE_SHIFT)) != jaroslav@1890: (int)(s >>> PHASE_SHIFT) && jaroslav@1895: !compareAndSwapLong jaroslav@1895: (s, jaroslav@1890: s = (((long)phase << PHASE_SHIFT) | jaroslav@1890: (s & PARTIES_MASK) | jaroslav@1890: ((p = (int)s >>> PARTIES_SHIFT) == 0 ? EMPTY : jaroslav@1890: (u = (int)s & UNARRIVED_MASK) == 0 ? p : u)))) jaroslav@1890: s = state; jaroslav@1890: } jaroslav@1890: return s; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a new phaser with no initially registered parties, no jaroslav@1890: * parent, and initial phase number 0. Any thread using this jaroslav@1890: * phaser will need to first register for it. jaroslav@1890: */ jaroslav@1890: public Phaser() { jaroslav@1890: this(null, 0); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a new phaser with the given number of registered jaroslav@1890: * unarrived parties, no parent, and initial phase number 0. jaroslav@1890: * jaroslav@1890: * @param parties the number of parties required to advance to the jaroslav@1890: * next phase jaroslav@1890: * @throws IllegalArgumentException if parties less than zero jaroslav@1890: * or greater than the maximum number of parties supported jaroslav@1890: */ jaroslav@1890: public Phaser(int parties) { jaroslav@1890: this(null, parties); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Equivalent to {@link #Phaser(Phaser, int) Phaser(parent, 0)}. jaroslav@1890: * jaroslav@1890: * @param parent the parent phaser jaroslav@1890: */ jaroslav@1890: public Phaser(Phaser parent) { jaroslav@1890: this(parent, 0); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a new phaser with the given parent and number of jaroslav@1890: * registered unarrived parties. When the given parent is non-null jaroslav@1890: * and the given number of parties is greater than zero, this jaroslav@1890: * child phaser is registered with its parent. jaroslav@1890: * jaroslav@1890: * @param parent the parent phaser jaroslav@1890: * @param parties the number of parties required to advance to the jaroslav@1890: * next phase jaroslav@1890: * @throws IllegalArgumentException if parties less than zero jaroslav@1890: * or greater than the maximum number of parties supported jaroslav@1890: */ jaroslav@1890: public Phaser(Phaser parent, int parties) { jaroslav@1890: if (parties >>> PARTIES_SHIFT != 0) jaroslav@1890: throw new IllegalArgumentException("Illegal number of parties"); jaroslav@1890: int phase = 0; jaroslav@1890: this.parent = parent; jaroslav@1890: if (parent != null) { jaroslav@1890: final Phaser root = parent.root; jaroslav@1890: this.root = root; jaroslav@1890: this.evenQ = root.evenQ; jaroslav@1890: this.oddQ = root.oddQ; jaroslav@1890: if (parties != 0) jaroslav@1890: phase = parent.doRegister(1); jaroslav@1890: } jaroslav@1890: else { jaroslav@1890: this.root = this; jaroslav@1890: this.evenQ = new AtomicReference(); jaroslav@1890: this.oddQ = new AtomicReference(); jaroslav@1890: } jaroslav@1890: this.state = (parties == 0) ? (long)EMPTY : jaroslav@1890: ((long)phase << PHASE_SHIFT) | jaroslav@1890: ((long)parties << PARTIES_SHIFT) | jaroslav@1890: ((long)parties); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Adds a new unarrived party to this phaser. If an ongoing jaroslav@1890: * invocation of {@link #onAdvance} is in progress, this method jaroslav@1890: * may await its completion before returning. If this phaser has jaroslav@1890: * a parent, and this phaser previously had no registered parties, jaroslav@1890: * this child phaser is also registered with its parent. If jaroslav@1890: * this phaser is terminated, the attempt to register has jaroslav@1890: * no effect, and a negative value is returned. jaroslav@1890: * jaroslav@1890: * @return the arrival phase number to which this registration jaroslav@1890: * applied. If this value is negative, then this phaser has jaroslav@1890: * terminated, in which case registration has no effect. jaroslav@1890: * @throws IllegalStateException if attempting to register more jaroslav@1890: * than the maximum supported number of parties jaroslav@1890: */ jaroslav@1890: public int register() { jaroslav@1890: return doRegister(1); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Adds the given number of new unarrived parties to this phaser. jaroslav@1890: * If an ongoing invocation of {@link #onAdvance} is in progress, jaroslav@1890: * this method may await its completion before returning. If this jaroslav@1890: * phaser has a parent, and the given number of parties is greater jaroslav@1890: * than zero, and this phaser previously had no registered jaroslav@1890: * parties, this child phaser is also registered with its parent. jaroslav@1890: * If this phaser is terminated, the attempt to register has no jaroslav@1890: * effect, and a negative value is returned. jaroslav@1890: * jaroslav@1890: * @param parties the number of additional parties required to jaroslav@1890: * advance to the next phase jaroslav@1890: * @return the arrival phase number to which this registration jaroslav@1890: * applied. If this value is negative, then this phaser has jaroslav@1890: * terminated, in which case registration has no effect. jaroslav@1890: * @throws IllegalStateException if attempting to register more jaroslav@1890: * than the maximum supported number of parties jaroslav@1890: * @throws IllegalArgumentException if {@code parties < 0} jaroslav@1890: */ jaroslav@1890: public int bulkRegister(int parties) { jaroslav@1890: if (parties < 0) jaroslav@1890: throw new IllegalArgumentException(); jaroslav@1890: if (parties == 0) jaroslav@1890: return getPhase(); jaroslav@1890: return doRegister(parties); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Arrives at this phaser, without waiting for others to arrive. jaroslav@1890: * jaroslav@1890: *

It is a usage error for an unregistered party to invoke this jaroslav@1890: * method. However, this error may result in an {@code jaroslav@1890: * IllegalStateException} only upon some subsequent operation on jaroslav@1890: * this phaser, if ever. jaroslav@1890: * jaroslav@1890: * @return the arrival phase number, or the (negative) jaroslav@1890: * {@linkplain #getPhase() current phase} if terminated jaroslav@1890: * @throws IllegalStateException if not terminated and the number jaroslav@1890: * of unarrived parties would become negative jaroslav@1890: */ jaroslav@1890: public int arriveAndAwaitAdvance() { jaroslav@1890: // Specialization of doArrive+awaitAdvance eliminating some reads/paths jaroslav@1890: final Phaser root = this.root; jaroslav@1890: for (;;) { jaroslav@1890: long s = (root == this) ? state : reconcileState(); jaroslav@1890: int phase = (int)(s >>> PHASE_SHIFT); jaroslav@1890: int counts = (int)s; jaroslav@1890: int unarrived = (counts & UNARRIVED_MASK) - 1; jaroslav@1890: if (phase < 0) jaroslav@1890: return phase; jaroslav@1890: else if (counts == EMPTY || unarrived < 0) { jaroslav@1890: if (reconcileState() == s) jaroslav@1890: throw new IllegalStateException(badArrive(s)); jaroslav@1890: } jaroslav@1895: else if (compareAndSwapLong(s, jaroslav@1890: s -= ONE_ARRIVAL)) { jaroslav@1890: if (unarrived != 0) jaroslav@1890: return root.internalAwaitAdvance(phase, null); jaroslav@1890: if (root != this) jaroslav@1890: return parent.arriveAndAwaitAdvance(); jaroslav@1890: long n = s & PARTIES_MASK; // base of next state jaroslav@1890: int nextUnarrived = (int)n >>> PARTIES_SHIFT; jaroslav@1890: if (onAdvance(phase, nextUnarrived)) jaroslav@1890: n |= TERMINATION_BIT; jaroslav@1890: else if (nextUnarrived == 0) jaroslav@1890: n |= EMPTY; jaroslav@1890: else jaroslav@1890: n |= nextUnarrived; jaroslav@1890: int nextPhase = (phase + 1) & MAX_PHASE; jaroslav@1890: n |= (long)nextPhase << PHASE_SHIFT; jaroslav@1895: if (!compareAndSwapLong(s, n)) jaroslav@1890: return (int)(state >>> PHASE_SHIFT); // terminated jaroslav@1890: releaseWaiters(phase); jaroslav@1890: return nextPhase; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Awaits the phase of this phaser to advance from the given phase jaroslav@1890: * value, returning immediately if the current phase is not equal jaroslav@1890: * to the given phase value or this phaser is terminated. jaroslav@1890: * jaroslav@1890: * @param phase an arrival phase number, or negative value if jaroslav@1890: * terminated; this argument is normally the value returned by a jaroslav@1890: * previous call to {@code arrive} or {@code arriveAndDeregister}. jaroslav@1890: * @return the next arrival phase number, or the argument if it is jaroslav@1890: * negative, or the (negative) {@linkplain #getPhase() current phase} jaroslav@1890: * if terminated jaroslav@1890: */ jaroslav@1890: public int awaitAdvance(int phase) { jaroslav@1890: final Phaser root = this.root; jaroslav@1890: long s = (root == this) ? state : reconcileState(); jaroslav@1890: int p = (int)(s >>> PHASE_SHIFT); jaroslav@1890: if (phase < 0) jaroslav@1890: return phase; jaroslav@1890: if (p == phase) jaroslav@1890: return root.internalAwaitAdvance(phase, null); jaroslav@1890: return p; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Awaits the phase of this phaser to advance from the given phase jaroslav@1890: * value, throwing {@code InterruptedException} if interrupted jaroslav@1890: * while waiting, or returning immediately if the current phase is jaroslav@1890: * not equal to the given phase value or this phaser is jaroslav@1890: * terminated. jaroslav@1890: * jaroslav@1890: * @param phase an arrival phase number, or negative value if jaroslav@1890: * terminated; this argument is normally the value returned by a jaroslav@1890: * previous call to {@code arrive} or {@code arriveAndDeregister}. jaroslav@1890: * @return the next arrival phase number, or the argument if it is jaroslav@1890: * negative, or the (negative) {@linkplain #getPhase() current phase} jaroslav@1890: * if terminated jaroslav@1890: * @throws InterruptedException if thread interrupted while waiting jaroslav@1890: */ jaroslav@1890: public int awaitAdvanceInterruptibly(int phase) jaroslav@1890: throws InterruptedException { jaroslav@1890: final Phaser root = this.root; jaroslav@1890: long s = (root == this) ? state : reconcileState(); jaroslav@1890: int p = (int)(s >>> PHASE_SHIFT); jaroslav@1890: if (phase < 0) jaroslav@1890: return phase; jaroslav@1890: if (p == phase) { jaroslav@1890: QNode node = new QNode(this, phase, true, false, 0L); jaroslav@1890: p = root.internalAwaitAdvance(phase, node); jaroslav@1890: if (node.wasInterrupted) jaroslav@1890: throw new InterruptedException(); jaroslav@1890: } jaroslav@1890: return p; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Awaits the phase of this phaser to advance from the given phase jaroslav@1890: * value or the given timeout to elapse, throwing {@code jaroslav@1890: * InterruptedException} if interrupted while waiting, or jaroslav@1890: * returning immediately if the current phase is not equal to the jaroslav@1890: * given phase value or this phaser is terminated. jaroslav@1890: * jaroslav@1890: * @param phase an arrival phase number, or negative value if jaroslav@1890: * terminated; this argument is normally the value returned by a jaroslav@1890: * previous call to {@code arrive} or {@code arriveAndDeregister}. jaroslav@1890: * @param timeout how long to wait before giving up, in units of jaroslav@1890: * {@code unit} jaroslav@1890: * @param unit a {@code TimeUnit} determining how to interpret the jaroslav@1890: * {@code timeout} parameter jaroslav@1890: * @return the next arrival phase number, or the argument if it is jaroslav@1890: * negative, or the (negative) {@linkplain #getPhase() current phase} jaroslav@1890: * if terminated jaroslav@1890: * @throws InterruptedException if thread interrupted while waiting jaroslav@1890: * @throws TimeoutException if timed out while waiting jaroslav@1890: */ jaroslav@1890: public int awaitAdvanceInterruptibly(int phase, jaroslav@1890: long timeout, TimeUnit unit) jaroslav@1890: throws InterruptedException, TimeoutException { jaroslav@1890: long nanos = unit.toNanos(timeout); jaroslav@1890: final Phaser root = this.root; jaroslav@1890: long s = (root == this) ? state : reconcileState(); jaroslav@1890: int p = (int)(s >>> PHASE_SHIFT); jaroslav@1890: if (phase < 0) jaroslav@1890: return phase; jaroslav@1890: if (p == phase) { jaroslav@1890: QNode node = new QNode(this, phase, true, true, nanos); jaroslav@1890: p = root.internalAwaitAdvance(phase, node); jaroslav@1890: if (node.wasInterrupted) jaroslav@1890: throw new InterruptedException(); jaroslav@1890: else if (p == phase) jaroslav@1890: throw new TimeoutException(); jaroslav@1890: } jaroslav@1890: return p; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Forces this phaser to enter termination state. Counts of jaroslav@1890: * registered parties are unaffected. If this phaser is a member jaroslav@1890: * of a tiered set of phasers, then all of the phasers in the set jaroslav@1890: * are terminated. If this phaser is already terminated, this jaroslav@1890: * method has no effect. This method may be useful for jaroslav@1890: * coordinating recovery after one or more tasks encounter jaroslav@1890: * unexpected exceptions. jaroslav@1890: */ jaroslav@1890: public void forceTermination() { jaroslav@1890: // Only need to change root state jaroslav@1890: final Phaser root = this.root; jaroslav@1890: long s; jaroslav@1890: while ((s = root.state) >= 0) { jaroslav@1895: if (compareAndSwapLong( s, s | TERMINATION_BIT)) { jaroslav@1890: // signal all threads jaroslav@1890: releaseWaiters(0); jaroslav@1890: releaseWaiters(1); jaroslav@1890: return; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the current phase number. The maximum phase number is jaroslav@1890: * {@code Integer.MAX_VALUE}, after which it restarts at jaroslav@1890: * zero. Upon termination, the phase number is negative, jaroslav@1890: * in which case the prevailing phase prior to termination jaroslav@1890: * may be obtained via {@code getPhase() + Integer.MIN_VALUE}. jaroslav@1890: * jaroslav@1890: * @return the phase number, or a negative value if terminated jaroslav@1890: */ jaroslav@1890: public final int getPhase() { jaroslav@1890: return (int)(root.state >>> PHASE_SHIFT); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the number of parties registered at this phaser. jaroslav@1890: * jaroslav@1890: * @return the number of parties jaroslav@1890: */ jaroslav@1890: public int getRegisteredParties() { jaroslav@1890: return partiesOf(state); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the number of registered parties that have arrived at jaroslav@1890: * the current phase of this phaser. If this phaser has terminated, jaroslav@1890: * the returned value is meaningless and arbitrary. jaroslav@1890: * jaroslav@1890: * @return the number of arrived parties jaroslav@1890: */ jaroslav@1890: public int getArrivedParties() { jaroslav@1890: return arrivedOf(reconcileState()); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the number of registered parties that have not yet jaroslav@1890: * arrived at the current phase of this phaser. If this phaser has jaroslav@1890: * terminated, the returned value is meaningless and arbitrary. jaroslav@1890: * jaroslav@1890: * @return the number of unarrived parties jaroslav@1890: */ jaroslav@1890: public int getUnarrivedParties() { jaroslav@1890: return unarrivedOf(reconcileState()); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the parent of this phaser, or {@code null} if none. jaroslav@1890: * jaroslav@1890: * @return the parent of this phaser, or {@code null} if none jaroslav@1890: */ jaroslav@1890: public Phaser getParent() { jaroslav@1890: return parent; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the root ancestor of this phaser, which is the same as jaroslav@1890: * this phaser if it has no parent. jaroslav@1890: * jaroslav@1890: * @return the root ancestor of this phaser jaroslav@1890: */ jaroslav@1890: public Phaser getRoot() { jaroslav@1890: return root; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns {@code true} if this phaser has been terminated. jaroslav@1890: * jaroslav@1890: * @return {@code true} if this phaser has been terminated jaroslav@1890: */ jaroslav@1890: public boolean isTerminated() { jaroslav@1890: return root.state < 0L; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Overridable method to perform an action upon impending phase jaroslav@1890: * advance, and to control termination. This method is invoked jaroslav@1890: * upon arrival of the party advancing this phaser (when all other jaroslav@1890: * waiting parties are dormant). If this method returns {@code jaroslav@1890: * true}, this phaser will be set to a final termination state jaroslav@1890: * upon advance, and subsequent calls to {@link #isTerminated} jaroslav@1890: * will return true. Any (unchecked) Exception or Error thrown by jaroslav@1890: * an invocation of this method is propagated to the party jaroslav@1890: * attempting to advance this phaser, in which case no advance jaroslav@1890: * occurs. jaroslav@1890: * jaroslav@1890: *

The arguments to this method provide the state of the phaser jaroslav@1890: * prevailing for the current transition. The effects of invoking jaroslav@1890: * arrival, registration, and waiting methods on this phaser from jaroslav@1890: * within {@code onAdvance} are unspecified and should not be jaroslav@1890: * relied on. jaroslav@1890: * jaroslav@1890: *

If this phaser is a member of a tiered set of phasers, then jaroslav@1890: * {@code onAdvance} is invoked only for its root phaser on each jaroslav@1890: * advance. jaroslav@1890: * jaroslav@1890: *

To support the most common use cases, the default jaroslav@1890: * implementation of this method returns {@code true} when the jaroslav@1890: * number of registered parties has become zero as the result of a jaroslav@1890: * party invoking {@code arriveAndDeregister}. You can disable jaroslav@1890: * this behavior, thus enabling continuation upon future jaroslav@1890: * registrations, by overriding this method to always return jaroslav@1890: * {@code false}: jaroslav@1890: * jaroslav@1890: *

 {@code
jaroslav@1890:      * Phaser phaser = new Phaser() {
jaroslav@1890:      *   protected boolean onAdvance(int phase, int parties) { return false; }
jaroslav@1890:      * }}

jaroslav@1890: * jaroslav@1890: * @param phase the current phase number on entry to this method, jaroslav@1890: * before this phaser is advanced jaroslav@1890: * @param registeredParties the current number of registered parties jaroslav@1890: * @return {@code true} if this phaser should terminate jaroslav@1890: */ jaroslav@1890: protected boolean onAdvance(int phase, int registeredParties) { jaroslav@1890: return registeredParties == 0; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a string identifying this phaser, as well as its jaroslav@1890: * state. The state, in brackets, includes the String {@code jaroslav@1890: * "phase = "} followed by the phase number, {@code "parties = "} jaroslav@1890: * followed by the number of registered parties, and {@code jaroslav@1890: * "arrived = "} followed by the number of arrived parties. jaroslav@1890: * jaroslav@1890: * @return a string identifying this phaser, as well as its state jaroslav@1890: */ jaroslav@1890: public String toString() { jaroslav@1890: return stateToString(reconcileState()); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Implementation of toString and string-based error messages jaroslav@1890: */ jaroslav@1890: private String stateToString(long s) { jaroslav@1890: return super.toString() + jaroslav@1890: "[phase = " + phaseOf(s) + jaroslav@1890: " parties = " + partiesOf(s) + jaroslav@1890: " arrived = " + arrivedOf(s) + "]"; jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Waiting mechanics jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes and signals threads from queue for phase. jaroslav@1890: */ jaroslav@1890: private void releaseWaiters(int phase) { jaroslav@1890: QNode q; // first element of queue jaroslav@1890: Thread t; // its thread jaroslav@1890: AtomicReference head = (phase & 1) == 0 ? evenQ : oddQ; jaroslav@1890: while ((q = head.get()) != null && jaroslav@1890: q.phase != (int)(root.state >>> PHASE_SHIFT)) { jaroslav@1890: if (head.compareAndSet(q, q.next) && jaroslav@1890: (t = q.thread) != null) { jaroslav@1890: q.thread = null; jaroslav@1890: LockSupport.unpark(t); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Variant of releaseWaiters that additionally tries to remove any jaroslav@1890: * nodes no longer waiting for advance due to timeout or jaroslav@1890: * interrupt. Currently, nodes are removed only if they are at jaroslav@1890: * head of queue, which suffices to reduce memory footprint in jaroslav@1890: * most usages. jaroslav@1890: * jaroslav@1890: * @return current phase on exit jaroslav@1890: */ jaroslav@1890: private int abortWait(int phase) { jaroslav@1890: AtomicReference head = (phase & 1) == 0 ? evenQ : oddQ; jaroslav@1890: for (;;) { jaroslav@1890: Thread t; jaroslav@1890: QNode q = head.get(); jaroslav@1890: int p = (int)(root.state >>> PHASE_SHIFT); jaroslav@1890: if (q == null || ((t = q.thread) != null && q.phase == p)) jaroslav@1890: return p; jaroslav@1890: if (head.compareAndSet(q, q.next) && t != null) { jaroslav@1890: q.thread = null; jaroslav@1890: LockSupport.unpark(t); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** The number of CPUs, for spin control */ jaroslav@1895: private static final int NCPU = 1; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The number of times to spin before blocking while waiting for jaroslav@1890: * advance, per arrival while waiting. On multiprocessors, fully jaroslav@1890: * blocking and waking up a large number of threads all at once is jaroslav@1890: * usually a very slow process, so we use rechargeable spins to jaroslav@1890: * avoid it when threads regularly arrive: When a thread in jaroslav@1890: * internalAwaitAdvance notices another arrival before blocking, jaroslav@1890: * and there appear to be enough CPUs available, it spins jaroslav@1890: * SPINS_PER_ARRIVAL more times before blocking. The value trades jaroslav@1890: * off good-citizenship vs big unnecessary slowdowns. jaroslav@1890: */ jaroslav@1890: static final int SPINS_PER_ARRIVAL = (NCPU < 2) ? 1 : 1 << 8; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Possibly blocks and waits for phase to advance unless aborted. jaroslav@1890: * Call only from root node. jaroslav@1890: * jaroslav@1890: * @param phase current phase jaroslav@1890: * @param node if non-null, the wait node to track interrupt and timeout; jaroslav@1890: * if null, denotes noninterruptible wait jaroslav@1890: * @return current phase jaroslav@1890: */ jaroslav@1890: private int internalAwaitAdvance(int phase, QNode node) { jaroslav@1890: releaseWaiters(phase-1); // ensure old queue clean jaroslav@1890: boolean queued = false; // true when node is enqueued jaroslav@1890: int lastUnarrived = 0; // to increase spins upon change jaroslav@1890: int spins = SPINS_PER_ARRIVAL; jaroslav@1890: long s; jaroslav@1890: int p; jaroslav@1890: while ((p = (int)((s = state) >>> PHASE_SHIFT)) == phase) { jaroslav@1890: if (node == null) { // spinning in noninterruptible mode jaroslav@1890: int unarrived = (int)s & UNARRIVED_MASK; jaroslav@1890: if (unarrived != lastUnarrived && jaroslav@1890: (lastUnarrived = unarrived) < NCPU) jaroslav@1890: spins += SPINS_PER_ARRIVAL; jaroslav@1890: boolean interrupted = Thread.interrupted(); jaroslav@1890: if (interrupted || --spins < 0) { // need node to record intr jaroslav@1890: node = new QNode(this, phase, false, false, 0L); jaroslav@1890: node.wasInterrupted = interrupted; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: else if (node.isReleasable()) // done or aborted jaroslav@1890: break; jaroslav@1890: else if (!queued) { // push onto queue jaroslav@1890: AtomicReference head = (phase & 1) == 0 ? evenQ : oddQ; jaroslav@1890: QNode q = node.next = head.get(); jaroslav@1890: if ((q == null || q.phase == phase) && jaroslav@1890: (int)(state >>> PHASE_SHIFT) == phase) // avoid stale enq jaroslav@1890: queued = head.compareAndSet(q, node); jaroslav@1890: } jaroslav@1890: else { jaroslav@1890: try { jaroslav@1890: ForkJoinPool.managedBlock(node); jaroslav@1890: } catch (InterruptedException ie) { jaroslav@1890: node.wasInterrupted = true; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: if (node != null) { jaroslav@1890: if (node.thread != null) jaroslav@1890: node.thread = null; // avoid need for unpark() jaroslav@1890: if (node.wasInterrupted && !node.interruptible) jaroslav@1890: Thread.currentThread().interrupt(); jaroslav@1890: if (p == phase && (p = (int)(state >>> PHASE_SHIFT)) == phase) jaroslav@1890: return abortWait(phase); // possibly clean up on abort jaroslav@1890: } jaroslav@1890: releaseWaiters(phase); jaroslav@1890: return p; jaroslav@1890: } jaroslav@1890: jaroslav@1895: private boolean compareAndSwapLong(long s, long l) { jaroslav@1895: if (this.state == s) { jaroslav@1895: this.state = l; jaroslav@1895: return true; jaroslav@1895: } jaroslav@1895: return false; jaroslav@1895: } jaroslav@1895: jaroslav@1890: /** jaroslav@1890: * Wait nodes for Treiber stack representing wait queue jaroslav@1890: */ jaroslav@1890: static final class QNode implements ForkJoinPool.ManagedBlocker { jaroslav@1890: final Phaser phaser; jaroslav@1890: final int phase; jaroslav@1890: final boolean interruptible; jaroslav@1890: final boolean timed; jaroslav@1890: boolean wasInterrupted; jaroslav@1890: long nanos; jaroslav@1890: long lastTime; jaroslav@1890: volatile Thread thread; // nulled to cancel wait jaroslav@1890: QNode next; jaroslav@1890: jaroslav@1890: QNode(Phaser phaser, int phase, boolean interruptible, jaroslav@1890: boolean timed, long nanos) { jaroslav@1890: this.phaser = phaser; jaroslav@1890: this.phase = phase; jaroslav@1890: this.interruptible = interruptible; jaroslav@1890: this.nanos = nanos; jaroslav@1890: this.timed = timed; jaroslav@1890: this.lastTime = timed ? System.nanoTime() : 0L; jaroslav@1890: thread = Thread.currentThread(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: public boolean isReleasable() { jaroslav@1890: if (thread == null) jaroslav@1890: return true; jaroslav@1890: if (phaser.getPhase() != phase) { jaroslav@1890: thread = null; jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: if (Thread.interrupted()) jaroslav@1890: wasInterrupted = true; jaroslav@1890: if (wasInterrupted && interruptible) { jaroslav@1890: thread = null; jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: if (timed) { jaroslav@1890: if (nanos > 0L) { jaroslav@1890: long now = System.nanoTime(); jaroslav@1890: nanos -= now - lastTime; jaroslav@1890: lastTime = now; jaroslav@1890: } jaroslav@1890: if (nanos <= 0L) { jaroslav@1890: thread = null; jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: jaroslav@1890: public boolean block() { jaroslav@1890: if (isReleasable()) jaroslav@1890: return true; jaroslav@1890: else if (!timed) jaroslav@1890: LockSupport.park(this); jaroslav@1890: else if (nanos > 0) jaroslav@1890: LockSupport.parkNanos(this, nanos); jaroslav@1890: return isReleasable(); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: }