Java 7：分支/合并框架

Question

有人能解释一下Fork/Join是什么吗？

- Fork-Join

Answer 1

Fork Join是一个新框架，其API更易于使用，用于并行分治算法。

假设您有一个长时间运行的任务，对于这个例子，它有一个复杂的算法。您需要将大任务分叉，现在处理这两个任务。现在假设这两个任务仍然太大，您会将每个任务分叉为两个任务（此时共有四个任务）。

您会继续进行此操作，直到每个任务达到可接受的大小并调用算法。了解每个任务的调用是并行完成的很重要。当任务完成后，它将与其他分叉的任务合并结果。

这将继续进行，直到所有任务都已合并，返回一个任务。

- John Vint

Answer 2

除了已经提到的内容，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)); 
  }

}

- Vitalii Fedorenko

Answer 3

假设你有一组需要处理的事物。你有若干个线程可以获取这个集合的子集并对它们进行处理。它们都会同时运行（分叉部分），然后等待最后一个完成（联接部分）才返回。

- Nathan Hughes

---

在这种情况下，当前的父进程会_停止执行_，直到所有并发工作完成，然后才会恢复执行。我知道这已经包含在您的描述中了，但我认为值得非常明确地说明，因为这是使它与任何其他显式并行性不同的唯一关键点。 - Gian

好的，这不是分叉一堆操作，执行它们然后再合并。这是一种分而治之的方法。 - Tom Hawtin - tackline

Answer 4

我将解释什么是Fork Join并行性。这是一种广泛用于许多系统以实现并发的并行设计模式之一。我将使用一个例子来解释这个设计模式。

例如，假设我们有一个执行任务序列的程序：

A -> B -> C -> D。这里的A、B、C、D都是任务。

A需要8秒钟，B需要4秒钟，C需要6秒钟，D需要7秒钟。因此，这个程序的执行总共需要8+4+6+7=25秒。

现在你发现任务A、B、C是独立的，而D则依赖于A、B、C任务的结果。现在你可能会觉得，与其等待A完成，不如同时开始执行B。同样，Task 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;

在分叉合并并行性中，只有当任务是独立的时才能使用新线程卸载任务。否则会出现竞争条件。如果您有一个程序，其中一个任务正在等待另一个任务执行，但这不依赖于其结果，则可以使用分叉合并并行性将这两个任务与新线程一起卸载，并获得性能提升。但是请始终考虑线程开销。如果您的任务非常轻量级，则使用这些并行模式会降低性能，因为会有线程创建和上下文切换的开销。

- Tharsanan