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

Question

我正在尝试仅使用 wait/notify 同步来实现合并排序。我知道更多高级结构，例如 Fork/Join，Executors。等等，但我需要在这里使用 work/notify 。基于此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

您将需要对数百万个值进行排序以查看并行性的效果，如果您这样做的话，因为您正在到处复制数组，这给系统带来了内存访问和垃圾方面的大部分压力collection，排序不上

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

如果您所做的只是试验，那么请使用 compare/compute 密集型算法，例如 bubble-sort。

请注意，如果这已被设置为作业，那么您的讲师可能希望您回答 您不能，因为 merge-sort 不适合并行处理.

Answer 2

问题出在嵌套的 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() 重新获取它和 return.

然后启动线程可以调用 right.wait() 这将释放 right 锁并允许其他子线程开始工作，因此等于顺序性能。对于每个子线程的生成，由于启动线程持有锁，子线程一个接一个地被强制执行运行。

解决此问题的一种方法是先启动线程，然后再获取锁，并且只获取您即将 wait 的一个锁，而不是嵌套 synchronized 块。这仍然受制于未指定的时间（现在，子线程可能已经完成其工作并甚至在您进入 synchronized(x) { x.wait(); } 块之前调用 notify）和所谓的 spurious唤醒。简单地说，您需要一个可验证的条件，该条件在调用 wait() 之前和之后进行检查，如 documentation of wait():

中所述

As in the one argument version, interrupts and spurious wakeups are possible, and this method should always be used in a loop:
synchronized (obj) {
    while (<condition does not hold>)
        obj.wait();
    ... // Perform action appropriate to condition
}

条件可能是子线程在调用 notify() 之前将 boolean 标志设置为 true 以表明工作已完成。

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

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

Java merge sort algorithm with wait()/notify() synchronization

java

concurrency

performance

mergesort

multithreading