专题进阶 · 操作系统算法推荐总顺序 · 第 142 / 148 课

在当前就绪任务中选择最短任务,用交换论证理解平均等待最优结论的条件。

先学会这些,再进入本课 先来先服务 堆
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

最短作业优先SJF

优先执行预估运行时间短的任务,需要知道或预测时长,也可能让长任务饥饿。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

在当前就绪任务中选择最短任务,用交换论证理解平均等待最优结论的条件。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

若几项工作都在等 CPU,先做短任务为何常能减少平均等待?新任务到来后又该如何处理?

02一步步得到方法

选择范围只能是已经到达的任务

SJF 每次 CPU 空闲时,从当前就绪集合选择预计运行时间最短者,本课采用非抢占版本。正在运行的长任务不会因短任务到来而立刻停止;可抢占的对应策略通常称为最短剩余时间优先。

真实操作系统往往不知道下一个 CPU burst 的精确长度,可能根据历史估计。本例把时长作为已知输入,是分析模型,而不是宣称系统能够预知未来。

同时到达时的交换论证

若两个相邻任务时长 a>b,却先执行 a,那么这两项对等待和的额外贡献为 a;交换后变为 b,减少 a−b,且它们之后任务的开始时间不变。

不断消除这样的逆序,得到短任务在前的顺序。因此所有任务同时到达、时长已知、无抢占等条件下,SJF 最小化平均等待。到达时间不同或允许主动空闲时,需要重新界定最优问题,不能机械套用结论。

代价是长任务可能久等

短任务持续到来时,长任务可能不断被推迟,称为饥饿风险。可以通过老化、时间片或多级反馈等机制调整公平性。

下面使用就绪最小堆和按到达时间排序的待到达列表。堆元素以时长为主键,以到达和输入顺序打破平局,使结果可复现。

03把一个小例子完全算清楚

同时到达:A 时长8,B 时长1,C 时长2。

步骤计算与状态为什么这样做
先 B0→1,等待0当前最短
再 C1→3,等待1剩余最短
最后 A3→11,等待3平均等待 4/3

窄屏可左右滑动表格,阅读完整计算与理由。

FCFS 顺序 A、B、C 的平均等待为 17/3;本例 SJF 降为 4/3。

04为什么这个方法成立

  1. 排序列表只把 arrival≤当前时间的任务送入就绪堆,因此不会选择未来任务。
  2. 堆顶是当前就绪任务中时长最小的任务,符合非抢占 SJF 的决策规则。
  3. 同时到达情形的最优性由相邻交换论证得到;一般到达情形的代码只声称实现此规则。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

A 在0到达且时长10,B在1到达且时长1,非抢占 SJF 先运行谁?

需要一点提示

时刻0只有A可用。

查看解析与答案

A 先运行到10,B 再运行到11。

练习 2 · 边界与辨析

为什么交换 a>b 的相邻任务不改变后续开始时刻?

需要一点提示

两项总运行时间没变。

查看解析与答案

它们合计仍为 a+b,仅交换两项内部的等待分配。

练习 3 · 变式与迁移

怎样缓解长任务饥饿?

需要一点提示

让等待本身影响选择。

查看解析与答案

可以使用老化提高等待久任务的优先程度,或配合时间片等策略。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。