Provides default implementations of ExecutorService
execution methods. This class implements the submit,
invokeAny and invokeAll methods using a
RunnableFuture returned by newTaskFor, which defaults
to the FutureTask class provided in this package.  For example,
the implementation of submit(Runnable) creates an
associated RunnableFuture that is executed and
returned. Subclasses may override the newTaskFor methods
to return RunnableFuture implementations other than
FutureTask.

Extension example. Here is a sketch of a class
that customizes ThreadPoolExecutor to use
a CustomTask class instead of the default FutureTask:


public class CustomThreadPoolExecutor extends ThreadPoolExecutor {

  static class CustomTask<V> implements RunnableFuture<V> {...}

  protected <V> RunnableFuture<V> newTaskFor(Callable<V> c) {
      return new CustomTask<V>(c);
  }
  protected <V> RunnableFuture<V> newTaskFor(Runnable r, V v) {
      return new CustomTask<V>(r, v);
  }
  // ... add constructors, etc.
}

A bounded java.util.concurrent.blocking queue backed by an
array.  This queue orders elements FIFO (first-in-first-out).  The
head of the queue is that element that has been on the
queue the longest time.  The tail of the queue is that
element that has been on the queue the shortest time. New elements
are inserted at the tail of the queue, and the queue retrieval
operations obtain elements at the head of the queue.

This is a classic "bounded buffer", in which a
fixed-sized array holds elements inserted by producers and
extracted by consumers.  Once created, the capacity cannot be
changed.  Attempts to put an element into a full queue
will result in the operation blocking; attempts to take an
element from an empty queue will similarly block.

This class supports an optional fairness policy for ordering
waiting producer and consumer threads.  By default, this ordering
is not guaranteed. However, a queue constructed with fairness set
to true grants threads access in FIFO order. Fairness
generally decreases throughput but reduces variability and avoids
starvation.

This class and its iterator implement all of the
optional methods of the Collection and Iterator interfaces.

This class is a member of the

Java Collections Framework.

A boolean value that may be updated atomically. See the
java.util.concurrent.atomic package specification for
description of the properties of atomic variables. An
AtomicBoolean is used in applications such as atomically
updated flags, and cannot be used as a replacement for a
Boolean.

An int value that may be updated atomically.  See the
java.util.concurrent.atomic package specification for
description of the properties of atomic variables. An
AtomicInteger is used in applications such as atomically
incremented counters, and cannot be used as a replacement for an
Integer. However, this class does extend
Number to allow uniform access by tools and utilities that
deal with numerically-based classes.

An int array in which elements may be updated atomically.
See the java.util.concurrent.atomic package
specification for description of the properties of atomic
variables.

A reflection-based utility that enables atomic updates to
designated volatile int fields of designated classes.
This class is designed for use in atomic data structures in which
several fields of the same node are independently subject to atomic
updates.

Note that the guarantees of the compareAndSet
method in this class are weaker than in other atomic classes.
Because this class cannot ensure that all uses of the field
are appropriate for purposes of atomic access, it can
guarantee atomicity only with respect to other invocations of
compareAndSet and set on the same updater.

A long value that may be updated atomically.  See the
java.util.concurrent.atomic package specification for
description of the properties of atomic variables. An
AtomicLong is used in applications such as atomically
incremented sequence numbers, and cannot be used as a replacement
for a Long. However, this class does extend
Number to allow uniform access by tools and utilities that
deal with numerically-based classes.

A long array in which elements may be updated atomically.
See the java.util.concurrent.atomic package specification
for description of the properties of atomic variables.

A reflection-based utility that enables atomic updates to
designated volatile long fields of designated classes.
This class is designed for use in atomic data structures in which
several fields of the same node are independently subject to atomic
updates.

Note that the guarantees of the compareAndSet
method in this class are weaker than in other atomic classes.
Because this class cannot ensure that all uses of the field
are appropriate for purposes of atomic access, it can
guarantee atomicity only with respect to other invocations of
compareAndSet and set on the same updater.

An AtomicMarkableReference maintains an object reference
along with a mark bit, that can be updated atomically.

Implementation note: This implementation maintains markable
references by creating internal objects representing "boxed"
[reference, boolean] pairs.

An object reference that may be updated atomically. See the java.util.concurrent.atomic package specification for description
of the properties of atomic variables.

An array of object references in which elements may be updated
atomically.  See the java.util.concurrent.atomic package
specification for description of the properties of atomic
variables.

A reflection-based utility that enables atomic updates to
designated volatile reference fields of designated
classes.  This class is designed for use in atomic data structures
in which several reference fields of the same node are
independently subject to atomic updates. For example, a tree node
might be declared as



class Node {
  private volatile Node left, right;

  private static final AtomicReferenceFieldUpdater<Node, Node> leftUpdater =
    AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "left");
  private static AtomicReferenceFieldUpdater<Node, Node> rightUpdater =
    AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "right");

  Node getLeft() { return left; }
  boolean compareAndSetLeft(Node expect, Node update) {
    return leftUpdater.compareAndSet(this, expect, update);
  }
  // ... and so on
}

Note that the guarantees of the compareAndSet
method in this class are weaker than in other atomic classes.
Because this class cannot ensure that all uses of the field
are appropriate for purposes of atomic access, it can
guarantee atomicity only with respect to other invocations of
compareAndSet and set on the same updater.

An AtomicStampedReference maintains an object reference
along with an integer "stamp", that can be updated atomically.

Implementation note: This implementation maintains stamped
references by creating internal objects representing "boxed"
[reference, integer] pairs.

One or more variables that together maintain a running double
value updated using a supplied function.  When updates (method
accumulate(double)) are contended across threads, the set of variables
may grow dynamically to reduce contention.  Method get()
(or, equivalently, doubleValue()) returns the current value
across the variables maintaining updates.

This class is usually preferable to alternatives when multiple
threads update a common value that is used for purposes such as
summary statistics that are frequently updated but less frequently
read.

The supplied accumulator function should be side-effect-free,
since it may be re-applied when attempted updates fail due to
contention among threads. The function is applied with the current
value as its first argument, and the given update as the second
argument.  For example, to maintain a running maximum value, you
could supply Double::max along with Double.NEGATIVE_INFINITY as the identity. The order of
accumulation within or across threads is not guaranteed. Thus, this
class may not be applicable if numerical stability is required,
especially when combining values of substantially different orders
of magnitude.

Class DoubleAdder provides analogs of the functionality
of this class for the common special case of maintaining sums.  The
call new DoubleAdder() is equivalent to new
DoubleAccumulator((x, y) -> x  y, 0.0).

This class extends Number, but does not define
methods such as equals, hashCode and compareTo because instances are expected to be mutated, and so are
not useful as collection keys.

One or more variables that together maintain an initially zero
double sum.  When updates (method add(double)) are
contended across threads, the set of variables may grow dynamically
to reduce contention.  Method sum() (or, equivalently doubleValue()) returns the current total combined across the
variables maintaining the sum. The order of accumulation within or
across threads is not guaranteed. Thus, this class may not be
applicable if numerical stability is required, especially when
combining values of substantially different orders of magnitude.

This class is usually preferable to alternatives when multiple
threads update a common value that is used for purposes such as
summary statistics that are frequently updated but less frequently
read.

This class extends Number, but does not define
methods such as equals, hashCode and compareTo because instances are expected to be mutated, and so are
not useful as collection keys.

One or more variables that together maintain a running long
value updated using a supplied function.  When updates (method
accumulate(long)) are contended across threads, the set of variables
may grow dynamically to reduce contention.  Method get()
(or, equivalently, longValue()) returns the current value
across the variables maintaining updates.

This class is usually preferable to AtomicLong when
multiple threads update a common value that is used for purposes such
as collecting statistics, not for fine-grained synchronization
control.  Under low update contention, the two classes have similar
characteristics. But under high contention, expected throughput of
this class is significantly higher, at the expense of higher space
consumption.

The order of accumulation within or across threads is not
guaranteed and cannot be depended upon, so this class is only
applicable to functions for which the order of accumulation does
not matter. The supplied accumulator function should be
side-effect-free, since it may be re-applied when attempted updates
fail due to contention among threads. The function is applied with
the current value as its first argument, and the given update as
the second argument.  For example, to maintain a running maximum
value, you could supply Long::max along with Long.MIN_VALUE as the identity.

