Java 合并排序算法与 wait()/notify() 同步

Question

我正在尝试仅使用等待/通知同步来实现合并排序。我知道更高级的结构，如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这里是输入数组。

结果，我看到排序的性能下降了，甚至比单线程排序慢。我猜瓶颈在数组左右部分的两个同步块中。有人知道如何重构它以使其比单线程排序更快吗？

Answer 1

问题出在嵌套的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块。这仍然受不确定的时间(现在，子线程可能已经完成了它的工作，甚至在你进入synchronized(x) { x.wait(); }块之前就调用了notify(和所谓的虚假唤醒。简单地说，您需要一个可验证的条件，该条件在调用wait()之前和之后进行检查，如wait()文档中所述：

与单参数版本一样，中断和虚假唤醒是可能的，此方法应始终在循环中使用：

synchronized (obj) {
    while (<condition does not hold>)
        obj.wait();
    ... // Perform action appropriate to condition
}

该条件可能是在调用 notify() 之前由子线程设置为true的 boolean 标志，以指示工作已完成。

请注意，这一切都是您使用时免费获得的 Thread.join() .同步发生在 join() 方法中，这两个调用不能重叠。此外，该实现使用可验证的条件(线程的活动状态(来确保仅在必要时调用wait()，并保护自身免受"虚假唤醒"的影响。

Answer 2

如果需要

的话，您将需要对数百万个值进行排序才能查看并行性的效果，因为您到处复制数组，这会给系统带来内存访问和垃圾回收的大部分压力，而不是排序。

要正确并行排序，您需要就地执行 - 这使得合并排序不太可能是一个好的候选者，因为它必须为目标创建一个新数组。

如果您所做的只是实验，请使用比较/计算密集型算法，例如气泡排序。

请注意，如果这已被设置为作业，那么您的讲师可能希望您回答，因为合并排序是并行性的不良候选者。