import java.util.Random;

import java.util.concurrent.locks.Condition;

     * Preference rules give first priority to processing tasks from

     * their own queues (LIFO or FIFO, depending on mode), then to

     * randomized FIFO steals of tasks in other worker queues, and

     * lastly to new submissions.

     *

     * The main throughput advantages of work-stealing stem from

     * decentralized control -- workers mostly take tasks from

     * themselves or each other. We cannot negate this in the

     * implementation of other management responsibilities. The main

     * tactic for avoiding bottlenecks is packing nearly all

     * essentially atomic control state into a single 64bit volatile

     * variable ("ctl"). This variable is read on the order of 10-100

     * times as often as it is modified (always via CAS). (There is

     * some additional control state, for example variable "shutdown"

     * for which we can cope with uncoordinated updates.)  This

     * streamlines synchronization and control at the expense of messy

     * constructions needed to repack status bits upon updates.

     * Updates tend not to contend with each other except during

     * bursts while submitted tasks begin or end.  In some cases when

     * they do contend, threads can instead do something else

     * (usually, scan for tasks) until contention subsides.

     *

     * To enable packing, we restrict maximum parallelism to (1<<15)-1

     * (which is far in excess of normal operating range) to allow

     * ids, counts, and their negations (used for thresholding) to fit

     * into 16bit fields.

     *

     * Recording Workers.  Workers are recorded in the "workers" array

     * that is created upon pool construction and expanded if (rarely)

     * necessary.  This is an array as opposed to some other data

     * structure to support index-based random steals by workers.

     * Updates to the array recording new workers and unrecording

     * terminated ones are protected from each other by a seqLock

     * (scanGuard) but the array is otherwise concurrently readable,

     * and accessed directly by workers. To simplify index-based

     * operations, the array size is always a power of two, and all

     * readers must tolerate null slots. To avoid flailing during

     * start-up, the array is presized to hold twice #parallelism

     * workers (which is unlikely to need further resizing during

     * execution). But to avoid dealing with so many null slots,

     * variable scanGuard includes a mask for the nearest power of two

     * that contains all current workers.  All worker thread creation

     * is on-demand, triggered by task submissions, replacement of

     * terminated workers, and/or compensation for blocked

     * workers. However, all other support code is set up to work with

     * other policies.  To ensure that we do not hold on to worker

     * references that would prevent GC, ALL accesses to workers are

     * via indices into the workers array (which is one source of some

     * of the messy code constructions here). In essence, the workers

     * array serves as a weak reference mechanism. Thus for example

     * the wait queue field of ctl stores worker indices, not worker

     * references.  Access to the workers in associated methods (for

     * example signalWork) must both index-check and null-check the

     * IDs. All such accesses ignore bad IDs by returning out early

     * from what they are doing, since this can only be associated

     * with termination, in which case it is OK to give up.

     * All uses of the workers array, as well as queue arrays, check

     * that the array is non-null (even if previously non-null). This

     * allows nulling during termination, which is currently not

     * necessary, but remains an option for resource-revocation-based

     * shutdown schemes.

     *

     * Wait Queuing. Unlike HPC work-stealing frameworks, we cannot

     * let workers spin indefinitely scanning for tasks when none can

     * be found immediately, and we cannot start/resume workers unless

     * there appear to be tasks available.  On the other hand, we must

     * quickly prod them into action when new tasks are submitted or

     * generated.  We park/unpark workers after placing in an event

     * wait queue when they cannot find work. This "queue" is actually

     * a simple Treiber stack, headed by the "id" field of ctl, plus a

     * 15bit counter value to both wake up waiters (by advancing their

     * count) and avoid ABA effects. Successors are held in worker

     * field "nextWait".  Queuing deals with several intrinsic races,

     * mainly that a task-producing thread can miss seeing (and

     * signalling) another thread that gave up looking for work but

     * has not yet entered the wait queue. We solve this by requiring

     * a full sweep of all workers both before (in scan()) and after

     * (in tryAwaitWork()) a newly waiting worker is added to the wait

     * queue. During a rescan, the worker might release some other

     * queued worker rather than itself, which has the same net

     * effect. Because enqueued workers may actually be rescanning

     * rather than waiting, we set and clear the "parked" field of

     * ForkJoinWorkerThread to reduce unnecessary calls to unpark.

     * (Use of the parked field requires a secondary recheck to avoid

     * missed signals.)

     *

     * Signalling.  We create or wake up workers only when there

     * appears to be at least one task they might be able to find and

     * execute.  When a submission is added or another worker adds a

     * task to a queue that previously had two or fewer tasks, they

     * signal waiting workers (or trigger creation of new ones if

     * fewer than the given parallelism level -- see signalWork).

     * These primary signals are buttressed by signals during rescans

     * as well as those performed when a worker steals a task and

     * notices that there are more tasks too; together these cover the

     * signals needed in cases when more than two tasks are pushed

     * but untaken.

     *

     * Trimming workers. To release resources after periods of lack of

     * use, a worker starting to wait when the pool is quiescent will

     * time out and terminate if the pool has remained quiescent for

     * SHRINK_RATE nanosecs. This will slowly propagate, eventually

     * terminating all workers after long periods of non-use.

     *

     * Submissions. External submissions are maintained in an

     * array-based queue that is structured identically to

     * ForkJoinWorkerThread queues except for the use of

     * submissionLock in method addSubmission. Unlike the case for

     * worker queues, multiple external threads can add new

     * submissions, so adding requires a lock.

     *

     * Compensation. Beyond work-stealing support and lifecycle

     * control, the main responsibility of this framework is to take

     * actions when one worker is waiting to join a task stolen (or

     * always held by) another.  Because we are multiplexing many

     * tasks on to a pool of workers, we can't just let them block (as

     * in Thread.join).  We also cannot just reassign the joiner's

     * run-time stack with another and replace it later, which would

     * be a form of "continuation", that even if possible is not

     * necessarily a good idea since we sometimes need both an

     * unblocked task and its continuation to progress. Instead we

     *      ForkJoinWorkerThread.joinTask tracks joining->stealing

     *      method tryPreBlock() may create or re-activate a spare

     *      thread to compensate for blocked joiners until they

     *      unblock.

     * It is impossible to keep exactly the target parallelism number

     * of threads running at any given time.  Determining the

     * existence of conservatively safe helping targets, the

     * availability of already-created spares, and the apparent need

     * to create new spares are all racy and require heuristic

     * guidance, so we rely on multiple retries of each.  Currently,

     * in keeping with on-demand signalling policy, we compensate only

     * if blocking would leave less than one active (non-waiting,

     * non-blocked) worker. Additionally, to avoid some false alarms

     * due to GC, lagging counters, system activity, etc, compensated

     * blocking for joins is only attempted after rechecks stabilize

     * (retries are interspersed with Thread.yield, for good

     * citizenship).  The variable blockedCount, incremented before

     * blocking and decremented after, is sometimes needed to

     * distinguish cases of waiting for work vs blocking on joins or

     * other managed sync. Both cases are equivalent for most pool

     * control, so we can update non-atomically. (Additionally,

     * contention on blockedCount alleviates some contention on ctl).

     * Shutdown and Termination. A call to shutdownNow atomically sets

     * the ctl stop bit and then (non-atomically) sets each workers

     * "terminate" status, cancels all unprocessed tasks, and wakes up

     * all waiting workers.  Detecting whether termination should

     * commence after a non-abrupt shutdown() call requires more work

     * and bookkeeping. We need consensus about quiesence (i.e., that

     * there is no more work) which is reflected in active counts so

     * long as there are no current blockers, as well as possible

     * re-evaluations during independent changes in blocking or

     * quiescing workers.

     * Style notes: There is a lot of representation-level coupling

     * ForkJoinTask.  Most fields of ForkJoinWorkerThread maintain

     * data structures managed by ForkJoinPool, so are directly

     * accessed.  Conversely we allow access to "workers" array by

     * changes anyway. All together, these low-level implementation

     * choices produce as much as a factor of 4 performance

     * improvement compared to naive implementations, and enable the

     * processing of billions of tasks per second, at the expense of

     * some ugliness.

     * Methods signalWork() and scan() are the main bottlenecks so are

     * especially heavily micro-optimized/mangled.  There are lots of

     * inline assignments (of form "while ((local = field) != 0)")

     * which are usually the simplest way to ensure the required read

     * orderings (which are sometimes critical). This leads to a

     * "C"-like style of listing declarations of these locals at the

     * heads of methods or blocks.  There are several occurrences of

     * the unusual "do {} while (!cas...)"  which is the simplest way

     * to force an update of a CAS'ed variable. There are also other

     * coding oddities that help some methods perform reasonably even

     * when interpreted (not compiled).

     * The order of declarations in this file is: (1) declarations of

     * statics (2) fields (along with constants used when unpacking

     * some of them), listed in an order that tends to reduce

     * contention among them a bit under most JVMs.  (3) internal

     * control methods (4) callbacks and other support for

     * ForkJoinTask and ForkJoinWorkerThread classes, (5) exported

     * methods (plus a few little helpers). (6) static block

     * initializing all statics in a minimally dependent order.

        defaultForkJoinWorkerThreadFactory;

    private static final RuntimePermission modifyThreadPermission;

    private static final AtomicInteger poolNumberGenerator;

     * Generator for initial random seeds for worker victim

     * selection. This is used only to create initial seeds. Random

     * steals use a cheaper xorshift generator per steal attempt. We

     * don't expect much contention on seedGenerator, so just use a

     * plain Random.

    static final Random workerSeedGenerator;

     * Array holding all worker threads in the pool.  Initialized upon

     * construction. Array size must be a power of two.  Updates and

     * replacements are protected by scanGuard, but the array is

     * always kept in a consistent enough state to be randomly

     * accessed without locking by workers performing work-stealing,

     * as well as other traversal-based methods in this class, so long

     * as reads memory-acquire by first reading ctl. All readers must

     * tolerate that some array slots may be null.

    ForkJoinWorkerThread[] workers;

     * Initial size for submission queue array. Must be a power of

     * two.  In many applications, these always stay small so we use a

     * small initial cap.

    private static final int INITIAL_QUEUE_CAPACITY = 8;

    /**

     * Maximum size for submission queue array. Must be a power of two

     * less than or equal to 1 << (31 - width of array entry) to

     * ensure lack of index wraparound, but is capped at a lower

     * value to help users trap runaway computations.

     */

    private static final int MAXIMUM_QUEUE_CAPACITY = 1 << 24; // 16M

     * Array serving as submission queue. Initialized upon construction.

    private ForkJoinTask<?>[] submissionQueue;

     * Lock protecting submissions array for addSubmission

    private final ReentrantLock submissionLock;

     * Condition for awaitTermination, using submissionLock for

     * convenience.

    private final Condition termination;

     * The uncaught exception handler used when any worker abruptly

     * terminates.

     */

    final Thread.UncaughtExceptionHandler ueh;

    /**

     * Prefix for assigning names to worker threads

     */

    private final String workerNamePrefix;

    /**

     * Main pool control -- a long packed with:

     * AC: Number of active running workers minus target parallelism (16 bits)

     * TC: Number of total workers minus target parallelism (16bits)

     * ST: true if pool is terminating (1 bit)