进程调度算法
目录
- 先来先服务（FCFS）
- 短作业优先（SJF）
- 轮转调度（Round Robin）
- 优先级调度（Priority Scheduling）
- 多级队列调度（Multilevel Queue Scheduling）
- 多级反馈队列（Multilevel Feedback Queue, MLFQ）
- 老化（Aging）
- 上下文切换（Context Switch）
- 调度算法性能评估指标
先来先服务（First-Come, First-Served, FCFS）
定义
先来先服务调度算法根据进程到达的顺序分配 CPU，即最先到达的进程最先得到服务。
常见用途
- 简单的批处理系统
- 需要按顺序处理任务的系统
技巧
- 队列实现：使用 FIFO 队列来管理进程
- 无抢占：一旦进程开始执行，它将运行直到完成
示例
进程 | 到达时间 | CPU突发时间
P1 | 0 | 4
P2 | 1 | 3
P3 | 2 | 1
P4 | 3 | 2
甘特图：
0 - 4 : P1
4 - 7 : P2
7 - 8 : P3
8 - 10: P4关键点
- 简单易实现
- 容易导致长时间等待（饥饿）的问题
- 平均等待时间可能较长
短作业优先（SJF）
定义
短作业优先调度算法选择下一个 CPU 突发时间最短的进程执行。
常见用途
- 需要减少平均等待时间的系统
- 常用于批处理系统
技巧
- 进程选择：选择下一个 CPU 突发时间最短的进程
抢占式短作业优先
定义
抢占式 SJF（Shortest Remaining Time First, SRTF）算法选择剩余时间最短的进程执行。如果新到达的进程剩余时间更短，则当前进程会被抢占。
常见用途
- 实时系统
技巧
- 进程选择：持续检查剩余时间最短的进程
- 抢占：新进程到达且剩余时间更短时进行切换
示例
进程 | 到达时间 | CPU突发时间
P1 | 0 | 8
P2 | 1 | 4
P3 | 2 | 9
P4 | 3 | 5
甘特图：
0 - 1 : P1
1 - 5 : P2
5 - 10: P1
10 - 15: P4
15 - 24: P3关键点
- 减少平均等待时间和周转时间
- 需要持续监控进程列表
- 频繁抢占导致高上下文切换开销
非抢占式短作业优先
定义
非抢占式 SJF 算法选择下一个 CPU 突发时间最短的进程执行，直到该进程完成。新到达的进程不会中断当前进程。
常见用途
- 批处理系统
技巧
- 进程选择：选择下一个 CPU 突发时间最短的进程
示例
进程 | 到达时间 | CPU突发时间
P1 | 0 | 6
P2 | 2 | 8
P3 | 4 | 7
P4 | 6 | 3
甘特图：
0 - 6 : P1
6 - 9 : P4
9 - 16: P3
16 - 24: P2关键点
- 减少平均等待时间和周转时间
- 简单易实现
- 可能导致长时间等待（饥饿）的问题
轮转调度（Round Robin）
定义
轮转调度是抢占式 CPU 调度算法，每个进程分配一个固定的时间片或时间量，CPU 调度器按循环顺序为每个进程分配 CPU 时间。
常见用途
- 分时系统
- 交互系统
技巧
- 时间片：每个进程允许运行的固定时间段
- 上下文切换：保存当前进程状态，加载下一个进程状态
示例
进程 | 到达时间 | CPU突发时间
P1 | 0 | 5
P2 | 1 | 4
P3 | 2 | 2
P4 | 3 | 1
时间片：2
甘特图：
0 - 2 : P1
2 - 4 : P2
4 - 6 : P3
6 - 7 : P4
7 - 9 : P1
9 - 11: P2关键点
- 公平分配 CPU 时间
- 上下文切换开销
- 性能依赖于时间片的选择
优先级调度（Priority Scheduling）
定义
优先级调度算法根据进程的优先级分配 CPU，优先级高的进程优先得到 CPU。
常见用途
- 实时系统
- 多任务处理系统
技巧
- 优先级分配：每个进程分配一个优先级
- 抢占或非抢占：可以是抢占式或非抢占式
示例
进程 | 到达时间 | CPU突发时间 | 优先级
P1 | 0 | 4 | 2
P2 | 1 | 3 | 1
P3 | 2 | 1 | 4
P4 | 3 | 2 | 3
甘特图（非抢占）：
0 - 4 : P1
4 - 7 : P2
7 - 8 : P3
8 - 10: P4关键点
- 高优先级进程可能导致低优先级进程饥饿
- 可以使用老化技术防止饥饿问题
多级队列调度（Multilevel Queue Scheduling）
定义
多级队列调度将进程分为多个队列，每个队列有不同的调度算法和优先级。
常见用途
- 复杂的多任务处理系统
技巧
- 队列划分：根据进程类型、优先级等将进程分为多个队列
- 队列调度：各队列有独立的调度算法
示例
队列1（优先级高）: 使用RR调度
队列2（优先级低）: 使用FCFS调度
队列1: P1, P2
队列2: P3, P4
甘特图：
0 - 2 : P1
2 - 4 : P2
4 - 8 : P3
8 - 12: P4关键点
- 灵活的调度策略
- 高优先级队列可能导致低优先级队列饥饿
多级反馈队列（Multilevel Feedback Queue, MLFQ）
定义
多级反馈队列调度允许进程在不同队列间移动，根据其行为和执行情况调整优先级。
常见用途
- 复杂的多任务处理系统
- 需要动态调整优先级的系统
技巧
- 队列移动：根据进程的 CPU 使用情况在队列间移动
- 优先级调整：频繁使用 CPU 的进程移动到低优先级
队列，反之亦然
示例
队列1（时间片2）：P1, P2
队列2（时间片4）：P3, P4
P1在队列1运行2个时间片后移动到队列2
甘特图：
0 - 2 : P1
2 - 4 : P2
4 - 6 : P1
6 - 10: P3
10 - 14: P4关键点
- 动态调整进程优先级
- 减少饥饿问题
- 复杂的实现和管理
老化（Aging）
定义
老化是防止某些进程长时间等待的一种技术。通过逐渐增加等待进程的优先级，确保它们最终获得 CPU 时间。
常见用途
- 防止长期等待（饥饿）问题
- 适用于多级反馈队列调度
技巧
- 优先级增加：定期增加等待进程的优先级
- 调度调整：根据新的优先级重新安排进程
示例
进程 | 初始优先级 | 等待时间
P1 | 3 | 5
P2 | 4 | 3
P3 | 1 | 8
随着时间推移，等待时间长的进程（如P3）的优先级会逐渐增加，最终获得CPU时间关键点
- 防止饥饿问题
- 需要适当的优先级增加策略
上下文切换（Context Switch）
定义
上下文切换是存储当前运行进程的状态并加载下一个要执行进程的状态的过程。
常见用途
- 多任务操作系统
- 分时系统
技巧
- 状态保存：保存当前进程状态（寄存器、程序计数器等）
- 状态加载：加载下一个进程的状态
示例
当时间片到期时，在轮转调度中发生上下文切换：
- 保存当前进程状态
- 加载下一个进程状态
关键点
- 多任务处理的必要条件
- 引入开销（CPU 时间和资源）
- 频繁的上下文切换会降低系统性能
调度算法性能评估指标
平均等待时间 Average Waiting Time
平均等待时间是所有进程等待时间的平均值，等待时间是进程到达时间和其第一次被执行时间之间的差。
平均周转时间 Average Turnaround Time (TAT)
平均周转时间是所有进程从提交到完成所需时间的平均值，包括等待时间和执行时间。
CPU 利用率
CPU 利用率是 CPU 实际执行时间与总时间的比率。
吞吐量
吞吐量是单位时间内完成的进程数量。
响应时间 Response Time
响应时间是从进程提交到系统第一次响应（例如，开始执行）的时间。
关键点
- 各指标权衡取舍：减少等待时间可能增加上下文切换开销
- 不同调度算法适用于不同场景
概括总结
进程调度算法是计算机操作系统管理 CPU 资源的重要方式。它决定了在什么时候运行哪个进程，以提高系统的效率和性能。这里是对常见调度算法的简单介绍：
- 先来先服务（FCFS）：按到达顺序处理进程，简单但可能导致长时间等待。
- 短作业优先（SJF）：选择下一个执行时间最短的进程，有抢占式（SRTF）和非抢占式两种，能减少平均等待时间，但需要预估执行时间。抢占式可能导致频繁上下文切换。
- 轮转调度（Round Robin）：每个进程轮流获得固定的 CPU 时间片，适合分时系统，但时间片选择需要平衡。
- 优先级调度：根据进程优先级分配 CPU，高优先级进程优先，但低优先级进程可能饿死，需要老化技术来防止。
- 多级队列调度：将进程分成多个队列，每个队列有不同的调度算法和优先级。
- 多级反馈队列（MLFQ）：进程可以在不同优先级队列间移动，根据其行为调整优先级，适合复杂系统。
- 老化：逐渐提高等待进程的优先级，防止它们长时间得不到 CPU 时间（进程饥饿）。
- 上下文切换：切换 CPU 执行进程时保存和恢复进程状态，支持多任务处理，但会有开销。