线程池多队列作业分派算法

Question

线程池多队列作业分派算法

multithreadingalgorithmthreadpool

7

我很想知道在线程池中管理线程资源的广泛接受的解决方案是否存在，考虑以下场景/约束条件：

1. 所有传入作业都具有相同的性质，并且可以由池中的任何线程处理。

2. 传入的作业将基于传入作业的某些属性被“分桶”到不同的队列中，以使所有进入同一桶/队列的作业必须串行处理。

3. 在程序生命周期的不同阶段，某些存储区比其他存储区要不忙。

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

编辑：另一个设计目标是尽可能消除作业在入队时和被选中处理之间的延迟，假设有可用的空闲线程。

编辑2：在我考虑的情况下，有大量队列（50-100个），其活动水平不可预测，但在任何给定时间可能只有25％的队列处于活动状态。

我能想到的第一个（也是最昂贵的）解决方案是仅为每个队列分配1个线程。虽然这将确保立即获取传入请求，但显然效率低下。

第二个解决方案是基于预期的活动水平将队列合并在一起，使队列数与池中线程数保持一致，允许为每个队列分配一个线程。问题在于，否则可以并行处理的传入作业将被迫互相等待。

第三种解决方案是创建最大数量的队列，为必须串行处理的作业集的每个集分配一个队列，但仅根据我们预计在任何给定时间内要忙碌的队列数（也可以在运行时由池进行调整）分配线程。这就是我的问题所在：假设队列比线程多，池如何以最有效的方式将空闲线程分配给传入作业？

我想知道是否有广泛接受的方法。还是说有不同的方法-谁使用了哪些方法？优缺点等是什么？

编辑3：这可能最好用伪代码来表达。

- hifier

3个回答

2

你应该将规范中的第2点删除。你只需要遵守线程占用桶并按顺序处理桶内队列的要求即可。使用另一个线程池处理串行队列或并行序列化任务没有意义。因此，你的规范简单地变成了线程迭代桶中的FIFO，由池管理器插入正确构造的桶。所以你的桶将是：

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

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

根据评论：如果桶列表的大小在程序运行期间已知且不太可能更改，则需要确定这一点是否对您重要。您需要一些方式让线程选择要接受的桶。最简单的方法是有一个由管理器填充并由线程清空的FIFO队列。经典的读者/写者问题。

另一个可能性是堆。工人从堆中删除最高优先级，并处理桶队列。工人的删除和管理器的插入都会重新排序堆，以便根节点是最高优先级。

这两种策略都假定工人们会丢弃桶，而管理器则会创建新桶。

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

- Mel

谢谢，但我问题是在当 #threads < #buckets 时如何分配线程到桶中。当一个线程完成它队列中的所有工作时会发生什么？它如何知道下一个要处理的桶是哪个？ - hifier

同样的问题。Fifo或堆并提取根。如果首先进入优先排序，则Fifo是首选排序，如果您有一些优先级，则使用堆。静态存储任务列表对我来说似乎不太实用，但是如果您不删除桶而将其标记为完成，则可能会发生这种情况。 - Mel

我明白了。也许这比我想象的要简单。这些桶将在启动时就已知（可能基于某些数据库或配置），但它们将在整个池的生命周期内存在。您所说的“静态”，是否指编译时已知？ - hifier

如果您更改答案正文以反映您的第二条评论，可能会有所帮助。就目前而言，我觉得答案没有解决我的问题根源。 - hifier

使用池本身管理的队列（或堆）桶的想法，并让工作者等待这个结构似乎是一个好的方法。但是，我认为您关于工作者在处理这些作业之前从桶中复制队列数据的最后一句话可能会导致无序处理--如果新作业被加入到该桶中并在第一个线程完成其作业之前被另一个线程拾取。该桶必须保持锁定状态，直到第一个线程将其归还给池... 我喜欢这个想法的方向。 - hifier

这实际上给了我一个好主意。我们是否可以使用堆来存储这些桶。当空闲线程拿起一个桶时，它只会处理队列中在那一时刻的作业。在此之后入队的任何内容都将留在队列中，并将桶交回池中。现在，如果我们使用某种时间戳作为堆的优先级键来表示桶中最老的作业，那么第一个作业最老的桶将始终被下一个线程拿走。我认为这将消除饥饿问题……也许明天我会用伪代码写出来。 - hifier

0

保持简单：我会为每个队列使用1个线程。简单性很重要，而线程相当便宜。在大多数操作系统上，100个线程不会成为问题。

