最早截止时间优先（EDF）算法详解

最早截止期限优先（EDF）调度根据截止期限动态分配优先级。截止期限越早，优先级越高；截止期限越晚，优先级越低。

根据 EDF 策略，当一个进程可运行时，它应向系统公布截止期限要求。优先级可能需要进行调整，以便反映新可运行进程的截止期限。注意单调速率调度与 EDF 调度的不同，前者的优先级是固定的。

图 1 错过截止期限的单调速率调度

为了说明 EDF 调度，我们再次调度如图 1 所示的进程，这些进程通过单调速率调 度不能满足截止期限要求。记住：进程 P₁ 有 ρ₁ = 50 和 t₁ = 25，进程 P₂ 有 ρ₂ = 80 和 t₂ = 35，这些进程的 EDF 调度如图 2 所示。

图 2 最早截止期限优先调度

进程 P₁ 的截止期限为最早，所以它的初始优先级比进程 P₂ 的要高。当 P₁ 的 CPU 执行结束时，进程 P₂ 开始运行。不过，虽然单调速率调度允许 P₁ 在时间 50（即下一周期开始之际）抢占 P₂，但是 EDF 调度允许进程 P₂ 继续运行。进程 P₂ 的优先级比 P₁ 的更高，因为它的下一个截止期限（时间 80）比 P₁ 的（时间 100）要早。因此，P₁ 和 P₂ 都能满足它们的第一个截止期限。

进程 P₁ 在时间 60 再次开始运行，在时间 85 完成第二个 CPU 执行，也满足第二个截止期限（在时间 100）。这时，进程 P₂ 开始运行，只是在时间 100 被 P₁ 抢占。P₂ 之所以被 P₁ 抢占是因为 P₁ 的截止期限（时间 150）要比 P₂ 的（160）更早。在时间 125，P₁ 完成 CPU 执行，P₂ 恢复执行；在时间 145，P₂ 完成，并满足它的截止期限。然后，系统空闲直到时间 150；在时间 150 进程 P₁ 开始再次被调度。

与单调速率调度不一样，EDF 调度不要求进程应是周期的，也不要求进程的 CPU 执行的长度是固定的。唯一的要求是，进程在变成可运行时，应宣布它的截止期限。

EDF 调度具有吸引力的地方是，它是理论上最佳的。从理论上说，它可以调度进程，使得每个进程都可以满足截止期限的要求并且 CPU 利用率将会是 100%。然而，在实际中，由于进程的上下文切换和中断处理的代价，这种级别的 CPU 利用率是不可能的。