8
votes

I'm using the jsr166y ForkJoinPool to distribute computational tasks amongst threads. But I clearly must be doing something wrong.

My tasks seem to work flawlessly if I create the ForkJoinPool with parallelism > 1 (the default is Runtime.availableProcessors(); I've been running with 2-8 threads). But if I create the ForkJoinPool with parallelism = 1, I see deadlocks after an unpredictable number of iterations.

Yes - setting parallelism = 1 is a strange practice. In this case, I'm profiling a parallel algorithm as thread-count increases, and I want to compare the parallel version, run with to a single thread, to a baseline serial implementation, so as to accurately ascertain the overhead of the parallel implementation.

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.

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 on task.join(), and the worker thread exits.

I'm running with JDK 1.6.0_21 and 1.6.0_22 under Linux, and using a version of jsr166y downloaded a few days ago from Doug Lea's website (http://gee.cs.oswego.edu/dl/concurrency-interest/index.html)

Any suggestions for what I'm missing? Many thanks in advance.

package concurrent;

import jsr166y.ForkJoinPool;
import jsr166y.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 THREADS = 1;
    private final static int TASKS = 16;
    private final static int ITERATIONS = 10000;

    public static void main(String[] args) {

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

        ForkJoinPool pool = new ForkJoinPool(THREADS);

        // Run through ITERATIONS loops, subdividing the iteration into TASKS F-J subtasks
        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)) {
                // We've reached the subdivision limit - 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));
            }
        }
    }
}
1
Looks like it is working as designed. You are requesting parallelism of 1, but then you are adding two tasks in invokeAll. But I'm not an expert on this, so I might be wrong. - Jochen Bedersdorfer
I've heard this before from other people, that setting the number of threads to 'one more' fixes things. - Chris Dennett
Re: Jochen - As I understand the framework, we should be able to add an arbitrary number of tasks, regardless of the parallelism level (thread count). E.g., we might recursively subdivide a large task into 256 separate small tasks, but we should be able to execute that algorithm on a machine with fewer than 256 processors. Also, the deadlock isn't immediate (as we would expect if 2 tasks / 1 thread was illegal - instead it's after an unpredictable number of iterations. But I'm relatively new to F-J too, so I might be misunderstanding. - AaronD
Re: Chris. Interesting. Thanks for that tidbit. I'll probably follow up on the jsr166y mailing list. - AaronD
It works fine on Java 7 with its own fork/join classes, but hangs with jsr166y.zip even on Java 7. Perhaps jsr166y.zip is not the latest version. - axtavt

1 Answers

6
votes

looks like a bug in the ForkJoinPool. everything i can see in the usage for the class fits your example. the only other possibility might be one of your tasks throwing an exception and dying abnormally (although that should still be handled).