工作窃取始终是最合适的用户级线程调度算法吗？

Question

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

我立即采用最流行的调度算法"偷工作",使用无锁的deques作为本地工作队列,我对这种方法比较满意.但是我想知道是否有任何常见的情况,工作窃取不是最好的方法.

对于这个特殊问题,我对每个单独任务的大小有一个很好的估计.工作窃取没有利用这些信息,我想知道是否有任何调度程序可以提供更好的负载平衡,而不是工作窃取这些信息(显然具有相同的效率).

NB.这个问题与之前的问题有关.

Answer 1

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

分配任务基本上是背包问题，每个队列应该花费相同的时间。

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