multithreading - Work Stealing 总是最合适的用户级线程调度算法吗？

Question

我一直在研究我正在实现的线程池的不同调度算法。由于我要解决的问题的性质，我可以假设并行运行的任务是独立的，不会产生任何新任务。任务可以有不同的大小。

我立即转向使用本地作业队列的无锁双端队列的最流行的调度算法“工作窃取”，我对这种方法比较满意。不过，我想知道是否有任何常见情况下工作窃取不是最佳方法。

对于这个特定问题，我对每个单独任务的大小都有很好的估计。工作窃取不使用此信息，我想知道是否有任何调度程序可以提供比使用此信息进行工作窃取更好的负载平衡(显然具有相同的效率)。

注意。这个问题与之前的 question 有关.

Answer 1

我会预先分配任务。有了它们的估计运行时间信息，您可以将它们分配到单独的队列中，每个线程一个。

分配任务基本上就是knapsack problem ，每个队列应该花费相同的时间。

您应该添加一些逻辑来在队列运行时对其进行修改。例如，在估计运行时间与实际运行时间相差一定量后，应进行重新分配。