代码之家 › 专栏 › 技术社区 › user171929

加权、负载平衡的资源调度算法

resource-scheduling load-balancing scheduling language-agnostic algorithm

user171929 · 技术社区 · 17 年前

我正在开发的软件应用程序需要能够根据用户当前拥有的任务数量将任务分配给一组用户,其中任务最少的用户最有可能获得下一个任务。但是,应将当前任务负载视为权重,而不是绝对顺序定义。我需要实现一个加权的负载平衡算法。

假设有五个用户,任务数量如下:

B:5 C:0 E:9

我想按照CABDE的顺序为下一个任务的用户排定优先级,其中C最有可能获得分配,E最不可能。这里有两件重要的事情需要注意:

现在,我们可以平等对待所有任务,尽管我不介意将任务难度作为一个变量,我可以在将来使用它——但这纯粹是锦上添花。

到目前为止,我提出的想法在某些情况下不是很好。如果有大量用户,它们可能会将用户的权重过于紧密地放在一起;如果用户没有当前任务,它们可能会一落千丈;或者。。。。

我试过上网,但运气不太好。有谁能给我一个快速总结的算法,将工作得很好?我不需要一个实际的实现--我会做那部分--只是一个很好的描述。另外,是否有一个好的网站可以免费访问?

此外,虽然我当然欣赏质量,但这不一定是统计上完美的。所以,如果你能想出一个好的但不是很好的技术,我很感兴趣!

1 回复 | 直到 17 年前

Community Mohan Dere 6 年前

正如您所指出的,这是一个负载平衡问题。这不是一个真正的日程安排问题,因为您并没有试图最小化任何事情(总时间、并发工作人员的数量等)。没有特别的限制(工作持续时间、时间冲突、要匹配的技能集等),所以实际上您的问题归结为选择适当的权重函数。

你说有些情况你想避免,比如用户权重太接近。你能提供更多细节吗?例如,让分配的机会与当前的工作量成正比,由其他工人的工作量标准化,这有什么不对?您可以将其视为一系列不同长度的块(任务),打包到一组箱子(工人)中,在这些箱子中,您试图保持箱子的总高度尽可能均匀。

编辑:示例负载平衡函数

根据您的评论,这里有一些简单函数的示例,可以为您提供不同的平衡行为。一个基本问题是,你想要的是确定性行为还是概率性行为。我将分别举几个例子。

1) 简单任务农场。

2) 保证公平的工作量。 如果工人以不同的速度工作,并且您不希望某些工人比其他工人做得更多,那么请跟踪每个工人已完成的+待处理的工作的数量。分配下一份工作以保持此数字均匀分布(快速工作的员工可获得免费休息)。

选择每个员工可以拥有的最大工作数量。每个工人的工作量都正常化为该数字。例如,如果每个工人的最大作业数为15,则在达到产能之前可以再添加50个作业。因此,对于每个工人来说,分配下一份工作的概率是

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

如果不想使用特定的最大阈值,可以使用当前挂起作业数最高的工作进程作为限制。在这种情况下,这是worker E,所以概率是

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

R 介于0和1之间,并将其与这些边界进行比较。所以如果 R R

4) 非线性归一化。 使用对数函数(而不是线性减法)对数字进行加权是获得非线性归一化的一种简单方法。你可以用它来扭曲概率,例如,使没有很多工作的工人更有可能得到更多的工作。

关键是,这样做的方法实际上是无限的。您使用的权重函数取决于您试图启用的特定行为。希望这能给你一些想法,作为一个起点。