第 19 讲：CPU 调度与完整时间表

调度是在已就绪的执行流中选一个占用 CPU。它不是寻找“全局最好的唯一算法”，而是在互相冲突的目标之间权衡：低响应时间、高吞吐、低平均等待、公平、截止期保证和低调度开销不可能永远同时最优。

What、When、How

What：下一个选哪个进程/线程；
When：什么时候可重新决策；
How：如何保存原上下文、恢复新上下文。

可能调度的时机包括：进程创建/终止，当前进程因 I/O/信号量阻塞，I/O 中断使某进程就绪，时钟中断使时间片到期，或更高优先级任务到达。只有 OS 重新获得 CPU 控制权时，才能真正切换。

三级调度

级别	选择对象	大致频率	主要问题
高级/作业调度	后备作业→进入系统	低	控制多道程序度和作业组合
中级/交换调度	驻留↔挂起	中	内存压力、抖动与负载控制
低级/CPU 调度	就绪队列→ CPU	高（毫秒级）	选下一个执行流

低级调度很频繁，因此算法本身不能比任务还贵。

常用性能指标

对作业 $i$ ：

T_i=C_i-A_i

是周转时间， $A_i$ 为到达， $C_i$ 为完成。若 CPU 服务时间为 $S_i$ ：

W_i=T_i-S_i

是等待时间（简化为无 I/O 时），

T_i^{weighted}=\frac{T_i}{S_i}

是带权周转时间。响应时间是从到达到首次获得 CPU/首次产生响应，不是到完成。

系统指标还包括 CPU 利用率、单位时间完成数的吞吐量和调度/切换开销。平均周转时间并不简单等于吞吐量倒数，因为并发、I/O 和观测区间不同。

抢占与非抢占

非抢占：进程获得 CPU 后，直到完成或主动阻塞才让出；实现简单，但长任务可拖住交互任务。
抢占：时间片到或高优先级/更短剩余任务到达时，OS 可强制换下当前进程；响应好，但切换、同步和内核可抢占边界更复杂。

FCFS：简单但有护航效应

按到达顺序非抢占执行。对同时到达、CPU 时间分别为 20、2、2 的 A、B、C：

等待时间是 $0,20,22$ ；
平均等待是 14。

一个长 CPU 密集任务让后面许多短任务全等着，称为 convoy effect。FCFS 公平地对待到达顺序，但不代表对响应时间公平。

SJF 与 SRTF

SJF/SPN：每次选当前已到达任务中 CPU 时间最短者，非抢占；
SRTF：每次选剩余 CPU 时间最短者，新短任务到达可抢占。

对同时已知且能准确估计的 CPU burst，SJF 能最小化平均等待；问题是真实系统不知道未来运行时间，常只能用历史预测，长任务还可能饥饿。

HRRN：等得越久，优先级越高

最高响应比优先在每次调度时计算：

R=\frac{W+S}{S}=1+\frac{W}{S}.

短任务因 $S$ 小容易有高响应比；长任务的 $W$ 持续增长后也会上升，因而比纯 SJF 更能防止饥饿。它通常是非抢占的作业调度算法。

RR：交互系统的基本公平

就绪进程按 FCFS 排队，每次最多运行时间片 $q$ ：

未用完就完成/阻塞：立即让出；
用完 $q$ 仍可运行：抢占并放回队尾。

$q$ 过大会退化为 FCFS； $q$ 过小会让上下文切换占比过高。课件用粗略关系 $T_{response}\approx Nq$ 表达轮到一次的最大等待与就绪数 $N$ 、时间片 $q$ 有关，但现实还要加切换开销和提前阻塞。

完整调度算例

设：

进程	到达	CPU 时间
A	0	5
B	1	3
C	2	1

FCFS

Gantt 图：

0        5        8    9
|   A    |   B    | C  |

进程	完成	周转	等待
A	5	5	0
B	8	7	4
C	9	7	6

平均等待 $=(0+4+6)/3=10/3$ 。

SRTF

$t=0$ 只有 A，运行 1，剩 4；
$t=1$ B 到达，3 < 4，抢占 A；
$t=2$ C 到达，1 < B 剩余 2，抢占 B；
C 在 3 完成；B 在 3–5 完成；A 在 5–9 完成。

0  1  2  3    5        9
|A |B |C | B  |    A    |

进程	完成	周转	等待
A	9	9	4
B	5	4	1
C	3	1	0

平均等待 $=5/3$ 。每次到达都要用当前剩余时间重新比较，不是用原始总时间。

