查找线程中的最小队列大小

Question

我正尝试使用多线程实现新的调度技术。每个线程都有自己的专用本地队列。这个想法是，每次从程序线程创建任务时，它应该搜索队列中的最小队列大小（任务数较少的队列）并排入其中。 线程之间的负载平衡方式，其中较少繁忙的队列排队更多。

能否请您建议一些逻辑（或）想法如何在编程的角度动态地在给定队列中找到最小大小的队列。

我正在使用visual studio 2008，C++编程语言在我们自己的多线程库中实现多速率同步数据流范例。

Answer 1

如果你真的想试试这个，每个队列不能只保留一个公共的'int count'成员，当任务被压入/弹出时用atomic inc/dec进行更新？

无论这样的设计是否值得管理开销，以及当任务排队等待恰好运行特别冗长的工作的线程时，另一个线程正准备离队一个非常短的工作时，偶尔会出现“错误”另一个问题。

Answer 2

为什么线程不从“主”工作队列中获取工作？

如果您确实想要将工作项目从主源派发到一组工作者，那么您就可以像您说的那样进行负载平衡。在那种情况下，你真的在​​谈论调度，除非你简单地进行循环式的平衡。计划是计算中非常深刻的主题，您可以轻松地花费数周或数月时间来了解计算。

Answer 3

您可以在线程中同步计数器。但我想这不是你想要的。

由于您想要使用数据流来实现所有功能，所有内容都应该是队列。

您的第一个选择是查询队列中的作业数量。我认为这并不容易，如果你想要一个单一的读写器模式，因为你可能不得不使用锁来进行这个操作，这不是你想要的。注意：我只是猜测，你不能在这里使用无锁队列;要么有计数器，要么取两个指针的差值，无论哪种方式你都有锁。

第二个选项（可以使用无锁代码完成）是将命令发送回调度程序线程，告诉他工作线程x已经完成了一项任务。使用这种方法，您有更多的队列，每个队列都从一个工作线程到调度程序线程。

Answer 4

正如你所看到的，试图找到加载较少的队列很麻烦，而且可能是一种效率低下的方法，因为只需要一项繁重的任务就可以将更多工作添加到队列中，而具有小型任务的队列将不会有更多的工作并快速失效。

你最好使用工作窃取启发式：当一个线程完成它自己的工作时，它会查看其他线程队列并“窃取”一些工作，而不是保持空闲或被终止。

然后系统将自动平衡，每个线程都处于活动状态，直到没有足够的工作给每个人。

你不应该有空闲的线程和工作等待处理的情况。