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

Question

我正在尝试仅使用等待/通知同步来实现合并排序。我知道更高级的结构，例如 Fork/Join、Executors。等等，但我需要在这里使用工作/通知。基于此https://courses.cs.washington.edu/courses/cse373/13wi/lectures/03-13/我用同步块(synchronized block)重构了方法 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 是这里的输入数组。

因此，我发现排序的性能下降了，甚至比单线程排序还要慢。我猜想瓶颈在于数组左右部分的两个同步块(synchronized block)内。有人知道如何重构它以使其比单线程排序更快吗？

Answer 1

问题出在您的嵌套同步 block 中:

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锁并允许另一个子线程启动它的工作，因此等于顺序性能。对于子线程的每次生成，由于启动线程持有的锁，子线程都被强制依次运行。

解决此问题的一种方法是首先启动线程，然后获取锁，并且仅获取您要等待的一个锁，而不是嵌套synchronized block 。这仍然受到未指定时间的影响(现在，即使在您输入 synchronized(x) { x.wait(); } 之前，子线程可能已经完成其工作并调用 notify block )和所谓的虚假唤醒。简而言之，您需要一个可验证的条件，在调用 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() 方法内，并且这两个调用不能重叠。此外，该实现使用可验证的条件(线程的 Activity 状态)来确保仅在必要时调用 wait() 并防止“虚假唤醒”。