algorithm - 某些给定任务的最佳任务调度算法是什么？

Question

我们有不同长度的任务列表、一些 cpu 核心和上下文切换时间。我们希望找到内核之间的最佳任务调度，以最大限度地提高处理器利用率。我们怎么能找到这个？如果我们从列表中选择最大的可用任务并将它们一个一个地交给当前就绪的核心，这不是最好的，或者你认为我们必须尝试所有订单才能找出最好的吗？

我必须补充一点，所有核心都在时间单元 0 就绪，任务应该同时工作。

Answer 1

这里的想法是没有 Elixir ，因为您必须考虑正在执行的任务的类型，并尝试尽可能好的安排它们。

• CPU 密集型任务不使用太多通信 (I/O)，因此需要连续执行，并且仅在必要时中断 -- 根据所使用的策略；

• I/O 绑定(bind)任务可能会在执行过程中不断搁置，允许其他进程工作，因为它会 sleep 很多时间，等待数据被检索到主内存；

• interactive tasks 必须要连续执行，但不能不间断执行，会产生中断，等待用户输入，但需要有高优先级，以免被用户注意到延迟执行。

考虑到这一点以及上下文切换成本，您必须评估您拥有的任务类型，从而为您的调度程序选择一个或多个策略。

编辑:

我认为这是一个简单的概念性问题。考虑到您必须实现解决方案，您必须分析需求。

由于您有任务的长度和上下文切换时间，并且您必须保持核心忙碌，这就变成了一个优化问题，您必须在任务结束时保持最少数量的核心空闲进程，但您需要保持最少数量的上下文切换，以便您的整体执行时间不会增长太多。

正如 svick 所指出的，这听起来像是一个划分问题，它是 NP 完全的，您需要将一个数字序列划分为给定数量的列表，以便每个列表的总和等于每个其他。

在您的问题中，您可以放宽目标，这样您就不再需要所有内核执行相同的时间量，但您希望任意两个内核执行时间之间的差异尽可能小.

在 svick 提供的引用资料中，您可以看到一种动态规划方法，您可以将其映射到您的问题上。