Luc*_*ore 5 algorithm optimization multitasking
我正在寻找一种算法来分配一些任务.问题如下:
假设我有一个中央任务生产者和一些客户消费者.生产者生成任务并且消费者接受任务(对于初学者,一次一个),处理它们,并且当它们完成时,接受新任务(我已经有任务队列).
问题是,如果您考虑从生产者到消费者的任务延迟,将任务组合在一起可能是有意义的.例如,假设我们总共有10个任务和2个消费者.如果每个任务需要5毫秒来处理并且网络延迟也是5毫秒,则每个消费者每组发送2组5个任务将花费5毫秒+ 5*5毫秒= 30毫秒,而单独发送任务需要5*5毫秒+ 5*5ms = 50ms,因为每个任务都会出现延迟开销.
它不像分组那么简单,因为某些任务可能需要更长时间,并且将它们分开发送是有意义的,以便让其他消费者并行处理花费较短时间的其他任务.我打算做一些关于任务类型的统计数据.消费者的数量也不是一成不变的.
想要一个好的算法或一个好的阅读,可以帮助我实现这个目标吗？
当生产者生成一个任务时，不立即发送它只会增加该任务的延迟。因此，我假设任务调度程序处理当前任务队列的快照：它获取队列中的所有任务，立即向各个方向发送它们，返回到队列，再次获取同时积累的所有任务，起泡，冲洗，重复。
调度程序维护每个消费者的完成时间的估计。它按照增加的完成时间对消费者进行排序，并将任务添加到最早完成时间的消费者的批次中。然后，它将平均任务时间添加到消费者完成时间估计中，从而获得新的估计，然后根据新的估计对消费者重新排序（使用O(log n)堆）并转到下一个任务。当前快照的所有任务处理完毕后，将批次发送给消费者并制作新的快照。
这项政策将实现平均消费者负荷均等。可以改进的是：
如果每个消费者都能够提供一些有关估计完成时间的反馈：它是平均任务时间乘以消费者中待处理的任务数量。它更精确，因为消费者将使用已完成任务的实际时间而不是平均时间
如果处理每个任务的时间是已知的或者可以估计每个任务的时间，那么调度程序将使用每个任务的估计而不是平均值。
编辑：忘记提及：
预计完成时间为start-time + average-task-time * number-of-tasks-sent-to-a-consumer + latency * number-of-batches-sent-to-a-consumer。