就是工作窃取总是最合适的用户级线程调度算法？ [英] Is Work Stealing always the most appropriate user-level thread scheduling algorithm?
问题描述
我一直在研究不同的调度算法，我在执行一个线程池。由于问题的性质，我解决我可以假设正在并行运行的任务是独立的，不衍生任何新的任务。该任务可以是不同大小的。
I've been investigating different scheduling algorithms for a thread pool I am implementing. Due to the nature of the problem I am solving I can assume that the tasks being run in parallel are independent and do not spawn any new tasks. The tasks can be of varying sizes.
我就立即最受欢迎的调度算法的工作窃取使用无锁双端本地作业队列，而我是比较满意这种方法。但是我不知道是否有任何共同的情况下，工作窃取是不是最好的方法。
I went immediately for the most popular scheduling algorithm "work stealing" using lock-free deques for the local job queues, and I am relatively happy with this approach. However I'm wondering whether there are any common cases where work-stealing is not the best approach.
有关这个特定的问题，我各个任务的大小的良好估计。工作窃取并没有使用这些信息，我不知道是否有任何计划程序，这将提供更好的负载平衡比工作窃取此信息（显然以同样的效率）。
For this particular problem I have a good estimate of the size of each individual task. Work-stealing does not make use of this information and I'm wondering if there is any scheduler which will give better load-balancing than work-stealing with this information (obviously with the same efficiency).
NB。这个问题占用了一个previous <一href="http://stackoverflow.com/questions/2447089/heuristic-algorithm-for-load-balancing-among-threads">question.
NB. This question ties up with a previous question.
推荐答案
我分配任务的前期。随着他们的预计运行时间的信息，您可以分发到每个队列，每个线程之一。
I'd distribute the tasks upfront. With the information of their estimated running time you can distribute them into individual queues, for each thread one.
分发任务基本是背包问题，每个队列应该采取相同的时间量
Distributing the tasks is basically the knapsack problem, each queue should take the same amount of time.
您应该添加一些逻辑，而他们运行修改队列。例如应该发生重新分配后的估计运行时间相差一定量从实际运行时间。
You should add some logic to modify the queues while they run. For example a re-distribution should occur after the estimated running time differs by a certain amount from the real running time.
这篇关于就是工作窃取总是最合适的用户级线程调度算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
