CODEWITHSUNDEEP
javamultithreadingquicksortexecutorservice
grecof88
grecof88

Reputation: 87

Threaded quicksort

Hello I've never tried using threads before, this is my first attempt but it doesn't stop, The normal verion works. if I remove awaitTermination it looks like it works but I need the method to finish when it's all sorted out(pun intended XD). Can you tell me what I did wrong? Thank you.

public class Sorting {

  private Sorting() {};

  private static Random r = new Random();
  private static int cores = Runtime.getRuntime().availableProcessors();
  private static ExecutorService executor = Executors.newFixedThreadPool(cores);

  public static void qsortP(int[] a) {
    qsortParallelo(a, 0, a.length - 1);
  }

  private static void qsortParallelo(int[] a, int first, int last) {
    while (first < last) {
      int p = first + r.nextInt(last - first + 1);
      int px = a[p];
      int i = first, j = last;
      do {
        while (a[i] < px)
          i++;
        while (a[j] > px)
          j--;
        if (i <= j) {
          scambia(a, i++, j--);
        }
      } while (i <= j);
      executor.submit(new qsortThread(a, first, j));
      first = i;
    }
    try {
      executor.awaitTermination(1, TimeUnit.DAYS);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }

  private static void scambia(int[] a, int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
  }

  public static class qsortThread implements Runnable {
    final int a[], first, last;

    public qsortThread(int[] a, int first, int last) {
      this.a = a;
      this.first = first;
      this.last = last;
    }

    public void run() {
      qsortParallelo(a, first, last);
    }
  }
}

Upvotes: 3

Views: 457

Answers (3)

biziclop
biziclop

Reputation: 49724

Instead of waiting for termination of the entire executor service (which probably isn't what you want at all), you should save all the Futures returned by executor.submit() and wait until they're all done (by calling 'get()` on them for example).

And though it's tempting to do this in the qsortParallelo() method, that would actually lead to a deadlock by exhaustion of the thread pool: parent tasks would hog the worker threads waiting for their child tasks to complete, but the child tasks would never be scheduled to run because there would be no available worker threads.

So you have to collect all the Future objects into a concurrent collection first, return the result to qsortP() and wait there for the Futures to finish.

Or use a ForkJoinPool, which was designed for exactly this kind of task and does all the donkey work for you. Recursively submitting tasks to an executor from application code is generally not a very good idea, it's very easy to get it wrong.

As an aside, the reason your code is deadlocked as it is is that every worker thread is stuck in executor.awaitTermination(), thereby preventing the termination of the executor service.

In general, the two most useful tools for designing and debugging multi-threaded applications are:

  1. A thread dump. You can generate that with jstack, VisualVM or any other tool, but it's invaluable in deadlock situations, it gives you an accurate image of what's (not) going on with your threads.
  2. A pen, a piece of paper and drawing a good old fashioned swimlane chart.

Upvotes: 1

Aleksei Shestakov
Aleksei Shestakov

Reputation: 2538

You are calling executor.awaitTermination inside a Thread which was launched by your executor. Thread will not stop until executor comes out of the awaitTermination and executor will not come out of awaitTermination until the Thread terminates. You need to move this code:

try {
  executor.awaitTermination(1, TimeUnit.DAYS);
} catch (InterruptedException e) {
  e.printStackTrace();
}

into the end of qsortP method.

Upvotes: 1

user4668606
user4668606

Reputation:

The mistake in this code is simply the while-loop in qsortParallelo. first and last are never modified. Apart from that you don't need the while-loop, since you already do that the further sorting in the executor. And you'll need to start another task for the second half of the array.

Upvotes: 0

Related Questions