14

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

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

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

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

4

2 回答 2

9

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

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

于 2012-08-31T16:21:14.043 回答
2

让我从一篇批评框架的文章开始[是的，我写了它]。Java Fork-Join 灾难

现在回答你的问题：

  1. 它不是。框架想要处理 DAG。这就是设计结构。

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

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

  4. 我当然同意代码很复杂。Scatter-gather 比应用程序的工作窃取要好得多。至于文档，什么文档？甲骨文没有提供详细信息。这一切都是为了使用该框架。

有替代方案。

于 2012-08-31T17:45:56.420 回答