fork / join框架如何比线程池更好?

问题

使用newfork/join framework有什么好处,只需在开始时将大任务分成N个子任务,将它们发送到缓存的线程池(来自Executors)并等待每个任务完成?我没有看到使用fork / join抽象如何简化问题或使解决方案从我们多年来的工作中提高效率。

例如,tutorial example中的并行化模糊算法可以这样实现:

public class Blur implements Runnable {
    private int[] mSource;
    private int mStart;
    private int mLength;
    private int[] mDestination;

    private int mBlurWidth = 15; // Processing window size, should be odd.

    public ForkBlur(int[] src, int start, int length, int[] dst) {
        mSource = src;
        mStart = start;
        mLength = length;
        mDestination = dst;
    }

    public void run() {
        computeDirectly();
    }

    protected void computeDirectly() {
        // As in the example, omitted for brevity
    }
}

在开头拆分并将任务​​发送到线程池:

// source image pixels are in src
// destination image pixels are in dst
// threadPool is a (cached) thread pool

int maxSize = 100000; // analogous to F-J's "sThreshold"
List<Future> futures = new ArrayList<Future>();

// Send stuff to thread pool:
for (int i = 0; i < src.length; i+= maxSize) {
    int size = Math.min(maxSize, src.length - i);
    ForkBlur task = new ForkBlur(src, i, size, dst);
    Future f = threadPool.submit(task);
    futures.add(f);
}

// Wait for all sent tasks to complete:
for (Future future : futures) {
    future.get();
}

// Done!

任务进入线程池的队列,当工作线程变为可用时,它们将从该队列执行。只要分裂足够精细(以避免必须特别等待最后一个任务)并且线程池具有足够的(至少N个处理器)线程,所有处理器都在全速工作,直到整个计算完成。

我错过了什么吗?使用fork / join框架的附加价值是什么?


#1 热门回答(113 赞)

我认为基本的误解是,Fork / Join的例子不是3778164398,而是显示工作窃取**但只是某种标准的分而治之。

工作窃取将是这样的:工人B已完成他的工作。他是一个善良的人,所以他环顾四周,看到工人A仍然非常努力。他漫步并问道:"嘿小伙子,我可以帮你一把。"回复。 "很酷,我有1000个单位的任务。到目前为止,我已经完成了345次离开655.你能不能在673到1000号工作,我会做346到672。" B说"好的,我们先来吧,我们可以早点去酒吧。"

你看 - 即使他们开始真正的工作,工人也必须彼此沟通。这是示例中缺少的部分。

另一方面,示例仅显示"使用分包商"之类的内容:

工人A:"Dang,我有1000个单位的工作。对我来说太多了。我会自己做500个并将500个转包给其他人。"这种情况一直持续到大任务被分解为每个10个单元的小包。这些将由可用的工人执行。但是,如果一个包是一种毒丸并且需要比其他包更长的时间 - 运气不好,分裂阶段就结束了。

Fork / Join和预先拆分任务之间唯一的区别是:在前期拆分时,你可以从一开始就完整地处理工作队列。示例:1000个单位,阈值为10,因此队列有100个条目。这些数据包被分发给线程池成员。

Fork / Join更复杂,并尝试将队列中的数据包数量保持较小:

  • 步骤1:将包含(1 ... 1000)的一个数据包放入队列
  • 步骤2:一个工作人员弹出数据包(1 ... 1000)并用两个数据包替换它:(1 ... 500)和(501 ... 1000)。
  • 步骤3:一名工作人员弹出数据包(500 ... 1000)并推送(500 ... 750)和(751 ... 1000)。
  • 步骤n:堆栈包含以下数据包:(1..500),(500 ... 750),(750 ... 875)...(991..1000)
  • 步骤n 1:弹出并执行包(991..1000)
  • 步骤n 2:弹出并执行包(981..990)
  • 步骤n 3:弹出包(961..980)并分成(961 ... 970)和(971..980)。 ....

你会看到:在Fork / Join中,队列较小(示例中为6),并且"split"和"work"阶段是交错的。

当多个工人同时弹出和推动时,互动当然不是那么清楚。


#2 热门回答(23 赞)

如果你有n个繁忙的线程都是100%独立工作,那么它将比Fork-Join(FJ)池中的n个线程更好。但它从来没有这样做过。

可能无法将问题精确地分成n个相等的部分。即使你这样做,线程调度也是不公平的。你最终会等待最慢的线程。如果你有多个任务,那么它们每个都可以运行时的并行性低于n路(通常效率更高),但是当其他任务完成时,它会进入n路。

那么为什么我们不把这个问题简化为FJ大小的部分并且有一个线程池工作。典型的FJ使用将问题分解成小块。以随机顺序执行这些操作需要在硬件级别进行大量协调。管理费用将是一个杀手。在FJ中,任务被放入队列中,线程以后进先出顺序(LIFO /堆栈)读取,并且工作窃取(通常在核心工作中)先进先出(FIFO /"队列")。结果是长阵列处理可以在很大程度上顺序完成,即使它被分成很小的块。 (同样的情况是,在一次大爆炸中将问题分解成小的均匀大小的块可能并不容易。假设处理某种形式的层次结构而没有平衡。)

结论:FJ允许在不平衡的情况下更有效地使用硬件线程,如果你有多个线程,则总是如此。


#3 热门回答(12 赞)

Fork / join与线程池不同,因为它实现了工作窃取。 FromFork/Join

与任何ExecutorService一样,fork / join框架将任务分配给线程池中的工作线程。 fork / join框架是不同的,因为它使用了工作窃取算法。不用做的事情的工作线程可以从仍然忙碌的其他线程中窃取任务。

假设你有两个线程,4个任务a,b,c,d分别需要1,1,5和6秒。最初,a和b分配给线程1,c和d分配给线程2.在线程池中,这将花费11秒。使用fork / join,线程1完成并可以从线程2中窃取工作,因此任务d最终将由线程1执行。线程1执行a,b和d,线程2只是c。总时间:8秒,而不是11秒。

编辑:正如Joonas指出的那样,任务不一定预先分配给一个线程。 fork / join的想法是线程可以选择将任务拆分为多个子块。所以要重申以上内容:

我们有两个任务(ab)和(cd)分别需要2和11秒。线程1开始执行ab并将其分成两个子任务a和b。与线程2类似,它分为两个子任务c&d。当线程1完成a&b时,它可以从线程2中窃取d。