Class LongAdder provides analogs of the functionality of
this class for the common special case of maintaining counts and
sums.  The call new LongAdder() is equivalent to new
LongAccumulator((x, y) -> x  y, 0L.

This class extends Number, but does not define
methods such as equals, hashCode and compareTo because instances are expected to be mutated, and so are
not useful as collection keys.

One or more variables that together maintain an initially zero
long sum.  When updates (method add(long)) are contended
across threads, the set of variables may grow dynamically to reduce
contention. Method sum() (or, equivalently, longValue()) returns the current total combined across the
variables maintaining the sum.

This class is usually preferable to AtomicLong when
multiple threads update a common sum that is used for purposes such
as collecting statistics, not for fine-grained synchronization
control.  Under low update contention, the two classes have similar
characteristics. But under high contention, expected throughput of
this class is significantly higher, at the expense of higher space
consumption.

LongAdders can be used with a ConcurrentHashMap to maintain a scalable
frequency map (a form of histogram or multiset). For example, to
add a count to a ConcurrentHashMap<String,LongAdder> freqs,
initializing if not already present, you can use freqs.computeIfAbsent(k -> new LongAdder()).increment();

This class extends Number, but does not define
methods such as equals, hashCode and compareTo because instances are expected to be mutated, and so are
not useful as collection keys.

First Element (Head)

Last Element (Tail)

BlockingQueue Method
Equivalent BlockingDeque Method


Insert

Remove

Examine

A Deque that additionally supports blocking operations that wait
for the deque to become non-empty when retrieving an element, and wait for
space to become available in the deque when storing an element.

BlockingDeque methods come in four forms, with different ways
of handling operations that cannot be satisfied immediately, but may be
satisfied at some point in the future:
one throws an exception, the second returns a special value (either
null or false, depending on the operation), the third
blocks the current thread indefinitely until the operation can succeed,
and the fourth blocks for only a given maximum time limit before giving
up.  These methods are summarized in the following table:


Summary of BlockingDeque methods

    First Element (Head)



   Throws exception
   Special value
   Blocks
   Times out


   Insert
   addFirst(e)
   offerFirst(e)
   putFirst(e)
   offerFirst(e, time, unit)


   Remove
   removeFirst()
   pollFirst()
   takeFirst()
   pollFirst(time, unit)


   Examine
   getFirst()
   peekFirst()
   not applicable
   not applicable


    Last Element (Tail)



   Throws exception
   Special value
   Blocks
   Times out


   Insert
   addLast(e)
   offerLast(e)
   putLast(e)
   offerLast(e, time, unit)


   Remove
   removeLast()
   pollLast()
   takeLast()
   pollLast(time, unit)


   Examine
   getLast()
   peekLast()
   not applicable
   not applicable



Like any BlockingQueue, a BlockingDeque is thread safe,
does not permit null elements, and may (or may not) be
capacity-constrained.

A BlockingDeque implementation may be used directly as a FIFO
BlockingQueue. The methods inherited from the
BlockingQueue interface are precisely equivalent to
BlockingDeque methods as indicated in the following table:


Comparison of BlockingQueue and BlockingDeque methods

    BlockingQueue Method
    Equivalent BlockingDeque Method


    Insert


   add(e)
   addLast(e)


   offer(e)
   offerLast(e)


   put(e)
   putLast(e)


   offer(e, time, unit)
   offerLast(e, time, unit)


    Remove


   remove()
   removeFirst()


   poll()
   pollFirst()


   take()
   takeFirst()


   poll(time, unit)
   pollFirst(time, unit)


    Examine


   element()
   getFirst()


   peek()
   peekFirst()



Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
BlockingDeque
happen-before
actions subsequent to the access or removal of that element from
the BlockingDeque in another thread.

This interface is a member of the

Java Collections Framework.

A Queue that additionally supports operations
that wait for the queue to become non-empty when retrieving an
element, and wait for space to become available in the queue when
storing an element.

BlockingQueue methods come in four forms, with different ways
of handling operations that cannot be satisfied immediately, but may be
satisfied at some point in the future:
one throws an exception, the second returns a special value (either
null or false, depending on the operation), the third
blocks the current thread indefinitely until the operation can succeed,
and the fourth blocks for only a given maximum time limit before giving
up.  These methods are summarized in the following table:


Summary of BlockingQueue methods


   Throws exception
   Special value
   Blocks
   Times out


   Insert
   add(e)
   offer(e)
   put(e)
   offer(e, time, unit)


   Remove
   remove()
   poll()
   take()
   poll(time, unit)


   Examine
   element()
   peek()
   not applicable
   not applicable



A BlockingQueue does not accept null elements.
Implementations throw NullPointerException on attempts
to add, put or offer a null.  A
null is used as a sentinel value to indicate failure of
poll operations.

A BlockingQueue may be capacity bounded. At any given
time it may have a remainingCapacity beyond which no
additional elements can be put without blocking.
A BlockingQueue without any intrinsic capacity constraints always
reports a remaining capacity of Integer.MAX_VALUE.

BlockingQueue implementations are designed to be used
primarily for producer-consumer queues, but additionally support
the Collection interface.  So, for example, it is
possible to remove an arbitrary element from a queue using
remove(x). However, such operations are in general
not performed very efficiently, and are intended for only
occasional use, such as when a queued message is cancelled.

BlockingQueue implementations are thread-safe.  All
queuing methods achieve their effects atomically using internal
locks or other forms of concurrency control. However, the
bulk Collection operations addAll,
containsAll, retainAll and removeAll are
not necessarily performed atomically unless specified
otherwise in an implementation. So it is possible, for example, for
addAll(c) to fail (throwing an exception) after adding
only some of the elements in c.

A BlockingQueue does not intrinsically support
any kind of "close" or "shutdown" operation to
indicate that no more items will be added.  The needs and usage of
such features tend to be implementation-dependent. For example, a
common tactic is for producers to insert special
end-of-stream or poison objects, that are
interpreted accordingly when taken by consumers.


Usage example, based on a typical producer-consumer scenario.
Note that a BlockingQueue can safely be used with multiple
producers and multiple consumers.


class Producer implements Runnable {
  private final BlockingQueue queue;
  Producer(BlockingQueue q) { queue = q; }
  public void run() {
    try {
      while (true) { queue.put(produce()); }
    } catch (InterruptedException ex) { ... handle ...}
  }
  Object produce() { ... }
}

class Consumer implements Runnable {
  private final BlockingQueue queue;
  Consumer(BlockingQueue q) { queue = q; }
  public void run() {
    try {
      while (true) { consume(queue.take()); }
    } catch (InterruptedException ex) { ... handle ...}
  }
  void consume(Object x) { ... }
}

class Setup {
  void main() {
    BlockingQueue q = new SomeQueueImplementation();
    Producer p = new Producer(q);
    Consumer c1 = new Consumer(q);
    Consumer c2 = new Consumer(q);
    new Thread(p).start();
    new Thread(c1).start();
    new Thread(c2).start();
  }
}

Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
BlockingQueue
happen-before
actions subsequent to the access or removal of that element from
the BlockingQueue in another thread.

This interface is a member of the

Java Collections Framework.

Exception thrown when a thread tries to wait upon a barrier that is
in a broken state, or which enters the broken state while the thread
is waiting.

A task that returns a result and may throw an exception.
Implementors define a single method with no arguments called
call.

The Callable interface is similar to Runnable, in that both are designed for classes whose
instances are potentially executed by another thread.  A
Runnable, however, does not return a result and cannot
throw a checked exception.

The Executors class contains utility methods to
convert from other common forms to Callable classes.

Exception indicating that the result of a value-producing task,
such as a FutureTask, cannot be retrieved because the task
was cancelled.

A Future that may be explicitly completed (setting its
value and status), and may be used as a CompletionStage,
supporting dependent functions and actions that trigger upon its
completion.

When two or more threads attempt to
complete,
completeExceptionally, or
cancel
a CompletableFuture, only one of them succeeds.

In addition to these and related methods for directly
manipulating status and results, CompletableFuture implements
interface CompletionStage with the following policies:

Actions supplied for dependent completions of
non-async methods may be performed by the thread that
completes the current CompletableFuture, or by any other caller of
a completion method.

All async methods without an explicit Executor
argument are performed using the ForkJoinPool.commonPool()
(unless it does not support a parallelism level of at least two, in
which case, a new Thread is created to run each task).  To simplify
monitoring, debugging, and tracking, all generated asynchronous
tasks are instances of the marker interface CompletableFuture.AsynchronousCompletionTask.

All CompletionStage methods are implemented independently of
other public methods, so the behavior of one method is not impacted
by overrides of others in subclasses.

CompletableFuture also implements Future with the following
policies:

Since (unlike FutureTask) this class has no direct
control over the computation that causes it to be completed,
cancellation is treated as just another form of exceptional
completion.  Method cancel has the same effect as
completeExceptionally(new CancellationException()). Method
isCompletedExceptionally() can be used to determine if a
CompletableFuture completed in any exceptional fashion.

In case of exceptional completion with a CompletionException,
methods get() and get(long, TimeUnit) throw an
ExecutionException with the same cause as held in the
corresponding CompletionException.  To simplify usage in most
contexts, this class also defines methods join() and
getNow(T) that instead throw the CompletionException directly
in these cases.

A marker interface identifying asynchronous tasks produced by
async methods. This may be useful for monitoring,
debugging, and tracking asynchronous activities.

Exception thrown when an error or other exception is encountered
in the course of completing a result or task.

A service that decouples the production of new asynchronous tasks
from the consumption of the results of completed tasks.  Producers
submit tasks for execution. Consumers take
completed tasks and process their results in the order they
complete.  A CompletionService can for example be used to
manage asynchronous I/O, in which tasks that perform reads are
submitted in one part of a program or system, and then acted upon
in a different part of the program when the reads complete,
possibly in a different order than they were requested.

Typically, a CompletionService relies on a separate
Executor to actually execute the tasks, in which case the
CompletionService only manages an internal completion
queue. The ExecutorCompletionService class provides an
implementation of this approach.

Memory consistency effects: Actions in a thread prior to
submitting a task to a CompletionService
happen-before
actions taken by that task, which in turn happen-before
actions following a successful return from the corresponding take().

A stage of a possibly asynchronous computation, that performs an
action or computes a value when another CompletionStage completes.
A stage completes upon termination of its computation, but this may
in turn trigger other dependent stages.  The functionality defined
in this interface takes only a few basic forms, which expand out to
a larger set of methods to capture a range of usage styles:

The computation performed by a stage may be expressed as a
Function, Consumer, or Runnable (using methods with names including
apply, accept, or run, respectively)
depending on whether it requires arguments and/or produces results.
For example, stage.thenApply(x -> square(x)).thenAccept(x ->
System.out.print(x)).thenRun(() -> System.out.println()). An
additional form (compose) applies functions of stages
themselves, rather than their results.

 One stage's execution may be triggered by completion of a
single stage, or both of two stages, or either of two stages.
Dependencies on a single stage are arranged using methods with
prefix then. Those triggered by completion of
both of two stages may combine their results or
effects, using correspondingly named methods. Those triggered by
either of two stages make no guarantees about which of the
results or effects are used for the dependent stage's
computation.

 Dependencies among stages control the triggering of
computations, but do not otherwise guarantee any particular
ordering. Additionally, execution of a new stage's computations may
be arranged in any of three ways: default execution, default
asynchronous execution (using methods with suffix async
that employ the stage's default asynchronous execution facility),
or custom (via a supplied Executor).  The execution
properties of default and async modes are specified by
CompletionStage implementations, not this interface. Methods with
explicit Executor arguments may have arbitrary execution
properties, and might not even support concurrent execution, but
are arranged for processing in a way that accommodates asynchrony.

 Two method forms support processing whether the triggering
stage completed normally or exceptionally: Method whenComplete allows injection of an action
regardless of outcome, otherwise preserving the outcome in its
completion. Method handle additionally allows the
stage to compute a replacement result that may enable further
processing by other dependent stages.  In all other cases, if a
stage's computation terminates abruptly with an (unchecked)
exception or error, then all dependent stages requiring its
completion complete exceptionally as well, with a CompletionException holding the exception as its cause.  If a
stage is dependent on both of two stages, and both
complete exceptionally, then the CompletionException may correspond
to either one of these exceptions.  If a stage is dependent on
either of two others, and only one of them completes
exceptionally, no guarantees are made about whether the dependent
stage completes normally or exceptionally. In the case of method
whenComplete, when the supplied action itself encounters an
exception, then the stage exceptionally completes with this
exception if not already completed exceptionally.



All methods adhere to the above triggering, execution, and
exceptional completion specifications (which are not repeated in
individual method specifications). Additionally, while arguments
used to pass a completion result (that is, for parameters of type
T) for methods accepting them may be null, passing a null
value for any other parameter will result in a NullPointerException being thrown.

This interface does not define methods for initially creating,
forcibly completing normally or exceptionally, probing completion
status or results, or awaiting completion of a stage.
Implementations of CompletionStage may provide means of achieving
such effects, as appropriate.  Method toCompletableFuture()
enables interoperability among different implementations of this
interface by providing a common conversion type.

A hash table supporting full concurrency of retrievals and
high expected concurrency for updates. This class obeys the
same functional specification as Hashtable, and
includes versions of methods corresponding to each method of
Hashtable. However, even though all operations are
thread-safe, retrieval operations do not entail locking,
and there is not any support for locking the entire table
in a way that prevents all access.  This class is fully
interoperable with Hashtable in programs that rely on its
thread safety but not on its synchronization details.

Retrieval operations (including get) generally do not
block, so may overlap with update operations (including put
and remove). Retrievals reflect the results of the most
recently completed update operations holding upon their
onset. (More formally, an update operation for a given key bears a
happens-before relation with any (non-null) retrieval for
that key reporting the updated value.)  For aggregate operations
such as putAll and clear, concurrent retrievals may
reflect insertion or removal of only some entries.  Similarly,
Iterators, Spliterators and Enumerations return elements reflecting the
state of the hash table at some point at or since the creation of the
iterator/enumeration.  They do not throw ConcurrentModificationException.
However, iterators are designed to be used by only one thread at a time.
Bear in mind that the results of aggregate status methods including
size, isEmpty, and containsValue are typically
useful only when a map is not undergoing concurrent updates in other threads.
Otherwise the results of these methods reflect transient states
that may be adequate for monitoring or estimation purposes, but not
for program control.

The table is dynamically expanded when there are too many
collisions (i.e., keys that have distinct hash codes but fall into
the same slot modulo the table size), with the expected average
effect of maintaining roughly two bins per mapping (corresponding
to a 0.75 load factor threshold for resizing). There may be much
variance around this average as mappings are added and removed, but
overall, this maintains a commonly accepted time/space tradeoff for
hash tables.  However, resizing this or any other kind of hash
table may be a relatively slow operation. When possible, it is a
good idea to provide a size estimate as an optional initialCapacity constructor argument. An additional optional
loadFactor constructor argument provides a further means of
customizing initial table capacity by specifying the table density
to be used in calculating the amount of space to allocate for the
given number of elements.  Also, for compatibility with previous
versions of this class, constructors may optionally specify an
expected concurrencyLevel as an additional hint for
internal sizing.  Note that using many keys with exactly the same
hashCode() is a sure way to slow down performance of any
hash table. To ameliorate impact, when keys are Comparable,
this class may use comparison order among keys to help break ties.

A Set projection of a ConcurrentHashMap may be created
(using newKeySet() or newKeySet(int)), or viewed
(using keySet(Object) when only keys are of interest, and the
mapped values are (perhaps transiently) not used or all take the
same mapping value.

A ConcurrentHashMap can be used as scalable frequency map (a
form of histogram or multiset) by using LongAdder values and initializing via
computeIfAbsent. For example, to add a count
to a ConcurrentHashMap<String,LongAdder> freqs, you can use
freqs.computeIfAbsent(k -> new LongAdder()).increment();

This class and its views and iterators implement all of the
optional methods of the Map and Iterator
interfaces.

Like Hashtable but unlike HashMap, this class
does not allow null to be used as a key or value.

ConcurrentHashMaps support a set of sequential and parallel bulk
operations that, unlike most Stream methods, are designed
to be safely, and often sensibly, applied even with maps that are
being concurrently updated by other threads; for example, when
computing a snapshot summary of the values in a shared registry.
There are three kinds of operation, each with four forms, accepting
functions with Keys, Values, Entries, and (Key, Value) arguments
and/or return values. Because the elements of a ConcurrentHashMap
are not ordered in any particular way, and may be processed in
different orders in different parallel executions, the correctness
of supplied functions should not depend on any ordering, or on any
other objects or values that may transiently change while
computation is in progress; and except for forEach actions, should
ideally be side-effect-free. Bulk operations on Map.Entry
objects do not support method setValue.


 forEach: Perform a given action on each element.
A variant form applies a given transformation on each element
before performing the action.

 search: Return the first available non-null result of
applying a given function on each element; skipping further
search when a result is found.

 reduce: Accumulate each element.  The supplied reduction
function cannot rely on ordering (more formally, it should be
both associative and commutative).  There are five variants:



 Plain reductions. (There is not a form of this method for
(key, value) function arguments since there is no corresponding
return type.)

 Mapped reductions that accumulate the results of a given
function applied to each element.

 Reductions to scalar doubles, longs, and ints, using a
given basis value.





These bulk operations accept a parallelismThreshold
argument. Methods proceed sequentially if the current map size is
estimated to be less than the given threshold. Using a value of
Long.MAX_VALUE suppresses all parallelism.  Using a value
of 1 results in maximal parallelism by partitioning into
enough subtasks to fully utilize the ForkJoinPool.commonPool() that is used for all parallel
computations. Normally, you would initially choose one of these
extreme values, and then measure performance of using in-between
values that trade off overhead versus throughput.

The concurrency properties of bulk operations follow
from those of ConcurrentHashMap: Any non-null result returned
from get(key) and related access methods bears a
happens-before relation with the associated insertion or
update.  The result of any bulk operation reflects the
composition of these per-element relations (but is not
necessarily atomic with respect to the map as a whole unless it
is somehow known to be quiescent).  Conversely, because keys
and values in the map are never null, null serves as a reliable
atomic indicator of the current lack of any result.  To
maintain this property, null serves as an implicit basis for
all non-scalar reduction operations. For the double, long, and
int versions, the basis should be one that, when combined with
any other value, returns that other value (more formally, it
should be the identity element for the reduction). Most common
reductions have these properties; for example, computing a sum
with basis 0 or a minimum with basis MAX_VALUE.

Search and transformation functions provided as arguments
should similarly return null to indicate the lack of any result
(in which case it is not used). In the case of mapped
reductions, this also enables transformations to serve as
filters, returning null (or, in the case of primitive
specializations, the identity basis) if the element should not
be combined. You can create compound transformations and
filterings by composing them yourself under this "null means
there is nothing there now" rule before using them in search or
reduce operations.

Methods accepting and/or returning Entry arguments maintain
key-value associations. They may be useful for example when
finding the key for the greatest value. Note that "plain" Entry
arguments can be supplied using new
AbstractMap.SimpleEntry(k,v).

Bulk operations may complete abruptly, throwing an
exception encountered in the application of a supplied
function. Bear in mind when handling such exceptions that other
concurrently executing functions could also have thrown
exceptions, or would have done so if the first exception had
not occurred.

Speedups for parallel compared to sequential forms are common
but not guaranteed.  Parallel operations involving brief functions
on small maps may execute more slowly than sequential forms if the
underlying work to parallelize the computation is more expensive
than the computation itself.  Similarly, parallelization may not
lead to much actual parallelism if all processors are busy
performing unrelated tasks.

All arguments to all task methods must be non-null.

This class is a member of the

Java Collections Framework.

A view of a ConcurrentHashMap as a Set of keys, in
which additions may optionally be enabled by mapping to a
common value.  This class cannot be directly instantiated.
See keySet(),
keySet(V),
newKeySet(),
newKeySet(int).

An unbounded concurrent java.util.deque based on linked nodes.
Concurrent insertion, removal, and access operations execute safely
across multiple threads.
A ConcurrentLinkedDeque is an appropriate choice when
many threads will share access to a common collection.
Like most other concurrent collection implementations, this class
does not permit the use of null elements.

Iterators and spliterators are
weakly consistent.

Beware that, unlike in most collections, the size method
is NOT a constant-time operation. Because of the
asynchronous nature of these deques, determining the current number
of elements requires a traversal of the elements, and so may report
inaccurate results if this collection is modified during traversal.
Additionally, the bulk operations addAll,
removeAll, retainAll, containsAll,
equals, and toArray are not guaranteed
to be performed atomically. For example, an iterator operating
concurrently with an addAll operation might view only some
of the added elements.

This class and its iterator implement all of the optional
methods of the Deque and Iterator interfaces.

Memory consistency effects: As with other concurrent collections,
actions in a thread prior to placing an object into a
ConcurrentLinkedDeque
happen-before
actions subsequent to the access or removal of that element from
the ConcurrentLinkedDeque in another thread.

This class is a member of the

Java Collections Framework.

An unbounded thread-safe java.util.queue based on linked nodes.
This queue orders elements FIFO (first-in-first-out).
The head of the queue is that element that has been on the
queue the longest time.
The tail of the queue is that element that has been on the
queue the shortest time. New elements
are inserted at the tail of the queue, and the queue retrieval
operations obtain elements at the head of the queue.
A ConcurrentLinkedQueue is an appropriate choice when
many threads will share access to a common collection.
Like most other concurrent collection implementations, this class
does not permit the use of null elements.

This implementation employs an efficient non-blocking
algorithm based on one described in  Simple,
Fast, and Practical Non-Blocking and Blocking Concurrent Queue
Algorithms by Maged M. Michael and Michael L. Scott.

Iterators are weakly consistent, returning elements
reflecting the state of the queue at some point at or since the
creation of the iterator.  They do not throw ConcurrentModificationException, and may proceed concurrently
with other operations.  Elements contained in the queue since the creation
of the iterator will be returned exactly once.

Beware that, unlike in most collections, the size method
is NOT a constant-time operation. Because of the
asynchronous nature of these queues, determining the current number
of elements requires a traversal of the elements, and so may report
inaccurate results if this collection is modified during traversal.
Additionally, the bulk operations addAll,
removeAll, retainAll, containsAll,
equals, and toArray are not guaranteed
to be performed atomically. For example, an iterator operating
concurrently with an addAll operation might view only some
of the added elements.

This class and its iterator implement all of the optional
methods of the Queue and Iterator interfaces.

Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
ConcurrentLinkedQueue
happen-before
actions subsequent to the access or removal of that element from
the ConcurrentLinkedQueue in another thread.

This class is a member of the

Java Collections Framework.

A Map providing thread safety and atomicity
guarantees.

Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
ConcurrentMap as a key or value
happen-before
actions subsequent to the access or removal of that object from
the ConcurrentMap in another thread.

This interface is a member of the

Java Collections Framework.

A ConcurrentMap supporting NavigableMap operations,
and recursively so for its navigable sub-maps.

This interface is a member of the

Java Collections Framework.

A scalable concurrent ConcurrentNavigableMap implementation.
The map is sorted according to the java.lang.natural
ordering of its keys, or by a Comparator provided at map
creation time, depending on which constructor is used.

This class implements a concurrent variant of SkipLists
providing expected average log(n) time cost for the
containsKey, get, put and
remove operations and their variants.  Insertion, removal,
update, and access operations safely execute concurrently by
multiple threads.

Iterators and spliterators are
weakly consistent.

Ascending key ordered views and their iterators are faster than
descending ones.

All Map.Entry pairs returned by methods in this class
and its views represent snapshots of mappings at the time they were
produced. They do not support the Entry.setValue
method. (Note however that it is possible to change mappings in the
associated map using put, putIfAbsent, or
replace, depending on exactly which effect you need.)

Beware that, unlike in most collections, the size
method is not a constant-time operation. Because of the
asynchronous nature of these maps, determining the current number
of elements requires a traversal of the elements, and so may report
inaccurate results if this collection is modified during traversal.
Additionally, the bulk operations putAll, equals,
toArray, containsValue, and clear are
not guaranteed to be performed atomically. For example, an
iterator operating concurrently with a putAll operation
might view only some of the added elements.

This class and its views and iterators implement all of the
optional methods of the Map and Iterator
interfaces. Like most other concurrent collections, this class does
not permit the use of null keys or values because some
null return values cannot be reliably distinguished from the absence of
elements.

This class is a member of the

Java Collections Framework.

A scalable concurrent NavigableSet implementation based on
a ConcurrentSkipListMap.  The elements of the set are kept
sorted according to their java.lang.natural ordering,
or by a Comparator provided at set creation time, depending
on which constructor is used.

This implementation provides expected average log(n) time
cost for the contains, add, and remove
operations and their variants.  Insertion, removal, and access
operations safely execute concurrently by multiple threads.

Iterators and spliterators are
weakly consistent.

Ascending ordered views and their iterators are faster than
descending ones.

Beware that, unlike in most collections, the size
method is not a constant-time operation. Because of the
asynchronous nature of these sets, determining the current number
of elements requires a traversal of the elements, and so may report
inaccurate results if this collection is modified during traversal.
Additionally, the bulk operations addAll,
removeAll, retainAll, containsAll,
equals, and toArray are not guaranteed
to be performed atomically. For example, an iterator operating
concurrently with an addAll operation might view only some
of the added elements.

This class and its iterators implement all of the
optional methods of the Set and Iterator
interfaces. Like most other concurrent collection implementations,
this class does not permit the use of null elements,
because null arguments and return values cannot be reliably
distinguished from the absence of elements.

This class is a member of the

Java Collections Framework.

A thread-safe variant of ArrayList in which all mutative
operations (add, set, and so on) are implemented by
making a fresh copy of the underlying array.

This is ordinarily too costly, but may be more efficient
than alternatives when traversal operations vastly outnumber
mutations, and is useful when you cannot or don't want to
synchronize traversals, yet need to preclude interference among
concurrent threads.  The "snapshot" style iterator method uses a
reference to the state of the array at the point that the iterator
was created. This array never changes during the lifetime of the
iterator, so interference is impossible and the iterator is
guaranteed not to throw ConcurrentModificationException.
The iterator will not reflect additions, removals, or changes to
the list since the iterator was created.  Element-changing
operations on iterators themselves (remove, set, and
add) are not supported. These methods throw
UnsupportedOperationException.

All elements are permitted, including null.

Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
CopyOnWriteArrayList
happen-before
actions subsequent to the access or removal of that element from
the CopyOnWriteArrayList in another thread.

This class is a member of the

Java Collections Framework.

A Set that uses an internal CopyOnWriteArrayList
for all of its operations.  Thus, it shares the same basic properties:

 It is best suited for applications in which set sizes generally
      stay small, read-only operations
      vastly outnumber mutative operations, and you need
      to prevent interference among threads during traversal.
 It is thread-safe.
 Mutative operations (add, set, remove, etc.)
     are expensive since they usually entail copying the entire underlying
     array.
 Iterators do not support the mutative remove operation.
 Traversal via iterators is fast and cannot encounter
     interference from other threads. Iterators rely on
     unchanging snapshots of the array at the time the iterators were
     constructed.


Sample Usage. The following code sketch uses a
copy-on-write set to maintain a set of Handler objects that
perform some action upon state updates.



class Handler { void handle(); ... }

class X {
  private final CopyOnWriteArraySet<Handler> handlers
    = new CopyOnWriteArraySet<Handler>();
  public void addHandler(Handler h) { handlers.add(h); }

  private long internalState;
  private synchronized void changeState() { internalState = ...; }

  public void update() {
    changeState();
    for (Handler handler : handlers)
      handler.handle();
  }
}

This class is a member of the

Java Collections Framework.

for (int i = 0; i < N; +i) // create and start threads
  new Thread(new Worker(startSignal, doneSignal)).start();

doSomethingElse();            // don't let run yet
startSignal.countDown();      // let all threads proceed
doSomethingElse();
doneSignal.await();           // wait for all to finish

for (int i = 0; i < N; +i) // create and start threads
  e.execute(new WorkerRunnable(doneSignal, i));

doneSignal.await();           // wait for all to finish

A synchronization aid that allows one or more threads to wait until
a set of operations being performed in other threads completes.

A CountDownLatch is initialized with a given count.
The await methods block until the current count reaches
zero due to invocations of the countDown() method, after which
all waiting threads are released and any subsequent invocations of
await return immediately.  This is a one-shot phenomenon
-- the count cannot be reset.  If you need a version that resets the
count, consider using a CyclicBarrier.

A CountDownLatch is a versatile synchronization tool
and can be used for a number of purposes.  A
CountDownLatch initialized with a count of one serves as a
simple on/off latch, or gate: all threads invoking await
wait at the gate until it is opened by a thread invoking countDown().  A CountDownLatch initialized to N
can be used to make one thread wait until N threads have
completed some action, or some action has been completed N times.

A useful property of a CountDownLatch is that it
doesn't require that threads calling countDown wait for
the count to reach zero before proceeding, it simply prevents any
thread from proceeding past an await until all
threads could pass.

Sample usage: Here is a pair of classes in which a group
of worker threads use two countdown latches:

The first is a start signal that prevents any worker from proceeding
until the driver is ready for them to proceed;
The second is a completion signal that allows the driver to wait
until all workers have completed.




class Driver { // ...
  void main() throws InterruptedException {
    CountDownLatch startSignal = new CountDownLatch(1);
    CountDownLatch doneSignal = new CountDownLatch(N);

    for (int i = 0; i < N; +i) // create and start threads
      new Thread(new Worker(startSignal, doneSignal)).start();

    doSomethingElse();            // don't let run yet
    startSignal.countDown();      // let all threads proceed
    doSomethingElse();
    doneSignal.await();           // wait for all to finish
  }
}

class Worker implements Runnable {
  private final CountDownLatch startSignal;
  private final CountDownLatch doneSignal;
  Worker(CountDownLatch startSignal, CountDownLatch doneSignal) {
    this.startSignal = startSignal;
    this.doneSignal = doneSignal;
  }
  public void run() {
    try {
      startSignal.await();
      doWork();
      doneSignal.countDown();
    } catch (InterruptedException ex) {} // return;
  }

  void doWork() { ... }
}

Another typical usage would be to divide a problem into N parts,
describe each part with a Runnable that executes that portion and
counts down on the latch, and queue all the Runnables to an
Executor.  When all sub-parts are complete, the coordinating thread
will be able to pass through await. (When threads must repeatedly
count down in this way, instead use a CyclicBarrier.)



class Driver2 { // ...
  void main() throws InterruptedException {
    CountDownLatch doneSignal = new CountDownLatch(N);
    Executor e = ...

    for (int i = 0; i < N; +i) // create and start threads
      e.execute(new WorkerRunnable(doneSignal, i));

    doneSignal.await();           // wait for all to finish
  }
}

class WorkerRunnable implements Runnable {
  private final CountDownLatch doneSignal;
  private final int i;
  WorkerRunnable(CountDownLatch doneSignal, int i) {
    this.doneSignal = doneSignal;
    this.i = i;
  }
  public void run() {
    try {
      doWork(i);
      doneSignal.countDown();
    } catch (InterruptedException ex) {} // return;
  }

  void doWork() { ... }
}

Memory consistency effects: Until the count reaches
zero, actions in a thread prior to calling
countDown()
happen-before
actions following a successful return from a corresponding
await() in another thread.

A ForkJoinTask with a completion action performed when
triggered and there are no remaining pending actions.
CountedCompleters are in general more robust in the
presence of subtask stalls and blockage than are other forms of
ForkJoinTasks, but are less intuitive to program.  Uses of
CountedCompleter are similar to those of other completion based
components (such as CompletionHandler)
except that multiple pending completions may be necessary
to trigger the completion action onCompletion(CountedCompleter),
not just one.
Unless initialized otherwise, the pending
count starts at zero, but may be (atomically) changed using
methods setPendingCount(int), addToPendingCount(int), and
compareAndSetPendingCount(int, int). Upon invocation of tryComplete(), if the pending action count is nonzero, it is
decremented; otherwise, the completion action is performed, and if
this completer itself has a completer, the process is continued
with its completer.  As is the case with related synchronization
components such as Phaser and
Semaphore, these methods
affect only internal counts; they do not establish any further
internal bookkeeping. In particular, the identities of pending
tasks are not maintained. As illustrated below, you can create
subclasses that do record some or all pending tasks or their
results when needed.  As illustrated below, utility methods
supporting customization of completion traversals are also
provided. However, because CountedCompleters provide only basic
synchronization mechanisms, it may be useful to create further
abstract subclasses that maintain linkages, fields, and additional
support methods appropriate for a set of related usages.

A concrete CountedCompleter class must define method compute(), that should in most cases (as illustrated below), invoke
tryComplete() once before returning. The class may also
optionally override method onCompletion(CountedCompleter)
to perform an action upon normal completion, and method
onExceptionalCompletion(Throwable, CountedCompleter) to
perform an action upon any exception.

CountedCompleters most often do not bear results, in which case
they are normally declared as CountedCompleter<Void>, and
will always return null as a result value.  In other cases,
you should override method getRawResult() to provide a
result from join(), invoke(), and related methods.  In
general, this method should return the value of a field (or a
function of one or more fields) of the CountedCompleter object that
holds the result upon completion. Method setRawResult(T) by
default plays no role in CountedCompleters.  It is possible, but
rarely applicable, to override this method to maintain other
objects or fields holding result data.

A CountedCompleter that does not itself have a completer (i.e.,
one for which getCompleter() returns null) can be
used as a regular ForkJoinTask with this added functionality.
However, any completer that in turn has another completer serves
only as an internal helper for other computations, so its own task
status (as reported in methods such as ForkJoinTask.isDone())
is arbitrary; this status changes only upon explicit invocations of
complete(T), ForkJoinTask.cancel(boolean),
ForkJoinTask.completeExceptionally(Throwable) or upon
exceptional completion of method compute. Upon any
exceptional completion, the exception may be relayed to a task's
completer (and its completer, and so on), if one exists and it has
not otherwise already completed. Similarly, cancelling an internal
CountedCompleter has only a local effect on that completer, so is
not often useful.

Sample Usages.

Parallel recursive decomposition. CountedCompleters may
be arranged in trees similar to those often used with RecursiveActions, although the constructions involved in setting
them up typically vary. Here, the completer of each task is its
parent in the computation tree. Even though they entail a bit more
bookkeeping, CountedCompleters may be better choices when applying
a possibly time-consuming operation (that cannot be further
subdivided) to each element of an array or collection; especially
when the operation takes a significantly different amount of time
to complete for some elements than others, either because of
intrinsic variation (for example I/O) or auxiliary effects such as
garbage collection.  Because CountedCompleters provide their own
continuations, other threads need not block waiting to perform
them.

For example, here is an initial version of a class that uses
divide-by-two recursive decomposition to divide work into single
pieces (leaf tasks). Even when work is split into individual calls,
tree-based techniques are usually preferable to directly forking
leaf tasks, because they reduce inter-thread communication and
improve load balancing. In the recursive case, the second of each
pair of subtasks to finish triggers completion of its parent
(because no result combination is performed, the default no-op
implementation of method onCompletion is not overridden).
A static utility method sets up the base task and invokes it
(here, implicitly using the ForkJoinPool.commonPool()).



class MyOperation<E> { void apply(E e) { ... }  }

class ForEach<E> extends CountedCompleter<Void> {

  public static <E> void forEach(E[] array, MyOperation<E> op) {
    new ForEach<E>(null, array, op, 0, array.length).invoke();
  }

  final E[] array; final MyOperation<E> op; final int lo, hi;
  ForEach(CountedCompleter<?> p, E[] array, MyOperation<E> op, int lo, int hi) {
    super(p);
    this.array = array; this.op = op; this.lo = lo; this.hi = hi;
  }

  public void compute() { // version 1
    if (hi - lo >= 2) {
      int mid = (lo  hi) >>> 1;
      setPendingCount(2); // must set pending count before fork
      new ForEach(this, array, op, mid, hi).fork(); // right child
      new ForEach(this, array, op, lo, mid).fork(); // left child
    }
    else if (hi > lo)
      op.apply(array[lo]);
    tryComplete();
  }
}

This design can be improved by noticing that in the recursive case,
the task has nothing to do after forking its right task, so can
directly invoke its left task before returning. (This is an analog
of tail recursion removal.)  Also, because the task returns upon
executing its left task (rather than falling through to invoke
tryComplete) the pending count is set to one:



class ForEach<E> ...
  public void compute() { // version 2
    if (hi - lo >= 2) {
      int mid = (lo  hi) >>> 1;
      setPendingCount(1); // only one pending
      new ForEach(this, array, op, mid, hi).fork(); // right child
      new ForEach(this, array, op, lo, mid).compute(); // direct invoke
    }
    else {
      if (hi > lo)
        op.apply(array[lo]);
      tryComplete();
    }
  }

As a further improvement, notice that the left task need not even exist.
Instead of creating a new one, we can iterate using the original task,
and add a pending count for each fork.  Additionally, because no task
in this tree implements an onCompletion(CountedCompleter) method,
tryComplete() can be replaced with propagateCompletion().



class ForEach<E> ...
  public void compute() { // version 3
    int l = lo,  h = hi;
    while (h - l >= 2) {
      int mid = (l  h) >>> 1;
      addToPendingCount(1);
      new ForEach(this, array, op, mid, h).fork(); // right child
      h = mid;
    }
    if (h > l)
      op.apply(array[l]);
    propagateCompletion();
  }

Additional improvements of such classes might entail precomputing
pending counts so that they can be established in constructors,
specializing classes for leaf steps, subdividing by say, four,
instead of two per iteration, and using an adaptive threshold
instead of always subdividing down to single elements.

Searching. A tree of CountedCompleters can search for a
value or property in different parts of a data structure, and
report a result in an AtomicReference as
soon as one is found. The others can poll the result to avoid
unnecessary work. (You could additionally cancel other tasks, but it is usually simpler and more efficient
to just let them notice that the result is set and if so skip
further processing.)  Illustrating again with an array using full
partitioning (again, in practice, leaf tasks will almost always
process more than one element):



class Searcher<E> extends CountedCompleter<E> {
  final E[] array; final AtomicReference<E> result; final int lo, hi;
  Searcher(CountedCompleter<?> p, E[] array, AtomicReference<E> result, int lo, int hi) {
    super(p);
    this.array = array; this.result = result; this.lo = lo; this.hi = hi;
  }
  public E getRawResult() { return result.get(); }
  public void compute() { // similar to ForEach version 3
    int l = lo,  h = hi;
    while (result.get() == null && h >= l) {
      if (h - l >= 2) {
        int mid = (l  h) >>> 1;
        addToPendingCount(1);
        new Searcher(this, array, result, mid, h).fork();
        h = mid;
      }
      else {
        E x = array[l];
        if (matches(x) && result.compareAndSet(null, x))
          quietlyCompleteRoot(); // root task is now joinable
        break;
      }
    }
    tryComplete(); // normally complete whether or not found
  }
  boolean matches(E e) { ... } // return true if found

  public static <E> E search(E[] array) {
      return new Searcher<E>(null, array, new AtomicReference<E>(), 0, array.length).invoke();
  }
}

In this example, as well as others in which tasks have no other
effects except to compareAndSet a common result, the trailing
unconditional invocation of tryComplete could be made
conditional (if (result.get() == null) tryComplete();)
because no further bookkeeping is required to manage completions
once the root task completes.

Recording subtasks. CountedCompleter tasks that combine
results of multiple subtasks usually need to access these results
in method onCompletion(CountedCompleter). As illustrated in the following
class (that performs a simplified form of map-reduce where mappings
and reductions are all of type E), one way to do this in
divide and conquer designs is to have each subtask record its
sibling, so that it can be accessed in method onCompletion.
This technique applies to reductions in which the order of
combining left and right results does not matter; ordered
reductions require explicit left/right designations.  Variants of
other streamlinings seen in the above examples may also apply.



class MyMapper<E> { E apply(E v) {  ...  } }
class MyReducer<E> { E apply(E x, E y) {  ...  } }
class MapReducer<E> extends CountedCompleter<E> {
  final E[] array; final MyMapper<E> mapper;
  final MyReducer<E> reducer; final int lo, hi;
  MapReducer<E> sibling;
  E result;
  MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
             MyReducer<E> reducer, int lo, int hi) {
    super(p);
    this.array = array; this.mapper = mapper;
    this.reducer = reducer; this.lo = lo; this.hi = hi;
  }
  public void compute() {
    if (hi - lo >= 2) {
      int mid = (lo  hi) >>> 1;
      MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
      MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
      left.sibling = right;
      right.sibling = left;
      setPendingCount(1); // only right is pending
      right.fork();
      left.compute();     // directly execute left
    }
    else {
      if (hi > lo)
          result = mapper.apply(array[lo]);
      tryComplete();
    }
  }
  public void onCompletion(CountedCompleter<?> caller) {
    if (caller != this) {
      MapReducer<E> child = (MapReducer<E>)caller;
      MapReducer<E> sib = child.sibling;
      if (sib == null || sib.result == null)
        result = child.result;
      else
        result = reducer.apply(child.result, sib.result);
    }
  }
  public E getRawResult() { return result; }

  public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
    return new MapReducer<E>(null, array, mapper, reducer,
                             0, array.length).invoke();
  }
}

Here, method onCompletion takes a form common to many
completion designs that combine results. This callback-style method
is triggered once per task, in either of the two different contexts
in which the pending count is, or becomes, zero: (1) by a task
itself, if its pending count is zero upon invocation of tryComplete, or (2) by any of its subtasks when they complete and
decrement the pending count to zero. The caller argument
distinguishes cases.  Most often, when the caller is this,
no action is necessary. Otherwise the caller argument can be used
(usually via a cast) to supply a value (and/or links to other
values) to be combined.  Assuming proper use of pending counts, the
actions inside onCompletion occur (once) upon completion of
a task and its subtasks. No additional synchronization is required
within this method to ensure thread safety of accesses to fields of
this task or other completed tasks.

Completion Traversals. If using onCompletion to
process completions is inapplicable or inconvenient, you can use
methods firstComplete() and nextComplete() to create
custom traversals.  For example, to define a MapReducer that only
splits out right-hand tasks in the form of the third ForEach
example, the completions must cooperatively reduce along
unexhausted subtask links, which can be done as follows:



class MapReducer<E> extends CountedCompleter<E> { // version 2
  final E[] array; final MyMapper<E> mapper;
  final MyReducer<E> reducer; final int lo, hi;
  MapReducer<E> forks, next; // record subtask forks in list
  E result;
  MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
             MyReducer<E> reducer, int lo, int hi, MapReducer<E> next) {
    super(p);
    this.array = array; this.mapper = mapper;
    this.reducer = reducer; this.lo = lo; this.hi = hi;
    this.next = next;
  }
  public void compute() {
    int l = lo,  h = hi;
    while (h - l >= 2) {
      int mid = (l  h) >>> 1;
      addToPendingCount(1);
      (forks = new MapReducer(this, array, mapper, reducer, mid, h, forks)).fork();
      h = mid;
    }
    if (h > l)
      result = mapper.apply(array[l]);
    // process completions by reducing along and advancing subtask links
    for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
      for (MapReducer t = (MapReducer)c, s = t.forks;  s != null; s = t.forks = s.next)
        t.result = reducer.apply(t.result, s.result);
    }
  }
  public E getRawResult() { return result; }

  public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
    return new MapReducer<E>(null, array, mapper, reducer,
                             0, array.length, null).invoke();
  }
}

