Threaded quicksort

Question

你好，我從來沒有嘗試過使用線程，這是我的第一次嘗試，但它並沒有停止，正常的版本工程。 如果我刪除awaitTermination它看起來像它的作品，但我需要的方法完成時，它的全部清理（雙關語XD）。 你能告訴我我做錯了什麼嗎？ 謝謝。

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); 
    } 
    } 
} 

Answer 1

而不是等待終止整個執行器服務（這可能不是你想要的），你應該保存所有由executor.submit()返回的Future，並等待它們全部完成（通過調用'get （）`例如）。

儘管在qsortParallelo()方法中這樣做很誘人，但實際上這會導致線程池耗盡導致死鎖：父任務會佔用等待子任務完成的工作線程，但子任務會從不計劃運行，因爲沒有可用的工作線程。

因此，您必須首先將所有Future對象收集到併發集合中，然後將結果返回到qsortP()並在那裏等待Future s完成。

或使用ForkJoinPool，這是專爲這種任務，併爲所有的驢子爲你工作。遞歸地將任務從應用程序代碼提交給執行者通常不是一個好主意，很容易弄錯。

---

順便說一句，你的代碼是僵持不下，因爲它的原因是，每一個工作線程卡在executor.awaitTermination()，從而防止執行服務的終止。

一般來說，設計和調試多線程應用程序的兩個最有用的工具是：

1. 線程轉儲。你可以用jstack，VisualVM或任何其他工具來生成它，但它在死鎖情況下非常有用，它可以給你準確的線索圖像。
2. 一支筆，一張紙，繪製一個老式的泳道圖。

Answer 2

該代碼中的錯誤僅僅是qsortParallelo中的while循環。 first和last從不修改。除此之外，您不需要while循環，因爲您已經在執行程序中進行了進一步的排序。你需要爲數組的後半部分開始另一項任務。

Answer 3

您正致電executor.awaitTermination在Thread裏面，這是由executor啓動的。 Thread將不會停止，直到awaitTermination中出現executor和executor不會從awaitTermination中出來，直到Thread終止。您需要移動此代碼：

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

結尾爲qsortP方法。