Home » openjdk-7 » java » util » concurrent » [javadoc | source]
java.util.concurrent
public class: ForkJoinPool [javadoc | source]
java.lang.Object
   java.util.concurrent.AbstractExecutorService
      java.util.concurrent.ForkJoinPool

All Implemented Interfaces:
    ExecutorService

An ExecutorService for running ForkJoinTask s. A {@code ForkJoinPool} provides the entry point for submissions from non-{@code ForkJoinTask} clients, as well as management and monitoring operations.

A {@code ForkJoinPool} differs from other kinds of ExecutorService mainly by virtue of employing work-stealing: all threads in the pool attempt to find and execute subtasks created by other active tasks (eventually blocking waiting for work if none exist). This enables efficient processing when most tasks spawn other subtasks (as do most {@code ForkJoinTask}s). When setting asyncMode to true in constructors, {@code ForkJoinPool}s may also be appropriate for use with event-style tasks that are never joined.

A {@code ForkJoinPool} is constructed with a given target parallelism level; by default, equal to the number of available processors. The pool attempts to maintain enough active (or available) threads by dynamically adding, suspending, or resuming internal worker threads, even if some tasks are stalled waiting to join others. However, no such adjustments are guaranteed in the face of blocked IO or other unmanaged synchronization. The nested ManagedBlocker interface enables extension of the kinds of synchronization accommodated.

