c++ - 在线程中查找最小队列大小

Question

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

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

我正在开发 Visual Studio 2008，我们自己的多线程库中的 C++ 编程语言实现了多速率同步数据流范例。

Answer 1

如您所见，尝试查找负载较少的队列很麻烦，并且可能是一种效率低下的方法，因为您可能会向仅具有一项繁重任务的队列添加更多工作，而具有小任务的队列将没有更多工作并且很快变得不活动。

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

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

您不应该遇到空闲线程和等待处理的工作的情况。

Answer 2

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

如果您真的想将工作项从主源分发到一组工作人员，那么您就是在进行负载平衡，正如您所说。在这种情况下，您实际上是在谈论调度，除非您只是进行循环式平衡。调度是计算中非常深入的主题，您可以轻松地花费数周或数月的时间来学习它。

Answer 3

如果您真的想尝试这个，每个队列是否不仅可以保留一个公共的“int count”成员，并在推送/弹出任务时使用原子 inc/dec 更新？

这样的设计是否值得管理开销以及当任务排队到恰好正在运行特别长的作业的线程时，当另一个线程即将出列一个非常短的作业时偶尔的“错误”是另一个问题。

Answer 4

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

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

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

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