Triggers. Some CountedCompleters are themselves never
forked, but instead serve as bits of plumbing in other designs;
including those in which the completion of one or more async tasks
triggers another async task. For example:



class HeaderBuilder extends CountedCompleter<...> { ... }
class BodyBuilder extends CountedCompleter<...> { ... }
class PacketSender extends CountedCompleter<...> {
  PacketSender(...) { super(null, 1); ... } // trigger on second completion
  public void compute() { } // never called
  public void onCompletion(CountedCompleter<?> caller) { sendPacket(); }
}
// sample use:
PacketSender p = new PacketSender();
new HeaderBuilder(p, ...).fork();
new BodyBuilder(p, ...).fork();

    try {
      barrier.await();
    } catch (InterruptedException ex) {
      return;
    } catch (BrokenBarrierException ex) {
      return;
    }
  }
}

List<Thread> threads = new ArrayList<Thread>(N);
for (int i = 0; i < N; i++) {
  Thread thread = new Thread(new Worker(i));
  threads.add(thread);
  thread.start();
}

// wait until done
for (Thread thread : threads)
  thread.join();

A synchronization aid that allows a set of threads to all wait for
each other to reach a common barrier point.  CyclicBarriers are
useful in programs involving a fixed sized party of threads that
must occasionally wait for each other. The barrier is called
cyclic because it can be re-used after the waiting threads
are released.

A CyclicBarrier supports an optional Runnable command
that is run once per barrier point, after the last thread in the party
arrives, but before any threads are released.
This barrier action is useful
for updating shared-state before any of the parties continue.

Sample usage: Here is an example of using a barrier in a
parallel decomposition design:



class Solver {
  final int N;
  final float[][] data;
  final CyclicBarrier barrier;

  class Worker implements Runnable {
    int myRow;
    Worker(int row) { myRow = row; }
    public void run() {
      while (!done()) {
        processRow(myRow);

        try {
          barrier.await();
        } catch (InterruptedException ex) {
          return;
        } catch (BrokenBarrierException ex) {
          return;
        }
      }
    }
  }