In addition to execution and lifecycle control methods, this class provides status check methods (for example #getStealCount ) that are intended to aid in developing, tuning, and monitoring fork/join applications. Also, method #toString returns indications of pool state in a convenient form for informal monitoring.

As is the case with other ExecutorServices, there are three main task execution methods summarized in the following table. These are designed to be used by clients not already engaged in fork/join computations in the current pool. The main forms of these methods accept instances of {@code ForkJoinTask}, but overloaded forms also allow mixed execution of plain {@code Runnable}- or {@code Callable}- based activities as well. However, tasks that are already executing in a pool should normally NOT use these pool execution methods, but instead use the within-computation forms listed in the table.
Call from non-fork/join clients Call from within fork/join computations
Arrange async execution #execute(ForkJoinTask) ForkJoinTask#fork
Await and obtain result #invoke(ForkJoinTask) ForkJoinTask#invoke
Arrange exec and obtain Future #submit(ForkJoinTask) ForkJoinTask#fork (ForkJoinTasks are Futures)

Sample Usage. Normally a single {@code ForkJoinPool} is used for all parallel task execution in a program or subsystem. Otherwise, use would not usually outweigh the construction and bookkeeping overhead of creating a large set of threads. For example, a common pool could be used for the {@code SortTasks} illustrated in RecursiveAction . Because {@code ForkJoinPool} uses threads in {@linkplain java.lang.Thread#isDaemon daemon} mode, there is typically no need to explicitly #shutdown such a pool upon program exit.

static final ForkJoinPool mainPool = new ForkJoinPool();
...
public void sort(long[] array) {
  mainPool.invoke(new SortTask(array, 0, array.length));
}

Implementation notes: This implementation restricts the maximum number of running threads to 32767. Attempts to create pools with greater than the maximum number result in {@code IllegalArgumentException}.

This implementation rejects submitted tasks (that is, by throwing RejectedExecutionException ) only when the pool is shut down or internal resources have been exhausted.

Nested Class Summary:
public static interface  ForkJoinPool.ForkJoinWorkerThreadFactory  Factory for creating new {@link ForkJoinWorkerThread}s. A {@code ForkJoinWorkerThreadFactory} must be defined and used for {@code ForkJoinWorkerThread} subclasses that extend base functionality or initialize threads with different contexts. 
static class  ForkJoinPool.DefaultForkJoinWorkerThreadFactory  Default ForkJoinWorkerThreadFactory implementation; creates a new ForkJoinWorkerThread. 
static final class  ForkJoinPool.InvokeAll   
public static interface  ForkJoinPool.ManagedBlocker  Interface for extending managed parallelism for tasks running in {@link ForkJoinPool}s.

A {@code ManagedBlocker} provides two methods. Method {@code isReleasable} must return {@code true} if blocking is not necessary. Method {@code block} blocks the current thread if necessary (perhaps internally invoking {@code isReleasable} before actually blocking). These actions are performed by any thread invoking {@link ForkJoinPool#managedBlock}. The unusual methods in this API accommodate synchronizers that may, but don't usually, block for long periods. Similarly, they allow more efficient internal handling of cases in which additional workers may be, but usually are not, needed to ensure sufficient parallelism. Toward this end, implementations of method {@code isReleasable} must be amenable to repeated invocation.

For example, here is a ManagedBlocker based on a ReentrantLock:

 {@code
class ManagedLocker implements ManagedBlocker {
  final ReentrantLock lock;
  boolean hasLock = false;
  ManagedLocker(ReentrantLock lock) { this.lock = lock; }
  public boolean block() {
    if (!hasLock)
      lock.lock();
    return true;
  }
  public boolean isReleasable() {
    return hasLock || (hasLock = lock.tryLock());
  }
}}

Here is a class that possibly blocks waiting for an item on a given queue:

 {@code
class QueueTaker implements ManagedBlocker {
  final BlockingQueue queue;
  volatile E item = null;
  QueueTaker(BlockingQueue q) { this.queue = q; }
  public boolean block() throws InterruptedException {
    if (item == null)
      item = queue.take();
    return true;
  }
  public boolean isReleasable() {
    return item != null || (item = queue.poll()) != null;
  }
  public E getItem() { // call after pool.managedBlock completes
    return item;
  }
}}
 
Field Summary
public static final  ForkJoinWorkerThreadFactory defaultForkJoinWorkerThreadFactory    Creates a new ForkJoinWorkerThread. This factory is used unless overridden in ForkJoinPool constructors. 
static final  Random workerSeedGenerator    Generator for initial random seeds for worker victim selection. This is used only to create initial seeds. Random steals use a cheaper xorshift generator per steal attempt. We don't expect much contention on seedGenerator, so just use a plain Random. 
 ForkJoinWorkerThread[] workers    Array holding all worker threads in the pool. Initialized upon construction. Array size must be a power of two. Updates and replacements are protected by scanGuard, but the array is always kept in a consistent enough state to be randomly accessed without locking by workers performing work-stealing, as well as other traversal-based methods in this class, so long as reads memory-acquire by first reading ctl. All readers must tolerate that some array slots may be null. 
final  UncaughtExceptionHandler ueh    The uncaught exception handler used when any worker abruptly terminates. 
volatile  long ctl    Main pool control -- a long packed with: AC: Number of active running workers minus target parallelism (16 bits) TC: Number of total workers minus target parallelism (16bits) ST: true if pool is terminating (1 bit) EC: the wait count of top waiting thread (15 bits) ID: ~poolIndex of top of Treiber stack of waiting threads (16 bits) When convenient, we can extract the upper 32 bits of counts and the lower 32 bits of queue state, u = (int)(ctl >>> 32) and e = (int)ctl. The ec field is never accessed alone, but always together with id and st. The offsets of counts by the target parallelism and the positionings of fields makes it possible to perform the most common checks via sign tests of fields: When ac is negative, there are not enough active workers, when tc is negative, there are not enough total workers, when id is negative, there is at least one waiting worker, and when e is negative, the pool is terminating. To deal with these possibly negative fields, we use casts in and out of "short" and/or signed shifts to maintain signedness. 
final  int parallelism    The target parallelism level. 
volatile  int queueBase    Index (mod submission queue length) of next element to take from submission queue. Usage is identical to that for per-worker queues -- see ForkJoinWorkerThread internal documentation. 
 int queueTop    Index (mod submission queue length) of next element to add in submission queue. Usage is identical to that for per-worker queues -- see ForkJoinWorkerThread internal documentation. 
volatile  boolean shutdown    True when shutdown() has been called. 
final  boolean locallyFifo    True if use local fifo, not default lifo, for local polling Read by, and replicated by ForkJoinWorkerThreads 
volatile  int quiescerCount    The number of threads in ForkJoinWorkerThreads.helpQuiescePool. When non-zero, suppresses automatic shutdown when active counts become zero. 
volatile  int blockedCount    The number of threads blocked in join. 
volatile  int scanGuard    SeqLock and index masking for updates to workers array. Locked when SG_UNIT is set. Unlocking clears bit by adding SG_UNIT. Staleness of read-only operations can be checked by comparing scanGuard to value before the reads. The low 16 bits (i.e, anding with SMASK) hold (the smallest power of two covering all worker indices, minus one, and is used to avoid dealing with large numbers of null slots when the workers array is overallocated. 
Constructor:
 public ForkJoinPool() 
    Throws:
    SecurityException - if a security manager exists and the caller is not permitted to modify threads because it does not hold java.lang.RuntimePermission {@code ("modifyThread")}
 public ForkJoinPool(int parallelism) 
 public ForkJoinPool(int parallelism,
    ForkJoinWorkerThreadFactory factory,
    UncaughtExceptionHandler handler,
    boolean asyncMode) 
    Creates a {@code ForkJoinPool} with the given parameters.
    Parameters:
    parallelism - the parallelism level. For default value, use java.lang.Runtime#availableProcessors .
    factory - the factory for creating new threads. For default value, use #defaultForkJoinWorkerThreadFactory .
    handler - the handler for internal worker threads that terminate due to unrecoverable errors encountered while executing tasks. For default value, use {@code null}.
    asyncMode - if true, establishes local first-in-first-out scheduling mode for forked tasks that are never joined. This mode may be more appropriate than default locally stack-based mode in applications in which worker threads only process event-style asynchronous tasks. For default value, use {@code false}.
    Throws:
    IllegalArgumentException - if parallelism less than or equal to zero, or greater than implementation limit
    NullPointerException - if the factory is null
    SecurityException - if a security manager exists and the caller is not permitted to modify threads because it does not hold java.lang.RuntimePermission {@code ("modifyThread")}
Method from java.util.concurrent.ForkJoinPool Summary:
addActiveCount,   addQuiescerCount,   awaitTermination,   deregisterWorker,   drainTasksTo,   execute,   execute,   getActiveThreadCount,   getAsyncMode,   getFactory,   getParallelism,   getPoolSize,   getQueuedSubmissionCount,   getQueuedTaskCount,   getRunningThreadCount,   getStealCount,   getUncaughtExceptionHandler,   hasQueuedSubmissions,   idlePerActive,   invoke,   invokeAll,   isAtLeastTerminating,   isQuiescent,   isShutdown,   isTerminated,   isTerminating,   managedBlock,   newTaskFor,   newTaskFor,   nextWorkerName,   pollSubmission,   registerWorker,   shutdown,   shutdownNow,   signalWork,   submit,   submit,   submit,   submit,   timedAwaitJoin,   toString,   tryAwaitJoin,   work
Methods from java.util.concurrent.AbstractExecutorService:
invokeAll,   invokeAll,   invokeAny,   invokeAny,   newTaskFor,   newTaskFor,   submit,   submit,   submit
Methods from java.lang.Object:
clone,   equals,   finalize,   getClass,   hashCode,   notify,   notifyAll,   toString,   wait,   wait,   wait
Method from java.util.concurrent.ForkJoinPool Detail:
 final  void addActiveCount(int delta) 
    Directly increment or decrement active count without queuing. This method is used to transiently assert inactivation while checking quiescence.
 final  void addQuiescerCount(int delta) 
    Increment or decrement quiescerCount. Needed only to prevent triggering shutdown if a worker is transiently inactive while checking quiescence.
 public boolean awaitTermination(long timeout,
    TimeUnit unit) throws InterruptedException 
    Blocks until all tasks have completed execution after a shutdown request, or the timeout occurs, or the current thread is interrupted, whichever happens first.
 final  void deregisterWorker(ForkJoinWorkerThread w,
    Throwable ex) 
    Final callback from terminating worker. Removes record of worker from array, and adjusts counts. If pool is shutting down, tries to complete termination.
 protected int drainTasksTo(Collection<ForkJoinTask> c) 
    Removes all available unexecuted submitted and forked tasks from scheduling queues and adds them to the given collection, without altering their execution status. These may include artificially generated or wrapped tasks. This method is designed to be invoked only when the pool is known to be quiescent. Invocations at other times may not remove all tasks. A failure encountered while attempting to add elements to collection {@code c} may result in elements being in neither, either or both collections when the associated exception is thrown. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress.
 public  void execute(ForkJoinTask<?> task) 
    Arranges for (asynchronous) execution of the given task.
 public  void execute(Runnable task) 
 public int getActiveThreadCount() 
    Returns an estimate of the number of threads that are currently stealing or executing tasks. This method may overestimate the number of active threads.
 public boolean getAsyncMode() 
    Returns {@code true} if this pool uses local first-in-first-out scheduling mode for forked tasks that are never joined.
 public ForkJoinWorkerThreadFactory getFactory() 
    Returns the factory used for constructing new workers.
 public int getParallelism() 
    Returns the targeted parallelism level of this pool.
 public int getPoolSize() 
    Returns the number of worker threads that have started but not yet terminated. The result returned by this method may differ from #getParallelism when threads are created to maintain parallelism when others are cooperatively blocked.
 public int getQueuedSubmissionCount() 
    Returns an estimate of the number of tasks submitted to this pool that have not yet begun executing. This method may take time proportional to the number of submissions.
 public long getQueuedTaskCount() 
    Returns an estimate of the total number of tasks currently held in queues by worker threads (but not including tasks submitted to the pool that have not begun executing). This value is only an approximation, obtained by iterating across all threads in the pool. This method may be useful for tuning task granularities.
 public int getRunningThreadCount() 
    Returns an estimate of the number of worker threads that are not blocked waiting to join tasks or for other managed synchronization. This method may overestimate the number of running threads.
 public long getStealCount() 
    Returns an estimate of the total number of tasks stolen from one thread's work queue by another. The reported value underestimates the actual total number of steals when the pool is not quiescent. This value may be useful for monitoring and tuning fork/join programs: in general, steal counts should be high enough to keep threads busy, but low enough to avoid overhead and contention across threads.
 public UncaughtExceptionHandler getUncaughtExceptionHandler() 
    Returns the handler for internal worker threads that terminate due to unrecoverable errors encountered while executing tasks.
 public boolean hasQueuedSubmissions() 
    Returns {@code true} if there are any tasks submitted to this pool that have not yet begun executing.
 final int idlePerActive() 
    Returns the approximate (non-atomic) number of idle threads per active thread.
 public T invoke(ForkJoinTask<T> task) 
    Performs the given task, returning its result upon completion. If the computation encounters an unchecked Exception or Error, it is rethrown as the outcome of this invocation. Rethrown exceptions behave in the same way as regular exceptions, but, when possible, contain stack traces (as displayed for example using {@code ex.printStackTrace()}) of both the current thread as well as the thread actually encountering the exception; minimally only the latter.
 public List<T> invokeAll(Collection<Callable> tasks) 
 final boolean isAtLeastTerminating() 
    Returns true if terminating or terminated. Used by ForkJoinWorkerThread.
 public boolean isQuiescent() 
    Returns {@code true} if all worker threads are currently idle. An idle worker is one that cannot obtain a task to execute because none are available to steal from other threads, and there are no pending submissions to the pool. This method is conservative; it might not return {@code true} immediately upon idleness of all threads, but will eventually become true if threads remain inactive.
 public boolean isShutdown() 
    Returns {@code true} if this pool has been shut down.
 public boolean isTerminated() 
    Returns {@code true} if all tasks have completed following shut down.
 public boolean isTerminating() 
    Returns {@code true} if the process of termination has commenced but not yet completed. This method may be useful for debugging. A return of {@code true} reported a sufficient period after shutdown may indicate that submitted tasks have ignored or suppressed interruption, or are waiting for IO, causing this executor not to properly terminate. (See the advisory notes for class ForkJoinTask stating that tasks should not normally entail blocking operations. But if they do, they must abort them on interrupt.)
 public static  void managedBlock(ManagedBlocker blocker) throws InterruptedException 
    Blocks in accord with the given blocker. If the current thread is a ForkJoinWorkerThread , this method possibly arranges for a spare thread to be activated if necessary to ensure sufficient parallelism while the current thread is blocked.

    If the caller is not a ForkJoinTask , this method is behaviorally equivalent to

     {@code
    while (!blocker.isReleasable())
      if (blocker.block())
        return;
    }
    If the caller is a {@code ForkJoinTask}, then the pool may first be expanded to ensure parallelism, and later adjusted.
 protected RunnableFuture<T> newTaskFor(Callable<T> callable) 
 protected RunnableFuture<T> newTaskFor(Runnable runnable,
    T value) 
 final String nextWorkerName() 
    Callback from ForkJoinWorkerThread constructor to assign a public name
 protected ForkJoinTask<?> pollSubmission() 
    Removes and returns the next unexecuted submission if one is available. This method may be useful in extensions to this class that re-assign work in systems with multiple pools.
 final int registerWorker(ForkJoinWorkerThread w) 
    Callback from ForkJoinWorkerThread constructor to determine its poolIndex and record in workers array.
 public  void shutdown() 
    Initiates an orderly shutdown in which previously submitted tasks are executed, but no new tasks will be accepted. Invocation has no additional effect if already shut down. Tasks that are in the process of being submitted concurrently during the course of this method may or may not be rejected.
 public List<Runnable> shutdownNow() 
    Attempts to cancel and/or stop all tasks, and reject all subsequently submitted tasks. Tasks that are in the process of being submitted or executed concurrently during the course of this method may or may not be rejected. This method cancels both existing and unexecuted tasks, in order to permit termination in the presence of task dependencies. So the method always returns an empty list (unlike the case for some other Executors).
 final  void signalWork() 
    Wakes up or creates a worker.
 public ForkJoinTask<T> submit(ForkJoinTask<T> task) 
    Submits a ForkJoinTask for execution.
 public ForkJoinTask<T> submit(Callable<T> task) 
 public ForkJoinTask<?> submit(Runnable task) 
 public ForkJoinTask<T> submit(Runnable task,
    T result) 
 final  void timedAwaitJoin(ForkJoinTask<?> joinMe,
    long nanos) 
    Possibly blocks the given worker waiting for joinMe to complete or timeout
 public String toString() 
    Returns a string identifying this pool, as well as its state, including indications of run state, parallelism level, and worker and task counts.
 final  void tryAwaitJoin(ForkJoinTask<?> joinMe) 
    Possibly blocks waiting for the given task to complete, or cancels the task if terminating. Fails to wait if contended.
 final  void work(ForkJoinWorkerThread w) 
    Top-level loop for worker threads: On each step: if the previous step swept through all queues and found no tasks, or there are excess threads, then possibly blocks. Otherwise, scans for and, if found, executes a task. Returns when pool and/or worker terminate.