调度、队头阻塞与公平性

等待不仅由流量和服务时长决定，还由“下一个服务谁”决定。调度优化的是一组目标：平均响应、尾部、公平、截止时间与完成工作量，不能只挑一个总体均值判断好坏。

用有限批次看见队头阻塞

五个任务在 0 s 同时到达，服务时间为 $[8,1,1,1,1]$ s，以编号打破 FIFO 的同刻平局。单台、无抢占、无切换开销。FIFO 完成时间为 $[8,9,10,11,12]$，平均系统时间 10 s；短任务优先（SJF）按 $[1,1,1,1,8]$ 执行，完成时间为 $[1,2,3,4,12]$，均值 4.4 s。

总服务量都是 12 s。改善平均值并没有提高处理能力，而是把短任务更早移出系统；长任务等待从 0 变成 4 s。

先切换顺序，观察每个任务的灰色等待条和有色服务条，再增加长任务大小。所有任务都在 0 s 到达，因此每条从原点到完成的长度就是系统时间。比较时任务编号保持身份，位置只表示执行顺序。

为什么短任务优先能降低这个批次的均值

设相邻任务服务长度为 $x>y$，前面已执行时间为 $t$。先 $x$ 后 $y$ 的两个完成时间之和为 $2t+2x+y$；交换后为 $2t+2y+x$，减少 $x-y$。后续任务开始时刻不变。反复消除逆序，即得同刻可用、大小已知、单台无抢占批次的最短处理时间顺序最小化平均完成时间。

这是一个带条件的交换论证。任务在线到达、服务大小未知、存在释放时间或切换费用时，需要重新选择策略，不能把批次证明原样推广。

从 SJF 到公平性

FCFS 按到达先后分配；SJF 选择已就绪任务中预计最短者；SRPT 允许抢占，选择剩余时间最短者。理想单台、准确知道大小且无抢占开销时，SRPT 对平均响应有强结论，但真实系统需要估计大小，且抢占可能造成缓存、事务与资源恢复成本。

度量 slowdown $T_i/S_i$ 可以看见短任务承受的相对损失。本批次 FIFO 的短任务最多 slowdown 为 12；SJF 最大为 4。有限批次终会完成，不能据此证明长期公平。若短任务不断到来，低优先级长任务可能长期等待。

优先级老化、按租户保留份额、加权公平队列和分离批处理，都能改变谁承担拥塞。应同时报告分请求类型、分租户的等待、最老未完成年龄、截止违约和服务份额。整体 p99 也可能掩盖占比低于 1% 的受损群体。

队头阻塞不止出现在一个列表

一个分区要求保序，慢任务可能阻挡该分区后续任务；共享线程池则可能让批处理占满所有工作者。拆分队列能隔离影响，但也可能失去池化收益。优先处理新数据适用于可过期更新，未必适用于必须最终执行的订单或账务操作。

自检

1. SJF 把本批次平均响应从 10 s 降到 4.4 s，是否意味着吞吐翻倍？

2. 只观察已完成任务的 p99，能发现优先级饥饿吗？

延伸

CMU 的 SRPT 研究将调度作为资源分配核心问题。AWS 积压处理原文讨论隔离与新旧工作分流；其适用性取决于工作能否过期及最终完成要求。消息保序与消费并行参见消费组与协作。