1

我正在阅读一篇关于并发运行时的文章，这篇文章中提到了算法work stealing。但我不知道这个算法是什么！所以我想要一点解释或一些好的链接，可以帮助我介绍这个算法。

4

4 回答 4

14

这些有帮助吗？

.NET 4.0 中的工作窃取

通过 Work Stealing 调度多线程计算

于 2012-01-31T14:47:13.310 回答
9

我最近阅读了那篇论文，它描述了一个带有工作窃取算法的 Java Fork/Join 框架，可以在此处找到

取自那篇论文，我们从这个开始：

Result solve(Problem problem) {
    if (problem is small)
       directly solve problem
    else {
       split problem into independent parts
       fork new subtasks to solve each part
       join all subtasks
       compose result from subresults
    }
}

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

简而言之，对于所有细节，我建议您查看论文。

于 2012-01-31T14:55:36.323 回答
5

您可以在以下 Channel9 视频中找到关于 Work Stealing 算法的非常漂亮且易于理解的解释： “并行扩展：并行深入任务内部”Duffy、Huseyin Yildiz、Daan Leijen、Stephen Toub，参见00:44:00（作者：Daan雷仁）

于 2012-03-11T15:42:55.277 回答
1

您可以查看用于任务调度程序的英特尔 TBB 算法，它使用工作窃取模式。请参阅https://software.intel.com/fr-fr/node/468190

于 2014-09-11T12:44:55.653 回答