我正在开发一个多线程程序，其中有许多工作线程执行长度不等的任务。我想对任务进行负载平衡，以确保它们完成大致相同的工作量。对于每个任务 Ti，我都有一个数字 ci，它提供了该任务所需工作量的一个很好的近似值。
我正在寻找一种高效的(O(N) N = 任务数或更好)的算法，在给定 ci 的值的情况下，该算法将“大致”提供良好的负载平衡。它不一定是最佳的，但我希望能够对结果分配的糟糕程度有一些理论上的限制。
有什么想法吗？
最佳答案
您想实现一个 work stealing algorithm .每个工作线程都有一个双端队列，新任务被添加到最小队列的底部。工作人员从自己队列的顶部移除任务(顶部/底部分离减少了争用)，当工作人员没有更多工作要做时，它会从最大队列的底部窃取工作。它很简单，而且效果很好，我相信这就是微软.net4.0 附带的并行系统所基于的算法。
结果分配非常好，只有在整个系统中没有更多工作可用时，工作线程才会无事可做。
铌。如果你想拆开一些示例代码，我的 friend 为 C# 编写了一个工作窃取系统，你可以找到它 here
关于algorithm - 线程间负载均衡的启发式算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2447089/