jdk/src/share/classes/java/util/concurrent/ForkJoinWorkerThread.java
author dl
Mon, 18 Apr 2011 15:50:18 +0100
changeset 9278 f4672926fe4c
parent 9242 ef138d47df58
child 11279 d9dab5ec5044
permissions -rw-r--r--
7037436: CR 7035020 fails to check shutdown Reviewed-by: chegar
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
     1
/*
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
     2
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
     3
 *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
     4
 * This code is free software; you can redistribute it and/or modify it
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
     5
 * under the terms of the GNU General Public License version 2 only, as
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 4110
diff changeset
     6
 * published by the Free Software Foundation.  Oracle designates this
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
     7
 * particular file as subject to the "Classpath" exception as provided
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 4110
diff changeset
     8
 * by Oracle in the LICENSE file that accompanied this code.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
     9
 *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    10
 * This code is distributed in the hope that it will be useful, but WITHOUT
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    11
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    12
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    13
 * version 2 for more details (a copy is included in the LICENSE file that
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    14
 * accompanied this code).
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    15
 *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    16
 * You should have received a copy of the GNU General Public License version
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    17
 * 2 along with this work; if not, write to the Free Software Foundation,
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    18
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    19
 *
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 4110
diff changeset
    20
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 4110
diff changeset
    21
 * or visit www.oracle.com if you need additional information or have any
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 4110
diff changeset
    22
 * questions.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    23
 */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    24
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    25
/*
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    26
 * This file is available under and governed by the GNU General Public
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    27
 * License version 2 only, as published by the Free Software Foundation.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    28
 * However, the following notice accompanied the original version of this
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    29
 * file:
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    30
 *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    31
 * Written by Doug Lea with assistance from members of JCP JSR-166
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    32
 * Expert Group and released to the public domain, as explained at
9242
ef138d47df58 7034657: Update Creative Commons license URL in legal notices
dl
parents: 8765
diff changeset
    33
 * http://creativecommons.org/publicdomain/zero/1.0/
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    34
 */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    35
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    36
package java.util.concurrent;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    37
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    38
import java.util.Collection;
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    39
import java.util.concurrent.RejectedExecutionException;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    40
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    41
/**
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    42
 * A thread managed by a {@link ForkJoinPool}, which executes
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    43
 * {@link ForkJoinTask}s.
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    44
 * This class is subclassable solely for the sake of adding
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    45
 * functionality -- there are no overridable methods dealing with
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    46
 * scheduling or execution.  However, you can override initialization
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    47
 * and termination methods surrounding the main task processing loop.
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    48
 * If you do create such a subclass, you will also need to supply a
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    49
 * custom {@link ForkJoinPool.ForkJoinWorkerThreadFactory} to use it
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
    50
 * in a {@code ForkJoinPool}.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    51
 *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    52
 * @since 1.7
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    53
 * @author Doug Lea
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    54
 */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    55
