Java fork/join框架逻辑

Question

这对于今天另一个问题的回答是一个"副作用" .这更多是关于好奇心而不是实际问题.

Java SE 7提供了Oracle称之为"fork/join框架"的东西.这是将工作安排到多个处理器的一种可能的优秀方式.虽然我理解它应该如何工作,但我无法理解它优越的地方和关于偷工作的说法.

也许其他人更深入地了解为什么这种方法是可取的(除了因为它有一个奇特的名字).

/加盟叉的根本原语ForkJoinTasks,这是FutureS,而这个想法是要么执行工作立即[原文](措辞是误导,因为"立即"意味着它同步发生在主线程,在现实中发生这种情况的内部a Future)低于某个阈值或递归地将工作划分为两个任务,直到达到阈值.

未来是一种封装任务的概念,该任务以不透明和未指定的方式异步运行到对象中.您有一个函数可以验证结果是否可用,并且您获得了一个允许您(等待和)检索结果的函数.
严格地说,你甚至不知道未来是否异步运行,它可以在内部执行get().从理论上讲,实现可以为每个未来生成一个线程或使用线程池.
实际上,Java将future作为任务队列上的任务实现,并附加了一个线程池(对于整个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).

问题:

1. 不是简单地将sThreshold连续项填充到一个任务中,而是将一个任务一个接一个地提交给线程池的任务队列,而是生成树状递归层次结构.这涉及为N个子任务构造,引用和销毁N + log2(N)对象,这些子任务事实上什么都不做.为什么这个优越？

2. 没有保留引用的位置.处理器缓存和虚拟内存都没有像那样对待.为什么这个优越？

3. 除了在单处理器系统上,保证任务不按照原始订单附近的顺序进行调度.如果它真的无关紧要,这可能不成问题,但它使像栅栏或栅栏这样的东西几乎不可行.像栅栏一样的唯一方法是等待根对象完成,然后只提交新任务.这相当于一个完整的管道停滞(这正是你不希望发生的).

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

---

^[1]让我们不要太复杂,并假设工作线程不会相互超越,任务都需要同时处理.否则,执行当然可能以不同的顺序发生,尽管提交将是相同的.

Answer 1

当您使用a时,ExecutorService 您将决定线程池中将有多少线程,并且您计划的任务与这些任务创建的子任务之间没有任何区别.
ForkJoinPool而是基于1)可用处理器和2)任务需求来管理线程.
在这种情况下,活动任务创建的子任务通过与外部任务不同的方法进行调度.
我们通常为整个应用程序提供一个fork-join池(与使用ExecutorService通常在任何非平凡应用程序中具有多于1 的位置不同)并且不需要shutdown.
我没有审查内部结构给你一个更低级别的解释,但如果你看到这里有一个演示文稿和一个基准测试显示测量显示承诺的并行性.

更新:
此框架解决了特定类型的问题(ExecutorService对于混合了CPU和I/O活动的任务更有效).
这里的基本思路是使用递归/分而治之的方法来保持CPU不断忙碌.我们的想法是创建新任务(分叉)并暂停当前任务,直到新任务完成(加入),但不创建新线程且没有共享工作队列.
因此,通过创建有限数量的工作线程(尽可能多的核心),使用工作窃取实现Fork-join框架.每个工作线程都维护一个私有的双端工作队列.
在分叉时,工人在其双端队列的头部推进新任务.在等待或空闲时,工作人员从其双端队列的头部弹出一个任务并执行它而不是睡觉.
如果工人的双端队列是空的,则从另一个随机选择的工人的双端队列的尾部偷走一个元素.
我建议您阅读Java中的数据并行,并自己做一些基准以确信.理论只有在一定程度上是好的.之后,进行测量以确定是否存在显着的性能优势