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

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

我知道，仅当任务抢占式地在单个处理器上调度时，EDF 才是最佳调度算法，因此我想知道是否可能对任务施加任何测试或约束，以验证我的任务集是否可以使用非抢占式 EDF。

任何帮助是极大的赞赏。谢谢

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

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

理由：您可能知道 Liu/Layland 标准 sum_i(e_1/P_i)

EDIT:我临时导出了上面的条件。然而，这只是一个足够的。为了进行更精确的分析，必须考虑一项任务只能被具有较大相对截止日期的另一任务阻止，即，相对于所使用的模型，具有较长周期的任务，参见例如，[JL00]*，定理 6.18。

因此，对于任务 T_1、...、T_n 且周期为 P_1

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

那么，任务集是可行的

sum_i L'_i/P_i <= 1.

C.f. [JL00]，第 8.3 节有关非抢占式关键节。

^{* [JL00] Jane W.S. Liu, Real-Time Systems, Prentice Hall, 2000}