Multithreaded program never stops executing

Question

I have a multithreaded quicksort algorithm witch runs correct but then never stops executing.

I tried adding return statemants everywhere but nothing helps.

How do I stop all thread from running when they are done? Is there a way for a thread terminate its self when done?

public class Parallel {
    private static final int numberOfThreads = Runtime.getRuntime().availableProcessors();
    private static final int fallback = 2;
    private static Executor pool = Executors.newFixedThreadPool(numberOfThreads);
    //public static int[] numberArray;


    public static <T extends Comparable<T>> void sort(int[] numberArray){

        if(numberArray == null || numberArray.length == 0){
          return;
        }

        final AtomicInteger count = new AtomicInteger(1);
        pool.execute(new QuicksortRunnable<T>(numberArray, 0, numberArray.length-1, count));

        try {
          synchronized (count) {
            count.wait();

          }
        } catch (InterruptedException e) {       
          e.printStackTrace();
        }
      }

    private static class QuicksortRunnable<T extends Comparable<T>> implements Runnable {
        private final int[] values;
        private final int left;
        private final int right;
        private final AtomicInteger count;

        public QuicksortRunnable(int[] values, int left, int right, AtomicInteger count) {
          this.values = values;
          this.left = left;
          this.right = right;
          this.count = count;
        }

        @Override
        public void run() {
          quicksort(left, right);
          synchronized (count) {
            // AtomicInteger.getAndDecrement() returns the old value. If the old value is 1, then we know that the actual value is 0.
            if (count.getAndDecrement() == 1)
                count.notify();                         
          }
          return;
        }

        private void quicksort(int pLeft, int pRight) {

          int pivotIndex = (pRight - pLeft) / 2 + pLeft;
          int pivot = values[pivotIndex];
          int j = pRight;
          int i = pLeft;

          while (i < j) {
            while (values[i] > pivot) {
              i++;
            }

            while (values[j] < pivot) {
              j--;
            }

            if (i <= j) {
              int temp = values[i];
              values[i] = values[j];
              values[j] = temp;
              i++;
              j--;
            }
          }

          if (count.get() >= fallback * numberOfThreads) {
            if (pLeft < j){

              quicksort(pLeft, j);
            }
            if (i < pRight) {

              quicksort(i, pRight);
            }
          } else {
            if (pLeft < j) {

              count.getAndAdd(1);
              pool.execute(new QuicksortRunnable<T>(values, pLeft, j, count));
            }
            if (i < pRight) {

              count.getAndAdd(1);
              pool.execute(new QuicksortRunnable<T>(values, i, pRight, count));
            }
          }
        }

      }

And my Main function

 public static void main(String args[]) {
        Random rand = new Random();
        int length = 100000;

        int[] parallelArray = new int[length];

        for (int i = 0; i < length; i++) {
            int temp = rand.nextInt(length);
            parallelArray[i] = temp;            
        }
        sort(parallelArray);
        boolean t = check(parallelArray);
        System.out.println(t);
    }

Function to test if code is sorted.

public static boolean check(int[] A) {
        for (int i = 0; i < A.length - 1; i++) {
            // System.out.print(" " + A[i]);
            if (A[i] < A[i + 1]) {
                return false;
            }
        }
        return true;
    }

Answer 1

When you use a ExecutorService you need to call the ExecutorService.shutdown() after all tasks are submitted, then you need to wait for the pool to shut down by calling ExecutorService.awaitTermination() and supply the time to wait as parameters. This is because the pool is comprised of non-daemon threads and the jvm does not exit if there are non-daemon threads still running.

So change the this to use the ExecutorService from Executor to enable hooks:

private static ExecutorService pool = Executors.newFixedThreadPool(numberOfThreads);

Then call shutdown() in the finally block:

public static <T extends Comparable<T>> void sort(int[] numberArray) {

        if (numberArray == null || numberArray.length == 0) {
            return;
        }

        final AtomicInteger count = new AtomicInteger(1);
        pool.execute(new QuicksortRunnable<T>(numberArray, 0, numberArray.length - 1, count));

        try {
            synchronized (count) {
                count.wait();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }finally {
            pool.shutdown(); //call shutdown() here
            try {
                pool.awaitTermination(5, TimeUnit.MINUTES); //wait for 5 minutes
            }catch (InterruptedException ie) {
                ie.printStackTrace();
            }
        }
    }

In the finally section call shutdown() to initiate a orderly shut down of the threads in the pool and as the shutdown call is not blocking the awaitTermination() has to be called for the calling thread to wait for the shut down process to finish.

Isn't 5 min to wait a bit too much?

The call to awaitTermination does not necessarily wait the full five minutes. The 5 minutes is the maximum time to wait, not the minimum. To quite the Javadoc:

Blocks until all tasks have completed execution after a shutdown request, or the timeout occurs, or the current thread is interrupted, whichever happens first.