处理器调度

到达时间与调度指标

调度器从就绪任务中选择下一项工作，并决定当前任务何时让出处理器。不同应用关注的指标不同：交互程序重视首次响应，批处理作业重视完成时间，实时任务还需要满足截止期限。比较调度策略之前，必须先固定任务集合、到达时间、服务需求和抢占规则，否则平均值之间没有一致的含义。

设任务 $i$ 的到达时间为 $a_i$，首次运行时间为 $s_i$，完成时间为 $c_i$，处理器服务需求为 $b_i$，单位均为毫秒。周转时间记录任务进入系统至完成的整个间隔，响应时间记录第一次获得处理器前的等待。只含一个处理器执行段、没有输入输出阻塞时，等待时间等于周转时间减去服务需求：

$T_i=c_i-a_i,\qquad R_i=s_i-a_i,\qquad W_i=T_i-b_i.$

抢占调度

抢占调度允许内核在任务主动阻塞或退出之前收回处理器，并把任务放回就绪队列。时钟中断提供触发机会，调度策略决定是否发生切换。非抢占策略通常让当前执行段运行至完成或主动等待事件。

响应时间与周转时间可能指向不同选择。让短任务优先通常降低平均周转时间，但长任务在短任务持续到达时可能长期等待。轮转调度提高初次获得服务的机会，同时增加切换成本。除了均值，我们还应查看最大等待时间或高分位响应时间，防止少数任务的长期等待被平均值掩盖。

先到先服务与短任务优先

先到先服务按到达顺序执行，结构简单，服务次序容易解释。它的主要代价来自较长任务阻挡后面的短任务。在所有任务同时到达、运行时长已知、无输入输出和切换开销的模型中，把短任务放在长任务前面能够降低平均周转时间。

这个结论可以用交换相邻任务说明。设相邻两项服务需求满足 $x>y$，它们开始前已经经过时间 $t$。先运行长任务时，两项完成时间之和为 $(t+x)+(t+x+y)=2t+2x+y$。交换后变为 $(t+y)+(t+y+x)=2t+2y+x$，减少 $x-y$。对所有逆序对重复交换就得到按时长递增的顺序，证明依赖同时到达和时长已知等条件。

三项任务的周转时间

任务甲、乙、丙在零时刻同时到达，服务需求分别为八、四、一毫秒。先到先服务固定按甲、乙、丙排序，完成时间为八、十二、十三毫秒，平均周转时间为 $33/3=11$ 毫秒，等待时间为零、八、十二毫秒。

短任务优先按丙、乙、甲执行，完成时间分别为一、五、十三毫秒。映射回甲、乙、丙后，周转时间为十三、五、一毫秒，平均为 $19/3\approx6.33$ 毫秒；等待时间为五、一、零毫秒，平均为两毫秒。我们核对总执行区间仍是十三毫秒，策略改变了完成次序，没有改变这组任务的总服务需求。

真实系统通常事先不知道任务的剩余执行时长。依据历史处理器执行段预测时长，只能提供估计。新任务到达、输入输出阻塞和多核共享缓存还会改变模型，因此上述最优性结论不能直接扩大为所有负载下的性能保证。OSTEP 的 CPU Scheduling 一章按这些假设逐步比较策略，阅读时应保留每一项模型条件。

时间片轮转

轮转调度维护就绪队列，每次给队首任务至多一个时间片。若任务提前完成或阻塞，它立即离开运行位置；若时间片耗尽但仍可运行，则移到队尾。时间片较小能缩短轮到下一项任务的等待，时间片较大能减少切换占比。新任务进入队列的位置和边界时刻的事件处理顺序也需要明确。

两毫秒时间片的执行次序

仍用服务需求八、四、一毫秒的甲、乙、丙，三者同时到达，初始队列按甲、乙、丙排列，时间片为两毫秒，忽略切换成本。运行区间依次为：甲零至二，乙二至四，丙四至五，甲五至七，乙七至九，甲九至十一，甲十一至十三。

丙在第五毫秒完成，乙在第九毫秒完成，甲在第十三毫秒完成。响应时间为零、二、四毫秒，平均两毫秒；周转时间为十三、九、五毫秒，平均九毫秒。等待时间分别为五、五、四毫秒，平均 $14/3$ 毫秒。剩余时间逐次减去实际执行长度，三项任务最终都减到零，这是检查时间线遗漏或重复执行的直接方法。

设每次处理器在不同任务间切换需要 $h$ 毫秒，任务通常用完整个 $q$ 毫秒时间片。在这种连续切换的近似模型中，服务时间占比为

$\eta=\frac{q}{q+h}.$

