我一直在研究我正在实现的线程池的不同调度算法。由于我正在解决的问题的性质，我可以假设并行运行的任务是独立的，不会产生任何新任务。任务的大小可以不同。
我立即选择了最流行的调度算法“工作窃取”，使用本地作业队列的无锁双端队列，我对这种方法比较满意。但是我想知道是否有任何常见的情况下工作窃取不是最好的方法。
对于这个特定的问题，我对每个单独任务的大小有一个很好的估计。工作窃取没有使用这些信息，我想知道是否有任何调度程序可以提供比使用这些信息进行工作窃取更好的负载平衡（显然具有相同的效率）。
注意。这个问题与上一个问题有关。
我会预先分配任务。使用它们的估计运行时间信息，您可以将它们分配到单独的队列中，每个线程一个。
分配任务基本上是背包问题，每个队列应该花费相同的时间。
您应该添加一些逻辑以在队列运行时对其进行修改。例如，在估计的运行时间与实际运行时间相差一定量之后，应该进行重新分配。
确实，工作窃取调度程序不使用该信息，但这是因为它不依赖它来提供它所做的理论限制（例如，它使用的内存、预期的工作人员之间的总通信以及预期的是时候执行一个完全严格的计算了，你可以在这里阅读：http: //supertech.csail.mit.edu/papers/steal.pdf）
一篇有趣的论文（我希望您可以访问：http ://dl.acm.org/citation.cfm?id=2442538 ）实际上使用有限的执行时间来提供正式证明（试图尽可能接近原始工作-尽可能地窃取边界）。
是的，在某些情况下工作窃取不能以最佳方式执行（例如，不平衡的树搜索和其他特殊情况）。但是对于这些情况，已经进行了优化（例如，允许窃取受害者的一半双端队列，而不是只执行一项任务：http ://dl.acm.org/citation.cfm?id=571876 ）。