public class ForkJoinWorkerThread extends Thread {
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    56
    /*
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    57
     * Overview:
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    58
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    59
     * ForkJoinWorkerThreads are managed by ForkJoinPools and perform
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    60
     * ForkJoinTasks. This class includes bookkeeping in support of
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    61
     * worker activation, suspension, and lifecycle control described
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    62
     * in more detail in the internal documentation of class
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    63
     * ForkJoinPool. And as described further below, this class also
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    64
     * includes special-cased support for some ForkJoinTask
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    65
     * methods. But the main mechanics involve work-stealing:
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
    66
     *
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    67
     * Work-stealing queues are special forms of Deques that support
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    68
     * only three of the four possible end-operations -- push, pop,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    69
     * and deq (aka steal), under the further constraints that push
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    70
     * and pop are called only from the owning thread, while deq may
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    71
     * be called from other threads.  (If you are unfamiliar with
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    72
     * them, you probably want to read Herlihy and Shavit's book "The
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    73
     * Art of Multiprocessor programming", chapter 16 describing these
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    74
     * in more detail before proceeding.)  The main work-stealing
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    75
     * queue design is roughly similar to those in the papers "Dynamic
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    76
     * Circular Work-Stealing Deque" by Chase and Lev, SPAA 2005
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    77
     * (http://research.sun.com/scalable/pubs/index.html) and
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    78
     * "Idempotent work stealing" by Michael, Saraswat, and Vechev,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    79
     * PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186).
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    80
     * The main differences ultimately stem from gc requirements that
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    81
     * we null out taken slots as soon as we can, to maintain as small
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    82
     * a footprint as possible even in programs generating huge
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    83
     * numbers of tasks. To accomplish this, we shift the CAS
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    84
     * arbitrating pop vs deq (steal) from being on the indices
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    85
     * ("queueBase" and "queueTop") to the slots themselves (mainly
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    86
     * via method "casSlotNull()"). So, both a successful pop and deq
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    87
     * mainly entail a CAS of a slot from non-null to null.  Because
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    88
     * we rely on CASes of references, we do not need tag bits on
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    89
     * queueBase or queueTop.  They are simple ints as used in any
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    90
     * circular array-based queue (see for example ArrayDeque).
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    91
     * Updates to the indices must still be ordered in a way that
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    92
     * guarantees that queueTop == queueBase means the queue is empty,
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    93
     * but otherwise may err on the side of possibly making the queue
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    94
     * appear nonempty when a push, pop, or deq have not fully
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    95
     * committed. Note that this means that the deq operation,
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    96
     * considered individually, is not wait-free. One thief cannot
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    97
     * successfully continue until another in-progress one (or, if
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
    98
     * previously empty, a push) completes.  However, in the
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
    99
     * aggregate, we ensure at least probabilistic non-blockingness.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   100
     * If an attempted steal fails, a thief always chooses a different
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   101
     * random victim target to try next. So, in order for one thief to
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   102
     * progress, it suffices for any in-progress deq or new push on
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   103
     * any empty queue to complete.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   104
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   105
     * This approach also enables support for "async mode" where local
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   106
     * task processing is in FIFO, not LIFO order; simply by using a
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   107
     * version of deq rather than pop when locallyFifo is true (as set
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   108
     * by the ForkJoinPool).  This allows use in message-passing
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   109
     * frameworks in which tasks are never joined.  However neither
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   110
     * mode considers affinities, loads, cache localities, etc, so
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   111
     * rarely provide the best possible performance on a given
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   112
     * machine, but portably provide good throughput by averaging over
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   113
     * these factors.  (Further, even if we did try to use such
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   114
     * information, we do not usually have a basis for exploiting
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   115
     * it. For example, some sets of tasks profit from cache
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   116
     * affinities, but others are harmed by cache pollution effects.)
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   117
     *
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   118
     * When a worker would otherwise be blocked waiting to join a
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   119
     * task, it first tries a form of linear helping: Each worker
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   120
     * records (in field currentSteal) the most recent task it stole
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   121
     * from some other worker. Plus, it records (in field currentJoin)
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   122
     * the task it is currently actively joining. Method joinTask uses
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   123
     * these markers to try to find a worker to help (i.e., steal back
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   124
     * a task from and execute it) that could hasten completion of the
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   125
     * actively joined task. In essence, the joiner executes a task
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   126
     * that would be on its own local deque had the to-be-joined task
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   127
     * not been stolen. This may be seen as a conservative variant of
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   128
     * the approach in Wagner & Calder "Leapfrogging: a portable
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   129
     * technique for implementing efficient futures" SIGPLAN Notices,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   130
     * 1993 (http://portal.acm.org/citation.cfm?id=155354). It differs
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   131
     * in that: (1) We only maintain dependency links across workers
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   132
     * upon steals, rather than use per-task bookkeeping.  This may
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   133
     * require a linear scan of workers array to locate stealers, but
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   134
     * usually doesn't because stealers leave hints (that may become
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   135
     * stale/wrong) of where to locate them. This isolates cost to
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   136
     * when it is needed, rather than adding to per-task overhead.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   137
     * (2) It is "shallow", ignoring nesting and potentially cyclic
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   138
     * mutual steals.  (3) It is intentionally racy: field currentJoin
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   139
     * is updated only while actively joining, which means that we
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   140
     * miss links in the chain during long-lived tasks, GC stalls etc
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   141
     * (which is OK since blocking in such cases is usually a good
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   142
     * idea).  (4) We bound the number of attempts to find work (see
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   143
     * MAX_HELP) and fall back to suspending the worker and if
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   144
     * necessary replacing it with another.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   145
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   146
     * Efficient implementation of these algorithms currently relies
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   147
     * on an uncomfortable amount of "Unsafe" mechanics. To maintain
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   148
     * correct orderings, reads and writes of variable queueBase
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   149
     * require volatile ordering.  Variable queueTop need not be
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   150
     * volatile because non-local reads always follow those of
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   151
     * queueBase.  Similarly, because they are protected by volatile
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   152
     * queueBase reads, reads of the queue array and its slots by
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   153
     * other threads do not need volatile load semantics, but writes
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   154
     * (in push) require store order and CASes (in pop and deq)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   155
     * require (volatile) CAS semantics.  (Michael, Saraswat, and
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   156
     * Vechev's algorithm has similar properties, but without support
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   157
     * for nulling slots.)  Since these combinations aren't supported
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   158
     * using ordinary volatiles, the only way to accomplish these
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   159
     * efficiently is to use direct Unsafe calls. (Using external
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   160
     * AtomicIntegers and AtomicReferenceArrays for the indices and
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   161
     * array is significantly slower because of memory locality and
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   162
     * indirection effects.)
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   163
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   164
     * Further, performance on most platforms is very sensitive to
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   165
     * placement and sizing of the (resizable) queue array.  Even
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   166
     * though these queues don't usually become all that big, the
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   167
     * initial size must be large enough to counteract cache
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   168
     * contention effects across multiple queues (especially in the
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   169
     * presence of GC cardmarking). Also, to improve thread-locality,
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   170
     * queues are initialized after starting.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   171
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   172
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   173
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   174
     * Mask for pool indices encoded as shorts
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   175
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   176
    private static final int  SMASK  = 0xffff;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   177
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   178
    /**
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   179
     * Capacity of work-stealing queue array upon initialization.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   180
     * Must be a power of two. Initial size must be at least 4, but is
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   181
     * padded to minimize cache effects.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   182
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   183
    private static final int INITIAL_QUEUE_CAPACITY = 1 << 13;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   184
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   185
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   186
     * Maximum size for queue array. Must be a power of two
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   187
     * less than or equal to 1 << (31 - width of array entry) to
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   188
     * ensure lack of index wraparound, but is capped at a lower
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   189
     * value to help users trap runaway computations.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   190
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   191
    private static final int MAXIMUM_QUEUE_CAPACITY = 1 << 24; // 16M
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   192
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   193
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   194
     * The work-stealing queue array. Size must be a power of two.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   195
     * Initialized when started (as oposed to when constructed), to
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   196
     * improve memory locality.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   197
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   198
    ForkJoinTask<?>[] queue;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   199
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   200
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   201
     * The pool this thread works in. Accessed directly by ForkJoinTask.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   202
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   203
    final ForkJoinPool pool;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   204
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   205
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   206
     * Index (mod queue.length) of next queue slot to push to or pop
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   207
     * from. It is written only by owner thread, and accessed by other
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   208
     * threads only after reading (volatile) queueBase.  Both queueTop
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   209
     * and queueBase are allowed to wrap around on overflow, but
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   210
     * (queueTop - queueBase) still estimates size.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   211
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   212
    int queueTop;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   213
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   214
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   215
     * Index (mod queue.length) of least valid queue slot, which is
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   216
     * always the next position to steal from if nonempty.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   217
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   218
    volatile int queueBase;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   219
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   220
    /**
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   221
     * The index of most recent stealer, used as a hint to avoid
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   222
     * traversal in method helpJoinTask. This is only a hint because a
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   223
     * worker might have had multiple steals and this only holds one
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   224
     * of them (usually the most current). Declared non-volatile,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   225
     * relying on other prevailing sync to keep reasonably current.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   226
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   227
    int stealHint;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   228
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   229
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   230
     * Index of this worker in pool array. Set once by pool before
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   231
     * running, and accessed directly by pool to locate this worker in
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   232
     * its workers array.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   233
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   234
    final int poolIndex;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   235
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   236
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   237
     * Encoded record for pool task waits. Usages are always
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   238
     * surrounded by volatile reads/writes
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   239
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   240
    int nextWait;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   241
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   242
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   243
     * Complement of poolIndex, offset by count of entries of task
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   244
     * waits. Accessed by ForkJoinPool to manage event waiters.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   245
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   246
    volatile int eventCount;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   247
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   248
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   249
     * Seed for random number generator for choosing steal victims.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   250
     * Uses Marsaglia xorshift. Must be initialized as nonzero.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   251
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   252
    int seed;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   253
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   254
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   255
     * Number of steals. Directly accessed (and reset) by pool when
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   256
     * idle.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   257
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   258
    int stealCount;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   259
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   260
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   261
     * True if this worker should or did terminate
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   262
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   263
    volatile boolean terminate;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   264
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   265
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   266
     * Set to true before LockSupport.park; false on return
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   267
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   268
    volatile boolean parked;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   269
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   270
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   271
     * True if use local fifo, not default lifo, for local polling.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   272
     * Shadows value from ForkJoinPool.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   273
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   274
    final boolean locallyFifo;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   275
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   276
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   277
     * The task most recently stolen from another worker (or
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   278
     * submission queue).  All uses are surrounded by enough volatile
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   279
     * reads/writes to maintain as non-volatile.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   280
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   281
    ForkJoinTask<?> currentSteal;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   282
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   283
    /**
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   284
     * The task currently being joined, set only when actively trying
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   285
     * to help other stealers in helpJoinTask. All uses are surrounded
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   286
     * by enough volatile reads/writes to maintain as non-volatile.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   287
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   288
    ForkJoinTask<?> currentJoin;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   289
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   290
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   291
     * Creates a ForkJoinWorkerThread operating in the given pool.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   292
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   293
     * @param pool the pool this thread works in
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   294
     * @throws NullPointerException if pool is null
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   295
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   296
    protected ForkJoinWorkerThread(ForkJoinPool pool) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   297
        super(pool.nextWorkerName());
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   298
        this.pool = pool;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   299
        int k = pool.registerWorker(this);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   300
        poolIndex = k;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   301
        eventCount = ~k & SMASK; // clear wait count
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   302
        locallyFifo = pool.locallyFifo;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   303
        Thread.UncaughtExceptionHandler ueh = pool.ueh;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   304
        if (ueh != null)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   305
            setUncaughtExceptionHandler(ueh);
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   306
        setDaemon(true);
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   307
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   308
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   309
    // Public methods
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   310
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   311
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   312
     * Returns the pool hosting this thread.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   313
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   314
     * @return the pool
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   315
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   316
    public ForkJoinPool getPool() {
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   317
        return pool;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   318
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   319
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   320
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   321
     * Returns the index number of this thread in its pool.  The
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   322
     * returned value ranges from zero to the maximum number of
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   323
     * threads (minus one) that have ever been created in the pool.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   324
     * This method may be useful for applications that track status or
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   325
     * collect results per-worker rather than per-task.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   326
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   327
     * @return the index number
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   328
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   329
    public int getPoolIndex() {
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   330
        return poolIndex;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   331
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   332
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   333
    // Randomization
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   334
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   335
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   336
     * Computes next value for random victim probes and backoffs.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   337
     * Scans don't require a very high quality generator, but also not
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   338
     * a crummy one.  Marsaglia xor-shift is cheap and works well
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   339
     * enough.  Note: This is manually inlined in FJP.scan() to avoid
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   340
     * writes inside busy loops.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   341
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   342
    private int nextSeed() {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   343
        int r = seed;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   344
        r ^= r << 13;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   345
        r ^= r >>> 17;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   346
        r ^= r << 5;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   347
        return seed = r;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   348
    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   349
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   350
    // Run State management
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   351
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   352
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   353
     * Initializes internal state after construction but before
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   354
     * processing any tasks. If you override this method, you must
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
   355
     * invoke {@code super.onStart()} at the beginning of the method.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   356
     * Initialization requires care: Most fields must have legal
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   357
     * default values, to ensure that attempted accesses from other
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   358
     * threads work correctly even before this thread starts
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   359
     * processing tasks.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   360
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   361
    protected void onStart() {
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   362
        queue = new ForkJoinTask<?>[INITIAL_QUEUE_CAPACITY];
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   363
        int r = pool.workerSeedGenerator.nextInt();
9278
f4672926fe4c 7037436: CR 7035020 fails to check shutdown
dl
parents: 9242
diff changeset
   364
        seed = (r == 0) ? 1 : r; //  must be nonzero
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   365
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   366
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   367
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   368
     * Performs cleanup associated with termination of this worker
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   369
     * thread.  If you override this method, you must invoke
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   370
     * {@code super.onTermination} at the end of the overridden method.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   371
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   372
     * @param exception the exception causing this thread to abort due
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   373
     * to an unrecoverable error, or {@code null} if completed normally
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   374
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   375
    protected void onTermination(Throwable exception) {
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   376
        try {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   377
            terminate = true;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   378
            cancelTasks();
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   379
            pool.deregisterWorker(this, exception);
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   380
        } catch (Throwable ex) {        // Shouldn't ever happen
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   381
            if (exception == null)      // but if so, at least rethrown
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   382
                exception = ex;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   383
        } finally {
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   384
            if (exception != null)
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   385
                UNSAFE.throwException(exception);
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   386
        }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   387
    }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   388
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   389
    /**
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   390
     * This method is required to be public, but should never be
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   391
     * called explicitly. It performs the main run loop to execute
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
   392
     * {@link ForkJoinTask}s.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   393
     */
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   394
    public void run() {
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   395
        Throwable exception = null;
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   396
        try {
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   397
            onStart();
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   398
            pool.work(this);
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   399
        } catch (Throwable ex) {
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   400
            exception = ex;
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   401
        } finally {
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   402
            onTermination(exception);
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   403
        }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   404
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   405
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   406
    /*
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   407
     * Intrinsics-based atomic writes for queue slots. These are
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   408
     * basically the same as methods in AtomicReferenceArray, but
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   409
     * specialized for (1) ForkJoinTask elements (2) requirement that
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   410
     * nullness and bounds checks have already been performed by
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   411
     * callers and (3) effective offsets are known not to overflow
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   412
     * from int to long (because of MAXIMUM_QUEUE_CAPACITY). We don't
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   413
     * need corresponding version for reads: plain array reads are OK
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   414
     * because they are protected by other volatile reads and are
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   415
     * confirmed by CASes.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   416
     *
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   417
     * Most uses don't actually call these methods, but instead
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   418
     * contain inlined forms that enable more predictable
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   419
     * optimization.  We don't define the version of write used in
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   420
     * pushTask at all, but instead inline there a store-fenced array
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   421
     * slot write.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   422
     *
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   423
     * Also in most methods, as a performance (not correctness) issue,
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   424
     * we'd like to encourage compilers not to arbitrarily postpone
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   425
     * setting queueTop after writing slot.  Currently there is no
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   426
     * intrinsic for arranging this, but using Unsafe putOrderedInt
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   427
     * may be a preferable strategy on some compilers even though its
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   428
     * main effect is a pre-, not post- fence. To simplify possible
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   429
     * changes, the option is left in comments next to the associated
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   430
     * assignments.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   431
     */
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   432
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   433
    /**
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   434
     * CASes slot i of array q from t to null. Caller must ensure q is
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   435
     * non-null and index is in range.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   436
     */
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   437
    private static final boolean casSlotNull(ForkJoinTask<?>[] q, int i,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   438
                                             ForkJoinTask<?> t) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   439
        return UNSAFE.compareAndSwapObject(q, (i << ASHIFT) + ABASE, t, null);
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   440
    }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   441
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   442
    /**
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   443
     * Performs a volatile write of the given task at given slot of
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   444
     * array q.  Caller must ensure q is non-null and index is in
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   445
     * range. This method is used only during resets and backouts.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   446
     */
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   447
    private static final void writeSlot(ForkJoinTask<?>[] q, int i,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   448
                                        ForkJoinTask<?> t) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   449
        UNSAFE.putObjectVolatile(q, (i << ASHIFT) + ABASE, t);
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   450
    }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   451
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   452
    // queue methods
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   453
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   454
    /**
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   455
     * Pushes a task. Call only from this thread.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   456
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   457
     * @param t the task. Caller must ensure non-null.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   458
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   459
    final void pushTask(ForkJoinTask<?> t) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   460
        ForkJoinTask<?>[] q; int s, m;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   461
        if ((q = queue) != null) {    // ignore if queue removed
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   462
            long u = (((s = queueTop) & (m = q.length - 1)) << ASHIFT) + ABASE;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   463
            UNSAFE.putOrderedObject(q, u, t);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   464
            queueTop = s + 1;         // or use putOrderedInt
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   465
            if ((s -= queueBase) <= 2)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   466
                pool.signalWork();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   467
            else if (s == m)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   468
                growQueue();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   469
        }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   470
    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   471
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   472
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   473
     * Creates or doubles queue array.  Transfers elements by
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   474
     * emulating steals (deqs) from old array and placing, oldest
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   475
     * first, into new array.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   476
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   477
    private void growQueue() {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   478
        ForkJoinTask<?>[] oldQ = queue;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   479
        int size = oldQ != null ? oldQ.length << 1 : INITIAL_QUEUE_CAPACITY;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   480
        if (size > MAXIMUM_QUEUE_CAPACITY)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   481
            throw new RejectedExecutionException("Queue capacity exceeded");
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   482
        if (size < INITIAL_QUEUE_CAPACITY)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   483
            size = INITIAL_QUEUE_CAPACITY;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   484
        ForkJoinTask<?>[] q = queue = new ForkJoinTask<?>[size];
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   485
        int mask = size - 1;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   486
        int top = queueTop;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   487
        int oldMask;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   488
        if (oldQ != null && (oldMask = oldQ.length - 1) >= 0) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   489
            for (int b = queueBase; b != top; ++b) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   490
                long u = ((b & oldMask) << ASHIFT) + ABASE;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   491
                Object x = UNSAFE.getObjectVolatile(oldQ, u);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   492
                if (x != null && UNSAFE.compareAndSwapObject(oldQ, u, x, null))
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   493
                    UNSAFE.putObjectVolatile
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   494
                        (q, ((b & mask) << ASHIFT) + ABASE, x);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   495
            }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   496
        }
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   497
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   498
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   499
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   500
     * Tries to take a task from the base of the queue, failing if
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   501
     * empty or contended. Note: Specializations of this code appear
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   502
     * in locallyDeqTask and elsewhere.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   503
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   504
     * @return a task, or null if none or contended
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   505
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   506
    final ForkJoinTask<?> deqTask() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   507
        ForkJoinTask<?> t; ForkJoinTask<?>[] q; int b, i;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   508
        if (queueTop != (b = queueBase) &&
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   509
            (q = queue) != null && // must read q after b
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   510
            (i = (q.length - 1) & b) >= 0 &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   511
            (t = q[i]) != null && queueBase == b &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   512
            UNSAFE.compareAndSwapObject(q, (i << ASHIFT) + ABASE, t, null)) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   513
            queueBase = b + 1;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   514
            return t;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   515
        }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   516
        return null;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   517
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   518
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   519
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   520
     * Tries to take a task from the base of own queue.  Called only
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   521
     * by this thread.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   522
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   523
     * @return a task, or null if none
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   524
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   525
    final ForkJoinTask<?> locallyDeqTask() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   526
        ForkJoinTask<?> t; int m, b, i;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   527
        ForkJoinTask<?>[] q = queue;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   528
        if (q != null && (m = q.length - 1) >= 0) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   529
            while (queueTop != (b = queueBase)) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   530
                if ((t = q[i = m & b]) != null &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   531
                    queueBase == b &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   532
                    UNSAFE.compareAndSwapObject(q, (i << ASHIFT) + ABASE,
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   533
                                                t, null)) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   534
                    queueBase = b + 1;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   535
                    return t;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   536
                }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   537
            }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   538
        }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   539
        return null;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   540
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   541
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   542
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   543
     * Returns a popped task, or null if empty.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   544
     * Called only by this thread.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   545
     */
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   546
    private ForkJoinTask<?> popTask() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   547
        int m;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   548
        ForkJoinTask<?>[] q = queue;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   549
        if (q != null && (m = q.length - 1) >= 0) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   550
            for (int s; (s = queueTop) != queueBase;) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   551
                int i = m & --s;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   552
                long u = (i << ASHIFT) + ABASE; // raw offset
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   553
                ForkJoinTask<?> t = q[i];
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   554
                if (t == null)   // lost to stealer
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   555
                    break;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   556
                if (UNSAFE.compareAndSwapObject(q, u, t, null)) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   557
                    queueTop = s; // or putOrderedInt
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   558
                    return t;
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   559
                }
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   560
            }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   561
        }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   562
        return null;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   563
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   564
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   565
    /**
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   566
     * Specialized version of popTask to pop only if topmost element
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   567
     * is the given task. Called only by this thread.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   568
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   569
     * @param t the task. Caller must ensure non-null.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   570
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   571
    final boolean unpushTask(ForkJoinTask<?> t) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   572
        ForkJoinTask<?>[] q;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   573
        int s;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   574
        if ((q = queue) != null && (s = queueTop) != queueBase &&
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   575
            UNSAFE.compareAndSwapObject
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   576
            (q, (((q.length - 1) & --s) << ASHIFT) + ABASE, t, null)) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   577
            queueTop = s; // or putOrderedInt
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   578
            return true;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   579
        }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   580
        return false;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   581
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   582
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   583
    /**
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   584
     * Returns next task, or null if empty or contended.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   585
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   586
    final ForkJoinTask<?> peekTask() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   587
        int m;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   588
        ForkJoinTask<?>[] q = queue;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   589
        if (q == null || (m = q.length - 1) < 0)
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   590
            return null;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   591
        int i = locallyFifo ? queueBase : (queueTop - 1);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   592
        return q[i & m];
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   593
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   594
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   595
    // Support methods for ForkJoinPool
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   596
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   597
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   598
     * Runs the given task, plus any local tasks until queue is empty
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   599
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   600
    final void execTask(ForkJoinTask<?> t) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   601
        currentSteal = t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   602
        for (;;) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   603
            if (t != null)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   604
                t.doExec();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   605
            if (queueTop == queueBase)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   606
                break;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   607
            t = locallyFifo ? locallyDeqTask() : popTask();
6674
2b22e69fdb75 6986050: Small clarifications and fixes for ForkJoin
dl
parents: 6543
diff changeset
   608
        }
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   609
        ++stealCount;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   610
        currentSteal = null;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   611
    }
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   612
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   613
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   614
     * Removes and cancels all tasks in queue.  Can be called from any
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   615
     * thread.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   616
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   617
    final void cancelTasks() {
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   618
        ForkJoinTask<?> cj = currentJoin; // try to cancel ongoing tasks
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   619
        if (cj != null && cj.status >= 0)
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   620
            cj.cancelIgnoringExceptions();
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   621
        ForkJoinTask<?> cs = currentSteal;
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
   622
        if (cs != null && cs.status >= 0)
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   623
            cs.cancelIgnoringExceptions();
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   624
        while (queueBase != queueTop) {
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   625
            ForkJoinTask<?> t = deqTask();
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   626
            if (t != null)
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   627
                t.cancelIgnoringExceptions();
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   628
        }
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   629
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   630
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   631
    /**
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   632
     * Drains tasks to given collection c.
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   633
     *
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   634
     * @return the number of tasks drained
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   635
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   636
    final int drainTasksTo(Collection<? super ForkJoinTask<?>> c) {
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   637
        int n = 0;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   638
        while (queueBase != queueTop) {
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   639
            ForkJoinTask<?> t = deqTask();
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   640
            if (t != null) {
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   641
                c.add(t);
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   642
                ++n;
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   643
            }
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   644
        }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   645
        return n;
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   646
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   647
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   648
    // Support methods for ForkJoinTask
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   649
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   650
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   651
     * Returns an estimate of the number of tasks in the queue.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   652
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   653
    final int getQueueSize() {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   654
        return queueTop - queueBase;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   655
    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   656
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   657
    /**
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   658
     * Gets and removes a local task.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   659
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   660
     * @return a task, if available
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   661
     */
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   662
    final ForkJoinTask<?> pollLocalTask() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   663
        return locallyFifo ? locallyDeqTask() : popTask();
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   664
    }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   665
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   666
    /**
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   667
     * Gets and removes a local or stolen task.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   668
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   669
     * @return a task, if available
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   670
     */
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   671
    final ForkJoinTask<?> pollTask() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   672
        ForkJoinWorkerThread[] ws;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   673
        ForkJoinTask<?> t = pollLocalTask();
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   674
        if (t != null || (ws = pool.workers) == null)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   675
            return t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   676
        int n = ws.length; // cheap version of FJP.scan
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   677
        int steps = n << 1;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   678
        int r = nextSeed();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   679
        int i = 0;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   680
        while (i < steps) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   681
            ForkJoinWorkerThread w = ws[(i++ + r) & (n - 1)];
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   682
            if (w != null && w.queueBase != w.queueTop && w.queue != null) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   683
                if ((t = w.deqTask()) != null)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   684
                    return t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   685
                i = 0;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   686
            }
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   687
        }
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   688
        return null;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   689
    }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   690
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   691
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   692
     * The maximum stolen->joining link depth allowed in helpJoinTask,
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   693
     * as well as the maximum number of retries (allowing on average
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   694
     * one staleness retry per level) per attempt to instead try
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   695
     * compensation.  Depths for legitimate chains are unbounded, but
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   696
     * we use a fixed constant to avoid (otherwise unchecked) cycles
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   697
     * and bound staleness of traversal parameters at the expense of
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   698
     * sometimes blocking when we could be helping.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   699
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   700
    private static final int MAX_HELP = 16;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   701
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   702
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   703
     * Possibly runs some tasks and/or blocks, until joinMe is done.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   704
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   705
     * @param joinMe the task to join
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   706
     * @return completion status on exit
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   707
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   708
    final int joinTask(ForkJoinTask<?> joinMe) {
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   709
        ForkJoinTask<?> prevJoin = currentJoin;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   710
        currentJoin = joinMe;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   711
        for (int s, retries = MAX_HELP;;) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   712
            if ((s = joinMe.status) < 0) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   713
                currentJoin = prevJoin;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   714
                return s;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   715
            }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   716
            if (retries > 0) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   717
                if (queueTop != queueBase) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   718
                    if (!localHelpJoinTask(joinMe))
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   719
                        retries = 0;           // cannot help
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   720
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   721
                else if (retries == MAX_HELP >>> 1) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   722
                    --retries;                 // check uncommon case
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   723
                    if (tryDeqAndExec(joinMe) >= 0)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   724
                        Thread.yield();        // for politeness
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   725
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   726
                else
