SJF 短作业优先调度

2026 大纲 二（二）4 CPU 调度算法的 SJF（短作业优先）及其抢占式变体 SRTF（最短剩余时间优先）。指标口径与算例数据沿用 调度的基本概念与目标。

交互可视化

加载可视化中...

长作业堵住短作业，那就先跑短的

FCFS 的病根很清楚：护航效应——一个长作业排在前面，后面一串短作业全被堵住。

修法看起来很直接：别按到达顺序排，按作业长短排，短的先跑。 这就是 SJF。

它确实有效，而且效果不是"差不多好一点"——可以证明它在平均等待时间上是最优的。 论证很短：把相邻的两个交换一下，总等待时间的变化量恰好是"后者服务时间 − 前者服务时间"； 只要后面那个更短，交换就一定更优。反复交换的终点，就是按服务时间升序排列。

⚠️ 但这个最优性有个前提：所有进程同时到达。到达时刻不同时， 非抢占的 SJF 就不再最优了——它的抢占版 SRTF（比较剩余时间）才是。

而 SRTF 之所以能抢占，正好印证了上一节那条通用判据： 运行者的剩余时间只减、等待者的键不变，两者差距越拉越大， 所以抢占检查只需要在新进程到达的那一刻做一次——这直接决定了做题时的动作。

代价也很明确，而且是两笔。第一笔是饥饿：只要短作业源源不断，长作业就永远排不上。 第二笔更根本——它要求预知服务时间，而这在真实系统里根本做不到， 只能靠历史数据做指数加权移动平均去猜，而猜就意味着可能猜错。

一、SJF 与 SRTF 的分界

变体	名称	比较键	抢占性
SJF	短作业优先	进程的总服务时间	非抢占式
SRTF	最短剩余时间优先（Shortest Remaining Time First）	进程的剩余服务时间	抢占式

剩余时间会随运行而减小，所以 SRTF 每次比较的对象都在变，抢占才有意义。而抢占检查只需在新进程到达时做一次——推导是：运行者的剩余时间只减、等待者的键不变，两者差距只会越拉越大，中途不可能出现超越，所以只有新进程进来时才可能改变胜负。这条直接决定了做题时的动作。

二、最优性：为什么"短的先做"能压低平均等待时间

结论：只要执行序列里还存在"长在前、短在后"的相邻对，当前顺序就不是最优的；反复交换直到不存在这样的相邻对，序列就是按服务时间升序排列的——这正是 SJF。

这条结论有一个两行的严格论证（相邻交换论证），也解释了"同时到达"这个前提为什么不能漏：论证假设"排在后面的进程随时可换到前面"，而进程未到达时根本换不上来。

相邻交换论证的完整推导，以及用算例数据的逐步验证（想弄清最优性为什么成立、前提从哪来时展开）

设所有进程同时到达，某个执行顺序里相邻的两个进程为 $X$（服务时间 $a$）和 $Y$（服务时间 $b$），$X$ 在前。设排在它俩之前的所有进程总服务时间为 $P$。

• 交换前：$X$ 等待 $P$，$Y$ 等待 $P+a$，两者等待之和 $=2P+a$
• 交换后：$Y$ 等待 $P$，$X$ 等待 $P+b$，两者等待之和 $=2P+b$

排在它俩之后的所有进程不受影响——因为无论谁先谁后，这两个进程执行完的时刻都是 $P+a+b$。

所以交换带来的总等待时间变化量是 $b-a$。若 $b<a$（后面那个更短），交换后总等待时间严格减少。

用算例数据验证（把四个进程都改成 t=0 同时到达，服务时间 7、4、1、4）：

• FCFS 顺序 P1→P2→P3→P4：总等待 $0+7+11+12=30$
• 交换开头相邻的一对（P1 长、P2 短）得 P2→P1→P3→P4：总等待 $0+4+11+12=27$，减少了 $7-4=3$，与 $a-b=3$ 吻合
• 一直交换到升序 P3→P2→P4→P1（1、4、4、7）：总等待 $0+1+5+9=15$，是 24 种排列中的最小值

三、无法预知服务时间怎么办：指数加权移动平均

SJF 有一个无法回避的问题：要比较服务时间，就得先知道服务时间，而实际系统事先并不知道一个进程要跑多久。标准解法是用历史行为预测未来：

$${\tau }_{n+1}=\alpha \cdot t_n+(1-\alpha )\cdot {\tau }_n$$

符号	含义
$t_n$	第 $n$ 次实际占用 CPU 的时长（已发生，可测量）
${\tau }_n$	对第 $n$ 次时长的预测值
${\tau }_{n+1}$	对下一次时长的预测值，即调度时拿来比较的那个数
$\alpha \in [0,1]$	权重，决定"最近一次实测"与"历史积累"谁说了算

把递推式展开一次就能看清它在干什么：

