FIFO与最短作业调度

同时到达时，短任务确实可以先离开 ​

先把A、B、C、D都安排在0到达，服务需求仍为9、4、2、1。FIFO按任务名打破同时到达的并列，次序为A、B、C、D，完成时刻依次9、13、15、16，平均周转为 $53/4=13.25$。

SJF选择D、C、B、A，完成时刻依次1、3、7、16，平均周转为 $27/4=6.75$。最后一项仍在16完成；改进来自更多任务更早完成，而不是CPU做得更快。

一种看法是数“还没完成的任务”：FIFO最初9毫秒一直有4个未完成者；SJF在1毫秒后就只剩3个，在3毫秒后只剩2个。周转总和恰是这条未完成数量曲线下面积，所以更早清掉短任务会减少面积。

交换两个相邻任务，证明为什么该这样排 ​

固定一批同时到达、时长已知、无I/O、无切换成本的任务，目标最小化所有任务完成时间之和。考虑某个次序中相邻的X、Y，它们从时刻 $t$ 开始，长度分别为 $x>y$。

先X后Y时，两者完成时间之和为

交换成先Y后X，和变为

新次序减少 $x-y>0$。更早的任务未变；两项合计仍占 $x+y$ 时间，因此更晚的任务开始时间也未变。只要存在“长的在短的前面”这一相邻逆序，就可以改进；消除全部逆序后得到按长度非降排列的SJF。

因此SJF在这组条件下最小化总完成时间，也最小化平均周转和平均等待，因为到达时刻与总服务都是固定常数。等长任务交换不改变目标，最优次序不一定唯一。这个论证没有涉及首次派发响应的最大值，也没有给出每个人都更好的保证。

这里无需把“队列”设为定义前置：算法可以线性扫描剩余任务，也可以使用其他表示。队列是实现FIFO的工具；证明SJF最优的是交换不等式，二者承担不同工作。

恢复真实到达时间，再算一次 ​

回到SCHED-16：A在0到达，B在1，C在2，D在4。时刻0只有A，FIFO和SJF都必须让A开始；由于非抢占，两者都要等到9才重新选择。

FIFO此时队列是B、C、D，得到A:0–9、B:9–13、C:13–15、D:15–16。按A、B、C、D排列的周转为 $(9,12,13,12)$，均值11.5。

SJF在9看见三个READY任务，选择D，再C，再B：

这次周转为A:9、B:15、C:10、D:6，平均10。D改善了，B却比FIFO更晚完成；“平均更小”不等于每一项更小。

图中还放了抢占和轮转作为后续比较；先只看前两行，注意两行第一段完全相同。晚到的短任务没有能力穿过非抢占边界。

晚到任务为何破坏刚才的最优性证明 ​

取X在0到达、长度5，Y在1到达、长度1。工作保守的非抢占SJF在0只能启动X，得到X在5完成、Y在6完成，完成时间和11。

若允许离线计划主动等待，CPU可空闲0–1，先做Y到2，再做X到7，完成时间和9。这不是SJF漏选了一个已经READY的任务，而是另一种允许利用未来到达信息并主动空闲的策略。因此不能把“所有任务同时到达”的交换证明直接当成任意释放时间的非抢占最优性定理。

允许抢占后，最短剩余时间理路最短剩余时间与到达时抢占Shortest remaining time first · SRTF · Shortest remaining processing time · SRPT · Shortest time-to-completion first · STCF每次到达或完成时选择剩余CPU服务最少者，逐段复算抢占轨迹，并用交换论证和持续短作业反例界定最优性与饥饿。会在Y到达时暂停X，避免这段空闲，且能得到更小的周转。这是改变可行动作集合，不是把SJF的名字换一下。

成本、预测与其他目标 ​

一批 $n$ 个同时到达任务可先排序，比较排序需 $O(n\log n)$ 次比较，再线性派发。动态到达时，可用最小堆维护READY任务，入队和取最小各 $O(\log n)$；若任务很少，$O(n)$ 扫描也可能更简单。这里不把CPU实际做的 $\sum b_i$ 工作算进调度器的比较次数。

错误预测能直接翻转决策：X真实长度20但预测1，Y真实长度2但预测3，预测SJF会把X放在前面。实验应分别报告预测误差与政策成本，不能只把采用了“最短”标签当成优化证据。

若每项有权重 $w_i$、目标改为 $\sum w_i{C}_i$，交换条件变为 $x/w_X\le y/w_Y$，不再仅比较长度。若目标是截止期或隔离份额，规则还会再变。本页的结论应随着它的目标函数一起使用。