3

我想在 C 中实现最早的截止日期调度，但我在网上找不到算法..

我理解下面的例子，当时间为 0 时，A1 和 B1 都到了。由于 A1 有最早的截止日期，所以它被排在最前面。当 A1 完成时，B1 将获得处理器。当时间为 20 时，A2 到达。因为 A2 的截止日期比 B1 早，所以 B1 被中断，以便 A2 可以执行完成。然后B1在时间为30时恢复。当时间为40时，A3到达。但是，B1 有一个更早的结束期限，并且允许在时间为 45 时执行完成。然后给 A3 处理器并在时间为 55 时完成。但是我无法想出解决方案。请帮我找到一个算法。谢谢..

示例图片

例子 http://imageshack.us/photo/my-images/840/scheduling.png/

4

2 回答 2

4
  • 当一个进程完成（和开始）时，将最低的进程processTimeToDeadline - processTimeToExecute作为新的当前进程
  • 当一个新进程到达时，当且仅当替换当前进程newProcessTimeToDeadline - newProcessTimeToExecute < currentProcessTimeToDeadline - currentProcessTimeStillNeededToExecute。

注意：如果使用多个 CPU 执行此操作，则会遇到多处理器调度问题，这是 NP 完全问题。

于 2011-10-02T15:11:52.677 回答
0

先前的答案描述了“最早可行的最后期限优先”（EFDF）调度程序，它完美地从 qestion 中获取图像。“Earliest Deadline First”（EDF）调度器更简单。调度程序只运行具有最早截止日期的任务。这就是全部。

于 2015-08-09T08:49:19.473 回答