问题标签 [work-stealing]

我目前正在开发一个带有绿色线程的 C++ 并发库，它使用工作窃取来实现多个硬件线程上的调度程序之间的负载平衡。

我已将主上下文固定到其硬件线程，这意味着它不能被盗，因此无法迁移到其他硬件线程。

我相信我已经在某处读到过这篇文章，如果主上下文被盗并在不同的硬件线程中返回（退出）来自它的起源是未定义的行为。但是，我现在似乎找不到任何来源。

这是未定义的行为吗？引用来源将是完美的。

我的项目需要定期完成两项低优先级任务。简单的解决方案是有一个预定的执行器，以固定的速率安排两个任务。

现在的问题是：可能还有其他更高优先级的任务。显而易见的解决方案可能是使用 workStealingPools。虽然我找不到计划的工作窃取池的实现。

对此是否有更好/不同的方法，或者是否有合理的理由说明这没有意义？或者：如何实施这样的解决方案？

这个想法是在 96 核机器上运行并行作业，工作窃取ForkJoinPool.

以下是我目前使用的代码：

在这里，sequence有大约20,000个项目。大多数项目需要 2-8 秒来处理，其中只有大约 200 个需要更长的时间，大约 40 秒。

问题：

一切都运行良好，但是，工作窃取方面似乎并没有很好地工作。以下是随着时间的推移与实际负载（蓝色）相比的预期总 CPU 负载（黑色）：

查看 CPU 活动时，很明显随着工作接近尾声，使用的内核越来越少。在最后 10 分钟内，只有 2 或 3 个核心还在忙于依次处理数十个项目，一个接一个。

为什么仍然在队列中的项目不会被其他空闲内核窃取，即使使用ForkJoinPool应该是工作窃取的 a ？

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinPool.html

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

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

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

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

我正在尝试基于 Dijkstra 的并发编程控制问题的解决方案以及 Frigo 和 Leiserson 以及 Randall 的 fork/join 线程池（由具有全局任务队列的主线程池和具有自己的任务队列的 N 个线程组成）实现 Dijkstra 算法cilk-5 多线程语言的实现。

但是，这似乎太复杂了。因此，我使用了 Art of Multiprocessor Programming 中的 Filter Lock，如下所示：

本书的实现

我在线程池中的实现

但是，在我的实现中，主循环比仅使用 pthread_mutex_lock 和 pthread_mutex_unlock 慢得多。我不确定我是否在错误的地方使用了算法，或者我的算法在这一点上是错误的。另外，我想知道如何以有效的方式从其他工作人员的队列中窃取要处理的任务（找到具有可用任务的工作人员）

我想异步做一些事情。但是我的代码永远不会执行。它无法让线程执行？

我已经阅读了很多关于这个算法的内容。在解释这个算法时，这些话是： 工作窃取算法 [关闭]

这些分叉的子任务可以递归地自己创建更多的子任务，从而填满并行工作线程的工作队列。如果一个线程完成并且无事可做，他可以从另一个线程的队列中“窃取”工作。

我知道这个算法是新的并且在 Executors.newCachedThreadPool / Executors.newFixedThreadPool 中不存在
我希望看到一个线程只处理它的队列。我创建了一个递归创建线程的小程序。见下文。我怎么能看到它不使用工作窃取算法？

这是输出：

如您所见：
主触发线程 2 和线程 1
线程 1 触发线程 3（计算 [1,2]）和线程 4
线程 2 触发线程 5 和线程 3（计算 [1,2 ] 完成计算后 [8,9,10])
据我了解，线程 3 处理线程 1 和线程 2 的工作。
看起来像线程 3工作窃取
如果我将其更改为

它支持偷窃算法，我看到了什么不同？

如您所见，我们有 5 个工人，工人 4 处理由工人 3 和工人 1 触发的工作。这与之前的执行有何不同？

你可以从github下载代码

我正在尝试维护多个线程之间的项目列表，每个线程一个（例如，每个线程一个套接字连接）。我将这个列表保存在一个ArrayDeque<>. 我面临的问题ArrayDeque<>是超过没有的项目。线程池中的线程数。

这是我的代码：

在我的代码中，我正在创建一个大小为 10 的工作窃取池，谁能告诉我为什么不。在这种情况下，元素的ArrayDeque<>数量超过 10？

我想使用由工作线程托管的 Boost.Fibers 而不仅仅是线程。我想在编写下面显示的代码时，我已经按照手册中的所有内容完成了所有操作，但它似乎不起作用——输出中缺少“<anonymous> called”。

有谁知道为什么？

我正在根据论文实现 Chase-lev 双端队列：“Correct and Efficient Work-Stealing for Weak Memory Models”。在论文中，它要求双端队列有一个带有原子元素的缓冲区：

为什么缓冲区中的元素是 typestd::atomic<int>而不是 plain int？