Java fork/join 框架逻辑

concurrency multithreading java java.util.concurrent fork-join

2022-09-04 03:46:20

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

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

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

fork/join的基础原语是s，它们是s，其思想是立即执行工作[原文如此]（措辞具有误导性，因为“立即”意味着它在主线程中同步发生，实际上这发生在低于某个阈值的a）内，或者将工作递归地分成两个任务，直到达到阈值。ForkJoinTaskFutureFuture

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

分叉/连接文档给出了以下具体用法示例：

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

答案 1

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

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

答案 2

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

现在回答您的问题：

事实并非如此。框架想要处理 DAG。这就是设计结构。
事实并非如此。正如文章所提到的，Java应用程序对缓存，内存等一无所知，因此这些假设是错误的。
是的。这正是所发生的事情。停滞是如此普遍，以至于框架需要创建“延续线程”来保持移动。本文引用了一个问题，其中需要700多个继续线程。
我当然同意代码很复杂。对于应用程序，Scatter-gather 比工作窃取要好得多。就文档而言，什么文档？甲骨文没有提供任何细节。这都是使用框架的推动力。

还有其他选择。