Java分支/合并框架逻辑

Question

Java分支/合并框架逻辑

javamultithreadingconcurrencyjava.util.concurrentfork-join

14

这个问题是在另一个问题的回答中作为“副作用”出现的，更多的是好奇而非实际问题。

Java SE 7提供了Oracle所称的“fork/join框架”。这是一种预计上优于其他方法的方式来调度任务到多个处理器。虽然我理解它应该如何工作，但我无法理解它为什么更优秀以及有关抢占式任务执行的声明。

也许有人对这种方法更有深入的见解（除了因为它有一个花哨的名字）。

fork/join的基本组件是ForkJoinTask，它们是Future，其思想是要么立即执行任务（“立即”这个词措辞不太准确，因为它暗示着任务会在主线程同步执行，事实上它是在Future内部执行），直到达到某个阈值或者将任务递归地分成两个任务，直到达到阈值。

Future是一个将异步运行的任务封装成一个对象的概念，具体实现方式是不透明和未指定的。你有一个函数可以验证结果是否可用，并且你可以得到一个函数来（等待并）检索结果。
严格来说，你甚至不知道Future是否异步运行，它可能在get()内执行。在理论上，实现也可以为每个Future创建一个线程或使用线程池。
实际上，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));
}

这将以与归并排序相同的方式遍历任务，并将它们提交到底层线程池的任务队列中（感谢递归）。
例如，假设我们有一个包含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,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 + log2（N）个实际上什么都不做的子任务对象。这种方法为什么更优越？

2.没有保留参考位置的本地性，既不缓存处理器，也不虚拟内存。这种方法为什么更优越？

3.除了在单处理器系统上，任务保证不会按其原始顺序的任何地方接近的顺序进行调度。如果确实没有关系，那可能就没有问题，但是这使得像围栏或障碍物之类的事情几乎不可行。唯一的方式是等待根对象完成，并且只在此之后提交新任务。这相当于完全的管道停顿（这正是您永远不想发生的）。

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

- Damon

2个回答

2

让我从一篇文章开始[是的，我写的]，批评这个框架。 Java分叉-加入灾难现在回答你的问题：

1.不是的。该框架希望处理DAG。这是设计结构。

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

3.是的。这正是发生的事情。停顿是如此普遍，以至于框架需要创建“连续线程”来保持运动。文章引用了一个问题，在那里需要超过700个连续线程。

4.我确实同意代码很复杂。散布收集比工作窃取更适用于应用程序。就文档而言，什么文档？Oracle没有详细信息。这都是推动使用该框架的。

还有其他选择。

- edharned

这篇文章和API文档都提到了关于工作窃取的内容。但我不太明白这是怎么实现的。请指教。 - Damon

不确定你所说的“这”是什么意思？工作窃取在操作系统中运行良好。工作共享在应用程序中运行良好。F/J框架的问题在于它试图模拟操作系统或伪操作系统，但缺乏任务控制、错误恢复、文档等功能。 - edharned

1

我不怀疑工作偷取机制的有效性，在应用程序中实现工作偷取机制也没有根本性的错误（虽然这不是我首选的方式）。然而，文档说明FW是“独特的，因为它使用工作偷取算法”，这是递归划分无法提供的内容（尽管他们使其听起来像是可以）。这是线程池实现的一个实现细节（至少我不知道有什么不同）。 - Damon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cratylus · Accepted Answer

当你使用 ExecutorService 时，你将决定线程池中有多少个线程，并且在你计划的任务和这些任务创建的子任务之间没有任何区别。
相反，ForkJoinPool 类会根据 1）可用处理器和 2）任务需求来管理线程。
在这种情况下，活动任务创建的子任务是通过不同于外部任务的方法进行调度的。
我们通常为整个应用程序使用一个 fork-join 池（不像使用 ExecutorService 在任何非微不足道的应用程序中都典型地有超过1个线程池），而且不需要 shutdown。
我没有审查内部以给您更低级别的解释，但如果您在 here 看到一个演示和基准测试，显示了所承诺的并行性。 更新：
这个框架解决了特定类型的问题（ExecutorService 对于具有 CPU 和 I/O 活动混合的任务效果更好）。
基本思路是采用递归/分治的方法，以使 CPU 不断保持繁忙状态。其想法是创建新任务（forking），并挂起当前任务直到新任务完成（join），但不创建新线程，也不需要共享工作队列。
因此，通过创建有限数量的工作线程（与内核数相同）来使用工作窃取实现 Fork-join 框架。每个工作线程维护一个私有的双端工作队列。
在 fork 时，工作线程将新任务推送到其 deque 的头部。在等待或空闲时，工作线程从其 deque 的头部弹出一个任务并执行它，而不是睡眠。
如果工作线程的 deque 是空的，则从随机选择的另一个工作线程的 deque 尾部窃取一个元素。
我建议阅读Java 中的数据并行性，并进行一些基准测试以确信。理论只能说明一部分，之后，您需要测量自己的数据，以查看是否存在显著的性能优势。