  public Solver(float[][] matrix) {
    data = matrix;
    N = matrix.length;
    Runnable barrierAction =
      new Runnable() { public void run() { mergeRows(...); }};
    barrier = new CyclicBarrier(N, barrierAction);

    List<Thread> threads = new ArrayList<Thread>(N);
    for (int i = 0; i < N; i++) {
      Thread thread = new Thread(new Worker(i));
      threads.add(thread);
      thread.start();
    }

    // wait until done
    for (Thread thread : threads)
      thread.join();
  }
}

Here, each worker thread processes a row of the matrix then waits at the
barrier until all rows have been processed. When all rows are processed
the supplied Runnable barrier action is executed and merges the
rows. If the merger
determines that a solution has been found then done() will return
true and each worker will terminate.

If the barrier action does not rely on the parties being suspended when
it is executed, then any of the threads in the party could execute that
action when it is released. To facilitate this, each invocation of
await() returns the arrival index of that thread at the barrier.
You can then choose which thread should execute the barrier action, for
example:


if (barrier.await() == 0) {
  // log the completion of this iteration
}

The CyclicBarrier uses an all-or-none breakage model
for failed synchronization attempts: If a thread leaves a barrier
point prematurely because of interruption, failure, or timeout, all
other threads waiting at that barrier point will also leave
abnormally via BrokenBarrierException (or
InterruptedException if they too were interrupted at about
the same time).

Memory consistency effects: Actions in a thread prior to calling
await()
happen-before
actions that are part of the barrier action, which in turn
happen-before actions following a successful return from the
corresponding await() in other threads.

A mix-in style interface for marking objects that should be
acted upon after a given delay.

An implementation of this interface must define a
compareTo method that provides an ordering consistent with
its getDelay method.

An unbounded java.util.concurrent.blocking queue of
Delayed elements, in which an element can only be taken
when its delay has expired.  The head of the queue is that
Delayed element whose delay expired furthest in the
past.  If no delay has expired there is no head and poll
will return null. Expiration occurs when an element's
getDelay(TimeUnit.NANOSECONDS) method returns a value less
than or equal to zero.  Even though unexpired elements cannot be
removed using take or poll, they are otherwise
treated as normal elements. For example, the size method
returns the count of both expired and unexpired elements.
This queue does not permit null elements.

This class and its iterator implement all of the
optional methods of the Collection and Iterator interfaces.  The Iterator provided in method iterator() is not guaranteed to traverse the elements of
the DelayQueue in any particular order.

This class is a member of the

Java Collections Framework.

A synchronization point at which threads can pair and swap elements
within pairs.  Each thread presents some object on entry to the
exchange method, matches with a partner thread,
and receives its partner's object on return.  An Exchanger may be
viewed as a bidirectional form of a SynchronousQueue.
Exchangers may be useful in applications such as genetic algorithms
and pipeline designs.

Sample Usage:
Here are the highlights of a class that uses an Exchanger
to swap buffers between threads so that the thread filling the
buffer gets a freshly emptied one when it needs it, handing off the
filled one to the thread emptying the buffer.


class FillAndEmpty {
  Exchanger<DataBuffer> exchanger = new Exchanger<DataBuffer>();
  DataBuffer initialEmptyBuffer = ... a made-up type
  DataBuffer initialFullBuffer = ...

  class FillingLoop implements Runnable {
    public void run() {
      DataBuffer currentBuffer = initialEmptyBuffer;
      try {
        while (currentBuffer != null) {
          addToBuffer(currentBuffer);
          if (currentBuffer.isFull())
            currentBuffer = exchanger.exchange(currentBuffer);
        }
      } catch (InterruptedException ex) { ... handle ... }
    }
  }

  class EmptyingLoop implements Runnable {
    public void run() {
      DataBuffer currentBuffer = initialFullBuffer;
      try {
        while (currentBuffer != null) {
          takeFromBuffer(currentBuffer);
          if (currentBuffer.isEmpty())
            currentBuffer = exchanger.exchange(currentBuffer);
        }
      } catch (InterruptedException ex) { ... handle ...}
    }
  }

  void start() {
    new Thread(new FillingLoop()).start();
    new Thread(new EmptyingLoop()).start();
  }
}

Memory consistency effects: For each pair of threads that
successfully exchange objects via an Exchanger, actions
prior to the exchange() in each thread
happen-before
those subsequent to a return from the corresponding exchange()
in the other thread.

Exception thrown when attempting to retrieve the result of a task
that aborted by throwing an exception. This exception can be
inspected using the Throwable.getCause() method.

An object that executes submitted Runnable tasks. This
interface provides a way of decoupling task submission from the
mechanics of how each task will be run, including details of thread
use, scheduling, etc.  An Executor is normally used
instead of explicitly creating threads. For example, rather than
invoking new Thread(new(RunnableTask())).start() for each
of a set of tasks, you might use:



Executor executor = anExecutor;
executor.execute(new RunnableTask1());
executor.execute(new RunnableTask2());
...

However, the Executor interface does not strictly
require that execution be asynchronous. In the simplest case, an
executor can run the submitted task immediately in the caller's
thread:



class DirectExecutor implements Executor {
  public void execute(Runnable r) {
    r.run();
  }
}

More typically, tasks are executed in some thread other
than the caller's thread.  The executor below spawns a new thread
for each task.



class ThreadPerTaskExecutor implements Executor {
  public void execute(Runnable r) {
    new Thread(r).start();
  }
}

Many Executor implementations impose some sort of
limitation on how and when tasks are scheduled.  The executor below
serializes the submission of tasks to a second executor,
illustrating a composite executor.



class SerialExecutor implements Executor {
  final Queue<Runnable> tasks = new ArrayDeque<Runnable>();
  final Executor executor;
  Runnable active;

  SerialExecutor(Executor executor) {
    this.executor = executor;
  }

  public synchronized void execute(final Runnable r) {
    tasks.offer(new Runnable() {
      public void run() {
        try {
          r.run();
        } finally {
          scheduleNext();
        }
      }
    });
    if (active == null) {
      scheduleNext();
    }
  }

  protected synchronized void scheduleNext() {
    if ((active = tasks.poll()) != null) {
      executor.execute(active);
    }
  }
}

The Executor implementations provided in this package
implement ExecutorService, which is a more extensive
interface.  The ThreadPoolExecutor class provides an
extensible thread pool implementation. The Executors class
provides convenient factory methods for these Executors.

Memory consistency effects: Actions in a thread prior to
submitting a Runnable object to an Executor
happen-before
its execution begins, perhaps in another thread.

if (result != null)
    use(result);

A CompletionService that uses a supplied Executor
to execute tasks.  This class arranges that submitted tasks are,
upon completion, placed on a queue accessible using take.
The class is lightweight enough to be suitable for transient use
when processing groups of tasks.



Usage Examples.

Suppose you have a set of solvers for a certain problem, each
returning a value of some type Result, and would like to
run them concurrently, processing the results of each of them that
return a non-null value, in some method use(Result r). You
could write this as:



void solve(Executor e,
           Collection<Callable<Result>> solvers)
    throws InterruptedException, ExecutionException {
    CompletionService<Result> ecs
        = new ExecutorCompletionService<Result>(e);
    for (Callable<Result> s : solvers)
        ecs.submit(s);
    int n = solvers.size();
    for (int i = 0; i < n; +i) {
        Result r = ecs.take().get();
        if (r != null)
            use(r);
    }
}

Suppose instead that you would like to use the first non-null result
of the set of tasks, ignoring any that encounter exceptions,
and cancelling all other tasks when the first one is ready:



void solve(Executor e,
           Collection<Callable<Result>> solvers)
    throws InterruptedException {
    CompletionService<Result> ecs
        = new ExecutorCompletionService<Result>(e);
    int n = solvers.size();
    List<Future<Result>> futures
        = new ArrayList<Future<Result>>(n);
    Result result = null;
    try {
        for (Callable<Result> s : solvers)
            futures.add(ecs.submit(s));
        for (int i = 0; i < n; +i) {
            try {
                Result r = ecs.take().get();
                if (r != null) {
                    result = r;
                    break;
                }
            } catch (ExecutionException ignore) {}
        }
    }
    finally {
        for (Future<Result> f : futures)
            f.cancel(true);
    }

    if (result != null)
        use(result);
}

Factory and utility methods for Executor, ExecutorService, ScheduledExecutorService, ThreadFactory, and Callable classes defined in this
package. This class supports the following kinds of methods:


   Methods that create and return an ExecutorService
       set up with commonly useful configuration settings.
   Methods that create and return a ScheduledExecutorService
       set up with commonly useful configuration settings.
   Methods that create and return a "wrapped" ExecutorService, that
       disables reconfiguration by making implementation-specific methods
       inaccessible.
   Methods that create and return a ThreadFactory
       that sets newly created threads to a known state.
   Methods that create and return a Callable
       out of other closure-like forms, so they can be used
       in execution methods requiring Callable.

An Executor that provides methods to manage termination and
methods that can produce a Future for tracking progress of
one or more asynchronous tasks.

An ExecutorService can be shut down, which will cause
it to reject new tasks.  Two different methods are provided for
shutting down an ExecutorService. The shutdown()
method will allow previously submitted tasks to execute before
terminating, while the shutdownNow() method prevents waiting
tasks from starting and attempts to stop currently executing tasks.
Upon termination, an executor has no tasks actively executing, no
tasks awaiting execution, and no new tasks can be submitted.  An
unused ExecutorService should be shut down to allow
reclamation of its resources.

Method submit extends base method Executor.execute(Runnable) by creating and returning a Future
that can be used to cancel execution and/or wait for completion.
Methods invokeAny and invokeAll perform the most
commonly useful forms of bulk execution, executing a collection of
tasks and then waiting for at least one, or all, to
complete. (Class ExecutorCompletionService can be used to
write customized variants of these methods.)

The Executors class provides factory methods for the
executor services provided in this package.

Usage Examples

Here is a sketch of a network service in which threads in a thread
pool service incoming requests. It uses the preconfigured Executors.newFixedThreadPool(int) factory method:



class NetworkService implements Runnable {
  private final ServerSocket serverSocket;
  private final ExecutorService pool;

  public NetworkService(int port, int poolSize)
      throws IOException {
    serverSocket = new ServerSocket(port);
    pool = Executors.newFixedThreadPool(poolSize);
  }

  public void run() { // run the service
    try {
      for (;;) {
        pool.execute(new Handler(serverSocket.accept()));
      }
    } catch (IOException ex) {
      pool.shutdown();
    }
  }
}

class Handler implements Runnable {
  private final Socket socket;
  Handler(Socket socket) { this.socket = socket; }
  public void run() {
    // read and service request on socket
  }
}

The following method shuts down an ExecutorService in two phases,
first by calling shutdown to reject incoming tasks, and then
calling shutdownNow, if necessary, to cancel any lingering tasks:



void shutdownAndAwaitTermination(ExecutorService pool) {
  pool.shutdown(); // Disable new tasks from being submitted
  try {
    // Wait a while for existing tasks to terminate
    if (!pool.awaitTermination(60, TimeUnit.SECONDS)) {
      pool.shutdownNow(); // Cancel currently executing tasks
      // Wait a while for tasks to respond to being cancelled
      if (!pool.awaitTermination(60, TimeUnit.SECONDS))
          System.err.println("Pool did not terminate");
    }
  } catch (InterruptedException ie) {
    // (Re-)Cancel if current thread also interrupted
    pool.shutdownNow();
    // Preserve interrupt status
    Thread.currentThread().interrupt();
  }
}

Memory consistency effects: Actions in a thread prior to the
submission of a Runnable or Callable task to an
ExecutorService
happen-before
any actions taken by that task, which in turn happen-before the
result is retrieved via Future.get().

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)

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

A ForkJoinPool differs from other kinds of ExecutorService mainly by virtue of employing
work-stealing: all threads in the pool attempt to find and
execute tasks submitted to the pool and/or 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 ForkJoinTasks), as well as when many small
tasks are submitted to the pool from external clients.  Especially
when setting asyncMode to true in constructors, ForkJoinPools may also be appropriate for use with event-style
tasks that are never joined.

A static commonPool() is available and appropriate for
most applications. The common pool is used by any ForkJoinTask that
is not explicitly submitted to a specified pool. Using the common
pool normally reduces resource usage (its threads are slowly
reclaimed during periods of non-use, and reinstated upon subsequent
use).

For applications that require separate or custom pools, a ForkJoinPool may be 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
I/O or other unmanaged synchronization. The nested ForkJoinPool.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 primarily by clients not already
engaged in fork/join computations in the current pool.  The main
forms of these methods accept instances of ForkJoinTask,
but overloaded forms also allow mixed execution of plain Runnable- or Callable- based activities as well.  However,
tasks that are already executing in a pool should normally instead
use the within-computation forms listed in the table unless using
async event-style tasks that are not usually joined, in which case
there is little difference among choice of methods.


Summary of task execution methods


    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)



The common pool is by default constructed with default
parameters, but these may be controlled by setting three
system properties:

java.util.concurrent.ForkJoinPool.common.parallelism
- the parallelism level, a non-negative integer
java.util.concurrent.ForkJoinPool.common.threadFactory
- the class name of a ForkJoinPool.ForkJoinWorkerThreadFactory
java.util.concurrent.ForkJoinPool.common.exceptionHandler
- the class name of a Thread.UncaughtExceptionHandler

If a SecurityManager is present and no factory is
specified, then the default pool uses a factory supplying
threads that have no Permissions enabled.
The system class loader is used to load these classes.
Upon any error in establishing these settings, default parameters
are used. It is possible to disable or limit the use of threads in
the common pool by setting the parallelism property to zero, and/or
using a factory that may return null. However doing so may
cause unjoined tasks to never be executed.

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
IllegalArgumentException.

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

Factory for creating new ForkJoinWorkerThreads.
A ForkJoinWorkerThreadFactory must be defined and used
for ForkJoinWorkerThread subclasses that extend base
functionality or initialize threads with different contexts.

Interface for extending managed parallelism for tasks running
in ForkJoinPools.

A ManagedBlocker provides two methods.  Method
isReleasable() must return true if blocking is
not necessary. Method block() blocks the current thread
if necessary (perhaps internally invoking isReleasable
before actually blocking). These actions are performed by any
thread invoking ForkJoinPool.managedBlock(ManagedBlocker).
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 isReleasable must be amenable
to repeated invocation.

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


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:


class QueueTaker<E> implements ManagedBlocker {
  final BlockingQueue<E> queue;
  volatile E item = null;
  QueueTaker(BlockingQueue<E> 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;
  }
}

Abstract base class for tasks that run within a ForkJoinPool.
A ForkJoinTask is a thread-like entity that is much
lighter weight than a normal thread.  Huge numbers of tasks and
subtasks may be hosted by a small number of actual threads in a
ForkJoinPool, at the price of some usage limitations.

A "main" ForkJoinTask begins execution when it is
explicitly submitted to a ForkJoinPool, or, if not already
engaged in a ForkJoin computation, commenced in the ForkJoinPool.commonPool() via fork(), invoke(), or
related methods.  Once started, it will usually in turn start other
subtasks.  As indicated by the name of this class, many programs
using ForkJoinTask employ only methods fork() and
join(), or derivatives such as invokeAll.  However, this class also
provides a number of other methods that can come into play in
advanced usages, as well as extension mechanics that allow support
of new forms of fork/join processing.

A ForkJoinTask is a lightweight form of Future.
The efficiency of ForkJoinTasks stems from a set of
restrictions (that are only partially statically enforceable)
reflecting their main use as computational tasks calculating pure
functions or operating on purely isolated objects.  The primary
coordination mechanisms are fork(), that arranges
asynchronous execution, and join(), that doesn't proceed
until the task's result has been computed.  Computations should
ideally avoid synchronized methods or blocks, and should
minimize other blocking synchronization apart from joining other
tasks or using synchronizers such as Phasers that are advertised to
cooperate with fork/join scheduling. Subdividable tasks should also
not perform blocking I/O, and should ideally access variables that
are completely independent of those accessed by other running
tasks. These guidelines are loosely enforced by not permitting
checked exceptions such as IOExceptions to be
thrown. However, computations may still encounter unchecked
exceptions, that are rethrown to callers attempting to join
them. These exceptions may additionally include RejectedExecutionException stemming from internal resource
exhaustion, such as failure to allocate internal task
queues. Rethrown exceptions behave in the same way as regular
exceptions, but, when possible, contain stack traces (as displayed
for example using ex.printStackTrace()) of both the thread
that initiated the computation as well as the thread actually
encountering the exception; minimally only the latter.

It is possible to define and use ForkJoinTasks that may block,
but doing do requires three further considerations: (1) Completion
of few if any other tasks should be dependent on a task
that blocks on external synchronization or I/O. Event-style async
tasks that are never joined (for example, those subclassing CountedCompleter) often fall into this category.  (2) To minimize
resource impact, tasks should be small; ideally performing only the
(possibly) blocking action. (3) Unless the ForkJoinPool.ManagedBlocker API is used, or the number of possibly
blocked tasks is known to be less than the pool's ForkJoinPool.getParallelism() level, the pool cannot guarantee that
enough threads will be available to ensure progress or good
performance.

The primary method for awaiting completion and extracting
results of a task is join(), but there are several variants:
The Future.get() methods support interruptible and/or timed
waits for completion and report results using Future
conventions. Method invoke() is semantically
equivalent to fork(); join() but always attempts to begin
execution in the current thread. The "quiet" forms of
these methods do not extract results or report exceptions. These
may be useful when a set of tasks are being executed, and you need
to delay processing of results or exceptions until all complete.
Method invokeAll (available in multiple versions)
performs the most common form of parallel invocation: forking a set
of tasks and joining them all.

In the most typical usages, a fork-join pair act like a call
(fork) and return (join) from a parallel recursive function. As is
the case with other forms of recursive calls, returns (joins)
should be performed innermost-first. For example, a.fork();
b.fork(); b.join(); a.join(); is likely to be substantially more
efficient than joining a before b.