RR， $q=2$

0    2    4  5    7    8  9
| A  | B  |C | A  | B  |A |

在 $t=2$ A 的时间片到时，B 和 C 已按到达加入就绪队列，A 放队尾；由此得到 B、C、A 的顺序。若题目对“到达与时间片结束同时”的入队顺序有专门规定，应按题设处理并注明。

优先级、饥饿与老化

优先级可静态设定，也可根据等待时间、CPU/I/O 行为动态调整。高优先级持续到达会让低优先级饥饿，aging 通过让等待越久的任务逐渐提升优先级来限制无穷等待。

优先级数的大小方向不统一：有的系统数值大优先，有的数值小优先。做题必须看定义，不能凭“优先数”字面猜。

多级队列与多级反馈队列

MQ 按进程类型分到固定队列，例如实时、交互、批处理各一队，队列之间再用固定优先级或时间比例。

MLFQ 允许进程在队列间移动：

新任务从高优先级、短时间片开始；
用完时间片还不阻塞，显得 CPU 密集，下降到更低队列和更长时间片；
快速发起 I/O 的交互任务常留在高优先级；
周期性提升所有进程，避免低队列饥饿。

它用实际行为在线猜测 CPU burst：不需要程序事先宣称自己是长任务还是短任务。

优先级反转

低优先级 L 持有锁，高优先级 H 因该锁阻塞；此时中优先级 M 反复抢占 L，使 L 迟迟不能释放锁，H 实际被 M 间接拖住。

优先级继承：L 临时继承等待者 H 的高优先级，快速运行到释锁；
优先级天花板：事先为锁设置可能使用它的最高优先级，持锁时提升到相应级别。

继承只在锁依赖期间有效，释锁后要恢复原优先级。

实时调度：正确但过期也是失败

周期任务 $i$ 有执行时间 $C_i$ 、周期 $T_i$ 和截止期 $D_i$ 。

RMS：周期越短，静态优先级越高。课件给出 $n$ 个周期任务在经典假设下的充分可调度利用率界：

\sum_{i=1}^{n}\frac{C_i}{T_i}\le n(2^{1/n}-1).

EDF：动态选绝对截止时间最早的就绪任务。在单处理器、可抢占等标准理想假设下，对隐式截止期周期任务，总利用率不超过 1 时可调度。

课件还把静态表驱动列为一类：离线分析全部周期任务，在时间轴上预先排好每次运行，在线开销小且行为可验证，但难适应未预见的到达和执行时间变化。RMS 是静态优先级，EDF 是动态优先级；不要把“表预先排好”和“优先级固定”混成一件事。

这些结论有前提：独立任务、已知最坏执行时间、抢占/上下文开销忽略或已纳入、截止期定义匹配。不能把一条利用率不等式无条件套在任意实时系统。

多处理器调度

多核不只是“每个核各运行一个单核调度器”，还有：

AMP：主处理器作调度/系统管理，从处理器执行分派任务；
SMP：处理器地位对等，可使用公共就绪队列或每核队列；
公共队列负载自然平衡，但多核争抢队列锁；
每核队列局部性好，但需负载平衡和进程迁移；
CPU affinity 可减少 Cache 冷启动，但过度绑定会妨碍平衡；
gang scheduling 让一组紧密协作线程同时获得多个 CPU，减少彼此空等。

专用处理器分配则把某些 CPU 在一段时间内固定交给一个作业/线程组，牺牲全局灵活性换可预测性和较少切换；是否值得取决于并行任务的通信紧密度与机器负载。

课件中 Linux/UNIX 调度实例的位置

课件介绍了 Linux 从 O( $n$ ) 调度器、O(1) 调度器到 CFS 的演变，以及 SCHED_OTHER、SCHED_FIFO、SCHED_RR 策略；也以传统 UNIX 的动态用户优先数、内核睡眠优先级和调度标志说明一个具体系统如何落地。

这些实例的目的是将原理对应到就绪队列、权重和时钟更新，不应把课件中某个历史 Linux 版本的 counter/goodness 实现当成当前所有 Linux 内核的永久接口。

调度计算题的标准流程

画到达时间轴，每个决策点更新就绪集；
先写是抢占还是非抢占，RR 再写 $q$ ；
每段运行后更新剩余时间，画出 Gantt 图；
从图上读每个完成时间，再算周转、等待和带权周转；
抢占式算法每次新到达都要重新比较；
明确同时事件的入队规则，并保持一致。