[concurrency-interest] Thread exhaustion

Alexey Kudravtsev cdracm at mail.ru
Tue Apr 6 03:51:49 EDT 2010


Hello,
I am now confronting the simple task of mass parallelism that should have been a perfect fit for FJ.
I have many (millions) elements of some sort  and relatively many (thousands) processors.
Each processor should process each element, independently.
So I wrote the program to simulate this:
-----------------------------------
public class Test {
    public static void main(String[] args) {
        final ForkJoinPool pool = new ForkJoinPool();
        pool.setMaximumPoolSize(Runtime.getRuntime().availableProcessors());

        ParallelArray<ParallelArray<Object>> matrix = ParallelArray.create(1000, ParallelArray.class, pool);
        // initialize
        matrix.replaceWithGeneratedValue(new Ops.Generator<ParallelArray<Object>>() {
            public ParallelArray<Object> op() {
                return ParallelArray.create(10000, Object.class, pool);
            }
        });
        // simulate processing: for each of 1000 processors concurrently process each of 10000 elements 
        matrix.apply(new Ops.Procedure<ParallelArray<Object>>() {
            public void op(ParallelArray<Object> elems) {
                // my workflow requires me to say processor.started() here
                elems.apply(new Ops.Procedure<Object>() {
                    public void op(Object elem) {
                        //apply processor to elem
                    }
                });
                // my workflow requires me to say processor.finished() here
            }
        });
    }
}
-----------------------------------------

It deadblocks immediately upon execution because of thread exhaustion (see http://gafter.blogspot.com/2006/11/thread-pool-puzzler.html
for details. Basically, each ParallelArray.apply() task calls join() which blocks the current thread until there are no threads left)
If I comment out pool.setMaximumPoolSize() line, it kinda works, but generate excessive number of 'spare' threads.
The snippet above allocated 64 threads on my machine, and my real data sets caused allocation of hundreds(!) spare threads, most of which do nothing just waiting. 

So I figured that replacing join() in ParallelArray.apply() with helpJoin() could help.
Unfortunately, the program still deadlocks even then. As far as I understand, the problem is that helpJoin() tries to steal tasks from other worker thread queue, and,
failing that, blocks hard, waiting for completion of its own task. There is a possibility that all worker thread queues went empty for a moment, and in this instant the helpJoin() will block its current thread.

What I need is to modify helpJoin() behaviour, or maybe introduce another method (named cinderellaHelpJoin() because she was not afraid of hard work) which does following:
- tries to execute tasks from local worker thread queue (helpJoin() does that)
- if can't, tries to steal tasks from other worker thread queues (helpJoin() does that)
- if can't, pop tasks off the ForkJoinPool submission queue (helpJoin() does not do that currently)
- if can't, wait for one of the queues above become nonempty or its own task' isDone(). (helpJoin() does not do that currently)

What do you think?

Alexey Kudravtsev

P.S. I think the fact that ParallelArray tasks use join() instead of helpJoin() or equivalent makes them not very useful.
All of the ParallelArray tasks are independent  and therefore are perfectly eligible for helpJoining each other.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20100406/185ec7d5/attachment-0001.html>


More information about the Concurrency-interest mailing list