[concurrency-interest] Handling DAGs with JSR166

Niko Matsakis niko at alum.mit.edu
Mon Nov 15 13:38:31 EST 2010


I am attempting to use the jsr166y ForkJoinPool to handle a parallel 
task computation (in fact, as the underlying thread pool for the 
Intervals parallel task framework [1]).  The idea is that each task 
represents a node in the DAG.  I don't know the DAG before hand, so I 
need to run the tasks to find out who will join which other tasks.  I've 
found that this is very prone to deadlocks, generally because of a stack 

1. Tasks X,  Y, and Z are forked.
2. Task X joins Task Z.
3. In the meantime, the worker thread tries to run Task Y.
4. Task Y joins Task X.

Clearly I am violating some assumption. A preliminary reading of the 
code suggests that while blocked on a join(), a ForkJoinWorkerThread 
will execute arbitrary tasks from the local queue.  This is not safe in 
this case, since all tasks are forked to begin with, and may in fact 
have dependencies on the joining task.

Is there a better way to handle encode such a problem with jsr166y?


[1] http://intervals.inf.ethz.ch

More information about the Concurrency-interest mailing list