multithreading - 线程池多队列作业调度算法

Question

我很想知道在给定以下场景/约束的情况下，是否有一个被广泛接受的解决方案来管理线程池中的线程资源:

1. 传入的工作都是一样的性质，可以通过任何处理池中的线程。
2. 新工作将被“存储”到不同的基于某些属性的队列传入的工作使得所有工作去同一个桶/队列必须被串行处理。
3. 一些桶会比其他人在不同的时间点程序的生命周期。

我的问题是关于线程池实现背后的理论。可以使用什么算法有效地将可用线程分配给所有存储桶中的传入作业？

编辑:另一个设计目标是尽可能多地消除作业排队和被拾取进行处理之间的延迟，假设有可用的空闲线程。

Edit2:在我考虑的情况下，有相对较多的队列 (50-100) 具有不可预测的事件水平，但可能只有 25% 的队列处于事件状态在任何给定时间。

我能想到的第一个(也是成本最高的)解决方案是简单地为每个队列分配一个线程。虽然这将确保立即接收传入的请求，但显然效率很低。

第二种解决方案是根据预期的事件水平将队列组合在一起，以便队列的数量与池中的线程数量一致，从而允许将一个线程分配给每个队列。这里的问题是，本来可以并行处理的传入作业将被迫相互等待。

第三种解决方案是创建最大数量的队列，每组必须串行处理的作业一个，但只根据我们预期在任何给定时间忙碌的队列数量分配线程(这也可以在运行时由池调整)。所以这就是我的问题所在:鉴于我们的队列比线程多，池如何以最有效的方式将空闲线程分配给传入的作业？

我想知道是否有一种被广泛接受的方法。或者如果有不同的方法——谁使用哪一种？优点/缺点等是什么？

Edit3:最好用伪代码来表达。

Answer 1

您可能应该消除 nr。 2 从你的规范。您真正需要遵守的是线程占用桶并按顺​​序处理桶内的队列。用另一个线程池处理序列化队列或并行执行一些任务序列化是没有意义的。因此，您的规范简单地变成了线程在桶中迭代 fifo，并且由 poolmanager 插入正确构造的桶。所以你的桶将是:

struct task_bucket
{
    void *ctx; // context relevant data
    fifo_t *queue; // your fifo
};

然后由您来使线程池足够智能，以知道在队列的每次迭代中要做什么。例如，ctx 可以是一个函数指针，队列可以包含该函数的数据，因此工作线程只需使用提供的数据在每次迭代中调用该函数。

反射(reflect)评论:如果遗愿 list 的大小是事先已知的，并且在程序的生命周期内不太可能改变，那么您需要弄清楚这对您是否重要。您将需要一些方法让线程选择要使用的桶。最简单的方法是拥有一个由管理器填充并由线程清空的 FIFO 队列。经典读者/作家。

另一种可能性是堆。 worker 从堆中移除最高优先级并处理 bucket 队列。 worker 的移除和 manager 的插入都会重新排序堆，以便根节点具有最高优先级。

这两种策略都假设 worker 扔掉水桶而经理制造新水桶。

如果保留桶很重要，那么您冒着工作人员只参与最后修改的任务的风险，因此经理将需要重新排序桶列表或修改每个桶的优先级，工作人员迭代寻找最高优先级. ctx 的内存在线程工作时保持相关性很重要，否则线程也必须复制它。 Workers 可以简单地在本地分配队列并在桶中将队列设置为 NULL。