你可以用两个简单的队列来做到这一点。busy
队列和队列waiting
。(请注意,在操作系统中,实际上有更多队列,其中最简单的是blocked
队列)。
队列包含已经有工作的busy
任务(或工作成员,如果需要)。waiting
队列保存已完成其工作的任务。根据您的初始配置,一个队列已满而另一个为空(例如,如果最初没有人有工作,则busy
队列为空且waiting
已满)。
现在您的任务分配算法很简单,如下所示:
Every 1 hour
If waiting.empty // If no one previously-known to be without a job
Linearly search busy and find who has finished their job
Add them in order to waiting while removing them from busy
(So, search busy from head to tail and add to waiting from tail)
If !waiting.empty // If now there is someone without a job
Assign a job to waiting.head and put it in the end of busy
该算法将通过保持任务有序来确保没有饥饿。因此,例如,如果两个任务非常快,而其他任务永远耗时,那么算法会在两个快速任务之间交替进行(而不是一直只给其中一个任务)。
现在,即使他获得了所有工作而其他人都没有,您实际上可能希望给出最快的大多数工作(不太可能,但我不知道您的目标)。在这种情况下,您需要一些簿记来对任务进行排名。例如,任务分配给他们的时间以及他们完成任务的时间。这意味着上述算法中的线性搜索应该每小时进行一次(而不是仅在waiting
为空时)。
因此,waiting
成为最大优先级队列,其中优先级越高,任务越快。因此,如果不忙,最快的任务总是会首先出现。
如果您想使用此算法在一定程度上补偿饥饿,您可以在age
每个任务中添加一个,每次他们进入waiting
并且没有找到工作时都会增加。那么优先级将是任务的速度和它的年龄的组合。如果您有两者的线性组合,则当任务老化时,您不需要重新排列优先级队列,因为顺序保持不变(因为它们都同时老化相同的数量)。
编辑:即使我不明白为什么在 php 中每个调度时间只能访问一个成员,但无论如何我都有你的解决方案。
由于您没有任何有关成员速度的信息,因此首先为每个成员分配任务是不可避免的。那就是学习阶段。因此,无论哪种结构包含任务,起初它都应该像 FIFO 一样工作。
随着您逐渐了解成员的速度,您需要更好地安排他们在队列中。
好吧,这使用与上面部分非常相似的算法(使用优先级队列),您可以实现这一点。
首先,为每个成员保留三个值work_time_start
:min_work_time
和max_work_time
。它们代表您对成员完成任务所需时间的理解。当您将工作分配给成员时,您将其设置为work_start_time
. 每当您在算法中的任何地方访问该节点时,根据它是否完成了他的任务,您都会更新它的min_work_time
or max_work_time
。最初min_work_time
是 1 并且max_work_time
是无穷大。
现在您可以拥有三个(优先级)队列;waiting
, busy
, maybe_busy
. 前两个队列和以前一样。第三个是你不确定他们是否完成任务的任务。换句话说,它包含当前执行时间介于min_work_time
和之间的任务max_work_time
。
注意:我假设您只能执行一次任务,但您可以根据需要检查您的簿记(其中可能包含不精确的数据)。那样行吗?
所以这是新算法:
Every one hour
// Note: busy is a min-priority queue on work_start_time + min_work_time
while busy.head satisfies (time() - work_start_time >= min_work_time)
remove busy.head and add it to maybe_busy
// Note: maybe_busy is a min-prioiry queue on work_start_time + max_work_time
while maybe_busy.head satisfies (time() - work_start_time >= max_work_time)
remove maybe_busy.head and add it to waiting
// Note: waiting is a min-priority queue on min_work_time
If !waiting.empty
take waiting.head
assign a task to it
put it in busy
Else
go to maybe_busy.head
If it is still busy
update its min_work_time
remove from maybe_busy and add to busy
sorry, but you can't assign a task this hour
If it is not busy
remove from maybe_busy
update its max_work_time
assign a task to it
put it in busy
该算法可能看起来很复杂,并且我可能引入了一些错误,但这个概念非常简单。任务具有三种状态:
WAITING
/ \
BUSY -- MAYBE BUSY
WAITING
任务肯定是免费的,因此您可以随时为它们分配任务。BUSY
任务肯定很忙,所以你不需要去找他们。
busy
是 上的最小优先级队列work_start_time + min_work_time
,这意味着查看其头部,您将获得第一个可能已完成其工作的成员。如果是这样,则将其移至maybe_busy
(并重复直到头部仍然很忙)
maybe_busy
是 上的最小优先队列work_start_time + max_work_time
,这意味着查看它的头部,你会得到第一个肯定已经完成工作的成员。如果是,则将其移至waiting
(并重复直到头部仍然不知道它是否忙)
前两个while
循环是簿记,不需要您实际去找会员。它们是根据您迄今为止收集的信息进行管理的。
然后,您检查waiting
. 如果它不为空,那么您有一个肯定可用的成员。你只要去它并给它一个任务。把他放进去,busy
因为你刚刚给了他一份工作。
如果waiting
是空的,不幸的是,你不得不去找一个你怀疑大多数人会完成工作的成员(负责人maybe_busy
)并询问他是否完成了。
如果他还没有完成,你更新它min_work_time
,这样你以后就会知道他比你以前想象的要慢。然后你需要将他添加到,busy
因为他现在肯定很忙(你刚刚问过他!)
如果他完成了,你会更新它max_work_time
,所以在未来你知道他比你以前快。然后,您为其分配任务并将其添加到其中,busy
因为您刚刚给了他一份工作。
起初,这个算法会不断地把每一个都放进maybe_busy
去,然后一个接一个地去,所以一开始它就像一个先进先出。然而,在第一次迭代之后,它会对每个任务可能需要多长时间有一个基本概念,并且会更好地猜测它应该首先执行哪个任务。每次访问后,都会对统计数据进行细化。
注意:该算法仍然存在饥饿问题。如果算法找出了超级快的成员,它将不断地给他工作。如果您不想饿死其他任务,您将再次需要引入age
.