4、短作业优先（SJF）：非抢占式与抢占式、最短剩余时间优先（SRTF）、饥饿问题
短作业优先，简称 SJF。这名字听着挺直白——谁活少谁先干。但实际用起来，坑不少。
我刚开始做调度器的时候，觉得这算法太简单了。不就是排个序嘛。后来被生产环境狠狠教育了一顿。嗯，咱们今天就把这个算法掰开揉碎了讲。
4.1 核心思想：谁短谁先跑
SJF 的目标很明确：最小化平均等待时间。你想想看，一个 2ms 的进程和一个 20ms 的进程同时等着，让短的先跑，长的后跑，平均等待时间肯定更低。
数学上可以证明，SJF 在「平均周转时间」这个指标上是最优的。但注意，我说的是「理论上」。实际中你根本不知道一个进程到底要跑多久。
关键点：SJF 需要预知进程的 CPU 执行时间。这是它最大的软肋。
4.2 非抢占式 SJF
非抢占式，说白了就是：一旦进程开始运行，就让它跑到完。中途不打断。
举个例子：
进程 到达时间 执行时间
P1 0 7
P2 2 4
P3 4 1
P4 5 4非抢占式 SJF 的执行顺序是这样的：
- 时间 0，只有 P1 到达，P1 开始运行
- 时间 7，P1 结束。此时 P2、P3、P4 都已到达。选执行时间最短的 P3（1ms）
- 时间 8，P3 结束。剩下 P2（4ms）和 P4（4ms），随便选一个，比如 P2
- 时间 12，P2 结束，P4 开始
- 时间 16，全部结束
平均等待时间 = (0 + (7-2) + (7-4) + (8-5)) / 4 = (0 + 5 + 3 + 3) / 4 = 2.75ms
我在项目中遇到过一个问题：非抢占式 SJF 对短进程的响应时间其实并不友好。因为如果有一个长进程先到了，它会把 CPU 占住，后面来的短进程只能干等着。这在交互式系统里是灾难。
4.3 抢占式 SJF：最短剩余时间优先（SRTF）
抢占式版本，也叫 SRTF。核心逻辑变了：每次新进程到达时，比较当前运行进程的剩余时间和新进程的执行时间。如果新来的更短，就抢过来。
还是刚才的例子：
进程 到达时间 执行时间
P1 0 7
P2 2 4
P3 4 1
P4 5 4SRTF 的执行过程：
- 时间 0，P1 到达，开始运行
- 时间 2，P2 到达。P1 剩余 5ms，P2 需要 4ms。P2 更短，P1 被抢占，P2 开始运行
- 时间 4，P3 到达。P2 剩余 2ms，P3 需要 1ms。P3 更短，P2 被抢占，P3 开始运行
- 时间 5，P3 结束。此时 P4 到达。P2 剩余 2ms，P4 需要 4ms。P2 继续运行
- 时间 7，P2 结束。P1 剩余 5ms，P4 需要 4ms。P4 更短，P4 开始运行
- 时间 11，P4 结束。P1 继续运行
- 时间 16，P1 结束
平均等待时间 = ((0-0) + (2-2) + (4-4) + (5-5) + (7-7) + (11-11)) ... 等等，我算一下：
P1 等待时间 = 0 + (7-2) + (11-7) = 9ms
P2 等待时间 = (2-2) + (4-4) = 0ms
P3 等待时间 = (4-4) = 0ms
P4 等待时间 = (5-5) = 0ms
平均 = (9 + 0 + 0 + 0) / 4 = 2.25ms
你看，比非抢占式的 2.75ms 更低了。但代价是——上下文切换次数增加了。每次抢占都要保存和恢复寄存器状态，这本身就有开销。
我的建议：SRTF 适合批处理系统，不适合交互式系统。因为频繁的抢占会导致响应时间抖动，用户体验很差。
4.4 饥饿问题：长进程的噩梦
这是 SJF 家族最严重的缺陷。什么叫饥饿？就是一个进程永远得不到 CPU。
为什么会这样？你想想看：
- 系统里不断有短进程到达
- 每次调度，短进程都比长进程优先
- 长进程永远排不上队
我曾经在一个实时系统中遇到过这个问题。有个后台日志处理进程，执行时间大约 500ms。结果系统里不断有几十微秒的键盘中断处理任务进来。那个日志进程等了整整 3 分钟才被调度到。用户以为系统死机了。
注意：饥饿问题在 SRTF 中比非抢占式 SJF 更严重。因为非抢占式至少保证长进程一旦开始就能跑完，而 SRTF 可能让长进程永远被抢占。
4.5 解决方案：老化技术
解决饥饿问题，最常用的方法是老化（Aging）。说白了就是：随着等待时间增长，动态提升进程的优先级。
具体做法：
- 每个进程维护一个「等待时间计数器」
- 每次调度时，计算「有效优先级 = 原始优先级 + 等待时间 × 系数」
- 等待越久，优先级越高，最终一定能被调度到
举个例子：
假设系数为 1，每等待 1 秒优先级 +1。
一个长进程初始优先级为 10。
等待 5 秒后，优先级变成 15。
等待 10 秒后，优先级变成 20。
最终它会超过所有短进程。核心原则：老化技术保证了「有界等待」——每个进程都能在有限时间内得到 CPU。
4.6 实际应用中的取舍
说实话，纯 SJF 在现代操作系统中很少直接使用。原因有三：
- 无法预知执行时间——除非你用历史数据做预测，但预测总有误差
- 饥饿问题——需要配合老化，但老化又增加了复杂度
- 不适用于交互式系统——用户希望每次操作都能快速响应，而不是等一个长进程跑完
我个人的习惯是：在嵌入式系统中，如果任务集是固定的、已知的，可以用 SJF 做离线调度。但在通用操作系统中，我更倾向于使用多级反馈队列（MLFQ），它结合了 SJF 的效率和轮转法的公平性。
一个小技巧：如果你非要用 SJF，可以结合「执行时间预估」。比如用指数平均法：预估时间 = α × 上次实际时间 + (1-α) × 上次预估时间。α 通常取 0.5。这样能一定程度上缓解「不知道执行时间」的问题。
4.7 本章小结
SJF 的核心是「谁短谁先跑」，理论上平均等待时间最优。但实际中：
- 非抢占式适合批处理，但短进程可能被长进程阻塞
- 抢占式（SRTF）进一步降低平均等待时间，但上下文切换开销大
- 饥饿问题是最大隐患，必须用老化技术解决
- 现代系统中很少单独使用，更多是作为 MLFQ 等算法的组成部分
嗯，关于 SJF 就讲这么多。下一节咱们聊聊优先级调度——那个看似简单实则暗藏杀机的算法。