The execution status of tasks may be queried at several levels
of detail: isDone() is true if a task completed in any way
(including the case where a task was cancelled without executing);
isCompletedNormally() is true if a task completed without
cancellation or encountering an exception; isCancelled() is
true if the task was cancelled (in which case getException()
returns a CancellationException); and
isCompletedAbnormally() is true if a task was either
cancelled or encountered an exception, in which case getException() will return either the encountered exception or
CancellationException.

The ForkJoinTask class is not usually directly subclassed.
Instead, you subclass one of the abstract classes that support a
particular style of fork/join processing, typically RecursiveAction for most computations that do not return results,
RecursiveTask for those that do, and CountedCompleter for those in which completed actions trigger
other actions.  Normally, a concrete ForkJoinTask subclass declares
fields comprising its parameters, established in a constructor, and
then defines a compute method that somehow uses the control
methods supplied by this base class.

Method join() and its variants are appropriate for use
only when completion dependencies are acyclic; that is, the
parallel computation can be described as a directed acyclic graph
(DAG). Otherwise, executions may encounter a form of deadlock as
tasks cyclically wait for each other.  However, this framework
supports other methods and techniques (for example the use of
Phaser, helpQuiesce(), and complete(V)) that
may be of use in constructing custom subclasses for problems that
are not statically structured as DAGs. To support such usages, a
ForkJoinTask may be atomically tagged with a short
value using setForkJoinTaskTag(short) or compareAndSetForkJoinTaskTag(short, short) and checked using getForkJoinTaskTag(). The ForkJoinTask implementation does not use
these protected methods or tags for any purpose, but they
may be of use in the construction of specialized subclasses.  For
example, parallel graph traversals can use the supplied methods to
avoid revisiting nodes/tasks that have already been processed.
(Method names for tagging are bulky in part to encourage definition
of methods that reflect their usage patterns.)

Most base support methods are final, to prevent
overriding of implementations that are intrinsically tied to the
underlying lightweight task scheduling framework.  Developers
creating new basic styles of fork/join processing should minimally
implement protected methods exec(), setRawResult(V), and getRawResult(), while also introducing
an abstract computational method that can be implemented in its
subclasses, possibly relying on other protected methods
provided by this class.

ForkJoinTasks should perform relatively small amounts of
computation. Large tasks should be split into smaller subtasks,
usually via recursive decomposition. As a very rough rule of thumb,
a task should perform more than 100 and less than 10000 basic
computational steps, and should avoid indefinite looping. If tasks
are too big, then parallelism cannot improve throughput. If too
small, then memory and internal task maintenance overhead may
overwhelm processing.

This class provides adapt methods for Runnable
and Callable, that may be of use when mixing execution of
ForkJoinTasks with other kinds of tasks. When all tasks are
of this form, consider using a pool constructed in asyncMode.

ForkJoinTasks are Serializable, which enables them to be
used in extensions such as remote execution frameworks. It is
sensible to serialize tasks only before or after, but not during,
execution. Serialization is not relied on during execution itself.

A thread managed by a ForkJoinPool, which executes
ForkJoinTasks.
This class is subclassable solely for the sake of adding
functionality -- there are no overridable methods dealing with
scheduling or execution.  However, you can override initialization
and termination methods surrounding the main task processing loop.
If you do create such a subclass, you will also need to supply a
custom ForkJoinPool.ForkJoinWorkerThreadFactory to
use it in a ForkJoinPool.

A Future represents the result of an asynchronous
computation.  Methods are provided to check if the computation is
complete, to wait for its completion, and to retrieve the result of
the computation.  The result can only be retrieved using method
get when the computation has completed, blocking if
necessary until it is ready.  Cancellation is performed by the
cancel method.  Additional methods are provided to
determine if the task completed normally or was cancelled. Once a
computation has completed, the computation cannot be cancelled.
If you would like to use a Future for the sake
of cancellability but not provide a usable result, you can
declare types of the form Future<?> and
return null as a result of the underlying task.


Sample Usage (Note that the following classes are all
made-up.)


interface ArchiveSearcher { String search(String target); }
class App {
  ExecutorService executor = ...
  ArchiveSearcher searcher = ...
  void showSearch(final String target)
      throws InterruptedException {
    Future<String> future
      = executor.submit(new Callable<String>() {
        public String call() {
            return searcher.search(target);
        }});
    displayOtherThings(); // do other things while searching
    try {
      displayText(future.get()); // use future
    } catch (ExecutionException ex) { cleanup(); return; }
  }
}

The FutureTask class is an implementation of Future that
implements Runnable, and so may be executed by an Executor.
For example, the above construction with submit could be replaced by:


FutureTask<String> future =
  new FutureTask<String>(new Callable<String>() {
    public String call() {
      return searcher.search(target);
  }});
executor.execute(future);

Memory consistency effects: Actions taken by the asynchronous computation
 happen-before
actions following the corresponding Future.get() in another thread.

A cancellable asynchronous computation.  This class provides a base
implementation of Future, with methods to start and cancel
a computation, query to see if the computation is complete, and
retrieve the result of the computation.  The result can only be
retrieved when the computation has completed; the get
methods will block if the computation has not yet completed.  Once
the computation has completed, the computation cannot be restarted
or cancelled (unless the computation is invoked using
runAndReset()).

A FutureTask can be used to wrap a Callable or
Runnable object.  Because FutureTask implements
Runnable, a FutureTask can be submitted to an
Executor for execution.

In addition to serving as a standalone class, this class provides
protected functionality that may be useful when creating
customized task classes.

An optionally-bounded java.util.concurrent.blocking deque based on
linked nodes.

The optional capacity bound constructor argument serves as a
way to prevent excessive expansion. The capacity, if unspecified,
is equal to Integer.MAX_VALUE.  Linked nodes are
dynamically created upon each insertion unless this would bring the
deque above capacity.

Most operations run in constant time (ignoring time spent
blocking).  Exceptions include remove,
removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk
operations, all of which run in linear time.

This class and its iterator implement all of the
optional methods of the Collection and Iterator interfaces.

This class is a member of the

Java Collections Framework.

An optionally-bounded java.util.concurrent.blocking queue based on
linked nodes.
This queue orders elements FIFO (first-in-first-out).
The head of the queue is that element that has been on the
queue the longest time.
The tail of the queue is that element that has been on the
queue the shortest time. New elements
are inserted at the tail of the queue, and the queue retrieval
operations obtain elements at the head of the queue.
Linked queues typically have higher throughput than array-based queues but
less predictable performance in most concurrent applications.

The optional capacity bound constructor argument serves as a
way to prevent excessive queue expansion. The capacity, if unspecified,
is equal to Integer.MAX_VALUE.  Linked nodes are
dynamically created upon each insertion unless this would bring the
queue above capacity.

This class and its iterator implement all of the
optional methods of the Collection and Iterator interfaces.

This class is a member of the

Java Collections Framework.

An unbounded TransferQueue based on linked nodes.
This queue orders elements FIFO (first-in-first-out) with respect
to any given producer.  The head of the queue is that
element that has been on the queue the longest time for some
producer.  The tail of the queue is that element that has
been on the queue the shortest time for some producer.

Beware that, unlike in most collections, the size method
is NOT a constant-time operation. Because of the
asynchronous nature of these queues, determining the current number
of elements requires a traversal of the elements, and so may report
inaccurate results if this collection is modified during traversal.
Additionally, the bulk operations addAll,
removeAll, retainAll, containsAll,
equals, and toArray are not guaranteed
to be performed atomically. For example, an iterator operating
concurrently with an addAll operation might view only some
of the added elements.

This class and its iterator implement all of the
optional methods of the Collection and Iterator interfaces.

Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
LinkedTransferQueue
happen-before
actions subsequent to the access or removal of that element from
the LinkedTransferQueue in another thread.

This class is a member of the

Java Collections Framework.

A synchronizer that may be exclusively owned by a thread.  This
class provides a basis for creating locks and related synchronizers
that may entail a notion of ownership.  The
AbstractOwnableSynchronizer class itself does not manage or
use this information. However, subclasses and tools may use
appropriately maintained values to help control and monitor access
and provide diagnostics.

A version of AbstractQueuedSynchronizer in
which synchronization state is maintained as a long.
This class has exactly the same structure, properties, and methods
as AbstractQueuedSynchronizer with the exception
that all state-related parameters and results are defined
as long rather than int. This class
may be useful when creating synchronizers such as
multilevel locks and barriers that require
64 bits of state.

See AbstractQueuedSynchronizer for usage
notes and examples.

// Acquires the lock if state is zero
public boolean tryAcquire(int acquires) {
  assert acquires == 1; // Otherwise unused
  if (compareAndSetState(0, 1)) {
    setExclusiveOwnerThread(Thread.currentThread());
    return true;
  }
  return false;
}

// Releases the lock by setting state to zero
protected boolean tryRelease(int releases) {
  assert releases == 1; // Otherwise unused
  if (getState() == 0) throw new IllegalMonitorStateException();
  setExclusiveOwnerThread(null);
  setState(0);
  return true;
}

// Provides a Condition
Condition newCondition() { return new ConditionObject(); }

// Deserializes properly
private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException {
  s.defaultReadObject();
  setState(0); // reset to unlocked state
}

protected int tryAcquireShared(int ignore) {
  return isSignalled() ? 1 : -1;
}

protected boolean tryReleaseShared(int ignore) {
  setState(1);
  return true;
}

Provides a framework for implementing blocking locks and related
synchronizers (semaphores, events, etc) that rely on
first-in-first-out (FIFO) wait queues.  This class is designed to
be a useful basis for most kinds of synchronizers that rely on a
single atomic int value to represent state. Subclasses
must define the protected methods that change this state, and which
define what that state means in terms of this object being acquired
or released.  Given these, the other methods in this class carry
out all queuing and blocking mechanics. Subclasses can maintain
other state fields, but only the atomically updated int
value manipulated using methods getState(), setState(int) and compareAndSetState(int, int) is tracked with respect
to synchronization.

Subclasses should be defined as non-public internal helper
classes that are used to implement the synchronization properties
of their enclosing class.  Class
AbstractQueuedSynchronizer does not implement any
synchronization interface.  Instead it defines methods such as
acquireInterruptibly(int) that can be invoked as
appropriate by concrete locks and related synchronizers to
implement their public methods.

This class supports either or both a default exclusive
mode and a shared mode. When acquired in exclusive mode,
attempted acquires by other threads cannot succeed. Shared mode
acquires by multiple threads may (but need not) succeed. This class
does not "understand" these differences except in the
mechanical sense that when a shared mode acquire succeeds, the next
waiting thread (if one exists) must also determine whether it can
acquire as well. Threads waiting in the different modes share the
same FIFO queue. Usually, implementation subclasses support only
one of these modes, but both can come into play for example in a
ReadWriteLock. Subclasses that support only exclusive or
only shared modes need not define the methods supporting the unused mode.

This class defines a nested AbstractQueuedSynchronizer.ConditionObject class that
can be used as a Condition implementation by subclasses
supporting exclusive mode for which method isHeldExclusively() reports whether synchronization is exclusively
held with respect to the current thread, method release(int)
invoked with the current getState() value fully releases
this object, and acquire(int), given this saved state value,
eventually restores this object to its previous acquired state.  No
AbstractQueuedSynchronizer method otherwise creates such a
condition, so if this constraint cannot be met, do not use it.  The
behavior of AbstractQueuedSynchronizer.ConditionObject depends of course on the
semantics of its synchronizer implementation.

This class provides inspection, instrumentation, and monitoring
methods for the internal queue, as well as similar methods for
condition objects. These can be exported as desired into classes
using an AbstractQueuedSynchronizer for their
synchronization mechanics.

Serialization of this class stores only the underlying atomic
integer maintaining state, so deserialized objects have empty
thread queues. Typical subclasses requiring serializability will
define a readObject method that restores this to a known
initial state upon deserialization.

Usage

To use this class as the basis of a synchronizer, redefine the
following methods, as applicable, by inspecting and/or modifying
the synchronization state using getState(), setState(int) and/or compareAndSetState(int, int):


 tryAcquire(int)
 tryRelease(int)
 tryAcquireShared(int)
 tryReleaseShared(int)
 isHeldExclusively()


Each of these methods by default throws UnsupportedOperationException.  Implementations of these methods
must be internally thread-safe, and should in general be short and
not block. Defining these methods is the only supported
means of using this class. All other methods are declared
final because they cannot be independently varied.

You may also find the inherited methods from AbstractOwnableSynchronizer useful to keep track of the thread
owning an exclusive synchronizer.  You are encouraged to use them
-- this enables monitoring and diagnostic tools to assist users in
determining which threads hold locks.

Even though this class is based on an internal FIFO queue, it
does not automatically enforce FIFO acquisition policies.  The core
of exclusive synchronization takes the form:



Acquire:
    while (!tryAcquire(arg)) {
       enqueue thread if it is not already queued;
       possibly block current thread;
    }

Release:
    if (tryRelease(arg))
       unblock the first queued thread;

(Shared mode is similar but may involve cascading signals.)

Because checks in acquire are invoked before
enqueuing, a newly acquiring thread may barge ahead of
others that are blocked and queued.  However, you can, if desired,
define tryAcquire and/or tryAcquireShared to
disable barging by internally invoking one or more of the inspection
methods, thereby providing a fair FIFO acquisition order.
In particular, most fair synchronizers can define tryAcquire
to return false if hasQueuedPredecessors() (a method
specifically designed to be used by fair synchronizers) returns
true.  Other variations are possible.

Throughput and scalability are generally highest for the
default barging (also known as greedy,
renouncement, and convoy-avoidance) strategy.
While this is not guaranteed to be fair or starvation-free, earlier
queued threads are allowed to recontend before later queued
threads, and each recontention has an unbiased chance to succeed
against incoming threads.  Also, while acquires do not
"spin" in the usual sense, they may perform multiple
invocations of tryAcquire interspersed with other
computations before blocking.  This gives most of the benefits of
spins when exclusive synchronization is only briefly held, without
most of the liabilities when it isn't. If so desired, you can
augment this by preceding calls to acquire methods with
"fast-path" checks, possibly prechecking hasContended()
and/or hasQueuedThreads() to only do so if the synchronizer
is likely not to be contended.

This class provides an efficient and scalable basis for
synchronization in part by specializing its range of use to
synchronizers that can rely on int state, acquire, and
release parameters, and an internal FIFO wait queue. When this does
not suffice, you can build synchronizers from a lower level using
atomic classes, your own custom
Queue classes, and LockSupport blocking
support.

Usage Examples

Here is a non-reentrant mutual exclusion lock class that uses
the value zero to represent the unlocked state, and one to
represent the locked state. While a non-reentrant lock
does not strictly require recording of the current owner
thread, this class does so anyway to make usage easier to monitor.
It also supports conditions and exposes
one of the instrumentation methods:



class Mutex implements Lock, java.io.Serializable {

  // Our internal helper class
  private static class Sync extends AbstractQueuedSynchronizer {
    // Reports whether in locked state
    protected boolean isHeldExclusively() {
      return getState() == 1;
    }

    // Acquires the lock if state is zero
    public boolean tryAcquire(int acquires) {
      assert acquires == 1; // Otherwise unused
      if (compareAndSetState(0, 1)) {
        setExclusiveOwnerThread(Thread.currentThread());
        return true;
      }
      return false;
    }

    // Releases the lock by setting state to zero
    protected boolean tryRelease(int releases) {
      assert releases == 1; // Otherwise unused
      if (getState() == 0) throw new IllegalMonitorStateException();
      setExclusiveOwnerThread(null);
      setState(0);
      return true;
    }

    // Provides a Condition
    Condition newCondition() { return new ConditionObject(); }

    // Deserializes properly
    private void readObject(ObjectInputStream s)
        throws IOException, ClassNotFoundException {
      s.defaultReadObject();
      setState(0); // reset to unlocked state
    }
  }

  // The sync object does all the hard work. We just forward to it.
  private final Sync sync = new Sync();

  public void lock()                { sync.acquire(1); }
  public boolean tryLock()          { return sync.tryAcquire(1); }
  public void unlock()              { sync.release(1); }
  public Condition newCondition()   { return sync.newCondition(); }
  public boolean isLocked()         { return sync.isHeldExclusively(); }
  public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
  public void lockInterruptibly() throws InterruptedException {
    sync.acquireInterruptibly(1);
  }
  public boolean tryLock(long timeout, TimeUnit unit)
      throws InterruptedException {
    return sync.tryAcquireNanos(1, unit.toNanos(timeout));
  }
}

Here is a latch class that is like a
CountDownLatch
except that it only requires a single signal to
fire. Because a latch is non-exclusive, it uses the shared
acquire and release methods.



class BooleanLatch {

  private static class Sync extends AbstractQueuedSynchronizer {
    boolean isSignalled() { return getState() != 0; }

    protected int tryAcquireShared(int ignore) {
      return isSignalled() ? 1 : -1;
    }

    protected boolean tryReleaseShared(int ignore) {
      setState(1);
      return true;
    }
  }

  private final Sync sync = new Sync();
  public boolean isSignalled() { return sync.isSignalled(); }
  public void signal()         { sync.releaseShared(1); }
  public void await() throws InterruptedException {
    sync.acquireSharedInterruptibly(1);
  }
}

Condition factors out the Object monitor
methods (wait, notify
and notifyAll) into distinct objects to
give the effect of having multiple wait-sets per object, by
combining them with the use of arbitrary Lock implementations.
Where a Lock replaces the use of synchronized methods
and statements, a Condition replaces the use of the Object
monitor methods.

Conditions (also known as condition queues or
condition variables) provide a means for one thread to
suspend execution (to "wait") until notified by another
thread that some state condition may now be true.  Because access
to this shared state information occurs in different threads, it
must be protected, so a lock of some form is associated with the
condition. The key property that waiting for a condition provides
is that it atomically releases the associated lock and
suspends the current thread, just like Object.wait.

A Condition instance is intrinsically bound to a lock.
To obtain a Condition instance for a particular Lock
instance use its newCondition() method.

As an example, suppose we have a bounded buffer which supports
put and take methods.  If a
take is attempted on an empty buffer, then the thread will block
until an item becomes available; if a put is attempted on a
full buffer, then the thread will block until a space becomes available.
We would like to keep waiting put threads and take
threads in separate wait-sets so that we can use the optimization of
only notifying a single thread at a time when items or spaces become
available in the buffer. This can be achieved using two
Condition instances.


