最短剩余时间与到达时抢占

一次次检查SCHED-16 ​

最初只有A，它从0运行到1，剩8。B在1到达，需要4，小于8，于是B抢占A。B刚运行1毫秒，C在2到达，需要2，小于B的剩3，C再抢占B。

每次只给真正运行者减剩余量。B在2到5虽然等了3毫秒，剩余仍为3，不是0；A从1等到8也仍剩8。

按A、B、C、D排列，完成时刻为 $(16,8,4,5)$，周转为 $(16,7,2,1)$，平均为6.5。首次派发时刻恰是各自到达时刻，所以四项响应都为0。A仍等了7毫秒：再次说明首次响应不等于总等待。

非抢占SJF理路FIFO与最短作业调度FIFO CPU scheduling · FCFS scheduling · Shortest job first · SJF · Shortest processing time用同一到达表比较FIFO与非抢占SJF，通过相邻交换证明同到达批作业的最短优先最优性，并给出晚到任务的边界。在同一到达表上平均周转为10。SRTF提前释放了C与D，却把A推迟到16。总服务仍为16，改进发生在完成次序。

为什么它能最小化这组条件下的平均周转 ​

先在有限个任务、整数到达时刻和整数服务量的模型中给出交换证明；允许每个整数边界抢占，切换免费。目标是最小化 $\sum C_i$。因为所有 $a_i$ 固定，这也等价于最小化 $\sum (C_i-a_i)$。

先消去有就绪任务时的空闲：把该任务以后的一单位服务搬到这一个空槽，不推迟其他任务，也不会使它更晚完成。对有限整数任务重复此操作，可以得到一个目标值不增的工作保守调度。

在这个调度中，找到它第一次没有选择SRTF所选任务的时刻 $t$。设SRTF选择X，原调度选择Y，且此时 $r_X\le r_Y$。两者在 $t$ 都已到达，因此以后专属于X或Y的运行槽，可以在这两项之间重新分配而不违反到达限制。

保留其他任务的所有运行槽。把原调度在 $t$ 之后分给X和Y的槽合在一起，先用这些槽完成X，再用剩下的槽完成Y。设原调度中两者第一次完成的时刻为 $u$，第二次为 $v$。在 $u$ 前，它至少为某一个任务提供了其全部剩余量；该量不小于 $r_X$，所以改排后X不晚于 $u$ 完成。两项总需求不变，Y在原最后一个槽结束时完成，即不晚于 $v$。

因此两者完成时间之和不增加，其他任务完成时刻不变，而且在时刻 $t$ 已经与SRTF一致。逐个修正后续第一个不同的槽，有限次后得到完整SRTF轨迹，总完成时间没有增加。零成本连续时间版本有对应的SRPT最优性定理，见Schrage原文；这里的有限槽证明足以覆盖本单元所有整数实例。

这份证明依赖“槽可以在两项间交换”：若X必须先等待I/O、运行需要重新热身，或者Y占着X需要的锁，替换就不再保持可行性。不能把这句话从模型中删掉，只留下一个无条件的“最优”。

有限批次最终完成，不等于永不饥饿 ​

有限批次的总服务有限，工作保守的单位速率调度最终会做完；SCHED-16里的A只是等得较久，不是永远得不到服务。

现在改成无限到达流。长任务L在0到达，需要100；每个整数时刻 $k=0,1,2,\dots$ 都到达一个需要1毫秒的短任务 $J_k$。SRTF始终执行刚到的短任务，下一个短任务恰在上一个结束时到达，L永远没有开始。系统一直完成工作，L却饥饿理路饥饿与公平性Starvation and fairness · 调度公平性 · 无饥饿用调度与服务选择的公平假设刻画持续请求者是否可能永久得不到完成机会。。

这个反例没有违反刚才的有限批次定理：任务集和目标总和的条件已经变了。也不应把无限负载反例夸大成“有限队列里SRTF会永不完成”。讨论公平时必须说清输入是否可以持续增长，以及是否对到达负载施加限制。

切换不免费时，要重新做选择题 ​

设A已经运行，还剩0.6毫秒；B现在到达，需要0.5毫秒。若忽略切换成本，先做B会使两项相对当前的完成时间为0.5和1.1，总和1.6；继续A则为0.6和1.1，总和1.7，前者略好。

但若每次不同任务交接需要0.2毫秒，继续A后切到B，完成时间为0.6与1.3，总和1.9。抢占去B、再切回A，完成时间为0.7与1.5，总和2.2。免费模型的小收益被额外交接吃掉，立刻抢占反而更差。

这不是实际时长预测误差，而是目标成本里漏掉了切换。可以设置抢占收益阈值或采用其他策略，但要重新说明规则与保证。

实现与可复算检查 ​

用最小优先队列理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。保存等待者，键为剩余服务；当前任务在队列外运行。到达事件先结算它本段的服务，再比较新最小值；若切换，把当前剩余记录重新插入。二叉堆每次插入或取最小可用 $O(\log n)$ 时间，事件表排序成本另计。

检查一条SRTF时间线时，只要在每个到达、完成边界写下全部剩余量，就能找到违反选择规则的第一步。最终还要核对每项服务恰为需求，并用周转与等待理路周转、响应与CPU利用率CPU scheduling metrics · Turnaround time · Scheduling response time · CPU utilization从同一执行轨迹分别计算完成、首次派发、就绪等待与整机吞吐，说明平均值、尾部与忙碌口径不能互相替代。读出结果。只有一张完成时间表，无法单独证明中间真的按SRTF执行过。