2

我需要一个算法(用于在 php 中使用)来管理我们的成员

我有一些成员,为我准备内容,

他们正在准备内容,完成后,等待我去获取他们的内容(会员无法参考我),在我参考他们并获取内容后,他们为新内容工作,下一个内容的未定义时间将完成(每1小时,我只能去1个成员)

成员工作完全分开!

我的会员工作速度有差异,有些会员快有些会员慢

如果我用先进先出的方法去会员(考虑所有会员,同样速度),一些会员很快,等待很长时间,而对于其他一些慢的会员,我去他们无效。

起初,我不知道成员的速度,应该考虑所有成员的速度相等,直到我检测到他们的速度

我像这样记录我对会员的访问:

╔════════╦════════════╦═══════════════════╗
║user id ║ last visit ║ work is complete? ║
╠════════╬════════════╬═══════════════════╣
║ 1      ║ 8:00       ║     Yes           ║
║ 2      ║ 9:00       ║     No            ║
║ 3      ║ 10:00      ║     No            ║
║ 4      ║ 11:00      ║     Yes           ║
║ 1      ║ 12:00      ║     Yes           ║
║ 2      ║ 13:00      ║     No            ║
║ 3      ║ 14:00      ║     No            ║
║ 4      ║ 15:00      ║     Yes           ║
║ 1      ║ 16:00      ║     Yes           ║
║ 2      ║ 17:00      ║     Yes           ║
║ 3      ║ 18:00      ║     Yes           ║
║ 4      ║ 19:00      ║     Yes           ║
╚════════╩════════════╩═══════════════════╝

在上面的例子中,用户 1,4 快,用户 2,3 慢

如何优先考虑所有成员,因为快速用户访问的次数更多,而慢速用户访问的次数更少,

以及如何检测哪个用户是下次访问的更好选择?

谢谢

4

1 回答 1

3

你可以用两个简单的队列来做到这一点。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_startmin_work_timemax_work_time。它们代表您对成员完成任务所需时间的理解。当您将工作分配给成员时,您将其设置为work_start_time. 每当您在算法中的任何地方访问该节点时,根据它是否完成了他的任务,您都会更新它的min_work_timeor 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.

于 2013-09-19T09:35:10.800 回答