алгоритм сортировки слияния Java с wait()/notify() synchronization

Question

Я пытаюсь реализовать сортировку слияния, используя только синхронизацию wait/notify. Я знаю о более высокоуровневых конструкциях, таких как 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 части может продолжаться, но инициирующая нить все еще держит right замок во время ожидания на left. После того, как суб-поток завершит обработку left, он назовет notify, а затем отпустит блокировку left, которая позволяет wait() переупаковывать ее и возвращать.

Затем инициирующее поток может вызвать right.wait(), который будет освободить right замок и позволяет другие подразделы нити, чтобы начать свою работу, следовательно, равный последовательную работу. Для каждого нереста подпотоков подчиненные потоки принудительно запускаются один за другим из-за блокировок, удерживаемых инициирующим потоком.

Один из способов исправить это будет первым запуском потоков и последующим приобретением замков, и только одна блокировка, которую вы собираетесь сделать до wait, а не гнездовые блоки .Это все еще зависит от неуточненного времени (теперь подпоток, возможно, завершил свою работу и вызвал notify еще до того, как вы введете блок synchronized(x) { x.wait(); }) и так называемые поддельные пробуждения. Проще говоря, вам нужно проверяемое условие, которое проверяется до и после вызова wait() как объяснено в documentation of wait():

Как и в одном аргументе версии, прерывание и ложные пробуждения возможны, и этот метод всегда должен быть использован в петля:

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

условие может быть boolean флаг установлен в true по суб-нить прямо перед вызовом notify() сигнализировать о том, что работа выполнена.

Обратите внимание, что это все, что вы получаете бесплатно при использовании Thread.join(). Синхронизация происходит в методе join(), и эти два вызова не могут пересекаться. Кроме того, реализация использует проверяемое условие (живое состояние потока), чтобы обеспечить вызов wait() только при необходимости и защитить себя от «побочных пробуждений».

Answer 2

Вам нужно будет отсортировать миллионы значений, чтобы увидеть эффект параллелизма, если вы когда-либо делаете это, потому что вы копируете массивы повсюду и накладываете большую нагрузку на систему на доступ к памяти и сборку мусора , а не сортировки.

Для правильной параллелизации сортировки вам нужно будет сделать это на месте - что делает слияние очень маловероятным, чтобы быть хорошим кандидатом, потому что он должен создать новый массив для цели.

Если все, что вы делаете, это эксперимент, используйте алгоритм сравнения/вычисления с интенсивным вычислением, подобный сортировке пузырьков.

Обратите внимание, что если это задано как задание, то ваш лектор, вероятно, ожидает, что вы ответите , вы не можете, потому что merge-sort является плохим кандидатом на параллелизм.