Java 7: Fork/Join Framework

Может кто-нибудь объяснить, что такое Fork/Join?

Ответ 1

Fork Join - это новый фреймворк, который имеет более простой в использовании API для алгоритма параллелизма, разделения и завоевания.

Допустим, у вас есть долгосрочное задание, которое, в данном случае, имеет сложный алгоритм. Вы хотели бы раскошелиться на большие задачи и теперь работать над этими двумя задачами. Теперь давайте скажем, что эти две задачи все еще слишком велики, вы бы разбили каждую на две задачи (на данный момент их четыре).

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

Это будет продолжаться до тех пор, пока все задачи не будут объединены и одна задача не будет возвращена.

Ответ 2

Проверьте эти ссылки -

http://www.artima.com/forums/flat.jsp?forum=276&thread=219155

http://lambda-the-ultimate.org/node/3521

http://www.ibm.com/developerworks/java/library/j-jtp11137.html

Ответ 3

В дополнение к тому, что уже было сказано, fork/join использует кражу работы - потоки, у которых заканчивается работа, могут красть задачи из других потоков, которые все еще заняты. И вот пример, который может помочь вам понять, как можно использовать FJ:

public class SumCounter extends RecursiveTask<Long> { 

  private final Node node; 

  public SumCounter(Node node) { 
    this.node = node; 
  } 

  @Override
  protected Long compute() { 
    long sum = node.getValue();
    List<ValueSumCounter> subTasks = new LinkedList<>(); 

    for(Node child : node.getChildren()) { 
      SumCounter task = new SumCounter(child); 
      task.fork(); // run asynchronously
      subTasks.add(task); 
    }

    for(SumCounter task : subTasks) { 
      sum += task.join(); // wait for the result 
    } 

    return sum;
  }

  public static void main(String[] args) { 
    Node root = getRootNode(); 
    new ForkJoinPool().invoke(new SumCounter(root)); 
  }

}

Ответ 4

Это очень хороший ресурс для понимания Fork and Join:

Вилка и присоединение: Java может Excel в бесконечном параллельном программировании! Жюльеном Понге

Ответ 5

Скажем, у вас есть коллекция вещей, которые необходимо обработать. У вас есть несколько потоков, которые могут захватывать подмножества этой коллекции и обрабатывать их. Все они делают это одновременно (часть разветвления), затем ждут, пока последний завершит работу (часть объединения), прежде чем вернуться.

Ответ 6

Позвольте мне просто поместить мои два цента, чтобы сделать базовое представление о вилке/объединении простым.

What is Fork/Join?

The fork/join framework is an implementation of the ExecutorService interface
that helps you take advantage of multiple processors. It is designed for work 
that can be broken into smaller pieces recursively. The goal is to use all the
available  processing power to enhance the performance of your application.

Эта структура очень полезна для моделирования деления и покорения проблемы. Этот подход подходит для задач, которые можно разделить рекурсивно и вычисляется в меньших масштабах; вычисленные результаты затем объединены.
Структура представляет собой реализацию интерфейса ExecutorService и обеспечивает простую в использовании параллельную платформу для использования нескольких процессоров.

Термин, полезный для этой структуры

Forking: разделение задачи на более мелкие задачи разворачивается.
Присоединение: объединение результатов из меньших задач объединяет

Как и в любой реализации ExecutorService, платформа fork/join распространяет задачи на рабочие потоки в пуле потоков. Структура fork/join отличается тем, что использует алгоритм обработки работы. Рабочие потоки, которые не работают, могут украсть задания из других потоков, которые все еще заняты.

Алгоритм Fork/Join разработан следующим образом:

разделенные задачи
fork задачи
присоединиться к задачам
составить результаты

doRecursiveTask(input){
  if( task is small enough to handled by a thread){
      compute the small task;
      if there is result to return, then do so
  }else{
      divide the task i.e, fork() into two parts
      call compute on first task, join on second task, combine both results and return
  }
}

Что такое алгоритм обработки работы?

Каждый рабочий поток в структуре Fork/Join имеет рабочую очередь, которая осуществляется с использованием Deque. Каждый раз, когда новая задача (или подзадача) созданный, он подталкивается к голове собственной очереди. Когда задание завершает задачу и выполняет соединение с другой задачей, которая не является завершен, он работает умный. Поток выдает новую задачу из голова его очереди и начинает выполнять, а не спать (в порядке дождаться завершения другой задачи). На самом деле, если очередь нить пуста, тогда поток выталкивает задачу из хвоста очередь, принадлежащую другому потоку. Это не что иное, как кража работы алгоритм. Подробнее здесь

Ответ 7

Я отвечу, что такое параллелизм Fork Join. Это один из шаблонов параллельного проектирования, широко используемых во многих системах для достижения параллелизма. Я объясню этот шаблон проектирования на примере.

Например, допустим, у нас есть программа, которая выполняет последовательность задач:

A → B → C → D. Здесь A, B, C, D - задачи.

А занимает 8 секунд
B занимает 4 секунды
C занимает 6 секунд
D занимает 7 секунд

Таким образом, для выполнения этой программы потребуется всего 8 + 4 + 6 + 7 = 25 секунд.

Теперь вы узнали, что задачи A, B, C независимы, а D зависит от результатов задач A, B, C. Теперь у вас может возникнуть ощущение, что вместо того, чтобы ждать завершения A, мы можем начать выполнение B одновременно. То же самое для задачи C Вы можете запустить задачу одновременно с A и B. То, что вы можете сделать, это: Вы можете вызвать 3 новых потока вашим основным потоком и назначить им задачи A, B, C и дождаться результатов, прежде чем начинать выполнение задачи D. Если ваш машина имеет несколько ядер, тогда эти потоки могут работать параллельно.

Теперь время выполнения программы:

max(time_taken_A,_B,_C) + time_taken_D + threading_overhead_time

который почти равен = 8 + 7 + k = 15 + k;

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