首页 > 编程笔记 > 操作系统笔记

最早截止时间优先(EDF)算法详解

最早截止期限优先(EDF)调度根据截止期限动态分配优先级。截止期限越早,优先级越高;截止期限越晚,优先级越低。

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

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

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

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

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

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

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

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

所有教程

优秀文章