线程快速排序
Threaded quicksort
您好,我以前从未尝试过使用线程,这是我的第一次尝试,但它并没有停止,正常的版本有效。
如果我删除 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);
}
}
}
此代码中的错误只是 qsortParallelo
中的 while 循环。 first
和 last
永远不会被修改。除此之外,您不需要 while 循环,因为您已经在执行程序中进行了进一步排序。你需要为数组的后半部分开始另一个任务。
您正在 executor
启动的 Thread
中调用 executor.awaitTermination
。 Thread
将在 executor
从 awaitTermination
出来之前停止,并且 executor
在 Thread
终止之前不会从 awaitTermination
出来。您需要移动此代码:
try {
executor.awaitTermination(1, TimeUnit.DAYS);
} catch (InterruptedException e) {
e.printStackTrace();
}
进入qsortP
方法的结尾。
与其等待整个执行程序服务终止(这可能根本不是您想要的),您应该保存所有由 [=11= 编辑的 Future
s return ] 并等待它们全部完成(例如,通过对它们调用“get()”)。
虽然在 qsortParallelo()
方法中这样做很诱人,但这实际上会因线程池耗尽而导致死锁:父任务会占用等待子任务完成的工作线程,但是子任务永远不会被安排到 运行 因为没有可用的工作线程。
所以你必须首先将所有 Future
个对象收集到一个并发集合中,return 结果到 qsortP()
并在那里等待 Future
s 完成.
或者使用 ForkJoinPool
,它专为此类任务而设计,可以为您完成所有的驴子工作。从应用程序代码递归地向执行器提交任务通常不是一个好主意,很容易出错。
顺便说一句,您的代码现在死锁的原因是每个工作线程都卡在 executor.awaitTermination()
中,从而阻止了执行程序服务的终止。
一般来说,设计和调试多线程应用程序的两个最有用的工具是:
- 线程转储。您可以使用
jstack
、VisualVM 或任何其他工具生成它,但它在死锁情况下非常宝贵,它可以让您准确了解线程正在(未)发生的事情。
- 一支笔,一张纸,画一张老式的泳道图。
您好,我以前从未尝试过使用线程,这是我的第一次尝试,但它并没有停止,正常的版本有效。 如果我删除 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);
}
}
}
此代码中的错误只是 qsortParallelo
中的 while 循环。 first
和 last
永远不会被修改。除此之外,您不需要 while 循环,因为您已经在执行程序中进行了进一步排序。你需要为数组的后半部分开始另一个任务。
您正在 executor
启动的 Thread
中调用 executor.awaitTermination
。 Thread
将在 executor
从 awaitTermination
出来之前停止,并且 executor
在 Thread
终止之前不会从 awaitTermination
出来。您需要移动此代码:
try {
executor.awaitTermination(1, TimeUnit.DAYS);
} catch (InterruptedException e) {
e.printStackTrace();
}
进入qsortP
方法的结尾。
与其等待整个执行程序服务终止(这可能根本不是您想要的),您应该保存所有由 [=11= 编辑的 Future
s return ] 并等待它们全部完成(例如,通过对它们调用“get()”)。
虽然在 qsortParallelo()
方法中这样做很诱人,但这实际上会因线程池耗尽而导致死锁:父任务会占用等待子任务完成的工作线程,但是子任务永远不会被安排到 运行 因为没有可用的工作线程。
所以你必须首先将所有 Future
个对象收集到一个并发集合中,return 结果到 qsortP()
并在那里等待 Future
s 完成.
或者使用 ForkJoinPool
,它专为此类任务而设计,可以为您完成所有的驴子工作。从应用程序代码递归地向执行器提交任务通常不是一个好主意,很容易出错。
顺便说一句,您的代码现在死锁的原因是每个工作线程都卡在 executor.awaitTermination()
中,从而阻止了执行程序服务的终止。
一般来说,设计和调试多线程应用程序的两个最有用的工具是:
- 线程转储。您可以使用
jstack
、VisualVM 或任何其他工具生成它,但它在死锁情况下非常宝贵,它可以让您准确了解线程正在(未)发生的事情。 - 一支笔,一张纸,画一张老式的泳道图。