1

我们有一个具有不同长度、多个 cpu 内核和上下文切换时间的任务列表。我们希望在内核之间找到最佳的任务调度，以最大限度地提高处理器利用率。我们怎么能找到这个？如果我们从列表中选择最大的可用任务并将它们一一分配给当前准备好的核心，这不是最好的，还是您认为我们必须尝试所有命令才能找出哪个是最好的？

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

4

1 回答 1

1

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

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

  • I/O 密集型任务可能会在执行过程中不断地搁置一边，让其他进程继续工作，因为它会sleeping持续很多时间，等待将数据检索到主内存；

  • 交互任务必须连续执行，但不能不中断执行，因为它会产生中断，等待用户输入，但需要有高优先级，以免让用户注意到执行延迟。

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

编辑：

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

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

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

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

在 svick 提供的参考资料中，您可以看到一种动态编程方法，您可以将其映射到您的问题上。

于 2012-12-22T17:12:48.300 回答