例如 $q=4$ 毫秒、$h=0.2$ 毫秒时，比例约为 $95.24\%$。这只是处理器服务时间比例，没有包含缓存恢复、设备等待和其他内核工作，也没有说明用户感知的响应质量。最后只剩一项任务时，调度器可能继续运行同一项任务，不能机械地为每个时间片边界计入一次完整切换。

优先级与反馈队列

静态优先级按照事先给定的级别选择任务，能够表达业务或系统重要性。如果高优先级任务持续占满处理器，低优先级任务可能饥饿。老化机制按等待时间逐步提高优先级，以改善长期等待；这也会改变严格优先级关系，使部分原本优先级较高的任务延后运行。

多级反馈队列根据任务近期行为调整级别与时间片。短暂运行后等待输入的任务通常需要快速响应，持续消耗处理器的任务则逐渐进入较长时间片队列。实现中必须记录累计消耗，否则任务可能在时间片结束前主动让出处理器，反复维持高优先级。周期性提升等待任务、对同级队列采用公平轮转，都是控制饥饿的常见办法。

优先级倒置与单纯的饥饿不同：高优先级任务等待低优先级任务持有的锁，中优先级任务又使锁持有者迟迟得不到执行。优先级继承临时提高锁持有者的调度优先级，使其有机会完成临界区并释放锁。它要求锁与调度机制配合，不能仅靠调整队列顺序解决任意资源等待。

多核调度中的负载与亲和性

多核系统可以让多个任务同时运行，但任务之间仍会竞争缓存、内存带宽与共享锁。把任务搬到较空闲的核心有助于平衡队列，却可能丢失原核心中的缓存局部性。处理器亲和性限制或偏好任务运行的位置，负载均衡则尝试避免某些核心繁忙、另一些核心空闲。

比较多核策略时，应明确吞吐量是单位时间内完成的任务数，还是完成的数据量，并固定输入规模、并行度和硬件配置。我们还要观察任务迁移次数与等待原因。若瓶颈已经位于共享锁或内存带宽，增加执行线程未必缩短运行时间；如果某些任务长期等待设备，单看就绪队列长度也不足以估计系统负载。

调度时间线练习

练习标记完成

所属知识

指标计算

难度

2/5

一个任务在第三毫秒到达，第五毫秒首次运行，第十七毫秒完成，共需要六毫秒处理器时间，且没有输入输出等待。求三个时间指标。

查看解答

周转时间为 $17-3=14$ 毫秒，响应时间为 $5-3=2$ 毫秒。按单执行段且无阻塞的假设，等待时间为 $14-6=8$ 毫秒。

练习标记完成

所属知识

短任务优先

难度

2/5

三项任务同时到达，服务需求分别为七、二、三毫秒。忽略切换成本，求短任务优先的顺序、平均周转时间和平均等待时间。

查看解答

按 2、3、7 毫秒执行，完成时间为 2、5、12 毫秒，平均周转时间为 19/3 毫秒。等待时间为 0、2、5 毫秒，平均为 7/3 毫秒。

练习标记完成

所属知识

切换开销

难度

2/5

时间片为一毫秒，每轮切换开销为零点一毫秒。计算连续完整时间片模型中的服务时间比例，并说明模型假设。

查看解答

服务时间比例为 $1/(1+0.1)=10/11$，约 90.91%。每轮总耗时为 1.1 毫秒。该估计假定每轮都有一次所给成本的切换，且没有其他开销。

练习标记完成

所属知识

策略条件

难度

3/5

一个短任务优先系统持续收到新短任务。解释长任务可能遭遇的情况，并提出一项具体改进及其代价。

查看解答

持续到达的短任务可一直排在长任务之前，使长任务饥饿。可以按等待时长老化优先级，或给长任务保留一定服务份额；代价是可能增加部分短任务的周转时间。

处理器调度参考资料

Operating Systems: Three Easy Pieces

Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau · 2023 · Arpaci-Dusseau Books

打开官方来源

OSTEP 的 CPU Scheduling 与 Multi-level Feedback 章节给出周转、响应和反馈队列的定义与条件。书中采用简化时间线分析策略；将模型用于实际系统时，还需单独测量任务长度估计误差和上下文切换成本。

xv6: a simple, Unix-like teaching operating system

Russ Cox, Frans Kaashoek, Robert Morris · 2025 · Massachusetts Institute of Technology

打开官方来源

MIT xv6 教材第 8 章介绍调度循环、进程上下文与切换函数，第 9 章分析睡眠和唤醒的配合。源码有助于区分调度策略与切换机制；教材中的简单策略不能代表通用系统在所有工作负载下的表现。