最早截止时间优先(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 利用率是不可能的。
所有教程
- C语言入门
- C语言编译器
- C语言项目案例
- 数据结构
- C++
- STL
- C++11
- socket
- GCC
- GDB
- Makefile
- OpenCV
- Qt教程
- Unity 3D
- UE4
- 游戏引擎
- Python
- Python并发编程
- TensorFlow
- Django
- NumPy
- Linux
- Shell
- Java教程
- 设计模式
- Java Swing
- Servlet
- JSP教程
- Struts2
- Maven
- Spring
- Spring MVC
- Spring Boot
- Spring Cloud
- Hibernate
- Mybatis
- MySQL教程
- MySQL函数
- NoSQL
- Redis
- MongoDB
- HBase
- Go语言
- C#
- MATLAB
- JavaScript
- Bootstrap
- HTML
- CSS教程
- PHP
- 汇编语言
- TCP/IP
- vi命令
- Android教程
- 区块链
- Docker
- 大数据
- 云计算