工作窃取：加入递归任务需要窃取？

Question

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

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();

这段代码应该在一个worker内部开始计算。这样的工作者将产生新的任务。然后，他试图获得这个嵌套任务的结果。这个嵌套任务是如何执行的？

Answer 1

分叉连接池为 Java 程序员提供了一个高性能、并行、细腻的任务执行框架。

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

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

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

一个WorkerThread从共享队列中取出任务，它们进入head并处理工作(使用非共享队列)。

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

我们的目标是尽量让WorkerThread保持忙碌，这样我们就希望它们总是有事情要做。

目标是最大限度地提高处理器内核利用率。

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

除此之外，其他共享队列曾经将非分叉联接任务放入分叉联接池中，排在第一位。

“deque”由WorkQueue（这是一个嵌套在ForkJoinPool中的Java类）实现。该类中的一些重要方法是 push（）、pop（） 和 poll（）。

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

这种连接不同于Java线程中的连接。

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

如果在Fork-Join中Join（）发生阻塞，则WorkerThread停止在当前线程上工作，并开始执行子任务。。

每当您在递归任务内的计算方法中调用fork（）时

如果任务是递归任务

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

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

我们为什么要做后进先出？为什么我们在前面推动，在前面弹出？为了提高引用的局部性，提高缓存性能，以便尽快得到处理，有时称为陈旧前的新鲜工作。

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

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

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

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

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

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

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

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

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

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

子任务完成时，join（）返回计算结果。分叉连接池中的连接不同于经典的Java线程连接。Java线程被用作屏障同步器，等待另一个线程完成，然后加入它（在另一个完成之前，不能继续）。

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

Fork-join池中的join不会简单地阻塞调用线程，相反，WorkerThread被分配来运行挂起的子任务。

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

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

WorkerThread 计算出，在子任务完成之前，该任务将被阻止，以便它开始处理子任务。

WorkerThread通过从自己的“队列”中弹出(子)任务，以LIFO顺序处理自己的“队列”。

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

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

Push（）和pop（）仅由所属的工作线程（位于“deque”的顶部）调用，这就是它们最有效的原因：它们使用无等待的“比较和交换”CAS操作。CAS是一种硬件级的自动检查和设置内存中锁的值——它从不阻塞。push（）和pop（）具有非常轻量级的锁。

Poll（）可以从另一个线程调用，以“窃取”作为子任务。当我们调用poll（）时，这是因为另一个线程被随机分配，试图以FIFO顺序从该deque的末尾“窃取”子任务。Poll（）是由另一个线程启动的，因此它可能并不总是无等待的，因此有时它必须“让步”并返回，稍后再试。“偷”很快，但可能不如推和跳那么快。