algorithm - 非抢占式最早截止时间优先调度

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。不可预置任务可以被视为对更高优先级任务的阻塞。阻塞时间可以被认为是额外的执行时间。最坏的情况是，在最长（低优先级）任务开始后，高优先级任务直接就绪。

编辑： 我已经得出了上述临时条件。然而，它只是一个足够的。为了进行更精确的分析，必须考虑到一个任务只能被另一个具有较长相对期限的任务阻塞，即，对于所使用的模型，具有较长周期的任务，cfeg，[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] Jane WS Liu，实时系统，Prentice Hall，2000}