9278
f4672926fe4c 7037436: CR 7035020 fails to check shutdown
dl
parents: 9242
diff changeset
   727
                    retries = helpJoinTask(joinMe) ? MAX_HELP : retries - 1;
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   728
            }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   729
            else {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   730
                retries = MAX_HELP;           // restart if not done
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   731
                pool.tryAwaitJoin(joinMe);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   732
            }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   733
        }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   734
    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   735
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   736
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   737
     * If present, pops and executes the given task, or any other
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   738
     * cancelled task
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   739
     *
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   740
     * @return false if any other non-cancelled task exists in local queue
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   741
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   742
    private boolean localHelpJoinTask(ForkJoinTask<?> joinMe) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   743
        int s, i; ForkJoinTask<?>[] q; ForkJoinTask<?> t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   744
        if ((s = queueTop) != queueBase && (q = queue) != null &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   745
            (i = (q.length - 1) & --s) >= 0 &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   746
            (t = q[i]) != null) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   747
            if (t != joinMe && t.status >= 0)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   748
                return false;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   749
            if (UNSAFE.compareAndSwapObject
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   750
                (q, (i << ASHIFT) + ABASE, t, null)) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   751
                queueTop = s;           // or putOrderedInt
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   752
                t.doExec();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   753
            }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   754
        }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   755
        return true;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   756
    }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   757
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   758
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   759
     * Tries to locate and execute tasks for a stealer of the given
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   760
     * task, or in turn one of its stealers, Traces
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
   761
     * currentSteal->currentJoin links looking for a thread working on
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
   762
     * a descendant of the given task and with a non-empty queue to
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   763
     * steal back and execute tasks from.  The implementation is very
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   764
     * branchy to cope with potential inconsistencies or loops
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   765
     * encountering chains that are stale, unknown, or of length
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   766
     * greater than MAX_HELP links.  All of these cases are dealt with
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   767
     * by just retrying by caller.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   768
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   769
     * @param joinMe the task to join
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   770
     * @param canSteal true if local queue is empty
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   771
     * @return true if ran a task
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   772
     */
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   773
    private boolean helpJoinTask(ForkJoinTask<?> joinMe) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   774
        boolean helped = false;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   775
        int m = pool.scanGuard & SMASK;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   776
        ForkJoinWorkerThread[] ws = pool.workers;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   777
        if (ws != null && ws.length > m && joinMe.status >= 0) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   778
            int levels = MAX_HELP;              // remaining chain length
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   779
            ForkJoinTask<?> task = joinMe;      // base of chain
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   780
            outer:for (ForkJoinWorkerThread thread = this;;) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   781
                // Try to find v, the stealer of task, by first using hint
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   782
                ForkJoinWorkerThread v = ws[thread.stealHint & m];
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   783
                if (v == null || v.currentSteal != task) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   784
                    for (int j = 0; ;) {        // search array
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   785
                        if ((v = ws[j]) != null && v.currentSteal == task) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   786
                            thread.stealHint = j;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   787
                            break;              // save hint for next time
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   788
                        }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   789
                        if (++j > m)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   790
                            break outer;        // can't find stealer
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   791
                    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   792
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   793
                // Try to help v, using specialized form of deqTask
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   794
                for (;;) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   795
                    ForkJoinTask<?>[] q; int b, i;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   796
                    if (joinMe.status < 0)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   797
                        break outer;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   798
                    if ((b = v.queueBase) == v.queueTop ||
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   799
                        (q = v.queue) == null ||
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   800
                        (i = (q.length-1) & b) < 0)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   801
                        break;                  // empty
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   802
                    long u = (i << ASHIFT) + ABASE;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   803
                    ForkJoinTask<?> t = q[i];
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   804
                    if (task.status < 0)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   805
                        break outer;            // stale
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   806
                    if (t != null && v.queueBase == b &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   807
                        UNSAFE.compareAndSwapObject(q, u, t, null)) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   808
                        v.queueBase = b + 1;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   809
                        v.stealHint = poolIndex;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   810
                        ForkJoinTask<?> ps = currentSteal;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   811
                        currentSteal = t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   812
                        t.doExec();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   813
                        currentSteal = ps;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   814
                        helped = true;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   815
                    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   816
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   817
                // Try to descend to find v's stealer
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   818
                ForkJoinTask<?> next = v.currentJoin;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   819
                if (--levels > 0 && task.status >= 0 &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   820
                    next != null && next != task) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   821
                    task = next;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   822
                    thread = v;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   823
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   824
                else
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   825
                    break;  // max levels, stale, dead-end, or cyclic
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
   826
            }
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   827
        }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   828
        return helped;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   829
    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   830
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   831
    /**
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   832
     * Performs an uncommon case for joinTask: If task t is at base of
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   833
     * some workers queue, steals and executes it.
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   834
     *
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   835
     * @param t the task
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   836
     * @return t's status
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   837
     */
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   838
    private int tryDeqAndExec(ForkJoinTask<?> t) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   839
        int m = pool.scanGuard & SMASK;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   840
        ForkJoinWorkerThread[] ws = pool.workers;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   841
        if (ws != null && ws.length > m && t.status >= 0) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   842
            for (int j = 0; j <= m; ++j) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   843
                ForkJoinTask<?>[] q; int b, i;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   844
                ForkJoinWorkerThread v = ws[j];
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   845
                if (v != null &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   846
                    (b = v.queueBase) != v.queueTop &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   847
                    (q = v.queue) != null &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   848
                    (i = (q.length - 1) & b) >= 0 &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   849
                    q[i] ==  t) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   850
                    long u = (i << ASHIFT) + ABASE;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   851
                    if (v.queueBase == b &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   852
                        UNSAFE.compareAndSwapObject(q, u, t, null)) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   853
                        v.queueBase = b + 1;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   854
                        v.stealHint = poolIndex;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   855
                        ForkJoinTask<?> ps = currentSteal;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   856
                        currentSteal = t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   857
                        t.doExec();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   858
                        currentSteal = ps;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   859
                    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   860
                    break;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   861
                }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   862
            }
