经典调度算法
经典调度算法
复习定位
FCFS、SJF、RR、优先级、多级反馈队列这五种算法是一个操作系统调度器设计的基础。现代Linux CFS是这些思想的综合实现。考试一般要求给定一组进程的到达时间和CPU区间——计算某调度方案下的平均等待时间/周转时间——并知道不同算法适用的场景。这部分学习离不开甘特图计算和手动推演。
FCFS先来先服务
FCFS的队列是第一道到达的进程在队首、后到的排入队尾。非抢占——一个进程持续运行直到退出或执行I/O发生阻塞。
FCFS的护航效应——一个长进程堵住就绪队列——所有短的后续进程排队等待。以三个进程为例：
| 进程 | CPU区间 | 到达时间 |
|---|---|---|
| P1 | 24 | 0 |
| P2 | 3 | 0 |
| P3 | 3 | 0 |
FCFS甘特图: P1(0-24) → P2(24-27) → P3(27-30)
平均等待: (0 + 24 + 27)/3 = 17
平均周转: (24 + 27 + 30)/3 = 27
如果到达顺序改为P2→P3→P1: P2(0-3) → P3(3-6) → P1(6-30)
平均等待: (0 + 3 + 6)/3 = 3
平均周转: (3 + 6 + 30)/3 = 13
护航效应造成的平均等待时间差距在现实中更加严重——一个长时间的计算作业可以让数十个交互命令的响应变差一个数量级。在多道程序系统中——FCFS通常只用于作业调度层面——进程调度几乎不会直接采用。
SJF短作业优先(非抢占)
选择预期CPU区间最小的就绪进程来执行——一旦开始就不被其他更短进程抢占。SJF在"所有进程同时就绪"的条件下可证明为最优——最小化平均等待时间。
证明思路(交换论证):假设一个非SJF最优调度中存在相邻的两个进程a和b——a比b先运行但a的CPU区间大于b——交换a和b的顺序——b先运行——a的等待时间增加b的CPU区间、b的等待时间减少a的CPU区间——净节约了a-b的时间——因此交换后平均等待时间更小。对调度序列反复应用此交换——最终得到按CPU区间递增排序的SJF序列——因此SJF平均等待时间最小。
| 进程 | CPU区间 | 到达时间 |
|---|---|---|
| P1 | 8 | 0 |
| P2 | 4 | 0 |
| P3 | 9 | 0 |
| P4 | 5 | 0 |
SJF顺序: P2(4)→P4(5)→P1(8)→P3(9)
甘特图: P2(0-4) → P4(4-9) → P1(9-17) → P3(17-26)
平均等待: (0+4+9+17)/4 = 7.5
FCFS顺序P1→P2→P3→P4: 等待:(0+8+12+21)/4=10.25。SJF确实更优——但需要预测每个进程的CPU区间长度。
SRTF短剩余时间优先(抢占SJF)
新进程的剩余CPU时间比当前运行进程的剩余CPU时间更短——则抢占。SRTF在实时性和缩短等待时间方面非常有前景——但计算的是当前剩余时间——每一次新进程进入时都要重新评估且CPU切换频率较高。
| 进程 | CPU区间 | 到达时间 |
|---|---|---|
| P1 | 8 | 0 |
| P2 | 4 | 1 |
| P3 | 9 | 2 |
| P4 | 5 | 3 |
时刻0只有P1→P1执行到时刻1。时刻1P2到达(剩余4<8-1=7)→抢占→P2执行。时刻2P3到达(9>3)不抢占P2继续。时刻3P4到达(5>2)不抢占P2继续。时刻5P2完成→此时P1(7)、P3(9)、P4(5)就绪→最短剩余P4→P4执行到时刻10(P4完成)→P1(7)执行到时刻17→P3(9)执行到时刻26。平均等待和周转经计算各自低于FCFS和SJF非抢占版本的结果在短任务负载下格外明显。
优先级调度
每个进程分配优先级(数字越小表示优先级越高)。调度器总是选择就绪进程中优先级最高的运行。优先级可以静态设置(如nice值)或动态调整(如交互进程因频繁I/O阻塞而升优先级、CPU密集进程因连续使用时间片而降级)。
优先级反转：高优先级进程H在等待低优先级进程L持有的锁——但L被不高不低的进程M抢占——导致H被M间接阻塞。解决方案：优先级继承——L暂时提升到H的优先级——M无法抢占L——L快速释放锁回退原优先级。
多级反馈队列(MLFQ)
MLFQ用多级队列和控制进程升降的规则实现"自动区分交互进程和CPU密集进程"——交互进程获得快速响应、CPU密集进程在底层拿到更长时间片。
MLFQ规则：
- 高优先级队列的进程先运行
- 同优先级进程之间轮转
- 新进程进入最高优先级队列
- 用完整时间片→降级(可能是CPU密集)
- 时间片用完前放弃CPU(如I/O阻塞)→保留或升级(可能是交互进程)
- 定期将所有进程提升回最高优先级队列(防止饥饿)
复习检查
FCFS的护航效应如何通过排序改变就绪队列的次序来改善？给出的三进程例子调换顺序将平均等待时间从17降至3——在现实中能否要求用户按作业大小排序提交？
SJF不是最优的——是什么假设让它成为一个理想的"最短"比较模型？现实中如何近似预测下一个进程的CPU区间长度？
SRTF每次新进程到达就重新评估剩余的CPU时间——这个过程本身增加了多少次调度/上下文切换——应该怎样评估这整个过程中增加的切换开销是否值得？
多级反馈队列为什么可以自动将我不经意间的CPU密集进程降级到低优先级——从规则4和规则5的理解角度分别解释交互进程和CPU密集进程的移动路径。
优先级在MLFQ中是如何决定的——它是直接分配给每个进程一个数字还是通过进程在哪个队列来间接确定的？