Java 7: Fork / Join Framework - PullRequest
Новая
       38

Java 7: Fork / Join Framework

10 голосов
/ 19 августа 2010

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

Ответы [ 6 ]

8 голосов
/ 20 августа 2010

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

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

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

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

4 голосов
/ 19 августа 2010
3 голосов
/ 06 ноября 2012

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

Fork and Join: Java может работать в Excel безболезненно при параллельном программировании! Автор: Julien Ponge

3 голосов
/ 08 февраля 2012

В дополнение к тому, что уже было сказано, форк / объединение использует кражу работы - потоки, у которых заканчивается работа, могут красть задачи из других потоков, которые все еще заняты. И вот пример, который может помочь вам понять, как можно использовать 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)); 
  }

}
2 голосов
/ 19 августа 2010

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

1 голос
/ 30 апреля 2014

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

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 и предоставляет простую в использовании платформу для одновременного использования несколько процессоров.

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

  • Форкинг: разделение задачи на более мелкие задачи является разветвлением.
  • Объединение: объединение результатов меньших задач - объединение

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

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

  • разделить задачи
  • форк задачи
  • присоединиться к заданиям
  • составьте результаты 
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. Каждый раз, когда новая задача (или подзадача) создано, оно выдвигается к голове собственной очереди. Когда задание завершает задачу и выполняет соединение с другой задачей, которая не завершено, все работает умно. В потоке появляется новое задание из глава своей очереди и начинает выполнять, а не спать (по порядку дождаться завершения другого задания). На самом деле, если очередь поток пуст, затем поток извлекает задачу из хвоста очередь, принадлежащая другому потоку. Это не что иное, как кража работы алгоритм. Подробнее здесь

...