org.metasyntactic.thread.concurrent
Class ForkJoinTaskRunner

java.lang.Object
  |
  +--java.lang.Thread
        |
        +--org.metasyntactic.thread.concurrent.ForkJoinTaskRunner

All Implemented Interfaces:

java.lang.Runnable

public class ForkJoinTaskRunner

extends java.lang.Thread

Specialized Thread subclass for running ForkJoinTasks.

Each ForkJoinTaskRunner keeps ForkJoinTasks in a double-ended queue (DEQ). Double-ended queues support stack-based operations push and pop, as well as queue- based operations put and take. Normally, threads run their own tasks. But they may also steal tasks from each others DEQs.

The algorithms are minor variants of those used in Cilk and Hood, and to a lesser extent Filaments, but are adapted to work in Java.

The two most important capabilities are:

• Fork a ForkJoinTask:

    Push task onto DEQ
    

• Get a task to run (for example within taskYield)

    If DEQ is not empty,
       Pop a task and run it.
    Else if any other DEQ is not empty,
       Take ("steal") a task from it and run it.
    Else if the entry queue for our group is not empty,
       Take a task from it and run it.
    Else if current thread is otherwise idling
       If all threads are idling
          Wait for a task to be put on group entry queue
    Else
        Yield or Sleep for a while, and then retry
    

The push, pop, and put are designed to only ever called by the current thread, and take (steal) is only ever called by other threads. All other operations are composites and variants of these, plus a few miscellaneous bookkeeping methods.

Implementations of the underlying representations and operations are geared for use on JVMs operating on multiple CPUs (although they should of course work fine on single CPUs as well).

A possible snapshot of a ForkJoinTaskRunner's DEQ is:

     0     1     2     3     4     5     6    ...
  +-----+-----+-----+-----+-----+-----+-----+--
  |     |  t  |  t  |  t  |  t  |     |     | ...  deq array
  +-----+-----+-----+-----+-----+-----+-----+--
           ^                       ^
          base                    top
   (incremented                     (incremented
       on take,                         on push
    decremented                     decremented
       on put)                          on pop)
 

ForkJoinTasks are held in elements of the DEQ. They are maintained in a bounded array that works similarly to a circular bounded buffer. To ensure visibility of stolen ForkJoinTasks across threads, the array elements must be volatile. Using volatile rather than synchronizing suffices here since each task accessed by a thread is either one that it created or one that has never seen before. Thus we cannot encounter any staleness problems executing run methods, although ForkJoinTask programmers must be still sure to either synch or use volatile for shared data within their run methods.

However, since there is no way to declare an array of volatiles in Java, the DEQ elements actually hold VolatileTaskRef objects, each of which in turn holds a volatile reference to a ForkJoinTask. Even with the double-indirection overhead of volatile refs, using an array for the DEQ works out better than linking them since fewer shared memory locations need to be touched or modified by the threads while using the DEQ. Further, the double indirection may alleviate cache-line sharing effects (which cannot otherwise be directly dealt with in Java).

The indices for the base and top of the DEQ are declared as volatile. The main contention point with multiple ForkJoinTaskRunner threads occurs when one thread is trying to pop its own stack while another is trying to steal from it. This is handled via a specialization of Dekker's algorithm, in which the popping thread pre-decrements top, and then checks it against base. To be conservative in the face of JVMs that only partially honor the specification for volatile, the pop proceeds without synchronization only if there are apparently enough items for both a simultaneous pop and take to succeed. It otherwise enters a synchronized lock to check if the DEQ is actually empty, if so failing. The stealing thread does almost the opposite, but is set up to be less likely to win in cases of contention: Steals always run under synchronized locks in order to avoid conflicts with other ongoing steals. They pre- increment base, and then check against top. They back out (resetting the base index and failing to steal) if the DEQ is empty or is about to become empty by an ongoing pop.

A push operation can normally run concurrently with a steal. A push enters a synch lock only if the DEQ appears full so must either be resized or have indices adjusted due to wrap-around of the bounded DEQ. The put operation always requires synchronization.

When a ForkJoinTaskRunner thread has no tasks of its own to run, it tries to be a good citizen. Threads run at lower priority while scanning for work.

If the task is currently waiting via yield, the thread alternates scans (starting at a randomly chosen victim) with Thread.yields. This is well-behaved so long as the JVM handles Thread.yield in a sensible fashion. (It need not. Thread.yield is so underspecified that it is legal for a JVM to treat it as a no-op.) This also keeps things well-behaved even if we are running on a uniprocessor JVM using a simple cooperative threading model.

If a thread needing work is is otherwise idle (which occurs only in the main runloop), and there are no available tasks to steal or poll, it instead enters into a sleep-based (actually timed wait(msec)) phase in which it progressively sleeps for longer durations (up to a maximum of ForkJoinTaskRunnerGroup.MAX_SLEEP_TIME, currently 100ms) between scans. If all threads in the group are idling, they further progress to a hard wait phase, suspending until a new task is entered into the ForkJoinTaskRunnerGroup entry queue. A sleeping ForkJoinTaskRunner thread may be awakened by a new task being put into the group entry queue or by another ForkJoinTaskRunner becoming active, but not merely by some DEQ becoming non-empty. Thus the MAX_SLEEP_TIME provides a bound for sleep durations in cases where all but one worker thread start sleeping even though there will eventually be work produced by a thread that is taking a long time to place tasks in DEQ. These sleep mechanics are handled in the ForkJoinTaskRunnerGroup class.