$${\tau }_{n+1}=\alpha t_n+(1-\alpha )\alpha t_{n-1}+(1-\alpha {)}^2\alpha t_{n-2}+\cdots +(1-\alpha {)}^n{\tau }_1$$

每往前推一次权重就乘一个 $(1-\alpha )<1$——越久远的历史权重按指数衰减。它既用上了全部历史，又只需保留一个 $\tau$ 值即可递推，这是它能进内核的关键。

$\alpha$ 的两个边界：$\alpha =0$ 时 ${\tau }_{n+1}={\tau }_n$，完全不看实测、等于放弃预测；$\alpha =1$ 时 ${\tau }_{n+1}=t_n$，只看最近一次、对波动极其敏感。常取 $\alpha =1/2$。

什么时候不适用：这个公式假设进程行为有惯性。对于行为模式突变的进程——比如一个交互程序突然开始做大批量计算——预测值会在相当一段时间里持续偏低，SJF 会误把它当短作业反复优先调度。这也是实际系统更倾向 多级反馈队列 的原因：它不预测，而是看进程实际跑了几个时间片再降级，用事后行为代替事前预测。

预测器跑七轮的实际形态：它抗噪声，但对真实趋势的跟随有滞后（想看 α 的取舍落到数字上时展开）

取 ${\tau }_1=10$、$\alpha =1/2$：

第 n 次	实测 $t_n$	预测下一次 ${\tau }_{n+1}=\frac{1}{2}{t}_n+\frac{1}{2}{\tau }_n$
1	6	0.5×6 + 0.5×10 = 8
2	4	0.5×4 + 0.5×8 = 6
3	6	0.5×6 + 0.5×6 = 6
4	4	0.5×4 + 0.5×6 = 5
5	13	0.5×13 + 0.5×5 = 9
6	13	0.5×13 + 0.5×9 = 11
7	13	0.5×13 + 0.5×11 = 12

前四次实测在 4～6 之间波动，预测值稳稳收在 5～6；第 5 次突然跳到 13，预测值不会立刻跟上（只到 9），而是用几次的时间逐步逼近。若把 $\alpha$ 调大，跟随快了，但一次异常抖动也会立刻污染预测。

四、缺点

缺点	说明	判据
可能饥饿	长作业可能永远得不到执行	排在它前面的进程数可以无限增长（不断有更短的作业到达）
无法预知服务时间	只能靠预测，预测就有误差	见上一节；估计过低还可能被系统按时终止
对长作业不公平	完全忽视等待时间	一个已等了很久的长作业，其等待时间在比较中权重为 0
不能保证紧迫性	完全不看紧迫程度	紧急但耗时长的任务会被一直推后

第三条正是 HRRN 要修补的：把等待时间重新加回比较键里。

同一组数据跑 SJF 与 SRTF：两张甘特图与三算法横向对比（想核对做题步骤、或看抢占把哪个指标改了时展开）

进程	到达时间	服务时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

非抢占 SJF。 t=0 时只有 P1 到达，别无选择，且非抢占意味着这个决定不再更改，P1 跑满 7 个单位。t=7 时 P2/P3/P4 均已到达，比较服务时间 4、1、4，选 P3。t=8 时 P2 与 P4 都是 4，按"相等时先到者先跑"选 P2。

时间区间	0–7	7–8	8–12	12–16
执行进程	P1	P3	P2	P4

进程	完成时间	周转时间	带权周转时间	等待时间	响应时间
P1	7	7	7/7 = 1.00	0	0
P3	8	4	4/1 = 4.00	3	3
P2	12	10	10/4 = 2.50	6	6
P4	16	11	11/4 = 2.75	7	7
平均		8.00	2.56	4.00	4.00

抢占 SRTF。 只在 t=2、4、5 三个到达时刻各比较一次：

时刻	事件	当前运行者剩余	新到者服务时间	判断
t=0	P1 到达	—	P1: 7	只有它，执行 P1
t=2	P2 到达	P1 剩 5	P2: 4	4 < 5，抢占，执行 P2
t=4	P3 到达	P2 剩 2	P3: 1	1 < 2，抢占，执行 P3
t=5	P3 完成且 P4 到达	—	就绪：P2 剩 2、P4 剩 4、P1 剩 5	选最小者 P2
t=7	P2 完成	—	就绪：P4 剩 4、P1 剩 5	选 P4
t=11	P4 完成	—	只剩 P1	执行 P1 至 16

时间区间	0–2	2–4	4–5	5–7	7–11	11–16
执行进程	P1	P2	P3	P2	P4	P1

进程	完成时间	周转时间	带权周转时间	等待时间（周转−服务）	响应时间
P1	16	16	16/7 ≈ 2.29	9	0
P2	7	5	5/4 = 1.25	1	0
P3	5	1	1/1 = 1.00	0	0
P4	11	6	6/4 = 1.50	2	2
平均		7.00	1.51	3.00	0.50

