偷窃：加入递归任务需要偷窃吗？

Question

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

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

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

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

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

此代码应在工作程序内部开始计算。这样的工人将产生新的任务。然后，他尝试获取此嵌套任务的结果。如何执行此嵌套任务？

Answer 1

fork-join池为Java程序员提供了高性能，并行，细粒度的任务执行框架。它通过分而治之解决了这个问题。将任务拆分为子任务。一个任务通过fork（）方法创建一个子任务。当任务客户端提交/调用/执行fork联接任务时，该任务进入共享队列，该共享队列用于馈送非共享双端队列（也称为“ < [[deque“）由WorkerThread管理。一个或多个WorkerThreads被称为Fork-Join池。WorkerThread从共享队列中拉出任务，然后他们开始处理工作（使用非共享队列）。Fork-Join-Pool中的每个WorkerThread（实际上是Java线程）都在循环中运行，该循环不断扫描要执行的（子）任务。目的是尝试使WorkerThreads尽可能繁忙，以便我们希望他们总是有事可做。目标是最大化处理器核心利用率。每个WorkerThread都有它的双端队列（又名“ deque”）作为其主要任务来源。除此以外，其他shared queue过去曾用于将非分叉加入任务放入分叉加入池中，排在第一位。“ deque”由WorkQueue（嵌套在ForkJoinPool中的Java类）实现。该类中的一些重要方法是push（），pop（）和poll（）。

在某些时候，该任务无法取得任何进展，因为它正在等待

join（）

方法完成子任务。此联接与Java线程中的联接不同。在Java Thread Join中，如果一个任务没有返回结果，则为块，并等待该另一个线程完成。如果在Fork-Join中join（）恰好阻塞，则WorkerThread停止在当前线程上工作并开始执行子任务。每当您在RecursiveTask <>或RecursiveAction内部的计算方法中调用fork（）时，该方法始终在fork-join-中的线程上下文中运行。池。如果RecursiveTask <>或RecursiveAction的任务由WorkerThread调用fork（）运行，则新的* ForkJoinTask **将被推到头部该工人的“ deque”线程。它以LIFO的顺序推动后进先出。当我们为此任务调用join（）时，该任务将从“ deque”（堆栈顶部）的开头弹出，并运行至完成（保持运行直到它已经完成）在WorkerThread中。为什么我们要LIFO？我们为什么要在前面推动而在前面弹出呢？为了提高引用的局部性，提高缓存性能，以便您尽快进行处理，有时称为过时的新工作。ForkJoinTask启用细粒度的数据并行性。ForkJoinTask比Java thread轻巧，它没有自己的运行时堆栈。ForkJoinTask将数据块与对该数据的计算相关联。真正的Java线程具有其自己的堆栈，寄存器和许多其他资源，这些资源使操作系统可以在内部由线程调度程序独立地对其进行调度。大量的ForkJoinTask可以在数目较少的WorkerThreads中运行。WorkerThreads的数量通常（如果未指定）是内核数量的函数。每个WorkerThread是一个Java thread对象，具有您希望从普通线程获得的所有装备。ForkJoinTask具有控制并行处理和合并结果的两种重要方法，分别是fork（）和join（）。fork（）安排在适当的线程池中异步执行此任务。 fork（）就像Thread.start（）的lightversion。fork（）不会（至少不是直接创建）创建Java工作线程，但是最终，它将在Java线程上运行。它不会立即开始运行，而是将子任务放在工作队列的开头。join（）在子Task完成时返回计算。Fork-Join池中的联接与经典Java线程联接不同。Java线程用作屏障同步器，以等待另一个线程结束，然后您加入它（直到另一个线程完成，您才能继续进行）。常规线程中的联接会阻止调用线程。Fork-Join池中的联接不只是阻塞调用线程，而是分配WorkerThread来运行挂起的子任务。当WorkerThread遇到join（）时，它将处理其他所有子任务，直到发现目标子任务已完成。在完成此子任务结果之前，WorkerThreads不会返回到调用方。在fork-join任务中的Join不会被阻塞，它保存当前任务，因此只有在join（）创建的子任务完成之后，计算才能继续。WorkerThread指出，直到子任务完成，任务才被阻塞，因此它开始在子任务上工作。A

WorkerThread

通过从其自己的“ deque中弹出（子）任务，以LIFO顺序处理其自身的“ deque”。WORK STEALING当WorkerThread没有其他事情可做时-“ idle”。如果WorkerThread自己的队列为空，它将去尝试从“尾部”的尾部“窃取”子任务。随机选择其他一些繁忙线程“ deque”，以最大化内核利用率。这些任务以FIFO顺序“被盗”，因为较旧的被盗任务可能会提供较大的工作量。Push（）和pop（）仅由拥有的工作线程调用（在“ deque的顶部”），这是它们效率最高的原因。使用免等待的“ C杂音-A nd-S wap” CAS操作。 CAS是自动检查和设置内存锁值的硬件级别，它从不阻塞。 push（）和pop（）具有非常轻巧的锁定。可以从另一个线程调用Poll（）作为子任务来“窃取”。当我们调用poll（）时，这是因为已随机分配另一个线程以尝试以FIFO顺序从此双端队列的末尾“窃取”子任务。 Poll（）由另一个线程启动，因此它可能并不总是不需要等待，因此有时它必须“屈服”并返回并稍后再试。 “窃取”的速度很快，但可能不如推动和弹出的速度快。