Java分叉/连接框架逻辑

Question

这是今天回答另一个问题的“副作用”。这更多的是好奇心而不是实际问题。

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

也许其他人更了解为什么这种方法是可取的（而不是因为它有一个奇特的名字）。

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

未来是一个以不透明和未指定的方式将异步运行的任务封装到对象中的概念。有一个函数可以验证结果是否可用，还有一个函数允许您（等待和）检索结果
严格地说，您甚至不知道future是否异步运行，它可以在＜code＞get（）在实践中，Java将期货实现为任务队列上的任务，并附加了线程池（整个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。< br >在双核处理器上，它将提交/执行(1，3)-(2，4)-(5，7)-(6，8) ^[1]。< br >在四核处理器上，这将提交/执行(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）。

问题：

>

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

不保留参考位置。无论是处理器缓存还是虚拟内存都不会像这样被对待。为什么这是优越的？

除了在单处理器系统上，可以保证任务不会以接近其原始顺序的顺序进行调度。如果这真的无关紧要，这可能不是问题，但它使得类似栅栏或屏障的事情几乎不可行。拥有类似栅栏的东西的唯一方法是等待根对象完成并在此之后只提交新任务。这相当于完全的管道停顿（这正是你永远不想发生的事情）。

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

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

Answer 1

让我从一篇批评这个框架的文章(是的，是我写的)开始。Java Fork-Join灾难

现在回答您的问题：

>

不是。框架想要处理DAG。这是设计结构。

不是。正如本文所提到的，Java应用程序对缓存、内存等一无所知，因此这些假设是错误的。

是的。这正是所发生的事情。停顿是如此普遍，以至于框架需要创建“延续线程”来保持移动。这篇文章引用了一个问题，这里需要700多个延续线程。

我当然同意代码很复杂。对于应用程序来说，分散收集比窃取工作要好得多。至于留档，什么留档？甲骨文没有提供细节。这都是使用框架的推动力。

还有其他选择。

Answer 2

使用 ExecutorService 时，您将决定线程池中将有多少个线程，并且您计划的任务与这些任务创建的子任务之间没有区别。
相反，ForkJoinPool 类根据 1） 可用处理器和 2） 任务需求来管理线程。
在这种情况下，由活动任务创建的子任务由与外部任务不同的方法进行计划。
我们通常为整个应用程序提供一个分叉连接池（与使用 ExecutorService 不同，在 ExecutorService 中，在任何重要的应用程序中通常都有 1 个以上的分支连接池），并且不需要关闭。
我还没有回顾内部结构，给你一个更低级的解释，但如果你看到这里，有一个演示和一个基准，显示测量结果，显示所promise的并行性。

更新：＜br＞此框架解决了特定类型的问题（＜code＞ExecutorService＜/code＞更适用于混合了CPU和I/O活动的任务）
这里的基本思想是使用递归/分治方法，以保持CPU持续忙碌。其思想是创建新任务（分叉）并暂停当前任务，直到新任务完成（加入），但不创建新线程，也不具有共享工作队列
因此，通过创建有限数量的工作线程（与核心一样多），使用工作窃取来实现Fork-join框架。每个工作线程维护一个专用的双端工作队列
在分叉时，工作人员将新任务推到其任务的前端。当等待或空闲时，worker从其deque的头部弹出一个任务并执行它，而不是睡觉
如果worker的deque为空，则从另一个随机选择的worker的de que尾部窃取元素
我建议您阅读Java中的数据并行性，并自己做一些基准测试，以确信这一点。理论只在一定程度上有用。之后，进行测量，看看是否有显著的性能优势