[concurrency-interest] Possible deadlock in ForkJoinPool when parallelism = 1 ?

Aaron Dunlop aaron.dunlop at gmail.com
Fri Apr 1 14:16:49 EDT 2011


This is a follow-up to a similar posting at StackOverflow
(http://stackoverflow.com/questions/5493399/forkjoinpool-parallelism-1-deadlock).
I'm pretty new to the Fork-Join framework, so this is probably an
obvious case of user-error, but I haven't been able to figure it out,
and thus far, none of the comments on that post have resolved the
issue either.

I'm profiling a parallel algorithm over a range of thread-counts. My
tasks seem to work flawlessly if I create the ForkJoinPool with
parallelism > 1 (I've normally been running with 2-24 threads). But if
I create the ForkJoinPool with parallelism = 1, I see deadlocks after
an unpredictable number of iterations. And yes - setting parallelism =
1 is a strange practice, but I want to accurately ascertain the
overhead of the parallel implementation, which means comparing the
serial version and the parallel version run with a single thread.

Below is a simple example that illustrates the issue I'm seeing. The
'task' is a dummy iteration over a fixed array, divided recursively
into 16 subtasks. I chose this odd iteration simply to produce a
memory-bound workload - it's possible the task itself interacts oddly
with F-J or with JIT optimizations, but if so, I haven't been able to
tease out those interactions.

If run with THREADS = 2 (or more), it runs reliably to completion, but
if run with THREADS = 1, it invariably deadlocks. After an
unpredictable number of iterations, the main loop hangs in
ForkJoinPool.invoke(), waiting in task.join(), and the worker thread
exits. (I've been running between 10000 and 50000 ITERATIONS,
depending on the host hardware)

I've tested using Java 1.7 using java.util.concurrent.ForkJoinPool:
--Linux JDK 1.7.0-ea-b136
  (contrary to a comment on the StackOverflow post, I've replicated
the issue on 1.7, although I haven't tested platforms other than
Linux)

And on Java 1.6, using a jsr166y, downloaded a few days ago from Doug
Lea's website:
--Linux, JDK 1.6.0_21 and JDK 1.6.0_22
--Mac OS JDK 1.6.0_24

Any suggestions for where I ought to look? I can provide stack or heap
dumps if that would be of interest.

Many thanks in advance,

Aaron Dunlop


==== Sample Code ====

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class TestFjDeadlock {

    private final static int[] intArray = new int[256 * 1024];
    private final static float[] floatArray = new float[256 * 1024];

    private final static int TASKS = 16;

    public static void main(String[] args) {

        final int THREADS = Integer.parseInt(args[0]);
        final int ITERATIONS = Integer.parseInt(args[1]);

        // Initialize the array
        for (int i = 0; i < intArray.length; i++) {
            intArray[i] = i;
        }

        ForkJoinPool pool = new ForkJoinPool(THREADS);

        for (int i = 0; i < ITERATIONS; i++) {
            pool.invoke(new RecursiveIterate(0, intArray.length));
        }

        pool.shutdown();
    }

    private static class RecursiveIterate extends RecursiveAction {

        final int start;
        final int end;

        public RecursiveIterate(final int start, final int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        protected void compute() {

            if ((end - start) <= (intArray.length / TASKS)) {
                // Iterate over the arrays
                for (int i = start; i < end; i += 3) {
                    floatArray[i] += i + intArray[i];
                }

            } else {
                // Subdivide and start new tasks
                final int mid = (start + end) >>> 1;
                invokeAll(new RecursiveIterate(start, mid), new
RecursiveIterate(mid, end));
            }
        }
    }
}


More information about the Concurrency-interest mailing list