Java fork/join 框架逻辑

Question

这是 an answer 的“副作用”。关于今天的另一个问题。与其说是实际问题，不如说是好奇心。

Java SE 7 提供了 Oracle 所谓的“fork/join 框架”。这可能是将工作安排到多个处理器的一种更好的方法。虽然我理解它应该如何工作，但我无法理解它的优越之处以及关于窃取工作的说法。

也许其他人更了解为什么这种方法是可取的(除了因为它有一个花哨的名字)。

fork/join 的底层原语是 ForkJoinTask s，它们是 Future s，想法是要么 立即执行工作 [原文如此](措辞具有误导性，因为“立即”意味着它在主线程中同步发生，实际上这发生在 Future 内)低于某个阈值 或 递归地将工作分成两个任务，直到达到阈值。

future 是将异步运行的任务以不透明和未指定的方式封装到对象中的概念。您有一个函数可以让您验证结果是否可用，您还有一个函数可以让您(等待和)检索结果。
严格来说，你甚至不知道 future 是否异步运行，它可以在 get() 内部执行.该实现理论上也可以为每个 future 生成一个线程或使用线程池。
在实践中，Java 将 futures 实现为任务队列上的任务，并附加了一个线程池(整个 fork/join 框架也是如此)。

fork/join 文档给出了这个具体的使用示例:

protected void compute() {
    if (mLength < sThreshold) {
        computeDirectly();
        return;
    }

    int split = mLength / 2;

    invokeAll(new ForkBlur(mSource, mStart, split, mDestination),
              new ForkBlur(mSource, mStart + split, mLength - split,
                           mDestination));
}

这以与 Mergesort 遍历它们的方式相同的方式将任务提交到底层线程池的任务队列(感谢递归)。
举例来说，我们有一个包含 32 个“项目”的数组要处理，阈值为 4，并均匀分割，它将产生 8 个任务，每个任务有 4 个“项目”，如下所示:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
                                               .
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
                       .                       .                       .
00 01 02 03 04 05 06 07|08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23|24 25 26 27 28 29 30 31
           .           .           .           .           .           .           .
00 01 02 03|04 05 06 07|08 09 10 11|12 13 14 15|16 17 18 19|20 21 22 23|24 25 26 27|28 29 30 31
------------------------------------------------------------------------------------------------
     1     |     2     |     3     |     4     |     5     |     6     |     7     |     8     | 

在单核处理器上，这将按顺序提交/执行(以非常复杂的方式)任务组 1-2-3-4-5-6-7-8。
在双核处理器上，这将提交/执行 (1,3)-(2,4)-(5,7)-(6,8) [1]。
在四核处理器上，这将提交/执行 (1,3,5,7)-(2,4,6,8)。

相比之下，没有所有高级魔法的幼稚实现只会立即将任务 1-2-3-4-5-6-7-8 提交到任务队列。总是。

在单核处理器上，这将提交/执行 1-2-3-4-5-6-7-8。
在双核处理器上，这将提交/执行 (1,2)-(3,4)-(5,6)-(7,8)。
在四核处理器上，这将提交/执行 (1,2,3,4)-(5,6,7,8)。

问题:

不是简单地将 sThreshold 连续项目塞进一个任务中，并一个接一个地提交任务到线程池的任务队列，而是生成了树状递归层次结构。这涉及为实际上什么都不做的 N 个子任务构造、引用和销毁 N+log2(N) 个对象。为什么这是优越的？

不保留引用位置。处理器缓存和虚拟内存都不会像这样被对待。为什么这是优越的？

除了在单处理器系统上，任务保证不会以接近其原始顺序的任何顺序进行调度。如果它真的无关紧要，这可能没有问题，但它会使诸如栅栏或屏障几乎不可行。拥有像围栏这样的东西的唯一方法是等待根对象完成，然后才提交新任务。这相当于一个完整的管道停顿(这正是您不想发生的事情)。

Oracle 文档声称这种方法实现了工作窃取，因此比线程池更好。我没有看到这种情况发生。我所看到的只是将任务提交到普通线程池的一种非常复杂的方式。这应该如何神奇地实现工作窃取？

[1] 让我们不要让它太复杂，假设工作线程不会超过彼此，任务都需要相同的时间来处理。否则，执行当然可能以不同的顺序发生，尽管提交是相同的。

Answer 1

当您使用 ExecutorService 时您将决定线程池中有多少线程，您安排的任务与这些任务创建的子任务之间没有任何区别。ForkJoinPool类代替，管理基于 1)可用处理器和 2)任务需求的线程。
在这种情况下，由 Activity 任务创建的子任务通过与外部任务不同的方法进行调度。
我们通常有一个用于整个应用程序的 fork-join 池(与使用 ExecutorService 不同，在任何非平凡应用程序中通常有超过 1 个)并且不需要 shutdown .
我没有回顾内部结构给你一个更底层的解释，但如果你看到 here有一个演示文稿和一个基准，显示了显示所 promise 的并行性的测量。

更新:
该框架解决了特定类型的问题(ExecutorService 更适用于同时具有 CPU 和 I/O Activity 的任务)。
这里的基本思想是使用递归/分而治之的方法来保持 CPU 不断忙碌。这个想法是创建新任务( fork )并挂起当前任务直到新任务完成(加入)但没有 创建新线程和 没有 有一个共享的工作队列。
因此 Fork-join 框架是通过创建有限数量的工作线程(与内核一样多)使用工作窃取来实现的。每个工作线程维护一个私有(private)的双端工作队列。
fork 时，worker 在其双端队列的头部推送新任务。当等待或空闲时，worker 从其双端队列的头部弹出一个任务并执行它而不是 hibernate 。
如果 worker 的双端队列为空，则从另一个随机选择的 worker 的双端队列尾部窃取一个元素。
我建议阅读 Data Parallelism in Java并且自己也做一些基准测试以被说服。理论只是在一定程度上是好的。之后进行测量以查看是否存在显着的性能优势