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.io.Serializable;
jaroslav@1890: import java.util.Collection;
jaroslav@1890: import java.util.List;
jaroslav@1890: import java.util.RandomAccess;
jaroslav@1890: import java.lang.ref.WeakReference;
jaroslav@1890: import java.lang.ref.ReferenceQueue;
jaroslav@1890: import java.util.concurrent.Callable;
jaroslav@1890: import java.util.concurrent.CancellationException;
jaroslav@1890: import java.util.concurrent.ExecutionException;
jaroslav@1890: import java.util.concurrent.Future;
jaroslav@1890: import java.util.concurrent.RejectedExecutionException;
jaroslav@1890: import java.util.concurrent.RunnableFuture;
jaroslav@1890: import java.util.concurrent.TimeUnit;
jaroslav@1890: import java.util.concurrent.TimeoutException;
jaroslav@1890: import java.util.concurrent.locks.ReentrantLock;
jaroslav@1890: import java.lang.reflect.Constructor;
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Abstract base class for tasks that run within a {@link ForkJoinPool}.
jaroslav@1890: * A {@code ForkJoinTask} is a thread-like entity that is much
jaroslav@1890: * lighter weight than a normal thread. Huge numbers of tasks and
jaroslav@1890: * subtasks may be hosted by a small number of actual threads in a
jaroslav@1890: * ForkJoinPool, at the price of some usage limitations.
jaroslav@1890: *
jaroslav@1890: *
A "main" {@code ForkJoinTask} begins execution when submitted
jaroslav@1890: * to a {@link ForkJoinPool}. Once started, it will usually in turn
jaroslav@1890: * start other subtasks. As indicated by the name of this class,
jaroslav@1890: * many programs using {@code ForkJoinTask} employ only methods
jaroslav@1890: * {@link #fork} and {@link #join}, or derivatives such as {@link
jaroslav@1890: * #invokeAll(ForkJoinTask...) invokeAll}. However, this class also
jaroslav@1890: * provides a number of other methods that can come into play in
jaroslav@1890: * advanced usages, as well as extension mechanics that allow
jaroslav@1890: * support of new forms of fork/join processing.
jaroslav@1890: *
jaroslav@1890: *
A {@code ForkJoinTask} is a lightweight form of {@link Future}.
jaroslav@1890: * The efficiency of {@code ForkJoinTask}s stems from a set of
jaroslav@1890: * restrictions (that are only partially statically enforceable)
jaroslav@1890: * reflecting their intended use as computational tasks calculating
jaroslav@1890: * pure functions or operating on purely isolated objects. The
jaroslav@1890: * primary coordination mechanisms are {@link #fork}, that arranges
jaroslav@1890: * asynchronous execution, and {@link #join}, that doesn't proceed
jaroslav@1890: * until the task's result has been computed. Computations should
jaroslav@1890: * avoid {@code synchronized} methods or blocks, and should minimize
jaroslav@1890: * other blocking synchronization apart from joining other tasks or
jaroslav@1890: * using synchronizers such as Phasers that are advertised to
jaroslav@1890: * cooperate with fork/join scheduling. Tasks should also not perform
jaroslav@1890: * blocking IO, and should ideally access variables that are
jaroslav@1890: * completely independent of those accessed by other running
jaroslav@1890: * tasks. Minor breaches of these restrictions, for example using
jaroslav@1890: * shared output streams, may be tolerable in practice, but frequent
jaroslav@1890: * use may result in poor performance, and the potential to
jaroslav@1890: * indefinitely stall if the number of threads not waiting for IO or
jaroslav@1890: * other external synchronization becomes exhausted. This usage
jaroslav@1890: * restriction is in part enforced by not permitting checked
jaroslav@1890: * exceptions such as {@code IOExceptions} to be thrown. However,
jaroslav@1890: * computations may still encounter unchecked exceptions, that are
jaroslav@1890: * rethrown to callers attempting to join them. These exceptions may
jaroslav@1890: * additionally include {@link RejectedExecutionException} stemming
jaroslav@1890: * from internal resource exhaustion, such as failure to allocate
jaroslav@1890: * internal task queues. Rethrown exceptions behave in the same way as
jaroslav@1890: * regular exceptions, but, when possible, contain stack traces (as
jaroslav@1890: * displayed for example using {@code ex.printStackTrace()}) of both
jaroslav@1890: * the thread that initiated the computation as well as the thread
jaroslav@1890: * actually encountering the exception; minimally only the latter.
jaroslav@1890: *
jaroslav@1890: *
The primary method for awaiting completion and extracting
jaroslav@1890: * results of a task is {@link #join}, but there are several variants:
jaroslav@1890: * The {@link Future#get} methods support interruptible and/or timed
jaroslav@1890: * waits for completion and report results using {@code Future}
jaroslav@1890: * conventions. Method {@link #invoke} is semantically
jaroslav@1890: * equivalent to {@code fork(); join()} but always attempts to begin
jaroslav@1890: * execution in the current thread. The "quiet" forms of
jaroslav@1890: * these methods do not extract results or report exceptions. These
jaroslav@1890: * may be useful when a set of tasks are being executed, and you need
jaroslav@1890: * to delay processing of results or exceptions until all complete.
jaroslav@1890: * Method {@code invokeAll} (available in multiple versions)
jaroslav@1890: * performs the most common form of parallel invocation: forking a set
jaroslav@1890: * of tasks and joining them all.
jaroslav@1890: *
jaroslav@1890: *
The execution status of tasks may be queried at several levels
jaroslav@1890: * of detail: {@link #isDone} is true if a task completed in any way
jaroslav@1890: * (including the case where a task was cancelled without executing);
jaroslav@1890: * {@link #isCompletedNormally} is true if a task completed without
jaroslav@1890: * cancellation or encountering an exception; {@link #isCancelled} is
jaroslav@1890: * true if the task was cancelled (in which case {@link #getException}
jaroslav@1890: * returns a {@link java.util.concurrent.CancellationException}); and
jaroslav@1890: * {@link #isCompletedAbnormally} is true if a task was either
jaroslav@1890: * cancelled or encountered an exception, in which case {@link
jaroslav@1890: * #getException} will return either the encountered exception or
jaroslav@1890: * {@link java.util.concurrent.CancellationException}.
jaroslav@1890: *
jaroslav@1890: *
The ForkJoinTask class is not usually directly subclassed.
jaroslav@1890: * Instead, you subclass one of the abstract classes that support a
jaroslav@1890: * particular style of fork/join processing, typically {@link
jaroslav@1890: * RecursiveAction} for computations that do not return results, or
jaroslav@1890: * {@link RecursiveTask} for those that do. Normally, a concrete
jaroslav@1890: * ForkJoinTask subclass declares fields comprising its parameters,
jaroslav@1890: * established in a constructor, and then defines a {@code compute}
jaroslav@1890: * method that somehow uses the control methods supplied by this base
jaroslav@1890: * class. While these methods have {@code public} access (to allow
jaroslav@1890: * instances of different task subclasses to call each other's
jaroslav@1890: * methods), some of them may only be called from within other
jaroslav@1890: * ForkJoinTasks (as may be determined using method {@link
jaroslav@1890: * #inForkJoinPool}). Attempts to invoke them in other contexts
jaroslav@1890: * result in exceptions or errors, possibly including
jaroslav@1890: * {@code ClassCastException}.
jaroslav@1890: *
jaroslav@1890: *
Method {@link #join} and its variants are appropriate for use
jaroslav@1890: * only when completion dependencies are acyclic; that is, the
jaroslav@1890: * parallel computation can be described as a directed acyclic graph
jaroslav@1890: * (DAG). Otherwise, executions may encounter a form of deadlock as
jaroslav@1890: * tasks cyclically wait for each other. However, this framework
jaroslav@1890: * supports other methods and techniques (for example the use of
jaroslav@1890: * {@link Phaser}, {@link #helpQuiesce}, and {@link #complete}) that
jaroslav@1890: * may be of use in constructing custom subclasses for problems that
jaroslav@1890: * are not statically structured as DAGs.
jaroslav@1890: *
jaroslav@1890: *
Most base support methods are {@code final}, to prevent
jaroslav@1890: * overriding of implementations that are intrinsically tied to the
jaroslav@1890: * underlying lightweight task scheduling framework. Developers
jaroslav@1890: * creating new basic styles of fork/join processing should minimally
jaroslav@1890: * implement {@code protected} methods {@link #exec}, {@link
jaroslav@1890: * #setRawResult}, and {@link #getRawResult}, while also introducing
jaroslav@1890: * an abstract computational method that can be implemented in its
jaroslav@1890: * subclasses, possibly relying on other {@code protected} methods
jaroslav@1890: * provided by this class.
jaroslav@1890: *
jaroslav@1890: *
ForkJoinTasks should perform relatively small amounts of
jaroslav@1890: * computation. Large tasks should be split into smaller subtasks,
jaroslav@1890: * usually via recursive decomposition. As a very rough rule of thumb,
jaroslav@1890: * a task should perform more than 100 and less than 10000 basic
jaroslav@1890: * computational steps, and should avoid indefinite looping. If tasks
jaroslav@1890: * are too big, then parallelism cannot improve throughput. If too
jaroslav@1890: * small, then memory and internal task maintenance overhead may
jaroslav@1890: * overwhelm processing.
jaroslav@1890: *
jaroslav@1890: *
This class provides {@code adapt} methods for {@link Runnable}
jaroslav@1890: * and {@link Callable}, that may be of use when mixing execution of
jaroslav@1890: * {@code ForkJoinTasks} with other kinds of tasks. When all tasks are
jaroslav@1890: * of this form, consider using a pool constructed in asyncMode.
jaroslav@1890: *
jaroslav@1890: *
ForkJoinTasks are {@code Serializable}, which enables them to be
jaroslav@1890: * used in extensions such as remote execution frameworks. It is
jaroslav@1890: * sensible to serialize tasks only before or after, but not during,
jaroslav@1890: * execution. Serialization is not relied on during execution itself.
jaroslav@1890: *
jaroslav@1890: * @since 1.7
jaroslav@1890: * @author Doug Lea
jaroslav@1890: */
jaroslav@1890: public abstract class ForkJoinTask implements Future, Serializable {
jaroslav@1890:
jaroslav@1890: /*
jaroslav@1890: * See the internal documentation of class ForkJoinPool for a
jaroslav@1890: * general implementation overview. ForkJoinTasks are mainly
jaroslav@1890: * responsible for maintaining their "status" field amidst relays
jaroslav@1890: * to methods in ForkJoinWorkerThread and ForkJoinPool. The
jaroslav@1890: * methods of this class are more-or-less layered into (1) basic
jaroslav@1890: * status maintenance (2) execution and awaiting completion (3)
jaroslav@1890: * user-level methods that additionally report results. This is
jaroslav@1890: * sometimes hard to see because this file orders exported methods
jaroslav@1890: * in a way that flows well in javadocs.
jaroslav@1890: */
jaroslav@1890:
jaroslav@1890: /*
jaroslav@1890: * The status field holds run control status bits packed into a
jaroslav@1890: * single int to minimize footprint and to ensure atomicity (via
jaroslav@1890: * CAS). Status is initially zero, and takes on nonnegative
jaroslav@1890: * values until completed, upon which status holds value
jaroslav@1890: * NORMAL, CANCELLED, or EXCEPTIONAL. Tasks undergoing blocking
jaroslav@1890: * waits by other threads have the SIGNAL bit set. Completion of
jaroslav@1890: * a stolen task with SIGNAL set awakens any waiters via
jaroslav@1890: * notifyAll. Even though suboptimal for some purposes, we use
jaroslav@1890: * basic builtin wait/notify to take advantage of "monitor
jaroslav@1890: * inflation" in JVMs that we would otherwise need to emulate to
jaroslav@1890: * avoid adding further per-task bookkeeping overhead. We want
jaroslav@1890: * these monitors to be "fat", i.e., not use biasing or thin-lock
jaroslav@1890: * techniques, so use some odd coding idioms that tend to avoid
jaroslav@1890: * them.
jaroslav@1890: */
jaroslav@1890:
jaroslav@1890: /** The run status of this task */
jaroslav@1890: volatile int status; // accessed directly by pool and workers
jaroslav@1890: private static final int NORMAL = -1;
jaroslav@1890: private static final int CANCELLED = -2;
jaroslav@1890: private static final int EXCEPTIONAL = -3;
jaroslav@1890: private static final int SIGNAL = 1;
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Marks completion and wakes up threads waiting to join this task,
jaroslav@1890: * also clearing signal request bits.
jaroslav@1890: *
jaroslav@1890: * @param completion one of NORMAL, CANCELLED, EXCEPTIONAL
jaroslav@1890: * @return completion status on exit
jaroslav@1890: */
jaroslav@1890: private int setCompletion(int completion) {
jaroslav@1890: for (int s;;) {
jaroslav@1890: if ((s = status) < 0)
jaroslav@1890: return s;
jaroslav@1890: if (UNSAFE.compareAndSwapInt(this, statusOffset, s, completion)) {
jaroslav@1890: if (s != 0)
jaroslav@1890: synchronized (this) { notifyAll(); }
jaroslav@1890: return completion;
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Tries to block a worker thread until completed or timed out.
jaroslav@1890: * Uses Object.wait time argument conventions.
jaroslav@1890: * May fail on contention or interrupt.
jaroslav@1890: *
jaroslav@1890: * @param millis if > 0, wait time.
jaroslav@1890: */
jaroslav@1890: final void tryAwaitDone(long millis) {
jaroslav@1890: int s;
jaroslav@1890: try {
jaroslav@1890: if (((s = status) > 0 ||
jaroslav@1890: (s == 0 &&
jaroslav@1890: UNSAFE.compareAndSwapInt(this, statusOffset, 0, SIGNAL))) &&
jaroslav@1890: status > 0) {
jaroslav@1890: synchronized (this) {
jaroslav@1890: if (status > 0)
jaroslav@1890: wait(millis);
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: } catch (InterruptedException ie) {
jaroslav@1890: // caller must check termination
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Blocks a non-worker-thread until completion.
jaroslav@1890: * @return status upon completion
jaroslav@1890: */
jaroslav@1890: private int externalAwaitDone() {
jaroslav@1890: int s;
jaroslav@1890: if ((s = status) >= 0) {
jaroslav@1890: boolean interrupted = false;
jaroslav@1890: synchronized (this) {
jaroslav@1890: while ((s = status) >= 0) {
jaroslav@1890: if (s == 0)
jaroslav@1890: UNSAFE.compareAndSwapInt(this, statusOffset,
jaroslav@1890: 0, SIGNAL);
jaroslav@1890: else {
jaroslav@1890: try {
jaroslav@1890: wait();
jaroslav@1890: } catch (InterruptedException ie) {
jaroslav@1890: interrupted = true;
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: if (interrupted)
jaroslav@1890: Thread.currentThread().interrupt();
jaroslav@1890: }
jaroslav@1890: return s;
jaroslav@1890: }
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Blocks a non-worker-thread until completion or interruption or timeout.
jaroslav@1890: */
jaroslav@1890: private int externalInterruptibleAwaitDone(long millis)
jaroslav@1890: throws InterruptedException {
jaroslav@1890: int s;
jaroslav@1890: if (Thread.interrupted())
jaroslav@1890: throw new InterruptedException();
jaroslav@1890: if ((s = status) >= 0) {
jaroslav@1890: synchronized (this) {
jaroslav@1890: while ((s = status) >= 0) {
jaroslav@1890: if (s == 0)
jaroslav@1890: UNSAFE.compareAndSwapInt(this, statusOffset,
jaroslav@1890: 0, SIGNAL);
jaroslav@1890: else {
jaroslav@1890: wait(millis);
jaroslav@1890: if (millis > 0L)
jaroslav@1890: break;
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890: return s;
jaroslav@1890: }
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Primary execution method for stolen tasks. Unless done, calls
jaroslav@1890: * exec and records status if completed, but doesn't wait for
jaroslav@1890: * completion otherwise.
jaroslav@1890: */
jaroslav@1890: final void doExec() {
jaroslav@1890: if (status >= 0) {
jaroslav@1890: boolean completed;
jaroslav@1890: try {
jaroslav@1890: completed = exec();
jaroslav@1890: } catch (Throwable rex) {
jaroslav@1890: setExceptionalCompletion(rex);
jaroslav@1890: return;
jaroslav@1890: }
jaroslav@1890: if (completed)
jaroslav@1890: setCompletion(NORMAL); // must be outside try block
jaroslav@1890: }
jaroslav@1890: }
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Primary mechanics for join, get, quietlyJoin.
jaroslav@1890: * @return status upon completion
jaroslav@1890: */
jaroslav@1890: private int doJoin() {
jaroslav@1890: Thread t; ForkJoinWorkerThread w; int s; boolean completed;
jaroslav@1890: if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) {
jaroslav@1890: if ((s = status) < 0)
jaroslav@1890: return s;
jaroslav@1890: if ((w = (ForkJoinWorkerThread)t).unpushTask(this)) {
jaroslav@1890: try {
jaroslav@1890: completed = exec();
jaroslav@1890: } catch (Throwable rex) {
jaroslav@1890: return setExceptionalCompletion(rex);
jaroslav@1890: }
jaroslav@1890: if (completed)
jaroslav@1890: return setCompletion(NORMAL);
jaroslav@1890: }
jaroslav@1890: return w.joinTask(this);
jaroslav@1890: }
jaroslav@1890: else
jaroslav@1890: return externalAwaitDone();
jaroslav@1890: }
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Primary mechanics for invoke, quietlyInvoke.
jaroslav@1890: * @return status upon completion
jaroslav@1890: */
jaroslav@1890: private int doInvoke() {
jaroslav@1890: int s; boolean completed;
jaroslav@1890: if ((s = status) < 0)
jaroslav@1890: return s;
jaroslav@1890: try {
jaroslav@1890: completed = exec();
jaroslav@1890: } catch (Throwable rex) {
jaroslav@1890: return setExceptionalCompletion(rex);
jaroslav@1890: }
jaroslav@1890: if (completed)
jaroslav@1890: return setCompletion(NORMAL);
jaroslav@1890: else
jaroslav@1890: return doJoin();
jaroslav@1890: }
jaroslav@1890:
jaroslav@1890: // Exception table support
jaroslav@1890:
jaroslav@1890: /**
jaroslav@1890: * Table of exceptions thrown by tasks, to enable reporting by
jaroslav@1890: * callers. Because exceptions are rare, we don't directly keep
jaroslav@1890: * them with task objects, but instead use a weak ref table. Note
jaroslav@1890: * that cancellation exceptions don't appear in the table, but are
jaroslav@1890: * instead recorded as status values.
jaroslav@1890: *
jaroslav@1890: * Note: These statics are initialized below in static block.
jaroslav@1890: */
jaroslav@1890: private static final ExceptionNode[] exceptionTable;
jaroslav@1890: private static final ReentrantLock exceptionTableLock;
jaroslav@1890: private static final ReferenceQueue