7976
f273c0d04215 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011
dl
parents: 6674
diff changeset
   863
        }
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   864
        return t.status;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   865
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   866
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   867
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   868
     * Implements ForkJoinTask.getSurplusQueuedTaskCount().  Returns
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   869
     * an estimate of the number of tasks, offset by a function of
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   870
     * number of idle workers.
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   871
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   872
     * This method provides a cheap heuristic guide for task
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   873
     * partitioning when programmers, frameworks, tools, or languages
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   874
     * have little or no idea about task granularity.  In essence by
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   875
     * offering this method, we ask users only about tradeoffs in
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   876
     * overhead vs expected throughput and its variance, rather than
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   877
     * how finely to partition tasks.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   878
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   879
     * In a steady state strict (tree-structured) computation, each
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   880
     * thread makes available for stealing enough tasks for other
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   881
     * threads to remain active. Inductively, if all threads play by
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   882
     * the same rules, each thread should make available only a
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   883
     * constant number of tasks.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   884
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   885
     * The minimum useful constant is just 1. But using a value of 1
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   886
     * would require immediate replenishment upon each steal to
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   887
     * maintain enough tasks, which is infeasible.  Further,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   888
     * partitionings/granularities of offered tasks should minimize
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   889
     * steal rates, which in general means that threads nearer the top
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   890
     * of computation tree should generate more than those nearer the
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   891
     * bottom. In perfect steady state, each thread is at
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   892
     * approximately the same level of computation tree. However,
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   893
     * producing extra tasks amortizes the uncertainty of progress and
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   894
     * diffusion assumptions.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   895
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   896
     * So, users will want to use values larger, but not much larger
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   897
     * than 1 to both smooth over transient shortages and hedge
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   898
     * against uneven progress; as traded off against the cost of
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   899
     * extra task overhead. We leave the user to pick a threshold
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   900
     * value to compare with the results of this call to guide
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   901
     * decisions, but recommend values such as 3.
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   902
     *
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   903
     * When all threads are active, it is on average OK to estimate
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   904
     * surplus strictly locally. In steady-state, if one thread is
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   905
     * maintaining say 2 surplus tasks, then so are others. So we can
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   906
     * just use estimated queue length (although note that (queueTop -
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   907
     * queueBase) can be an overestimate because of stealers lagging
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   908
     * increments of queueBase).  However, this strategy alone leads
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   909
     * to serious mis-estimates in some non-steady-state conditions
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   910
     * (ramp-up, ramp-down, other stalls). We can detect many of these
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   911
     * by further considering the number of "idle" threads, that are
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   912
     * known to have zero queued tasks, so compensate by a factor of
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   913
     * (#idle/#active) threads.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   914
     */
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   915
    final int getEstimatedSurplusTaskCount() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   916
        return queueTop - queueBase - pool.idlePerActive();
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   917
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   918
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   919
    /**
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   920
     * Runs tasks until {@code pool.isQuiescent()}. We piggyback on
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   921
     * pool's active count ctl maintenance, but rather than blocking
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   922
     * when tasks cannot be found, we rescan until all others cannot
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   923
     * find tasks either. The bracketing by pool quiescerCounts
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   924
     * updates suppresses pool auto-shutdown mechanics that could
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   925
     * otherwise prematurely terminate the pool because all threads
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   926
     * appear to be inactive.
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   927
     */
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   928
    final void helpQuiescePool() {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   929
        boolean active = true;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   930
        ForkJoinTask<?> ps = currentSteal; // to restore below
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   931
        ForkJoinPool p = pool;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   932
        p.addQuiescerCount(1);
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   933
        for (;;) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   934
            ForkJoinWorkerThread[] ws = p.workers;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   935
            ForkJoinWorkerThread v = null;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   936
            int n;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   937
            if (queueTop != queueBase)
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   938
                v = this;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   939
            else if (ws != null && (n = ws.length) > 1) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   940
                ForkJoinWorkerThread w;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   941
                int r = nextSeed(); // cheap version of FJP.scan
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   942
                int steps = n << 1;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   943
                for (int i = 0; i < steps; ++i) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   944
                    if ((w = ws[(i + r) & (n - 1)]) != null &&
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   945
                        w.queueBase != w.queueTop) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   946
                        v = w;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   947
                        break;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   948
                    }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   949
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   950
            }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   951
            if (v != null) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   952
                ForkJoinTask<?> t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   953
                if (!active) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   954
                    active = true;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   955
                    p.addActiveCount(1);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   956
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   957
                if ((t = (v != this) ? v.deqTask() :
9278
f4672926fe4c 7037436: CR 7035020 fails to check shutdown
dl
parents: 9242
diff changeset
   958
                     locallyFifo ? locallyDeqTask() : popTask()) != null) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   959
                    currentSteal = t;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   960
                    t.doExec();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   961
                    currentSteal = ps;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   962
                }
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   963
            }
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   964
            else {
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   965
                if (active) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   966
                    active = false;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   967
                    p.addActiveCount(-1);
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   968
                }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   969
                if (p.isQuiescent()) {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   970
                    p.addActiveCount(1);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   971
                    p.addQuiescerCount(-1);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   972
                    break;
6543
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   973
                }
c06e5f2c6bb1 6978087: jsr166y Updates
dl
parents: 5506
diff changeset
   974
            }
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   975
        }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   976
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   977
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   978
    // Unsafe mechanics
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   979
    private static final sun.misc.Unsafe UNSAFE;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   980
    private static final long ABASE;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   981
    private static final int ASHIFT;
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   982
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   983
    static {
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   984
        int s;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   985
        try {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   986
            UNSAFE = sun.misc.Unsafe.getUnsafe();
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   987
            Class a = ForkJoinTask[].class;
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   988
            ABASE = UNSAFE.arrayBaseOffset(a);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   989
            s = UNSAFE.arrayIndexScale(a);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   990
        } catch (Exception e) {
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   991
            throw new Error(e);
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   992
        }
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   993
        if ((s & (s-1)) != 0)
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   994
            throw new Error("data type scale not a power of two");
8765
dfc2a131d08a 7023006: Reduce unnecessary thread activity in ForkJoinPool
dl
parents: 7976
diff changeset
   995
        ASHIFT = 31 - Integer.numberOfLeadingZeros(s);
4110
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   996
    }
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   997
ac033ba6ede4 6865582: jsr166y - jsr166 maintenance update
dl
parents:
diff changeset
   998
}