Composite operations such as taskJoin include heavy manual inlining of the most time-critical operations (mainly ForkJoinTask.invoke). This opens up a few opportunities for further hand-optimizations. Until Java compilers get a lot smarter, these tweaks improve performance significantly enough for task-intensive programs to be worth the poorer maintainability and code duplication.

Because they are so fragile and performance-sensitive, nearly all methods are declared as final. However, nearly all fields and methods are also declared as protected, so it is possible, with much care, to extend functionality in subclasses. (Normally you would also need to subclass ForkJoinTaskRunnerGroup.)

None of the normal java.lang.Thread class methods should ever be called on ForkJoinTaskRunners. For this reason, it might have been nicer to declare ForkJoinTaskRunner as a Runnable to run within a Thread. However, this would have complicated many minor logistics. And since no ForkJoinTaskRunner methods should normally be called from outside the ForkJoinTask and ForkJoinTaskRunnerGroup classes either, this decision doesn't impact usage.

You might think that layering this kind of framework on top of Java threads, which are already several levels removed from raw CPU scheduling on most systems, would lead to very poor performance. But on the platforms tested, the performance is quite good.

See Also:

ForkJoinTask, ForkJoinTaskRunnerGroup

Field Summary

protected boolean	active Record whether current thread may be processing a task (i.e., has been started and is not in an idle wait).
protected int	runs Total number of tasks run
protected int	scans Total number of queues scanned for work
protected int	steals Total number of tasks obtained via scan

Fields inherited from class java.lang.Thread

MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Constructor Summary

protected

ForkJoinTaskRunner(ForkJoinTaskRunnerGroup g) Constructor called only during ForkJoinTaskRunnerGroup initialization

Method Summary

protected void	coInvoke(ForkJoinTask[] tasks) Array-based version of coInvoke
protected void	coInvoke(ForkJoinTask w, ForkJoinTask v) A specialized expansion of w.fork(); invoke(v); w.join();
protected int	deqSize() Current size of the task DEQ
protected ForkJoinTaskRunnerGroup	getGroup() Return the ForkJoinTaskRunnerGroup of which this thread is a member
protected void	push(ForkJoinTask r) Push a task onto DEQ.
void	run() Main runloop
protected void	setRunPriority(int pri) Set the priority to use while running tasks.
protected void	setScanPriority(int pri) Set the priority to use while scanning.
protected void	taskJoin(ForkJoinTask w) Process tasks until w is done.
protected void	taskYield() Execute a task in this thread.

Methods inherited from class java.lang.Thread

activeCount, checkAccess, countStackFrames, currentThread, destroy, dumpStack, enumerate, getContextClassLoader, getName, getPriority, getThreadGroup, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, resume, setContextClassLoader, setDaemon, setName, setPriority, sleep, sleep, start, stop, stop, suspend, toString, yield

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

active

protected boolean active

Record whether current thread may be processing a task (i.e., has been started and is not in an idle wait). Accessed, under synch, ONLY by ForkJoinTaskRunnerGroup, but the field is stored here for simplicity.

runs

protected int runs

Total number of tasks run

scans

protected int scans

Total number of queues scanned for work

steals

protected int steals

Total number of tasks obtained via scan

Constructor Detail

ForkJoinTaskRunner

protected ForkJoinTaskRunner(ForkJoinTaskRunnerGroup g)

Constructor called only during ForkJoinTaskRunnerGroup initialization

Parameters:

g -

Method Detail

getGroup

protected final ForkJoinTaskRunnerGroup getGroup()

Return the ForkJoinTaskRunnerGroup of which this thread is a member

Returns:

deqSize

protected int deqSize()

Current size of the task DEQ

Returns:

setScanPriority

protected void setScanPriority(int pri)

Set the priority to use while scanning. We do not bother synchronizing access, since by the time the value is needed, both this ForkJoinTaskRunner and its ForkJoinTaskRunnerGroup will necessarily have performed enough synchronization to avoid staleness problems of any consequence.

Parameters:

pri -

setRunPriority

protected void setRunPriority(int pri)

Set the priority to use while running tasks. Same usage and rationale as setScanPriority.

Parameters:

pri -

push

protected final void push(ForkJoinTask r)

Push a task onto DEQ. Called ONLY by current thread.

Parameters:

r -

run

public void run()

Main runloop

Specified by:

run in interface java.lang.Runnable

Overrides:

run in class java.lang.Thread

taskYield

protected final void taskYield()

Execute a task in this thread. Generally called when current task cannot otherwise continue.

taskJoin

protected final void taskJoin(ForkJoinTask w)

Process tasks until w is done. Equivalent to while(!w.isDone()) taskYield();

Parameters:

w -

coInvoke

protected final void coInvoke(ForkJoinTask w,
                              ForkJoinTask v)

A specialized expansion of w.fork(); invoke(v); w.join();

Parameters:

w -

v -

coInvoke

protected final void coInvoke(ForkJoinTask[] tasks)

Array-based version of coInvoke

Parameters:

tasks -