Re: Multi-threading: wait for tasks to complete
Kevin McMurtrie wrote:
Thread.start() can cause run() to execute before start() completes, or
maybe run() happens later. It varies by OS and JVM version.
This is a good point. I had already accounted for that. The parent
thread calls countUp() before dispatching a child thread. The child
thread calls countDown() when it terminates.
Here's part of the algorithm. It's a multi-threaded quick sort, inspire
by the previous conversation about multi-threading sorts.
public class NonRecursiveMultiThreadedQuickSort
extends Sort
{
....
final ExecutorService executor = Executors.newFixedThreadPool(
Runtime.getRuntime().availableProcessors() );
....
private <T extends Comparable<? super T>> void quicksort( T[] a,
int l,
int r,
UpDownLatch counter )
{
while( l < r ) {
if( r - l <= 8 ) {
insertionSort( a, l, r );
break;
}
int i = partition( a, l, r );
if( i - l > r - i ) {
if( l < i - 1 ) {
counter.countUp();
SortTask task = new SortTask<T>( a, l, i - 1, counter );
Callable<?> call = (Callable<?>) task;
executor.submit( call );
}
l = i + 1;
} else {
if( i + 1 < r ) {
counter.countUp();
SortTask task = new SortTask<T>( a, i + 1, r, counter );
Callable<?> call = (Callable<?>) task;
executor.submit( call );
}
r = i - 1;
}
}
}
....
}
It still needs a bit of work, but that's the basic algorithm right now.
You can see that counter.countUp() is called before I dispatch the
sub-task to the executor service. There's no chance of a synchronization
problem.
public void run ()
{
try
{
...code or super.run()
}
finally
{
synchronized(latch)
{
latch.countDown(); //Do this before thread exits.
}
}
}
This bit here is a better point. I've tested the heck out of my code,
but in the field someone might pass it an array with null references or
a bad compareTo() method. So the finally statement is a good idea,
perhaps a necessary one. Thanks for pointing that out.