2

我试图了解工作窃取对递归任务的影响：工作窃取的优点之一是当前工作/线程可能执行其自己的衍生任务；增加数据局部性。但是，当工作人员加入其派生任务时，通常情况下会发生什么？例如：

Future<String> a=pool.submit(()->doA());
b=doB();
return a.get()+b;

我认为这里当前线程将被阻塞，因此无法从自己的队列中获取工作，因此另一个工作人员将不得不窃取这些工作。这将否定工作窃取的地方优势。但是，根据维基百科（https://en.wikipedia.org/wiki/Work_stealing）“工作窃取是为并行计算的“严格”分叉连接模型设计的”我的推理肯定有一些错误，但我可以没找到。

更多详细信息，请考虑以下代码：

Future<String> res=pool.submit(()->{
  Future<String> a=pool.submit(()->doA());
  b=doB();
  return a.get()+b;
  });
res.get();

此代码应在工作人员内部开始计算。这样的工人将产生一个新的任务。然后他尝试得到这个嵌套任务的结果。这个嵌套任务是如何执行的？

4

1 回答 1

2

fork-join pool 为 Java 程序员提供了一个高性能、并行、精细的任务执行框架。

它通过分而治之来解决问题。将任务拆分为子任务。任务通过fork()方法创建子任务。

当任务客户端提交/调用/执行分叉连接任务时，任务进入共享队列，该共享队列用于提供由WorkerThread管理的非共享双端队列（又名“双端队列”） 。

一个或多个WorkerThread称为 Fork-Join 池。

一个WorkerThread从共享队列中拉出任务，然后他们开始处理工作（使用非共享队列）。

Fork-Join-Pool 中的每个WorkerThread（实际上是一个Java 线程）都在一个循环中运行，该循环不断扫描（子）任务以执行。

我们的目标是尽量让WorkerThreads尽可能忙碌，所以我们希望它们总是有事可做。

目标是最大化处理器核心利用率。

每个WorkerThread都有它的双端队列（又名“双端队列”），作为其主要任务来源。

除此之外，用于将非分叉连接任务获取到分叉连接池中的其他共享队列排在第一位。

“双端队列”由WorkQueue（嵌套在 ForkJoinPool 中的 Java 类）实现。该类中的一些重要方法是push()、pop() 和 poll()。

在某些时候，任务无法取得任何进展，因为它正在通过join()方法等待子任务完成。

此连接不同于 Java 线程中的连接。

在Java Thread Join中，如果一个任务没有返回结果，就会阻塞，并等待另一个线程完成。

如果在 Fork-Join 中join()发生阻塞，那么WorkerThread 将停止在当前线程上工作并开始执行子任务。

每当您在RecursiveTask<>或 RecursiveAction内部的计算方法中调用fork()时， 该方法始终在 fork-join-pool 中的线程上下文中运行。

如果WorkerThread调用fork()正在运行RecursiveTask<>或 RecursiveAction任务，则新的ForkJoinTask * 将被推送到该工人“双端队列”线程的头部。

它以后进先出的顺序推动它。

当我们为此任务调用join()时，该任务将从“双端队列”（堆栈顶部）的头部弹出并在WorkerThread中运行到完成（继续运行直到完成）。

我们为什么要做后进先出法？为什么我们在前面推，在前面弹出？为了提高引用的局部性，提高缓存性能，让你尽可能快地得到处理，有时称为新鲜工作之前过时。

ForkJoinTask 支持细粒度的数据并行。

ForkJoinTask比Java 线程轻，它没有自己的运行时堆栈。

ForkJoinTask将数据块与对该数据的计算相关联。

一个真正的 Java 线程有它自己的堆栈、寄存器和许多其他资源，这些资源允许它被操作系统内部的线程调度程序独立管理。

大量的 ForkJoinTask可以在Fork-Join-Pool 中少得多的WorkerThread中运行。

WorkerThread的数量通常（如果未指定）是内核数量的函数。每个WorkerThread都是一个Java 线程对象，具有您期望从普通线程获得的所有装备。

ForkJoinTask有两个重要的方法来控制并行处理和合并结果，它们是fork()和join()。

fork()安排在适当的线程池中异步执行此任务。fork()就像 Thread.start() 的轻量版。

fork()不会创建 Java 工作线程（至少不是直接创建），但最终它将在 Java 线程上运行。

它不会立即开始运行，而是将子任务放在工作队列的头部。

当子任务完成时，join()返回计算。Fork-Join 池中的加入不同于经典的 Java 线程加入。Java 线程用作屏障同步器以等待另一个线程完成然后加入它（在另一个线程完成之前您不能继续）。

常规线程中的连接会阻塞调用线程。

Fork-Join 池中的连接不会简单地阻塞调用线程，而是分配WorkerThread来运行挂起的子任务。

当WorkerThread遇到join()时，它会处理任何其他子任务，直到它注意到目标子任务已完成。在此子任务结果完成之前， WorkerThreads不会返回给调用者。

fork-join 任务中的 Join 不是阻塞的，它保存当前任务，因此只有在join()创建的子任务完成后才能继续计算。

WorkerThread发现，该任务在子任务完成之前被阻塞，因此它开始处理子任务。

WorkerThread以LIFO顺序处理它自己的“deque”，方法是从它自己的“ deque ”中弹出（子）任务。

工作窃取
当WorkerThread没有其他事情可做时 - “空闲”。如果WorkerThread自己的队列为空，它会尝试从其他繁忙线程“ deque ”的尾部“窃取”一个子任务"，即随机选择，以最大限度地提高核心利用率。

这些任务按FIFO顺序“被盗” ，因为较旧的被盗任务可能会提供大量工作单元。

Push()和 pop()仅由拥有的工作线程调用（到“双端队列”的顶部），这就是它们最高效的原因，它们使用无等待“ C ompare - A nd- S wap” CAS操作. CAS是在内存中原子检查和设置 lock 值的硬件级别——它从不阻塞。push()和pop()有一个非常轻量级的锁定。

可以从另一个线程调用Poll()以“窃取”作为子任务。当我们调用poll()时，这是因为另一个线程已被随机分配以尝试以FIFO顺序从该双端队列的末尾“窃取”子任务。Poll()由另一个线程启动，因此它可能并不总是免等待，因此有时它必须“屈服”并稍后再试。“偷”很快，但它可能不如推和弹出那么快。

于 2019-11-30T20:52:11.433 回答