队列作业调度算法
我很想知道是否有一个被广泛接受的解决方案来管理线程池中的线程资源，给出以下场景/约束：
我的问题是关于线程池实现背后的理论。 什么算法可以用来有效地将可用线程分配给所有桶中的传入作业？
编辑 ：另一个设计目标是消除排队和正在处理的作业之间尽可能多的延迟，假设有空闲线程。
编辑2 ：在这种情况下，我想到有相当大数量的队列（50-100）具有不可预知的活动级别，但是在任何给定时间可能只有25％的队列处于活动状态。
我能想到的第一个（也是最昂贵的）解决方案是简单地为每个队列分配一个线程。 虽然这将确保立即收到传入请求，但显然效率不高。
第二种解决方案是根据预期的活动级别将这些队列组合在一起，以便队列数量与池中的线程数内联，从而允许将一个线程分配给每个队列。 这里的问题将是传入的工作，否则可能会并行处理，将被迫相互等待。
第三种解决方案是创建最大数量的队列，每个队列必须连续处理一组作业，但只能根据我们预期在任何给定时间处于繁忙状态的队列数分配线程（也可以通过调整运行时池）。 所以这就是我的问题出现的地方：由于我们有比线程更多的队列，因此池如何以最有效的方式将空闲线程分配给传入作业？
我想知道是否有一个被广泛接受的方法。 或者如果有不同的方法 - 谁使用哪一种？ 有什么优点/缺点等？
编辑3 ：这可能最好用伪代码表示。
你应该消除nr。 2从你的规格。 所有你需要遵守的是线程占用桶并按顺序处理桶内的队列。 用另一个线程池处理一个序列化队列或者并行执行一些任务序列化是没有意义的。 因此，您的规范只是变成线程迭代桶中的fifo，并由池管理员来插入正确构建的桶。 所以你的斗将是：
struct task_bucket
{
void *ctx; // context relevant data
fifo_t *queue; // your fifo
};
然后，由线程池足够聪明地知道在每次迭代队列中要做什么，这取决于你。 例如，ctx可以是一个函数指针，并且队列可以包含该函数的数据，因此工作线程只需使用提供的数据在每次迭代中调用该函数即可。
反映评论：如果事先知道存储桶列表的大小，并且在程序的整个生命周期中不可能改变，那么您需要弄清楚这对您是否重要。 你需要一些线程来选择一个桶。 最简单的方法是有一个由管理器填充并由线程清空的FIFO队列。 经典读者/作家。
另一种可能性是堆。 工作人员从堆中移除最高优先级并处理存储桶队列。 工人的删除和管理员的插入都重新排序堆，以便根节点是最高优先级。
这两种策略都假定工人们扔掉桶，而经理人制造新桶。
如果保持存储桶非常重要，那么只会承担工人参与上次修改任务的风险，因此，经理将需要重新排列存储桶列表或修改每个存储桶的优先级，并且工作人员重复查找最高优先级。 在线程正在工作或线程将不得不复制这些内容的同时，ctx的内存保持相关性非常重要。 工作人员可以简单地在本地分配队列，并将队列中的队列设置为NULL。
补充说：我现在倾向于同意，你可能会开始简单，只为每个桶保留一个单独的线程，并且只有当这个简单的解决方案被理解为有问题时，你才会寻找不同的东西。 而更好的解决方案可能取决于简单问题导致的问题。
无论如何，我在下面留下我的初步答案，并附加一个事后补充。
您可以创建一个特殊的全局队列“作业在桶X中可用”信号。
所有空闲的工作人员都会在这个队列中等待，当一个信号被放入队列时，一个线程将把它带到相应的存储区中，直到该存储区变空为止。
当传入作业提交到有序存储桶中时，应检查是否已将工作线程分配到此存储桶。 如果已分配，则新工作将最终由该工作线程处理，因此不应发送任何信号。 如果未分配工人，请检查存储桶是否为空。 如果为空，则将一个信号放入全局信号队列中，新作业已经到达该桶; 如果不是空的话，应该已经发出了这样的信号，工作者线程应该很快到达，所以什么也不做。
ADDED：我认为，如果线程数量少于“活动”桶的数量， 并且存在传入任务的非结束流，则我的上述想法可能会导致某些作业不能正常工作。 如果所有线程都已占线，并且新作业到达尚未提供服务的存储桶，则可能需要很长时间才能释放线程以处理此新作业。 因此，需要检查是否有闲置的工人，如果没有，则创建一个新的......这增加了更多的复杂性。
保持简单：每队列使用1个线程。 简单是值得的，线程很便宜。 在大多数操作系统中，100个线程不会成为问题。
通过使用每个队列的线程，您还可以获得真正的调度程序。 如果一个线程阻塞（取决于你在做什么），另一个线程可以排队。 直到每一个块都被阻塞，你将不会陷入僵局。 如果使用较少的线程，则不能这么说 - 如果队列中的线程恰好在服务于块，那么即使其他队列是“可运行的”，即使这些其他队列可能会阻塞阻塞的线程，您也会遇到死锁。
现在，在特定情况下，使用线程池可能是值得的。 但是那时你在谈论优化一个特定的系统，而且细节很重要。 线程有多昂贵？ 调度程序有多好？ 怎么样封锁？ 排队多久，更新频率如何等等。
所以一般来说，只要有大约100个队列的信息，我只需要为每个队列提供一个线程。 是的，有一些开销：所有的解决方案都会有。 线程池将引入同步问题和开销。 有限数量的线程开销很小。 你主要谈论大约100MB的地址空间 - 不一定是内存。 如果您知道大多数队列将处于空闲状态，则可以进一步实施优化以停止空队列上的线程，并在需要时启动它们（但要注意竞态条件和抖动）。
链接地址: http://www.djcxy.com/p/52575.html