窃取工作总是最合适的用户级线程调度算法吗?

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

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

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

确实,工作窃取调度程序不使用该信息,但这是因为它不依赖于它来提供它所提供的理论限制(例如,它使用的内存、工作人员之间的预期总通信量以及执行完全严格计算的预期时间)。在这里你可以看到: http://supertech.csail.mit.edu/papers/steal.pdf )

一篇有趣的论文(我希望您可以访问: http://dl.acm.org/citation.cfm?id=2442538 )实际上,使用有界的执行时间来提供形式化的证明(尽可能接近原始工作窃取边界)。

是的,在某些情况下,窃取工作并没有达到最佳效果(例如,不平衡树搜索和其他特殊情况)。但对于这些情况,已经进行了优化(例如,允许窃取受害者一半的deque,而不是只执行一个任务: http://dl.acm.org/citation.cfm?id=571876 )