SJF算法即最短作业优先调度算法(Shortest Job First),又称最短作业优先、短作业优先,是一种按作业或进程所需运行时间安排执行次序的调度策略,每次从就绪队列中选取预计运行时间最短者投入运行[1]。它是操作系统作业调度与进程调度的经典算法,在作业同时到达时可使平均等待时间与平均周转时间最小[2]。SJF有非抢占式与抢占式两种形式,后者称最短剩余时间优先;由于需要预先知道作业长度,并可能使长作业长期得不到调度,它常被用作衡量其他调度算法的参照[3]。
定义
最短作业优先调度算法以作业或进程要求的处理器运行时间为排序依据,调度时总是挑选预计计算时间最短的作业投入运行,而不考虑它们进入系统的先后顺序[4]。这里的作业既可以是批处理系统中外存后备队列里的待处理任务,也可以是内存中就绪的进程,因此该算法同时适合作业调度和进程调度[5]。当若干作业的预计运行时间相同时,通常按照先来先服务的顺序处理[5]。
原理
设队列中第 i 个作业需要的处理时间为 $s_i$,把这些作业按 $s_1 \leq s_2 \leq \cdots \leq s_n$ 的次序排列后依次执行,该组作业的总完成时间、平均完成时间、平均等待时间以及平均周转时间都取到最小值[2][6]。其道理在于,把短作业移到长作业之前,短作业等待时间的减少量大于长作业等待时间的增加量,平均值因而下降[7]。这种最优性以所有作业同时就绪为前提,若各作业到达时间不同,结论不再严格成立[8]。
从优先级的角度看,SJF属于优先级调度的一种特殊情形:进程的优先级由它完成下一段处理器执行所需的时间决定,所需时间越短,优先级越高[9][6]。
非抢占式版本中,进程一旦获得处理器就会一直运行到结束或主动让出;抢占式版本则会在新进程到达、且其所需时间短于当前进程剩余时间时切换执行对象,因此也称最短剩余时间优先[8]。
算法实现的关键是估计进程下一段处理器执行时间,常用指数平均法:$T_{n+1} = \alpha T_n + (1-\alpha) t_n$,其中 $t_n$ 为最近一次实际执行时间,$0 \leq \alpha \leq 1$ 用于调节历史估计与新观测值所占的权重[2]。
发展历程
最短作业优先的思想源头在运筹学与排队论。20世纪50年代中期,Cobham研究了等待队列中的优先级分配问题,Phipps等人把相关结论用于机器维修的排序,并指出现实中有些长作业不宜中途打断、而在某些情况下短作业出现后又应当优先处理[10]。
1960年,Codd在《多道程序设计》一文中讨论了让计算机自行安排待处理工作负载的调度算法,同一时期多道批处理系统的发展使作业调度成为必须解决的问题[11]。
1967年,Conway、Maxwell与Miller合著的《Theory of Scheduling》出版,书中整理并引用了以最短作业规则为代表的排序与调度研究成果[12]。
此后,SJF成为操作系统教材中的基本算法,并衍生出引入抢占机制的最短剩余时间优先等变体,以实现更小的平均周转时间[7]。
应用
在批处理系统中,SJF多用于作业调度:系统从外存后备队列中选出估计运行时间最短的作业,优先调入内存执行[5][8]。
针对交互式进程,由于进程何时阻塞难以预知,实践中采用最短进程优先的近似做法,即依据进程过去若干次处理器执行段的长短估计下一次执行所需时间,再据此决定调度顺序[9][1]。
在云计算的任务调度研究中,SJF与先来先服务、时间片轮转等算法被放在同一框架下比较,已有实验显示优先处理短任务可以获得更低的平均等待时间和周转时间[13]。
这种短者先做的排序思路也被用于计算机之外的场景,例如有专利把最短作业优先用作手术排程策略,按预计手术时间的长短安排患者顺序[14];在敏捷开发中则出现了加权最短作业优先,用延迟成本对任务加权以决定处理次序[1]。
局限
最直接的困难在于算法要求事先知道作业或进程将要运行多久,而这一信息在实际系统中很难准确获得,估计上的偏差会使调度结果偏离真正的短作业优先[4][7]。当运行时间由用户自行估计时,用户还可能有意缩短自己作业的估计值,进一步削弱算法的实际效果[3]。
只要有短作业不断进入,长作业就可能长期得不到处理器,出现饥饿现象,缓解办法之一是老化,即让等待时间越长的进程优先级逐渐提高[9][15]。有研究指出,SJF及其抢占版本虽把平均等待时间压到最低,但个别作业的最大等待时间可能变得很大,长作业被拖延的代价相当明显[16]。
非抢占式SJF缺少剥夺机制,不适合分时系统和交互式事务处理环境;它只按作业长短排序,不考虑紧迫程度,因而无法保证紧急作业得到及时处理[5][7][3]。
参见
参考资料
- Shortest+job+next . thefreedictionary.com [引用日期2026-09-29]
- Context switch overhead . cornell.edu [引用日期2026-09-29]
- 秒懂算法 | 调度算法-阿里云开发者社区 . aliyun.com [引用日期2026-09-29]
- 操作系统之低级调度算法 . aliyun.com [引用日期2026-09-29]
- 秒懂算法 | 调度算法-云社区-华为云 . huaweicloud.com [引用日期2026-09-29]
- 8a_Scheduler(PDF) . unibo.it [引用日期2026-09-29]
- sjf . baidu.com [引用日期2026-09-29]
- Shortest Job First (SJF) Scheduling in OS . guvi.in [引用日期2026-09-29]
- Operating Systems . nyu.edu [引用日期2026-09-29]
- Shortest Job First (SJF) . educative.io [引用日期2026-09-29]
- acm.org 上的网页 . acm.org [引用日期2026-09-29]
- Research Notes for Chapter \(14^{*}\) . dartmouth.edu [引用日期2026-09-29]
- ieee.org 上的网页 . ieee.org [引用日期2026-09-29]
- google.com 上的网页 . google.com [引用日期2026-09-29]
- A K-Factor CPU Scheduling Algorithm . ieee.org [引用日期2026-09-29]
- arxiv.org 上的网页 . arxiv.org [引用日期2026-09-29]
浏览次数：0 次
阅读量：0 次 · 阅读完成量：0 次
最近更新：2026-09-29T11:31:42Z
完成率 = 阅读完成量 ÷ 阅读量，分母是阅读量不是浏览次数 —— 关了 JS 的、秒退的都在浏览次数里、不在阅读量里。 详细口径在后台的「数据统计」页。