具有等待()/notify()同步的Java排序算法
我只使用等待/通知同步来实现合并排序。我知道有更多的高层结构，比如Fork/Join，Executors。等等，但我需要在这里使用工作/通知。基于这个https://courses.cs.washington.edu/courses/cse373/13wi/lectures/03-13/，我用同步块重构了方法parallelMergeSort()：
public void parallelMergeSort() {
synchronized (values) {
if (threadCount <= 1) {
mergeSort(values);
values.notify();
} else if (values.length >= 2) {
// split array in half
int[] left = Arrays.copyOfRange(values, 0, values.length / 2);
int[] right = Arrays.copyOfRange(values, values.length / 2, values.length);
synchronized(left) {
synchronized (right) {
// sort the halves
// mergeSort(left);
// mergeSort(right);
Thread lThread = new Thread(new ParallelMergeSort(left, threadCount / 2));
Thread rThread = new Thread(new ParallelMergeSort(right, threadCount / 2));
lThread.start();
rThread.start();
/*try {
lThread.join();
rThread.join();
} catch (InterruptedException ie) {}*/
try {
left.wait();
right.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
// merge them back together
merge(left, right, values);
}
}
values.notify();
}
}
}values在这里是一个输入数组。
因此，我看到排序的性能下降了，甚至比单线程排序还要慢。我猜瓶颈在数组的左右两个同步块内。有人知道如何重构它，以使它比单线程排序更快吗？
回答 2
Stack Overflow用户
发布于 2015-04-08 19:09:31
问题在于嵌套的synchronized块：
synchronized(left) {
synchronized (right) {
Thread lThread = new Thread(…);
Thread rThread = new Thread(…);
lThread.start();
rThread.start();
try {
left.wait();
right.wait();
}
…当启动新线程时，您将同时持有这两个锁，而新线程又试图获取这些锁。因此，新线程将被阻塞，直到启动线程释放这些锁为止。当线程调用wait()但…时，这种情况会隐式地发生。一次只能等待一个条件！
因此，当初始化线程调用left.wait()时，它释放left实例的锁，为处理left部件而生成的子线程可以继续执行，但是启动线程在等待left时仍然持有right锁。一旦子线程完成了对left的处理，它将调用notify，然后释放left锁，允许wait()重新获取该锁并返回。
然后，启动线程可以调用right.wait()，这将释放right锁，并允许其他子线程启动其工作，因此这等同于顺序性能。对于每一个子线程的产卵，由于启动线程所持有的锁，子线程被强制一个接一个地运行。
解决这一问题的一种方法是先启动线程，然后获取锁，然后只获取要使用wait的一个锁，而不是嵌套synchronized块。这仍然取决于未指定的时间(现在，子线程可能已经完成了它的工作，甚至在您进入notify块之前就调用了synchronized(x) { x.wait(); } )和所谓的虚假唤醒。简单地说，您需要一个可验证的条件，在调用wait()之前和之后进行检查，如wait()中所解释的那样。
就像在一个参数版本中一样，中断和虚假的唤醒是可能的，这个方法应该始终用于循环： 同步(obj) { while () obj.wait()；. //执行适合条件}的操作
该条件可能是子线程在调用boolean以指示工作已经完成之前设置为true的一个notify()标志。
请注意，这都是您在使用Thread.join()时免费获得的。同步在join()方法中进行，这两个调用不能重叠。此外，实现使用一个可验证的条件(线程的活动状态)来确保只在必要时调用wait()，并保护自己不受“虚假唤醒”的影响。
Stack Overflow用户
发布于 2015-04-07 13:29:51
如果曾经这样做，您需要对数百万个值进行排序，以查看并行性的效果，因为您正在到处复制数组，这使系统面临的大部分压力是内存访问和垃圾收集，而不是排序。
要正确地并行排序，您需要就地执行-这使得合并排序不太可能是一个好的候选项，因为它必须为目标创建一个新的数组。
如果您所做的只是实验，那么使用一个比较/计算密集型算法，比如冒泡排序。
请注意，如果这已被设置为一项任务，那么您的讲师可能会期望您做出回应，因为合并排序是并行性的糟糕选择。
https://stackoverflow.com/questions/29492460
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号