algorithm - 非抢占式 Earliest deadline 优先调度

Question

我正在开发一个任务调度器，我想使用 EDF 调度。我需要安排的任务集仅包含截止日期等于其周期的任务，并且必须定期安排任务。我遇到的问题是任务一旦开始执行就不能中断。

我知道只有当任务被抢先安排在单个处理器上时，EDF 才是最佳调度算法，所以我想知道是否可以对任务施加任何测试或约束以验证我的任务集可以使用非抢占式 EDF 进行调度。

非常感谢任何帮助。谢谢

Answer 1

设e_i为任务i的执行时间，P_i为周期，e_m=max_i(e_i)。然后，你可以保证你的任务集是可行的，如果

U = sum_i ((e_i + e_m)/P_i) <= 1

理由:您可能知道 Liu/Layland 标准 sum_i(e_1/P_i) <= 1。不可前导任务可被视为对更高优先级任务的阻塞。阻塞时间可以被认为是额外的执行时间。最坏的情况是在最长(较低优先级)的任务启动后，较高优先级的任务直接准备就绪。

编辑:我已经临时得出了上述条件。但是，这仅是一个足够的。为了进行更精确的分析，必须考虑一个任务只能被另一个具有更大相对截止日期的任务阻塞，即，相对于使用的模型，具有更长周期的任务，c.f.例如，[JL00]*，定理 6.18。

因此，对于包含任务 T_1、...、T_n 且周期为 P_1 < P_2 < ... < P_n 的任务集，可以计算

L'_i = e_i + max_{j=i...n}(e_j).

那么，任务集是可行的

sum_i L'_i/P_i <= 1.

比照[JL00]，关于非抢占式关键部分的第 8.3 节。

^{* [JL00] 简 W.S. Liu，实时系统，Prentice Hall，2000}