01先把问题说具体
若几项工作都在等 CPU,先做短任务为何常能减少平均等待?新任务到来后又该如何处理?
02一步步得到方法
选择范围只能是已经到达的任务
SJF 每次 CPU 空闲时,从当前就绪集合选择预计运行时间最短者,本课采用非抢占版本。正在运行的长任务不会因短任务到来而立刻停止;可抢占的对应策略通常称为最短剩余时间优先。
真实操作系统往往不知道下一个 CPU burst 的精确长度,可能根据历史估计。本例把时长作为已知输入,是分析模型,而不是宣称系统能够预知未来。
同时到达时的交换论证
若两个相邻任务时长 a>b,却先执行 a,那么这两项对等待和的额外贡献为 a;交换后变为 b,减少 a−b,且它们之后任务的开始时间不变。
不断消除这样的逆序,得到短任务在前的顺序。因此所有任务同时到达、时长已知、无抢占等条件下,SJF 最小化平均等待。到达时间不同或允许主动空闲时,需要重新界定最优问题,不能机械套用结论。
代价是长任务可能久等
短任务持续到来时,长任务可能不断被推迟,称为饥饿风险。可以通过老化、时间片或多级反馈等机制调整公平性。
下面使用就绪最小堆和按到达时间排序的待到达列表。堆元素以时长为主键,以到达和输入顺序打破平局,使结果可复现。
03把一个小例子完全算清楚
同时到达:A 时长8,B 时长1,C 时长2。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 先 B | 0→1,等待0 | 当前最短 |
| 再 C | 1→3,等待1 | 剩余最短 |
| 最后 A | 3→11,等待3 | 平均等待 4/3 |
窄屏可左右滑动表格,阅读完整计算与理由。
FCFS 顺序 A、B、C 的平均等待为 17/3;本例 SJF 降为 4/3。
04为什么这个方法成立
- 排序列表只把 arrival≤当前时间的任务送入就绪堆,因此不会选择未来任务。
- 堆顶是当前就绪任务中时长最小的任务,符合非抢占 SJF 的决策规则。
- 同时到达情形的最优性由相邻交换论证得到;一般到达情形的代码只声称实现此规则。
05把推导翻译成代码
Python · 可独立运行的教学实现
from heapq import heappush,heappop
def sjf(jobs):
if any(a<0 or d<=0 for _,a,d in jobs):
raise ValueError("invalid job")
pending = sorted(enumerate(jobs),key=lambda item:item[1][1])
ready,result = [],[]
time = index = 0
while index<len(pending) or ready:
if not ready:
time = max(time,pending[index][1][1])
while index<len(pending) and pending[index][1][1]<=time:
order,(name,arrival,duration) = pending[index]
heappush(ready,(duration,arrival,order,name))
index += 1
duration,arrival,order,name = heappop(ready)
start = time
time += duration
result.append((name,start,time,start-arrival))
return result
print(sjf([("A",0,8),("B",0,1),("C",0,2)]))逐个理解关键决定
pending[index][1][1]<=time- 在每次决策前加入运行期间新到达的任务。
(duration,arrival,order,name)- 用时长作为主排序键,并明确平局顺序。
time += duration- 一次执行到完成,当前实现没有抢占。
06时间、空间与实现范围
每个任务入堆出堆各一次,总时间 O(n log n),空间 O(n)。
若 burst 时长需要预测,预测开销与误差属于额外系统问题,不包含在离线调度模拟中。
07改变条件,检查哪里会出错
短任务到达就立即切走
那是抢占式策略,不是本课非抢占 SJF。
所有工作负载下平均等待全局最优
最优性结论依赖同时到达、时长已知等条件。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
A 在0到达且时长10,B在1到达且时长1,非抢占 SJF 先运行谁?
需要一点提示
时刻0只有A可用。
查看解析与答案
A 先运行到10,B 再运行到11。
为什么交换 a>b 的相邻任务不改变后续开始时刻?
需要一点提示
两项总运行时间没变。
查看解析与答案
它们合计仍为 a+b,仅交换两项内部的等待分配。
怎样缓解长任务饥饿?
需要一点提示
让等待本身影响选择。
查看解析与答案
可以使用老化提高等待久任务的优先程度,或配合时间片等策略。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Arpaci-Dusseau · Operating Systems: Three Easy Pieces