class BoundedBuffer {
  final Lock lock = new ReentrantLock();
  final Condition notFull  = lock.newCondition();
  final Condition notEmpty = lock.newCondition();

  final Object[] items = new Object[100];
  int putptr, takeptr, count;

  public void put(Object x) throws InterruptedException {
    lock.lock();
    try {
      while (count == items.length)
        notFull.await();
      items[putptr] = x;
      if (++putptr == items.length) putptr = 0;
      +count;
      notEmpty.signal();
    } finally {
      lock.unlock();
    }
  }

  public Object take() throws InterruptedException {
    lock.lock();
    try {
      while (count == 0)
        notEmpty.await();
      Object x = items[takeptr];
      if (++takeptr == items.length) takeptr = 0;
      --count;
      notFull.signal();
      return x;
    } finally {
      lock.unlock();
    }
  }
}

(The ArrayBlockingQueue class provides
this functionality, so there is no reason to implement this
sample usage class.)

A Condition implementation can provide behavior and semantics
that is
different from that of the Object monitor methods, such as
guaranteed ordering for notifications, or not requiring a lock to be held
when performing notifications.
If an implementation provides such specialized semantics then the
implementation must document those semantics.

Note that Condition instances are just normal objects and can
themselves be used as the target in a synchronized statement,
and can have their own monitor wait and
notification methods invoked.
Acquiring the monitor lock of a Condition instance, or using its
monitor methods, has no specified relationship with acquiring the
Lock associated with that Condition or the use of its
waiting and signalling methods.
It is recommended that to avoid confusion you never use Condition
instances in this way, except perhaps within their own implementation.

Except where noted, passing a null value for any parameter
will result in a NullPointerException being thrown.

Implementation Considerations

When waiting upon a Condition, a "spurious
wakeup" is permitted to occur, in
general, as a concession to the underlying platform semantics.
This has little practical impact on most application programs as a
Condition should always be waited upon in a loop, testing
the state predicate that is being waited for.  An implementation is
free to remove the possibility of spurious wakeups but it is
recommended that applications programmers always assume that they can
occur and so always wait in a loop.

The three forms of condition waiting
(interruptible, non-interruptible, and timed) may differ in their ease of
implementation on some platforms and in their performance characteristics.
In particular, it may be difficult to provide these features and maintain
specific semantics such as ordering guarantees.
Further, the ability to interrupt the actual suspension of the thread may
not always be feasible to implement on all platforms.

Consequently, an implementation is not required to define exactly the
same guarantees or semantics for all three forms of waiting, nor is it
required to support interruption of the actual suspension of the thread.

An implementation is required to
clearly document the semantics and guarantees provided by each of the
waiting methods, and when an implementation does support interruption of
thread suspension then it must obey the interruption semantics as defined
in this interface.

As interruption generally implies cancellation, and checks for
interruption are often infrequent, an implementation can favor responding
to an interrupt over normal method return. This is true even if it can be
shown that the interrupt occurred after another action that may have
unblocked the thread. An implementation should document this behavior.

Lock implementations provide more extensive locking
operations than can be obtained using synchronized methods
and statements.  They allow more flexible structuring, may have
quite different properties, and may support multiple associated
Condition objects.

A lock is a tool for controlling access to a shared resource by
multiple threads. Commonly, a lock provides exclusive access to a
shared resource: only one thread at a time can acquire the lock and
all access to the shared resource requires that the lock be
acquired first. However, some locks may allow concurrent access to
a shared resource, such as the read lock of a ReadWriteLock.

The use of synchronized methods or statements provides
access to the implicit monitor lock associated with every object, but
forces all lock acquisition and release to occur in a block-structured way:
when multiple locks are acquired they must be released in the opposite
order, and all locks must be released in the same lexical scope in which
they were acquired.

While the scoping mechanism for synchronized methods
and statements makes it much easier to program with monitor locks,
and helps avoid many common programming errors involving locks,
there are occasions where you need to work with locks in a more
flexible way. For example, some algorithms for traversing
concurrently accessed data structures require the use of
"hand-over-hand" or "chain locking": you
acquire the lock of node A, then node B, then release A and acquire
C, then release B and acquire D and so on.  Implementations of the
Lock interface enable the use of such techniques by
allowing a lock to be acquired and released in different scopes,
and allowing multiple locks to be acquired and released in any
order.

With this increased flexibility comes additional
responsibility. The absence of block-structured locking removes the
automatic release of locks that occurs with synchronized
methods and statements. In most cases, the following idiom
should be used:



Lock l = ...;
l.lock();
try {
  // access the resource protected by this lock
} finally {
  l.unlock();
}

When locking and unlocking occur in different scopes, care must be
taken to ensure that all code that is executed while the lock is
held is protected by try-finally or try-catch to ensure that the
lock is released when necessary.

