Threadpool多队列作业调度算法

Question

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

1. 传入的作业都具有相同的性质,可以由池中的任何线程处理.
2. 传入的作业将根据传入作业的某些属性"划分"到不同的队列中,以便所有进入同一存储桶/队列的作业必须按顺序处理.
3. 在程序的生命周期中,某些存储桶在不同点上的忙碌程度会低于其他存储桶.

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

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

编辑2:在我想到的情况下,有相对大量的队列(50-100)具有不可预测的活动水平,但在任何给定时间可能只有25%的队列将处于活动状态.

我能想到的第一个(也是最昂贵的)解决方案是简单地为每个队列分配一个线程.虽然这将确保立即获取传入请求,但这显然是低效的.

第二种解决方案是根据预期的活动级别将队列组合在一起,以便队列数与池中的线程数一致,允许将一个线程分配给每个队列.这里的问题是传入的作业,否则可以并行处理,将被迫相互等待.

第三种解决方案是创建最大队列数,每个队列必须连续处理一组,但只根据我们期望在任何给定时间忙的队列数分配线程(也可以通过运行时的池).所以这就是我的问题所在:假设我们有比队列更多的队列,那么池如何以最有效的方式为进入的作业分配空闲线程？

我想知道是否有一种被广泛接受的方法.或者,如果有不同的方法 - 谁使用哪一个？有哪些优点/缺点等？

Edit3:这可能最好用伪代码表示.

Answer 1

你也许应该消除 nr。2 根据您的规格。您真正需要遵守的是线程占用桶并按顺​​序处理桶内的队列。使用另一个线程池处理序列化队列或并行执行一些任务序列化是没有意义的。因此，您的规范就变成了线程迭代存储桶中的 fifo，并且由池管理器插入正确构造的存储桶。所以你的桶将是：

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

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

反映评论：如果预先知道愿望清单的大小并且在程序的生命周期内不太可能改变，那么您需要弄清楚这对您是否重要。您将需要某种方式让线程选择要获取的存储桶。最简单的方法是使用一个 FIFO 队列，由管理器填充并由线程清空。经典读者/作家。

另一种可能性是堆。工作线程从堆中移除最高优先级并处理桶队列。工作线程的移除和管理器的插入都会对堆进行重新排序，以便根节点具有最高优先级。

这两种策略都假设工人扔掉水桶，经理制造新的水桶。

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