Appearance
SJF 短作业优先调度
考情分析
SJF 及其抢占式变体 SRTF 是调度算法中的核心考点，计算题高频出现。属于 🔥🔥🔥 高频核心。
FCFS 的问题是短作业被长作业卡住。反过来想：如果总是让最短的任务先做完，整体等待时间就能降到最低。这就是 SJF 的出发点。
算法规则
短作业优先（Shortest Job First）：从就绪队列中选择服务时间最短的进程分配 CPU。
| 变体 | 名称 | 抢占性 |
|---|---|---|
| SJF | 短作业优先 | 非抢占式 |
| SRTF | 最短剩余时间优先（Shortest Remaining Time First） | 抢占式 |
非抢占式 SJF 示例
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
时间: 0 7 8 12 16
├───────────┤──┤────────┤────────┤
P1 P3 P2 P4P1 到达时没有其他进程，先执行。P1 完成后，P2/P3/P4 都已到达，P3 最短（1），先执行 P3。
| 进程 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|
| P1 | 7 | 7 | 1.00 |
| P3 | 8 | 4 | 4.00 |
| P2 | 12 | 10 | 2.50 |
| P4 | 16 | 11 | 2.75 |
| 平均 | 8.00 | 2.56 |
对比 FCFS 的平均周转时间 8.75，SJF 降低到了 8.00。
抢占式 SRTF 示例
同样的数据，使用 SRTF：
时间: 0 2 4 5 7 11 16
├───┤───┤─┤───┤───────┤───────┤
P1 P2 P3 P2 P1 P4- t=0：只有 P1，执行 P1（剩余7）
- t=2：P2 到达（服务4），P1 剩余5。4<5，抢占，执行 P2
- t=4：P3 到达（服务1），P2 剩余2。1<2，抢占，执行 P3
- t=5：P3 完成，P4 到达（服务4），P2 剩余2。2<4<5，执行 P2
- t=7：P2 完成，P1 剩余5，P4 服务4。4<5，执行 P4
- t=11：P4 完成，执行 P1
- t=16：P1 完成
| 进程 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|
| P1 | 16 | 16 | 2.29 |
| P2 | 7 | 5 | 1.25 |
| P3 | 5 | 1 | 1.00 |
| P4 | 11 | 6 | 1.50 |
| 平均 | 7.00 | 1.51 |
SRTF 的平均周转时间进一步降低到 7.00。
交互可视化
SJF 的最优性
在所有进程同时到达的前提下，SJF（非抢占）可以证明平均等待时间最小。其抢占版本 SRTF 则在所有调度算法中平均等待时间最小（不要求同时到达）。
直觉理解：让短作业先执行，减少了后面作业的等待时间，总的等待时间之和最小。
缺点
| 缺点 | 说明 |
|---|---|
| 饥饿 | 长作业可能永远得不到执行（不断有短作业到达） |
| 无法预知服务时间 | 实际中很难提前知道进程需要多长时间 |
| 对长作业不公平 | 短作业优先意味着长作业被歧视 |
考研高频考点
- 🔥🔥🔥 SJF 和 SRTF 的调度过程和指标计算
- 🔥🔥🔥 SJF 平均等待时间最优（非抢占式调度中）
- 🔥🔥 SJF 可能导致饥饿
- 🔥🔥 抢占式（SRTF）vs 非抢占式（SJF）的区别
- 🔥 实际中无法预知服务时间的问题
SJF 追求最短平均等待时间，但在交互式系统中，用户更在乎响应速度。下一篇看时间片轮转如何兼顾每个进程的响应。