Lock implementations provide additional functionality
over the use of synchronized methods and statements by
providing a non-blocking attempt to acquire a lock (tryLock()), an attempt to acquire the lock that can be
interrupted (lockInterruptibly(), and an attempt to acquire
the lock that can timeout (tryLock(long, TimeUnit)).

A Lock class can also provide behavior and semantics
that is quite different from that of the implicit monitor lock,
such as guaranteed ordering, non-reentrant usage, or deadlock
detection. If an implementation provides such specialized semantics
then the implementation must document those semantics.

Note that Lock instances are just normal objects and can
themselves be used as the target in a synchronized statement.
Acquiring the
monitor lock of a Lock instance has no specified relationship
with invoking any of the lock() methods of that instance.
It is recommended that to avoid confusion you never use Lock
instances in this way, except within their own implementation.

Except where noted, passing a null value for any
parameter will result in a NullPointerException being
thrown.

Memory Synchronization

All Lock implementations must enforce the same
memory synchronization semantics as provided by the built-in monitor
lock, as described in

The Java Language Specification (17.4 Memory Model):

A successful lock operation has the same memory
synchronization effects as a successful Lock action.
A successful unlock operation has the same
memory synchronization effects as a successful Unlock action.


Unsuccessful locking and unlocking operations, and reentrant
locking/unlocking operations, do not require any memory
synchronization effects.

Implementation Considerations

The three forms of lock acquisition (interruptible,
non-interruptible, and timed) may differ in their performance
characteristics, ordering guarantees, or other implementation
qualities.  Further, the ability to interrupt the ongoing
acquisition of a lock may not be available in a given Lock
class.  Consequently, an implementation is not required to define
exactly the same guarantees or semantics for all three forms of
lock acquisition, nor is it required to support interruption of an
ongoing lock acquisition.  An implementation is required to clearly
document the semantics and guarantees provided by each of the
locking methods. It must also obey the interruption semantics as
defined in this interface, to the extent that interruption of lock
acquisition is supported: which is either totally, or only on
method entry.

As interruption generally implies cancellation, and checks for
interruption are often infrequent, an implementation can favor responding
to an interrupt over normal method return. This is true even if it can be
shown that the interrupt occurred after another action may have unblocked
the thread. An implementation should document this behavior.

// Block while not first in queue or cannot acquire lock
while (waiters.peek() != current ||
       !locked.compareAndSet(false, true)) {
  LockSupport.park(this);
  if (Thread.interrupted()) // ignore interrupts while waiting
    wasInterrupted = true;
}

waiters.remove();
if (wasInterrupted)          // reassert interrupt status on exit
  current.interrupt();

Basic thread blocking primitives for creating locks and other
synchronization classes.

This class associates, with each thread that uses it, a permit
(in the sense of the Semaphore class). A call to park will return immediately
if the permit is available, consuming it in the process; otherwise
it may block.  A call to unpark makes the permit
available, if it was not already available. (Unlike with Semaphores
though, permits do not accumulate. There is at most one.)

Methods park and unpark provide efficient
means of blocking and unblocking threads that do not encounter the
problems that cause the deprecated methods Thread.suspend
and Thread.resume to be unusable for such purposes: Races
between one thread invoking park and another thread trying
to unpark it will preserve liveness, due to the
permit. Additionally, park will return if the caller's
thread was interrupted, and timeout versions are supported. The
park method may also return at any other time, for "no
reason", so in general must be invoked within a loop that rechecks
conditions upon return. In this sense park serves as an
optimization of a "busy wait" that does not waste as much time
spinning, but must be paired with an unpark to be
effective.

The three forms of park each also support a
blocker object parameter. This object is recorded while
the thread is blocked to permit monitoring and diagnostic tools to
identify the reasons that threads are blocked. (Such tools may
access blockers using method getBlocker(Thread).)
The use of these forms rather than the original forms without this
parameter is strongly encouraged. The normal argument to supply as
a blocker within a lock implementation is this.

These methods are designed to be used as tools for creating
higher-level synchronization utilities, and are not in themselves
useful for most concurrency control applications.  The park
method is designed for use only in constructions of the form:



while (!canProceed()) { ... LockSupport.park(this); }

where neither canProceed nor any other actions prior to the
call to park entail locking or blocking.  Because only one
permit is associated with each thread, any intermediary uses of
park could interfere with its intended effects.

Sample Usage. Here is a sketch of a first-in-first-out
non-reentrant lock class:


class FIFOMutex {
  private final AtomicBoolean locked = new AtomicBoolean(false);
  private final Queue<Thread> waiters
    = new ConcurrentLinkedQueue<Thread>();

  public void lock() {
    boolean wasInterrupted = false;
    Thread current = Thread.currentThread();
    waiters.add(current);

    // Block while not first in queue or cannot acquire lock
    while (waiters.peek() != current ||
           !locked.compareAndSet(false, true)) {
      LockSupport.park(this);
      if (Thread.interrupted()) // ignore interrupts while waiting
        wasInterrupted = true;
    }

    waiters.remove();
    if (wasInterrupted)          // reassert interrupt status on exit
      current.interrupt();
  }

  public void unlock() {
    locked.set(false);
    LockSupport.unpark(waiters.peek());
  }
}

A ReadWriteLock maintains a pair of associated locks, one for read-only operations and one for writing.
The read lock may be held simultaneously by
multiple reader threads, so long as there are no writers.  The
write lock is exclusive.

All ReadWriteLock implementations must guarantee that
the memory synchronization effects of writeLock operations
(as specified in the Lock interface) also hold with respect
to the associated readLock. That is, a thread successfully
acquiring the read lock will see all updates made upon previous
release of the write lock.

A read-write lock allows for a greater level of concurrency in
accessing shared data than that permitted by a mutual exclusion lock.
It exploits the fact that while only a single thread at a time (a
writer thread) can modify the shared data, in many cases any
number of threads can concurrently read the data (hence reader
threads).
In theory, the increase in concurrency permitted by the use of a read-write
lock will lead to performance improvements over the use of a mutual
exclusion lock. In practice this increase in concurrency will only be fully
realized on a multi-processor, and then only if the access patterns for
the shared data are suitable.

Whether or not a read-write lock will improve performance over the use
of a mutual exclusion lock depends on the frequency that the data is
read compared to being modified, the duration of the read and write
operations, and the contention for the data - that is, the number of
threads that will try to read or write the data at the same time.
For example, a collection that is initially populated with data and
thereafter infrequently modified, while being frequently searched
(such as a directory of some kind) is an ideal candidate for the use of
a read-write lock. However, if updates become frequent then the data
spends most of its time being exclusively locked and there is little, if any
increase in concurrency. Further, if the read operations are too short
the overhead of the read-write lock implementation (which is inherently
more complex than a mutual exclusion lock) can dominate the execution
cost, particularly as many read-write lock implementations still serialize
all threads through a small section of code. Ultimately, only profiling
and measurement will establish whether the use of a read-write lock is
suitable for your application.


Although the basic operation of a read-write lock is straight-forward,
there are many policy decisions that an implementation must make, which
may affect the effectiveness of the read-write lock in a given application.
Examples of these policies include:

Determining whether to grant the read lock or the write lock, when
both readers and writers are waiting, at the time that a writer releases
the write lock. Writer preference is common, as writes are expected to be
short and infrequent. Reader preference is less common as it can lead to
lengthy delays for a write if the readers are frequent and long-lived as
expected. Fair, or "in-order" implementations are also possible.

Determining whether readers that request the read lock while a
reader is active and a writer is waiting, are granted the read lock.
Preference to the reader can delay the writer indefinitely, while
preference to the writer can reduce the potential for concurrency.

Determining whether the locks are reentrant: can a thread with the
write lock reacquire it? Can it acquire a read lock while holding the
write lock? Is the read lock itself reentrant?

Can the write lock be downgraded to a read lock without allowing
an intervening writer? Can a read lock be upgraded to a write lock,
in preference to other waiting readers or writers?


You should consider all of these things when evaluating the suitability
of a given implementation for your application.

A reentrant mutual exclusion Lock with the same basic
behavior and semantics as the implicit monitor lock accessed using
synchronized methods and statements, but with extended
capabilities.

A ReentrantLock is owned by the thread last
successfully locking, but not yet unlocking it. A thread invoking
lock will return, successfully acquiring the lock, when
the lock is not owned by another thread. The method will return
immediately if the current thread already owns the lock. This can
be checked using methods isHeldByCurrentThread(), and getHoldCount().

The constructor for this class accepts an optional
fairness parameter.  When set true, under
contention, locks favor granting access to the longest-waiting
thread.  Otherwise this lock does not guarantee any particular
access order.  Programs using fair locks accessed by many threads
may display lower overall throughput (i.e., are slower; often much
slower) than those using the default setting, but have smaller
variances in times to obtain locks and guarantee lack of
starvation. Note however, that fairness of locks does not guarantee
fairness of thread scheduling. Thus, one of many threads using a
fair lock may obtain it multiple times in succession while other
active threads are not progressing and not currently holding the
lock.
Also note that the untimed tryLock() method does not
honor the fairness setting. It will succeed if the lock
is available even if other threads are waiting.

It is recommended practice to always immediately
follow a call to lock with a try block, most
typically in a before/after construction such as:



class X {
  private final ReentrantLock lock = new ReentrantLock();
  // ...

  public void m() {
    lock.lock();  // block until condition holds
    try {
      // ... method body
    } finally {
      lock.unlock()
    }
  }
}

In addition to implementing the Lock interface, this
class defines a number of public and protected
methods for inspecting the state of the lock.  Some of these
methods are only useful for instrumentation and monitoring.

Serialization of this class behaves in the same way as built-in
locks: a deserialized lock is in the unlocked state, regardless of
its state when serialized.

This lock supports a maximum of 2147483647 recursive locks by
the same thread. Attempts to exceed this limit result in
Error throws from locking methods.

try {
  use(data);
} finally {
  rwl.readLock().unlock();
}

An implementation of ReadWriteLock supporting similar
semantics to ReentrantLock.
This class has the following properties:


Acquisition order

This class does not impose a reader or writer preference
ordering for lock access.  However, it does support an optional
fairness policy.


Non-fair mode (default)
When constructed as non-fair (the default), the order of entry
to the read and write lock is unspecified, subject to reentrancy
constraints.  A nonfair lock that is continuously contended may
indefinitely postpone one or more reader or writer threads, but
will normally have higher throughput than a fair lock.

Fair mode
When constructed as fair, threads contend for entry using an
approximately arrival-order policy. When the currently held lock
is released, either the longest-waiting single writer thread will
be assigned the write lock, or if there is a group of reader threads
waiting longer than all waiting writer threads, that group will be
assigned the read lock.

A thread that tries to acquire a fair read lock (non-reentrantly)
will block if either the write lock is held, or there is a waiting
writer thread. The thread will not acquire the read lock until
after the oldest currently waiting writer thread has acquired and
released the write lock. Of course, if a waiting writer abandons
its wait, leaving one or more reader threads as the longest waiters
in the queue with the write lock free, then those readers will be
assigned the read lock.

A thread that tries to acquire a fair write lock (non-reentrantly)
will block unless both the read lock and write lock are free (which
implies there are no waiting threads).  (Note that the non-blocking
ReentrantReadWriteLock.ReadLock.tryLock() and ReentrantReadWriteLock.WriteLock.tryLock() methods
do not honor this fair setting and will immediately acquire the lock
if it is possible, regardless of waiting threads.)



Reentrancy

This lock allows both readers and writers to reacquire read or
write locks in the style of a ReentrantLock. Non-reentrant
readers are not allowed until all write locks held by the writing
thread have been released.

Additionally, a writer can acquire the read lock, but not
vice-versa.  Among other applications, reentrancy can be useful
when write locks are held during calls or callbacks to methods that
perform reads under read locks.  If a reader tries to acquire the
write lock it will never succeed.

Lock downgrading
Reentrancy also allows downgrading from the write lock to a read lock,
by acquiring the write lock, then the read lock and then releasing the
write lock. However, upgrading from a read lock to the write lock is
not possible.

Interruption of lock acquisition
The read lock and write lock both support interruption during lock
acquisition.

Condition support
The write lock provides a Condition implementation that
behaves in the same way, with respect to the write lock, as the
Condition implementation provided by
ReentrantLock.newCondition() does for ReentrantLock.
This Condition can, of course, only be used with the write lock.

The read lock does not support a Condition and
readLock().newCondition() throws
UnsupportedOperationException.

Instrumentation
This class supports methods to determine whether locks
are held or contended. These methods are designed for monitoring
system state, not for synchronization control.


Serialization of this class behaves in the same way as built-in
locks: a deserialized lock is in the unlocked state, regardless of
its state when serialized.

Sample usages. Here is a code sketch showing how to perform
lock downgrading after updating a cache (exception handling is
particularly tricky when handling multiple locks in a non-nested
fashion):



class CachedData {
  Object data;
  volatile boolean cacheValid;
  final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();

  void processCachedData() {
    rwl.readLock().lock();
    if (!cacheValid) {
      // Must release read lock before acquiring write lock
      rwl.readLock().unlock();
      rwl.writeLock().lock();
      try {
        // Recheck state because another thread might have
        // acquired write lock and changed state before we did.
        if (!cacheValid) {
          data = ...
          cacheValid = true;
        }
        // Downgrade by acquiring read lock before releasing write lock
        rwl.readLock().lock();
      } finally {
        rwl.writeLock().unlock(); // Unlock write, still hold read
      }
    }

    try {
      use(data);
    } finally {
      rwl.readLock().unlock();
    }
  }
}

ReentrantReadWriteLocks can be used to improve concurrency in some
uses of some kinds of Collections. This is typically worthwhile
only when the collections are expected to be large, accessed by
more reader threads than writer threads, and entail operations with
overhead that outweighs synchronization overhead. For example, here
is a class using a TreeMap that is expected to be large and
concurrently accessed.



class RWDictionary {
  private final Map<String, Data> m = new TreeMap<String, Data>();
  private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
  private final Lock r = rwl.readLock();
  private final Lock w = rwl.writeLock();

  public Data get(String key) {
    r.lock();
    try { return m.get(key); }
    finally { r.unlock(); }
  }
  public String[] allKeys() {
    r.lock();
    try { return m.keySet().toArray(); }
    finally { r.unlock(); }
  }
  public Data put(String key, Data value) {
    w.lock();
    try { return m.put(key, value); }
    finally { w.unlock(); }
  }
  public void clear() {
    w.lock();
    try { m.clear(); }
    finally { w.unlock(); }
  }
}

Implementation Notes

This lock supports a maximum of 65535 recursive write locks
and 65535 read locks. Attempts to exceed these limits result in
Error throws from locking methods.

The lock returned by method ReentrantReadWriteLock.readLock().

The lock returned by method ReentrantReadWriteLock.writeLock().

A capability-based lock with three modes for controlling read/write
access.  The state of a StampedLock consists of a version and mode.
Lock acquisition methods return a stamp that represents and
controls access with respect to a lock state; "try" versions of
these methods may instead return the special value zero to
represent failure to acquire access. Lock release and conversion
methods require stamps as arguments, and fail if they do not match
the state of the lock. The three modes are:



 Writing. Method writeLock() possibly blocks
  waiting for exclusive access, returning a stamp that can be used
  in method unlockWrite(long) to release the lock. Untimed and
  timed versions of tryWriteLock are also provided. When
  the lock is held in write mode, no read locks may be obtained,
  and all optimistic read validations will fail.

 Reading. Method readLock() possibly blocks
  waiting for non-exclusive access, returning a stamp that can be
  used in method unlockRead(long) to release the lock. Untimed
  and timed versions of tryReadLock are also provided.

 Optimistic Reading. Method tryOptimisticRead()
  returns a non-zero stamp only if the lock is not currently held
  in write mode. Method validate(long) returns true if the lock
  has not been acquired in write mode since obtaining a given
  stamp.  This mode can be thought of as an extremely weak version
  of a read-lock, that can be broken by a writer at any time.  The
  use of optimistic mode for short read-only code segments often
  reduces contention and improves throughput.  However, its use is
  inherently fragile.  Optimistic read sections should only read
  fields and hold them in local variables for later use after
  validation. Fields read while in optimistic mode may be wildly
  inconsistent, so usage applies only when you are familiar enough
  with data representations to check consistency and/or repeatedly
  invoke method validate().  For example, such steps are
  typically required when first reading an object or array
  reference, and then accessing one of its fields, elements or
  methods.



This class also supports methods that conditionally provide
conversions across the three modes. For example, method tryConvertToWriteLock(long) attempts to "upgrade" a mode, returning
a valid write stamp if (1) already in writing mode (2) in reading
mode and there are no other readers or (3) in optimistic mode and
the lock is available. The forms of these methods are designed to
help reduce some of the code bloat that otherwise occurs in
retry-based designs.

StampedLocks are designed for use as internal utilities in the
development of thread-safe components. Their use relies on
knowledge of the internal properties of the data, objects, and
methods they are protecting.  They are not reentrant, so locked
bodies should not call other unknown methods that may try to
re-acquire locks (although you may pass a stamp to other methods
that can use or convert it).  The use of read lock modes relies on
the associated code sections being side-effect-free.  Unvalidated
optimistic read sections cannot call methods that are not known to
tolerate potential inconsistencies.  Stamps use finite
representations, and are not cryptographically secure (i.e., a
valid stamp may be guessable). Stamp values may recycle after (no
sooner than) one year of continuous operation. A stamp held without
use or validation for longer than this period may fail to validate
correctly.  StampedLocks are serializable, but always deserialize
into initial unlocked state, so they are not useful for remote
locking.

The scheduling policy of StampedLock does not consistently
prefer readers over writers or vice versa.  All "try" methods are
best-effort and do not necessarily conform to any scheduling or
fairness policy. A zero return from any "try" method for acquiring
or converting locks does not carry any information about the state
of the lock; a subsequent invocation may succeed.

Because it supports coordinated usage across multiple lock
modes, this class does not directly implement the Lock or
ReadWriteLock interfaces. However, a StampedLock may be
viewed asReadLock(), asWriteLock(), or asReadWriteLock() in applications requiring only the associated
set of functionality.

Sample Usage. The following illustrates some usage idioms
in a class that maintains simple two-dimensional points. The sample
code illustrates some try/catch conventions even though they are
not strictly needed here because no exceptions can occur in their
bodies.



class Point {
  private double x, y;
  private final StampedLock sl = new StampedLock();

  void move(double deltaX, double deltaY) { // an exclusively locked method
    long stamp = sl.writeLock();
    try {
      x = deltaX;
      y = deltaY;
    } finally {
      sl.unlockWrite(stamp);
    }
  }

  double distanceFromOrigin() { // A read-only method
    long stamp = sl.tryOptimisticRead();
    double currentX = x, currentY = y;
    if (!sl.validate(stamp)) {
       stamp = sl.readLock();
       try {
         currentX = x;
         currentY = y;
       } finally {
          sl.unlockRead(stamp);
       }
    }
    return Math.sqrt(currentX * currentX  currentY * currentY);
  }

  void moveIfAtOrigin(double newX, double newY) { // upgrade
    // Could instead start with optimistic, not read mode
    long stamp = sl.readLock();
    try {
      while (x == 0.0 && y == 0.0) {
        long ws = sl.tryConvertToWriteLock(stamp);
        if (ws != 0L) {
          stamp = ws;
          x = newX;
          y = newY;
          break;
        }
        else {
          sl.unlockRead(stamp);
          stamp = sl.writeLock();
        }
      }
    } finally {
      sl.unlock(stamp);
    }
  }
}

A reusable synchronization barrier, similar in functionality to
CyclicBarrier and
CountDownLatch
but supporting more flexible usage.

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

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



   Arrival. Methods arrive() and
      arriveAndDeregister() record arrival.  These methods
      do not block, but return an associated arrival phase
      number; that is, the phase number of the phaser to which
      the arrival applied. When the final party for a given phase
      arrives, an optional action is performed and the phase
      advances.  These actions are performed by the party
      triggering a phase advance, and are arranged by overriding
      method onAdvance(int, int), which also controls
      termination. Overriding this method is similar to, but more
      flexible than, providing a barrier action to a CyclicBarrier.

   Waiting. Method awaitAdvance(int) requires an
      argument indicating an arrival phase number, and returns when
      the phaser advances to (or is already at) a different phase.
      Unlike similar constructions using CyclicBarrier,
      method awaitAdvance continues to wait even if the
      waiting thread is interrupted. Interruptible and timeout
      versions are also available, but exceptions encountered while
      tasks wait interruptibly or with timeout do not change the
      state of the phaser. If necessary, you can perform any
      associated recovery within handlers of those exceptions,
      often after invoking forceTermination.  Phasers may
      also be used by tasks executing in a ForkJoinPool,
      which will ensure sufficient parallelism to execute tasks
      when others are blocked waiting for a phase to advance.



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

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

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

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

Sample usages:

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



void runTasks(List<Runnable> tasks) {
  final Phaser phaser = new Phaser(1); // "1" to register self
  // create and start threads
  for (final Runnable task : tasks) {
    phaser.register();
    new Thread() {
      public void run() {
        phaser.arriveAndAwaitAdvance(); // await all creation
        task.run();
      }
    }.start();
  }

  // allow threads to start and deregister self
  phaser.arriveAndDeregister();
}

One way to cause a set of threads to repeatedly perform actions
for a given number of iterations is to override onAdvance:



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

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


  // ...
  phaser.register();
  while (!phaser.isTerminated())
    phaser.arriveAndAwaitAdvance();

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



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


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



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

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

Implementation notes: This implementation restricts the
maximum number of parties to 65535. Attempts to register additional
parties result in IllegalStateException. However, you can and
should create tiered phasers to accommodate arbitrarily large sets
of participants.

An unbounded java.util.concurrent.blocking queue that uses
the same ordering rules as class PriorityQueue and supplies
blocking retrieval operations.  While this queue is logically
unbounded, attempted additions may fail due to resource exhaustion
(causing OutOfMemoryError). This class does not permit
null elements.  A priority queue relying on java.lang.natural ordering also does not permit insertion of
non-comparable objects (doing so results in
ClassCastException).

This class and its iterator implement all of the
optional methods of the Collection and Iterator interfaces.  The Iterator provided in method iterator() is not guaranteed to traverse the elements of
the PriorityBlockingQueue in any particular order. If you need
ordered traversal, consider using
Arrays.sort(pq.toArray()).  Also, method drainTo
can be used to remove some or all elements in priority
order and place them in another collection.

Operations on this class make no guarantees about the ordering
of elements with equal priority. If you need to enforce an
ordering, you can define custom classes or comparators that use a
secondary key to break ties in primary priority values.  For
example, here is a class that applies first-in-first-out
tie-breaking to comparable elements. To use it, you would insert a
new FIFOEntry(anEntry) instead of a plain entry object.



class FIFOEntry<E extends Comparable<? super E>>
    implements Comparable<FIFOEntry<E>> {
  static final AtomicLong seq = new AtomicLong(0);
  final long seqNum;
  final E entry;
  public FIFOEntry(E entry) {
    seqNum = seq.getAndIncrement();
    this.entry = entry;
  }
  public E getEntry() { return entry; }
  public int compareTo(FIFOEntry<E> other) {
    int res = entry.compareTo(other.entry);
    if (res == 0 && other.entry != this.entry)
      res = (seqNum < other.seqNum ? -1 : 1);
    return res;
  }
}

This class is a member of the

Java Collections Framework.

A recursive resultless ForkJoinTask.  This class
establishes conventions to parameterize resultless actions as
Void ForkJoinTasks. Because null is the
only valid value of type Void, methods such as join
always return null upon completion.

Sample Usages. Here is a simple but complete ForkJoin
sort that sorts a given long[] array:



static class SortTask extends RecursiveAction {
  final long[] array; final int lo, hi;
  SortTask(long[] array, int lo, int hi) {
    this.array = array; this.lo = lo; this.hi = hi;
  }
  SortTask(long[] array) { this(array, 0, array.length); }
  protected void compute() {
    if (hi - lo < THRESHOLD)
      sortSequentially(lo, hi);
    else {
      int mid = (lo  hi) >>> 1;
      invokeAll(new SortTask(array, lo, mid),
                new SortTask(array, mid, hi));
      merge(lo, mid, hi);
    }
  }
  // implementation details follow:
  static final int THRESHOLD = 1000;
  void sortSequentially(int lo, int hi) {
    Arrays.sort(array, lo, hi);
  }
  void merge(int lo, int mid, int hi) {
    long[] buf = Arrays.copyOfRange(array, lo, mid);
    for (int i = 0, j = lo, k = mid; i < buf.length; j++)
      array[j] = (k == hi || buf[i] < array[k]) ?
        buf[i++] : array[k++];
  }
}

You could then sort anArray by creating new
SortTask(anArray) and invoking it in a ForkJoinPool.  As a more
concrete simple example, the following task increments each element
of an array:


class IncrementTask extends RecursiveAction {
  final long[] array; final int lo, hi;
  IncrementTask(long[] array, int lo, int hi) {
    this.array = array; this.lo = lo; this.hi = hi;
  }
  protected void compute() {
    if (hi - lo < THRESHOLD) {
      for (int i = lo; i < hi; +i)
        array[i]++;
    }
    else {
      int mid = (lo  hi) >>> 1;
      invokeAll(new IncrementTask(array, lo, mid),
                new IncrementTask(array, mid, hi));
    }
  }
}

The following example illustrates some refinements and idioms
that may lead to better performance: RecursiveActions need not be
fully recursive, so long as they maintain the basic
divide-and-conquer approach. Here is a class that sums the squares
of each element of a double array, by subdividing out only the
right-hand-sides of repeated divisions by two, and keeping track of
them with a chain of next references. It uses a dynamic
threshold based on method getSurplusQueuedTaskCount, but
counterbalances potential excess partitioning by directly
performing leaf actions on unstolen tasks rather than further
subdividing.



double sumOfSquares(ForkJoinPool pool, double[] array) {
  int n = array.length;
  Applyer a = new Applyer(array, 0, n, null);
  pool.invoke(a);
  return a.result;
}

class Applyer extends RecursiveAction {
  final double[] array;
  final int lo, hi;
  double result;
  Applyer next; // keeps track of right-hand-side tasks
  Applyer(double[] array, int lo, int hi, Applyer next) {
    this.array = array; this.lo = lo; this.hi = hi;
    this.next = next;
  }

  double atLeaf(int l, int h) {
    double sum = 0;
    for (int i = l; i < h; +i) // perform leftmost base step
      sum = array[i] * array[i];
    return sum;
  }

  protected void compute() {
    int l = lo;
    int h = hi;
    Applyer right = null;
    while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {
      int mid = (l  h) >>> 1;
      right = new Applyer(array, mid, h, right);
      right.fork();
      h = mid;
    }
    double sum = atLeaf(l, h);
    while (right != null) {
      if (right.tryUnfork()) // directly calculate if not stolen
        sum = right.atLeaf(right.lo, right.hi);
      else {
        right.join();
        sum = right.result;
      }
      right = right.next;
    }
    result = sum;
  }
}

A recursive result-bearing ForkJoinTask.

For a classic example, here is a task computing Fibonacci numbers:



class Fibonacci extends RecursiveTask<Integer> {
  final int n;
  Fibonacci(int n) { this.n = n; }
  Integer compute() {
    if (n <= 1)
      return n;
    Fibonacci f1 = new Fibonacci(n - 1);
    f1.fork();
    Fibonacci f2 = new Fibonacci(n - 2);
    return f2.compute()  f1.join();
  }
}

However, besides being a dumb way to compute Fibonacci functions
(there is a simple fast linear algorithm that you'd use in
practice), this is likely to perform poorly because the smallest
subtasks are too small to be worthwhile splitting up. Instead, as
is the case for nearly all fork/join applications, you'd pick some
minimum granularity size (for example 10 here) for which you always
sequentially solve rather than subdividing.

Exception thrown by an Executor when a task cannot be
accepted for execution.

A handler for tasks that cannot be executed by a ThreadPoolExecutor.

A Future that is Runnable. Successful execution of
the run method causes completion of the Future
and allows access to its results.

A ScheduledFuture that is Runnable. Successful
execution of the run method causes completion of the
Future and allows access to its results.

An ExecutorService that can schedule commands to run after a given
delay, or to execute periodically.

The schedule methods create tasks with various delays
and return a task object that can be used to cancel or check
execution. The scheduleAtFixedRate and
scheduleWithFixedDelay methods create and execute tasks
that run periodically until cancelled.

Commands submitted using the Executor.execute(Runnable)
and ExecutorService submit methods are scheduled
with a requested delay of zero. Zero and negative delays (but not
periods) are also allowed in schedule methods, and are
treated as requests for immediate execution.

All schedule methods accept relative delays and
periods as arguments, not absolute times or dates. It is a simple
matter to transform an absolute time represented as a Date to the required form. For example, to schedule at
a certain future date, you can use: schedule(task,
date.getTime() - System.currentTimeMillis(),
TimeUnit.MILLISECONDS). Beware however that expiration of a
relative delay need not coincide with the current Date at
which the task is enabled due to network time synchronization
protocols, clock drift, or other factors.

The Executors class provides convenient factory methods for
the ScheduledExecutorService implementations provided in this package.

Usage Example

Here is a class with a method that sets up a ScheduledExecutorService
to beep every ten seconds for an hour:



import static java.util.concurrent.TimeUnit.*;
class BeeperControl {
  private final ScheduledExecutorService scheduler =
    Executors.newScheduledThreadPool(1);

  public void beepForAnHour() {
    final Runnable beeper = new Runnable() {
      public void run() { System.out.println("beep"); }
    };
    final ScheduledFuture<?> beeperHandle =
      scheduler.scheduleAtFixedRate(beeper, 10, 10, SECONDS);
    scheduler.schedule(new Runnable() {
      public void run() { beeperHandle.cancel(true); }
    }, 60 * 60, SECONDS);
  }
}

A delayed result-bearing action that can be cancelled.
Usually a scheduled future is the result of scheduling
a task with a ScheduledExecutorService.

A ThreadPoolExecutor that can additionally schedule
commands to run after a given delay, or to execute
periodically. This class is preferable to Timer
when multiple worker threads are needed, or when the additional
flexibility or capabilities of ThreadPoolExecutor (which
this class extends) are required.

Delayed tasks execute no sooner than they are enabled, but
without any real-time guarantees about when, after they are
enabled, they will commence. Tasks scheduled for exactly the same
execution time are enabled in first-in-first-out (FIFO) order of
submission.

When a submitted task is cancelled before it is run, execution
is suppressed. By default, such a cancelled task is not
automatically removed from the work queue until its delay
elapses. While this enables further inspection and monitoring, it
may also cause unbounded retention of cancelled tasks. To avoid
this, set setRemoveOnCancelPolicy(boolean) to true, which
causes tasks to be immediately removed from the work queue at
time of cancellation.

Successive executions of a task scheduled via
scheduleAtFixedRate or
scheduleWithFixedDelay do not overlap. While different
executions may be performed by different threads, the effects of
prior executions happen-before
those of subsequent ones.

While this class inherits from ThreadPoolExecutor, a few
of the inherited tuning methods are not useful for it. In
particular, because it acts as a fixed-sized pool using
corePoolSize threads and an unbounded queue, adjustments
to maximumPoolSize have no useful effect. Additionally, it
is almost never a good idea to set corePoolSize to zero or
use allowCoreThreadTimeOut because this may leave the pool
without threads to handle tasks once they become eligible to run.

Extension notes: This class overrides the
execute and
submit
methods to generate internal ScheduledFuture objects to
control per-task delays and scheduling.  To preserve
functionality, any further overrides of these methods in
subclasses must invoke superclass versions, which effectively
disables additional task customization.  However, this class
provides alternative protected extension method
decorateTask (one version each for Runnable and
Callable) that can be used to customize the concrete task
types used to execute commands entered via execute,
submit, schedule, scheduleAtFixedRate,
and scheduleWithFixedDelay.  By default, a
ScheduledThreadPoolExecutor uses a task type extending
FutureTask. However, this may be modified or replaced using
subclasses of the form:



public class CustomScheduledExecutor extends ScheduledThreadPoolExecutor {

  static class CustomTask<V> implements RunnableScheduledFuture<V> { ... }

  protected <V> RunnableScheduledFuture<V> decorateTask(
               Runnable r, RunnableScheduledFuture<V> task) {
      return new CustomTask<V>(r, task);
  }

  protected <V> RunnableScheduledFuture<V> decorateTask(
               Callable<V> c, RunnableScheduledFuture<V> task) {
      return new CustomTask<V>(c, task);
  }
  // ... add constructors, etc.
}

A counting semaphore.  Conceptually, a semaphore maintains a set of
permits.  Each acquire() blocks if necessary until a permit is
available, and then takes it.  Each release() adds a permit,
potentially releasing a blocking acquirer.
However, no actual permit objects are used; the Semaphore just
keeps a count of the number available and acts accordingly.

Semaphores are often used to restrict the number of threads than can
access some (physical or logical) resource. For example, here is
a class that uses a semaphore to control access to a pool of items:


class Pool {
  private static final int MAX_AVAILABLE = 100;
  private final Semaphore available = new Semaphore(MAX_AVAILABLE, true);

  public Object getItem() throws InterruptedException {
    available.acquire();
    return getNextAvailableItem();
  }

  public void putItem(Object x) {
    if (markAsUnused(x))
      available.release();
  }

  // Not a particularly efficient data structure; just for demo

  protected Object[] items = ... whatever kinds of items being managed
  protected boolean[] used = new boolean[MAX_AVAILABLE];

  protected synchronized Object getNextAvailableItem() {
    for (int i = 0; i < MAX_AVAILABLE; +i) {
      if (!used[i]) {
         used[i] = true;
         return items[i];
      }
    }
    return null; // not reached
  }

  protected synchronized boolean markAsUnused(Object item) {
    for (int i = 0; i < MAX_AVAILABLE; +i) {
      if (item == items[i]) {
         if (used[i]) {
           used[i] = false;
           return true;
         } else
           return false;
      }
    }
    return false;
  }
}

Before obtaining an item each thread must acquire a permit from
the semaphore, guaranteeing that an item is available for use. When
the thread has finished with the item it is returned back to the
pool and a permit is returned to the semaphore, allowing another
thread to acquire that item.  Note that no synchronization lock is
held when acquire() is called as that would prevent an item
from being returned to the pool.  The semaphore encapsulates the
synchronization needed to restrict access to the pool, separately
from any synchronization needed to maintain the consistency of the
pool itself.

A semaphore initialized to one, and which is used such that it
only has at most one permit available, can serve as a mutual
exclusion lock.  This is more commonly known as a binary
semaphore, because it only has two states: one permit
available, or zero permits available.  When used in this way, the
binary semaphore has the property (unlike many Lock
implementations), that the "lock" can be released by a
thread other than the owner (as semaphores have no notion of
ownership).  This can be useful in some specialized contexts, such
as deadlock recovery.

 The constructor for this class optionally accepts a
fairness parameter. When set false, this class makes no
guarantees about the order in which threads acquire permits. In
particular, barging is permitted, that is, a thread
invoking acquire() can be allocated a permit ahead of a
thread that has been waiting - logically the new thread places itself at
the head of the queue of waiting threads. When fairness is set true, the
semaphore guarantees that threads invoking any of the acquire methods are selected to obtain permits in the order in
which their invocation of those methods was processed
(first-in-first-out; FIFO). Note that FIFO ordering necessarily
applies to specific internal points of execution within these
methods.  So, it is possible for one thread to invoke
acquire before another, but reach the ordering point after
the other, and similarly upon return from the method.
Also note that the untimed tryAcquire methods do not
honor the fairness setting, but will take any permits that are
available.

Generally, semaphores used to control resource access should be
initialized as fair, to ensure that no thread is starved out from
accessing a resource. When using semaphores for other kinds of
synchronization control, the throughput advantages of non-fair
ordering often outweigh fairness considerations.

This class also provides convenience methods to acquire and release multiple
permits at a time.  Beware of the increased risk of indefinite
postponement when these methods are used without fairness set true.

Memory consistency effects: Actions in a thread prior to calling
a "release" method such as release()
happen-before
actions following a successful "acquire" method such as acquire()
in another thread.

A java.util.concurrent.blocking queue in which each insert
operation must wait for a corresponding remove operation by another
thread, and vice versa.  A synchronous queue does not have any
internal capacity, not even a capacity of one.  You cannot
peek at a synchronous queue because an element is only
present when you try to remove it; you cannot insert an element
(using any method) unless another thread is trying to remove it;
you cannot iterate as there is nothing to iterate.  The
head of the queue is the element that the first queued
inserting thread is trying to add to the queue; if there is no such
queued thread then no element is available for removal and
poll() will return null.  For purposes of other
Collection methods (for example contains), a
SynchronousQueue acts as an empty collection.  This queue
does not permit null elements.

Synchronous queues are similar to rendezvous channels used in
CSP and Ada. They are well suited for handoff designs, in which an
object running in one thread must sync up with an object running
in another thread in order to hand it some information, event, or
task.

This class supports an optional fairness policy for ordering
waiting producer and consumer threads.  By default, this ordering
is not guaranteed. However, a queue constructed with fairness set
to true grants threads access in FIFO order.

This class and its iterator implement all of the
optional methods of the Collection and Iterator interfaces.

This class is a member of the

Java Collections Framework.

An object that creates new threads on demand.  Using thread factories
removes hardwiring of calls to new Thread,
enabling applications to use special thread subclasses, priorities, etc.


The simplest implementation of this interface is just:


class SimpleThreadFactory implements ThreadFactory {
  public Thread newThread(Runnable r) {
    return new Thread(r);
  }
}

The Executors.defaultThreadFactory() method provides a more
useful simple implementation, that sets the created thread context
to known values before returning it.

A random number generator isolated to the current thread.  Like the
global Random generator used by the Math class, a ThreadLocalRandom is initialized
with an internally generated seed that may not otherwise be
modified. When applicable, use of ThreadLocalRandom rather
than shared Random objects in concurrent programs will
typically encounter much less overhead and contention.  Use of
ThreadLocalRandom is particularly appropriate when multiple
tasks (for example, each a ForkJoinTask) use random numbers
in parallel in thread pools.

Usages of this class should typically be of the form:
ThreadLocalRandom.current().nextX(...) (where
X is Int, Long, etc).
When all usages are of this form, it is never possible to
accidently share a ThreadLocalRandom across multiple threads.

This class also provides additional commonly used bounded random
generation methods.

Instances of ThreadLocalRandom are not cryptographically
secure.  Consider instead using SecureRandom
in security-sensitive applications. Additionally,
default-constructed instances do not use a cryptographically random
seed unless the system property
java.util.secureRandomSeed is set to true.

An ExecutorService that executes each submitted task using
one of possibly several pooled threads, normally configured
using Executors factory methods.

Thread pools address two different problems: they usually
provide improved performance when executing large numbers of
asynchronous tasks, due to reduced per-task invocation overhead,
and they provide a means of bounding and managing the resources,
including threads, consumed when executing a collection of tasks.
Each ThreadPoolExecutor also maintains some basic
statistics, such as the number of completed tasks.

To be useful across a wide range of contexts, this class
provides many adjustable parameters and extensibility
hooks. However, programmers are urged to use the more convenient
Executors factory methods Executors.newCachedThreadPool() (unbounded thread pool, with
automatic thread reclamation), Executors.newFixedThreadPool(int)
(fixed size thread pool) and Executors.newSingleThreadExecutor() (single background thread), that
preconfigure settings for the most common usage
scenarios. Otherwise, use the following guide when manually
configuring and tuning this class:



Core and maximum pool sizes

A ThreadPoolExecutor will automatically adjust the
pool size (see getPoolSize())
according to the bounds set by
corePoolSize (see getCorePoolSize()) and
maximumPoolSize (see getMaximumPoolSize()).

When a new task is submitted in method execute(Runnable),
and fewer than corePoolSize threads are running, a new thread is
created to handle the request, even if other worker threads are
idle.  If there are more than corePoolSize but less than
maximumPoolSize threads running, a new thread will be created only
if the queue is full.  By setting corePoolSize and maximumPoolSize
the same, you create a fixed-size thread pool. By setting
maximumPoolSize to an essentially unbounded value such as Integer.MAX_VALUE, you allow the pool to accommodate an arbitrary
number of concurrent tasks. Most typically, core and maximum pool
sizes are set only upon construction, but they may also be changed
dynamically using setCorePoolSize(int) and setMaximumPoolSize(int).

On-demand construction

By default, even core threads are initially created and
started only when new tasks arrive, but this can be overridden
dynamically using method prestartCoreThread() or prestartAllCoreThreads().  You probably want to prestart threads if
you construct the pool with a non-empty queue.

Creating new threads

New threads are created using a ThreadFactory.  If not
otherwise specified, a Executors.defaultThreadFactory() is
used, that creates threads to all be in the same ThreadGroup and with the same NORM_PRIORITY priority and
non-daemon status. By supplying a different ThreadFactory, you can
alter the thread's name, thread group, priority, daemon status,
etc. If a ThreadFactory fails to create a thread when asked
by returning null from newThread, the executor will
continue, but might not be able to execute any tasks. Threads
should possess the "modifyThread" RuntimePermission. If
worker threads or other threads using the pool do not possess this
permission, service may be degraded: configuration changes may not
take effect in a timely manner, and a shutdown pool may remain in a
state in which termination is possible but not completed.

Keep-alive times

If the pool currently has more than corePoolSize threads,
excess threads will be terminated if they have been idle for more
than the keepAliveTime (see getKeepAliveTime(TimeUnit)).
This provides a means of reducing resource consumption when the
pool is not being actively used. If the pool becomes more active
later, new threads will be constructed. This parameter can also be
changed dynamically using method setKeepAliveTime(long,
TimeUnit).  Using a value of Long.MAX_VALUE TimeUnit.NANOSECONDS effectively disables idle threads from ever
terminating prior to shut down. By default, the keep-alive policy
applies only when there are more than corePoolSize threads. But
method allowCoreThreadTimeOut(boolean) can be used to
apply this time-out policy to core threads as well, so long as the
keepAliveTime value is non-zero.

Queuing

Any BlockingQueue may be used to transfer and hold
submitted tasks.  The use of this queue interacts with pool sizing:



 If fewer than corePoolSize threads are running, the Executor
always prefers adding a new thread
rather than queuing.

 If corePoolSize or more threads are running, the Executor
always prefers queuing a request rather than adding a new
thread.

 If a request cannot be queued, a new thread is created unless
this would exceed maximumPoolSize, in which case, the task will be
rejected.



There are three general strategies for queuing:


  Direct handoffs. A good default choice for a work
queue is a SynchronousQueue that hands off tasks to threads
without otherwise holding them. Here, an attempt to queue a task
will fail if no threads are immediately available to run it, so a
new thread will be constructed. This policy avoids lockups when
handling sets of requests that might have internal dependencies.
Direct handoffs generally require unbounded maximumPoolSizes to
avoid rejection of new submitted tasks. This in turn admits the
possibility of unbounded thread growth when commands continue to
arrive on average faster than they can be processed.

 Unbounded queues. Using an unbounded queue (for
example a LinkedBlockingQueue without a predefined
capacity) will cause new tasks to wait in the queue when all
corePoolSize threads are busy. Thus, no more than corePoolSize
threads will ever be created. (And the value of the maximumPoolSize
therefore doesn't have any effect.)  This may be appropriate when
each task is completely independent of others, so tasks cannot
affect each others execution; for example, in a web page server.
While this style of queuing can be useful in smoothing out
transient bursts of requests, it admits the possibility of
unbounded work queue growth when commands continue to arrive on
average faster than they can be processed.

Bounded queues. A bounded queue (for example, an
ArrayBlockingQueue) helps prevent resource exhaustion when
used with finite maximumPoolSizes, but can be more difficult to
tune and control.  Queue sizes and maximum pool sizes may be traded
off for each other: Using large queues and small pools minimizes
CPU usage, OS resources, and context-switching overhead, but can
lead to artificially low throughput.  If tasks frequently block (for
example if they are I/O bound), a system may be able to schedule
time for more threads than you otherwise allow. Use of small queues
generally requires larger pool sizes, which keeps CPUs busier but
may encounter unacceptable scheduling overhead, which also
decreases throughput.





Rejected tasks

New tasks submitted in method execute(Runnable) will be
rejected when the Executor has been shut down, and also when
the Executor uses finite bounds for both maximum threads and work queue
capacity, and is saturated.  In either case, the execute method
invokes the RejectedExecutionHandler.rejectedExecution(Runnable, ThreadPoolExecutor)
method of its RejectedExecutionHandler.  Four predefined handler
policies are provided:



 In the default ThreadPoolExecutor.AbortPolicy, the
handler throws a runtime RejectedExecutionException upon
rejection.

 In ThreadPoolExecutor.CallerRunsPolicy, the thread
that invokes execute itself runs the task. This provides a
simple feedback control mechanism that will slow down the rate that
new tasks are submitted.

 In ThreadPoolExecutor.DiscardPolicy, a task that
cannot be executed is simply dropped.

In ThreadPoolExecutor.DiscardOldestPolicy, if the
executor is not shut down, the task at the head of the work queue
is dropped, and then execution is retried (which can fail again,
causing this to be repeated.)



It is possible to define and use other kinds of RejectedExecutionHandler classes. Doing so requires some care
especially when policies are designed to work only under particular
capacity or queuing policies.

Hook methods

This class provides protected overridable
beforeExecute(Thread, Runnable) and
afterExecute(Runnable, Throwable) methods that are called
before and after execution of each task.  These can be used to
manipulate the execution environment; for example, reinitializing
ThreadLocals, gathering statistics, or adding log entries.
Additionally, method terminated() can be overridden to perform
any special processing that needs to be done once the Executor has
fully terminated.

If hook or callback methods throw exceptions, internal worker
threads may in turn fail and abruptly terminate.

Queue maintenance

Method getQueue() allows access to the work queue
for purposes of monitoring and debugging.  Use of this method for
any other purpose is strongly discouraged.  Two supplied methods,
remove(Runnable) and purge() are available to
assist in storage reclamation when large numbers of queued tasks
become cancelled.

Finalization

A pool that is no longer referenced in a program AND
has no remaining threads will be shutdown automatically. If
you would like to ensure that unreferenced pools are reclaimed even
if users forget to call shutdown(), then you must arrange
that unused threads eventually die, by setting appropriate
keep-alive times, using a lower bound of zero core threads and/or
setting allowCoreThreadTimeOut(boolean).



Extension example. Most extensions of this class
override one or more of the protected hook methods. For example,
here is a subclass that adds a simple pause/resume feature:



class PausableThreadPoolExecutor extends ThreadPoolExecutor {
  private boolean isPaused;
  private ReentrantLock pauseLock = new ReentrantLock();
  private Condition unpaused = pauseLock.newCondition();

  public PausableThreadPoolExecutor(...) { super(...); }

  protected void beforeExecute(Thread t, Runnable r) {
    super.beforeExecute(t, r);
    pauseLock.lock();
    try {
      while (isPaused) unpaused.await();
    } catch (InterruptedException ie) {
      t.interrupt();
    } finally {
      pauseLock.unlock();
    }
  }

  public void pause() {
    pauseLock.lock();
    try {
      isPaused = true;
    } finally {
      pauseLock.unlock();
    }
  }

  public void resume() {
    pauseLock.lock();
    try {
      isPaused = false;
      unpaused.signalAll();
    } finally {
      pauseLock.unlock();
    }
  }
}

A handler for rejected tasks that throws a
RejectedExecutionException.

A handler for rejected tasks that runs the rejected task
directly in the calling thread of the execute method,
unless the executor has been shut down, in which case the task
is discarded.

A handler for rejected tasks that discards the oldest unhandled
request and then retries execute, unless the executor
is shut down, in which case the task is discarded.

A handler for rejected tasks that silently discards the
rejected task.

Exception thrown when a blocking operation times out.  Blocking
operations for which a timeout is specified need a means to
indicate that the timeout has occurred. For many such operations it
is possible to return a value that indicates timeout; when that is
not possible or desirable then TimeoutException should be
declared and thrown.

A BlockingQueue in which producers may wait for consumers
to receive elements.  A TransferQueue may be useful for
example in message passing applications in which producers
sometimes (using method transfer(E)) await receipt of
elements by consumers invoking take or poll, while
at other times enqueue elements (via method put) without
waiting for receipt.
Non-blocking and
time-out versions of
tryTransfer are also available.
A TransferQueue may also be queried, via hasWaitingConsumer(), whether there are any threads waiting for
items, which is a converse analogy to a peek operation.

Like other blocking queues, a TransferQueue may be
capacity bounded.  If so, an attempted transfer operation may
initially block waiting for available space, and/or subsequently
block waiting for reception by a consumer.  Note that in a queue
with zero capacity, such as SynchronousQueue, put
and transfer are effectively synonymous.

This interface is a member of the

Java Collections Framework.