多级反馈队列调度算法详解
通常在使用多级队列调度算法时,进程进入系统时被永久地分配到某个队列。例如,如果前台和后台进程分别具有单独队列,那么进程并不从一个队列移到另一个队列,这是因为进程不会改变前台或后台的性质。这种设置的优点是调度开销低,缺点是不够灵活。
相反,多级反馈队列调度算法允许进程在队列之间迁移。这种想法是,根据不同 CPU 执行的特点来区分进程。如果进程使用过多的 CPU 时间,那么它会被移到更低的优先级队列。这种方案将 I/O 密集型和交互进程放在更高优先级队列上。 此外,在较低优先级队列中等待过长的进程会被移到更高优先级队列。这种形式的老化可阻止饥饿的发生。
图 1 多级反馈队列
例如,一个多级反馈队列的调度程序有三个队列,从 0 到 2(图 1)。调度程序首先执行队列 0 内的所有进程。只有当队列 0 为空时,它才能执行队列 1 内的进程。类似地,只有队列 0 和 1 都为空时,队列 2 的进程才能执行。到达队列 1 的进程会抢占队列 2 的进程。同样,到达队列 0 的进程会抢占队列 1 的进程。
每个进程在进入就绪队列后,就被添加到队列 0 内。队列 0 内的每个进程都有 8ms 的时间片。如果一个进程不能在这一时间片内完成,那么它就被移到队列 1 的尾部。如果队列 0 为空,队列 1 头部的进程会得到一个 16ms 的时间片。如果它不能完成,那么将被抢占,并添加到队列 2。只有当队列 0 和 1 为空时,队列 2 内的进程才可根据 FCFS 来运行。
这种调度算法将给那些 CPU 执行不超过 8ms 的进程最高优先级。这类进程可以很快得到 CPU,完成 CPU 执行,并且处理下个 I/O 执行。
所需超过 8ms 但不超过 24ms 的进程也会很快得以服务,但是它们的优先级要低一点。长进程会自动沉入队列 2,队列 0 和 1 不用的 CPU 周期按 FCFS 顺序来服务。
通常,多级反馈队列调度程序可由下列参数来定义:
多级反馈队列调度程序的定义使其成为最通用的 CPU 调度算法。通过配置,它能适应所设计的特定系统。遗憾的是,由于需要一些方法来选择参数以定义最佳的调度程序,所以它也是最复杂的算法。
相反,多级反馈队列调度算法允许进程在队列之间迁移。这种想法是,根据不同 CPU 执行的特点来区分进程。如果进程使用过多的 CPU 时间,那么它会被移到更低的优先级队列。这种方案将 I/O 密集型和交互进程放在更高优先级队列上。 此外,在较低优先级队列中等待过长的进程会被移到更高优先级队列。这种形式的老化可阻止饥饿的发生。
图 1 多级反馈队列
例如,一个多级反馈队列的调度程序有三个队列,从 0 到 2(图 1)。调度程序首先执行队列 0 内的所有进程。只有当队列 0 为空时,它才能执行队列 1 内的进程。类似地,只有队列 0 和 1 都为空时,队列 2 的进程才能执行。到达队列 1 的进程会抢占队列 2 的进程。同样,到达队列 0 的进程会抢占队列 1 的进程。
每个进程在进入就绪队列后,就被添加到队列 0 内。队列 0 内的每个进程都有 8ms 的时间片。如果一个进程不能在这一时间片内完成,那么它就被移到队列 1 的尾部。如果队列 0 为空,队列 1 头部的进程会得到一个 16ms 的时间片。如果它不能完成,那么将被抢占,并添加到队列 2。只有当队列 0 和 1 为空时,队列 2 内的进程才可根据 FCFS 来运行。
这种调度算法将给那些 CPU 执行不超过 8ms 的进程最高优先级。这类进程可以很快得到 CPU,完成 CPU 执行,并且处理下个 I/O 执行。
所需超过 8ms 但不超过 24ms 的进程也会很快得以服务,但是它们的优先级要低一点。长进程会自动沉入队列 2,队列 0 和 1 不用的 CPU 周期按 FCFS 顺序来服务。
通常,多级反馈队列调度程序可由下列参数来定义:
- 队列数量。
- 每个队列的调度算法。
- 用以确定何时升级到更高优先级队列的方法。
- 用以确定何时降级到更低优先级队列的方法。
- 用以确定进程在需要服务时将会进入哪个队列的方法。
多级反馈队列调度程序的定义使其成为最通用的 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视频