最早截止时间优先(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 利用率是不可能的。
根据 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 利用率是不可能的。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频