注意 P1 这一行：它的响应时间是 0（t=0 就上了 CPU），等待时间却是 9。抢占式下这两个数必然分开，等待时间只能用「周转 − 服务」算。

算法	平均周转	平均带权周转	平均等待	平均响应
FCFS	8.75	3.50	4.75	4.75
SJF（非抢占）	8.00	2.56	4.00	4.00
SRTF（抢占）	7.00	1.51	3.00	0.50

SJF 相对 FCFS 的降幅在带权周转上大得多（3.50 → 2.56），因为它优先照顾的正是"服务时间小、最怕等"的那类进程。SJF 的平均周转 8.00 而 SRTF 还能压到 7.00，这也是"非抢占 SJF 需要同时到达才最优"的反例。

考点速记

1. SJF 从已到达的进程中选总服务时间最短者（非抢占）；SRTF 比较剩余时间（抢占）。
2. ⚠️SRTF 的抢占只发生在新进程到达的时刻——运行者的键（剩余时间）只减、等待者的键不变，两者差距越拉越大，中途不可能出现超越。这直接决定了做题时只需在每个到达时刻检查一次。
3. 相邻交换论证给出最优性：交换相邻一对的总等待变化量是"后者服务时间 − 前者服务时间"，反复交换的终点就是按服务时间升序。
4. ⚠️非抢占 SJF 的最优性以"所有进程同时到达"为前提；到达时刻不同时，SRTF 才是最优的。
5. 四条缺点：可能饥饿（短作业源源不断则长作业永远排不上）、无法预知服务时间、对长作业不公平、不能保证紧迫任务及时处理。
6. 服务时间未知时用指数加权移动平均预测（历史权重指数衰减，只需保留一个 $\tau$ 值），代价是抗噪声但跟随滞后。

这一节在真题里被考过的形式：

只出过一道题，而且是与 FCFS 对照着考的。

• 给四个作业的到达时刻与运行时间，比较 FCFS 与 SJF 的平均周转时间（2017-23，与 FCFS 共享）。⚠️ 唯一的坑是"已到达"这个前提——SJF 挑的是当前已经到达且未完成的作业里最短的那个，不能挑一个还没来的，哪怕它更短。做法：按时刻往前推，每次 CPU 空出来时先圈出此刻已到达的集合，再在集合里挑。
• 另外，SJF 与 SRTF 是"哪些算法会饥饿"这类判断题的固定素材（2014-23 在调度的基本概念讲），答案是两个都会。

复习优先级：必须会手算，且要分清 SJF 与 SRTF。 第二条（抢占只在新进程到达时检查） 是 SRTF 手算的全部技巧；第四条（最优性的前提）是概念题的落点。 指数加权移动平均至今没考过计算，理解它"为什么抗噪但滞后"即可。

易错：SJF 手算时挑了一个还没到达的更短作业。只能在已到达的集合里挑。

易错：认为非抢占 SJF 在任何情况下平均等待时间最优。前提是所有进程同时到达；否则要用 SRTF。

易错：SRTF 手算时在每个时刻都做抢占检查。只需在新进程到达的时刻检查——其余时刻不可能发生超越。

易错：认为 SJF 不会饥饿。会——短作业源源不断时长作业永远排不上。

易错：把 SJF 比较的键说成剩余时间。SJF 比总服务时间，SRTF 才比剩余时间。

教材出处

• 汤小丹《计算机操作系统》3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法（SJF 以作业长短定优先级；四条缺点：必须预知运行时间、对长作业不利且可能饥饿、无法人机交互、未考虑紧迫程度），印刷 p90

相关知识

调度的基本概念与目标｜FCFS 先来先服务调度｜时间片轮转调度｜高响应比优先调度｜多级反馈队列调度

真题练习

相关真题（12题）

2025Q252分2024Q302分2021Q252分2020Q262分2019Q272分2017Q232分2016Q466分2014Q232分2013Q312分2011Q232分2010Q262分2009Q242分

上一篇FCFS 先来先服务调度下一篇时间片轮转调度

相关文章

• 进程基本概念
• 进程状态与转换
• 线程（内核级与用户级）
• 进程的组织与控制
• 进程间通信
• 调度的基本概念与目标
• FCFS 先来先服务调度
• 时间片轮转调度
• 优先级调度
• 高响应比优先调度
• 多级队列调度
• 多级反馈队列调度
• 公平调度算法
• 调度算法对比模拟器
• 多处理机调度
• 上下文切换机制
• 上下文切换模拟器
• 同步与互斥基本概念
• 同步互斥实现方法
• 锁
• 信号量
• 条件变量
• 生产者-消费者问题
• 读者-写者问题
• 哲学家进餐问题
• 死锁的概念与预防
• 银行家算法
• 死锁检测与解除