通过为每个队列使用一个线程，您还可以获得真正的调度程序。如果一个线程阻塞（取决于您正在做什么），则可以排队另一个线程。除非每个线程都阻塞，否则您不会出现死锁。如果您使用较少的线程，则无法这样说-如果线程所服务的队列阻塞，即使其他队列是“可运行的”，即使这些其他队列可能会解除阻塞的线程，您也将出现死锁。

现在，在特定情况下，使用线程池可能值得一试。但是，那时您正在谈论优化特定系统，并且细节很重要。线程有多贵？调度程序有多好？阻止怎么样？队列有多长，更新频率如何等等。

总的来说，仅凭你拥有大约100个队列的信息，我会推荐每个队列一个线程。是的，这样会有一些开销：所有的解决方案都会有这个问题。线程池会引入同步问题和开销。而有限数量的线程开销相对较小。你主要考虑的是大约100MB的地址空间 - 并非必然是内存。如果你知道大部分队列会处于空闲状态，你可以进一步实现一个优化，即在空队列上停止线程，在需要时启动它们（但要注意竞争条件和过度使用）。

- Eamon Nerbonne

在企业级别，100个进程并不算多，而且我从未说过有数百个队列 - 我说的是50-100个。这些都是具有32-64个核心的大型机器。话虽如此，如果您只需要25个（或更少）线程，则不希望每个进程启动100个线程。我知道这不是一个晦涩的问题，有多队列线程池可用，可以让您在处理线程数量上设置下限和上限。我正在尝试了解它们的工作原理。这种设计并不意味着会出现死锁或饥饿情况。请参见@Mel的帖子中的讨论。 - hifier

Eamon，我对这个语句感到困惑：“如果队列中的线程正在服务时被阻塞，即使其他队列是“可运行”的，即使这些其他队列可能会解除已阻塞的线程，你仍然会遇到死锁。” 如果这种情况确实存在，那么似乎这是一个应用程序级别的缺陷。我不明白如果应用程序正确管理共享资源并正确设计其作业为独立工作单元（除了保证顺序之外，不做任何关于线程池如何分派它们的假设），死锁怎么会发生。 - hifier

假设线程池最终处于运行任务1-N的情况。然而，在执行此时，每个任务都在等待某些共享资源（不一定是相同的资源）。这些共享资源将由任务N+1...?释放。如果您使用线程运行此系统，它将正常工作-当线程阻塞时，其他线程会被调度；共享资源被解锁，一切都能正常工作。这是一个边缘情况，但实际上并不罕见-例如，任何障碍同步都会出现这种情况。 - Eamon Nerbonne

重点是，无论如何，您需要更精确地指定什么是“OK”，以及期望的行为。如果您想要完全的通用性，最终会得到等价于线程的东西。 - Eamon Nerbonne

Eamon，很抱歉我仍然不理解你的观点（也许是我太笨了）。应用程序似乎不能依赖于尚未被接收的作业以便已经在进行中的作业能够完成。多队列线程池需要保证的唯一事情就是处理同一队列中作业的顺序。鉴于此，您可以设计您的应用程序，使死锁不可能发生。 - hifier

显示剩余7条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alexey Kukanov · Accepted Answer

新增：我现在倾向于最好从简单的开始，为每个桶保留一个独立的线程，只有当这种简单解决方案被认为存在问题时，才寻找其他解决方案。更好的解决方案可能取决于简单方法引起的问题。

无论如何，我将保留我的初始答案并附上一些思考。

您可以创建一个特殊的全局队列，用于“工作可用于桶X”的信号。

所有空闲的工作线程都会等待这个队列，当信号放入队列中时，一个线程将取出它并继续相应的桶来处理工作，直到该桶变为空。

当一个新的工作任务提交到一个有序桶中时，应检查是否已经分配了一个工作线程给该桶。如果已经分配，则新任务最终将由此工作线程处理，因此不应发送任何信号。如果没有分配工作线程，则检查桶是否为空。如果是空的，则在全局信号队列中放置一个信号，说明该桶中已经有新的任务到达；如果不为空，则应该已经发出了这样的信号，并且工作线程很快就会到达，因此不需要做任何操作。

新增：我认为我上面的想法可能会导致某些工作任务被饿死，如果线程数少于“活动”桶的数量并且有大量的传入任务。如果所有线程都已经忙碌，并且一个新的工作任务到达了尚未服务的桶中，那么需要等待很长时间才能释放出一个线程来处理这个新任务。因此需要检查是否有空闲的工作线程，如果没有，则创建一个新线程......这增加了更多的复杂性。