COMP3230 第 4 讲：处理器调度（Processor Scheduling）

调度器到底在决定什么

在单核处理器上，同一时刻只能有一个可运行实体真正执行。就绪队列中可能同时存在多个进程，调度器需要决定：

• 下一个运行哪个进程；
• 当前进程运行多久；
• 什么时候因为阻塞、完成或定时器中断重新选择；
• 如何让短任务尽快完成，同时避免长任务长期得不到处理器；
• 多个处理器核心存在时，任务应该放在哪个核心上。

调度不是单纯的排序问题。进程切换需要保存和恢复寄存器状态，还可能破坏处理器缓存中的局部性。因此，调度器要在响应时间、周转时间、公平性和切换开销之间作出取舍。

先固定一组工作负载

为了比较不同策略，先使用同一组进程。每个进程只包含一个 CPU burst，不在运行期间发起 I/O。

本文采用以下约定：

1. 这是单核处理器；
2. 新进程在对应时刻的调度决策前进入就绪队列；
3. 同一时刻需要打破平局时，优先考虑更早进入队列的进程；
4. A(0-3) 表示进程 A 在时间区间 [0, 3) 运行；
5. 不考虑上下文切换耗时，时间单位可以理解为抽象的处理器时间单位。

现实中的 I/O-bound 进程可以拆成多个 CPU burst。每个 burst 结束后，进程进入阻塞状态；I/O 完成后重新回到就绪队列。

四个评价指标

设进程的到达时间为 $T_{\mathrm{arrival}}$，第一次运行时间为 $T_{\mathrm{first}}$，完成时间为 $T_{\mathrm{completion}}$，CPU burst 为 $B$。

周转时间（turnaround time）

它描述一个进程从到达系统到完成所经历的总时间。

等待时间（waiting time）

对于本文中只有一个 CPU burst 的工作负载：

更一般地，等待时间是进程在就绪队列中等待处理器的累计时间，不包括运行时间和阻塞在 I/O 上的时间。

响应时间（response time）

响应时间只看第一次得到处理器的速度。交互式程序通常更关注这个指标。

此外，还可以观察吞吐量、平均周转时间、公平性和上下文切换次数。一个策略在某个指标上表现较好，不代表它在其他指标上也同样较好。

FIFO：按到达顺序运行

FIFO（First-In, First-Out）也称 FCFS（First-Come, First-Served）。进程按到达顺序进入队列，获得 CPU 后通常运行到完成或主动阻塞。

逐步选择

• 时间 0：只有 A，运行 A(0-3)；
• 时间 3：B 已经到达，运行 B(3-9)；
• 时间 9：C、D、E 都在等待，继续按到达顺序选择 C；
• 之后依次运行 D 和 E。

完整时间线为：

A(0-3) | B(3-9) | C(9-13) | D(13-18) | E(18-20)

结果如下。

平均周转时间为：

FIFO 的问题可以直接从时间线看出：只需要 2 个时间单位的 E，必须等到 B、C、D 全部完成后才能运行。这种长任务阻塞多个短任务的现象称为护航效应（convoy effect）。

SJF：选择最短 CPU burst

SJF（Shortest Job First）是非抢占式策略。当前进程完成后，调度器从已经到达的进程中选择 CPU burst 最短者。

在时间 0，只有 A，因此先运行：

A(0-3)

时间 3 时只有 B 到达，所以 B 不能被 E 取代。B 在时间 9 完成后，C、D、E 都已到达，此时 burst 分别是 4、5 和 2，因此选择 E，再运行 C 和 D：

A(0-3) | B(3-9) | E(9-11) | C(11-15) | D(15-20)

结果如下。

平均周转时间为：

SJF 在已知 CPU burst 的理想模型中可以降低平均等待时间，但它有两个限制。第一，它不能打断已经运行的长进程；第二，真实系统通常只能估计进程未来需要的处理器时间，不能直接知道精确值。

HRRN：让等待时间进入决策

HRRN（Highest Response Ratio Next）仍然是非抢占式的，但它不只看 CPU burst，还考虑进程已经等待了多久。对一个等待进程，响应比为：

时间 0 到 9 的选择与 SJF 相同：

A(0-3) | B(3-9)

时间 9 时：

因此选择 C，而不是只看 service time 时会选择的 E。C 在时间 13 完成后，E 已经等待 5 个时间单位，响应比为 $1+5/2=3.5$，高于 D 的 $1+7/5=2.4$，于是执行 E：

A(0-3) | B(3-9) | C(9-13) | E(13-15) | D(15-20)

平均周转时间为 8.0。HRRN 通过老化（aging）让长期等待的进程逐渐获得更高优先级，从而降低饥饿风险。

STCF：允许短任务抢占长任务

STCF（Shortest Time-to-Completion First）是 SJF 的抢占式版本。调度器比较的是剩余运行时间：

执行过程如下：

1. 0-2 运行 A。时间 2 时 B 到达，但 A 只剩 1 个时间单位，因此 A 继续运行到 3；
2. 3-4 运行 B。时间 4 时 C 到达，B 还剩 5，C 只需 4，所以 C 抢占 B；
3. C 在 8 完成。此时 E 刚到达且只需要 2，所以运行 E；
4. E 完成后，B 和 D 都剩 5。按较早进入等待状态的顺序先运行 B。

A(0-3) | B(3-4) | C(4-8) | E(8-10) | B(10-15) | D(15-20)

平均周转时间为 7.2，平均响应时间为 2.0。STCF 能让短任务较快完成，但长进程可能被多次抢占，等待时间的差异也会扩大。它还需要维护每个进程已经运行了多久。

Round Robin：用时间片换响应速度

Round Robin（RR）把就绪进程放入 FIFO 队列，每次只允许队首进程运行一个时间片。时间片用尽后，进程被放到队尾。

调度器的核心过程可以写成：

while ready_queue is not empty:
    process = ready_queue.pop_front()
    run process for at most one quantum
    if process is unfinished:
        ready_queue.push_back(process)

时间片为 1

根据上面的工作负载，时间线为：

A(0-1) | A(1-2) | B(2-3) | A(3-4) | B(4-5)
| C(5-6) | B(6-7) | D(7-8) | C(8-9) | B(9-10)
| E(10-11) | D(11-12) | C(12-13) | B(13-14)
| E(14-15) | D(15-16) | C(16-17) | B(17-18)
| D(18-20)

完成时间为 A=4、B=18、C=17、D=20、E=15。因此：

短时间片让新到达的进程很快得到第一次运行机会，但上下文切换次数会增加。

时间片为 2

时间片变大后，时间线变为：

A(0-2) | B(2-4) | A(4-5) | C(5-7) | B(7-9)
| D(9-11) | C(11-13) | E(13-15) | B(15-17)
| D(17-20)

结果为：

时间片过大时，RR 会逐渐接近 FIFO；时间片过小时，系统可能把过多时间用于上下文切换。时间片需要在交互响应和处理器效率之间取中间值。

把经典算法放在一起比较

对同一组进程，得到的平均值如下。

这张表不是算法的永久排名。它只描述当前到达时间、CPU burst 和时间片参数下的结果。换一组工作负载，结论就可能变化。

MLFQ：不知道未来运行时间时怎么办

SJF 和 STCF 依赖 CPU burst 或剩余运行时间，而操作系统通常不能在进程启动时准确知道这些信息。多级反馈队列（Multilevel Feedback Queue，MLFQ）改为观察进程已经表现出的行为。

一个典型策略包含多个优先级队列：

1. 新进程进入最高优先级队列；
2. 高优先级队列优先于低优先级队列；
3. 同一队列内部使用 RR；
4. 进程耗尽当前层级的累计时间配额后降级；
5. 进程在时间片用尽前主动阻塞，通常可以保留当前优先级；
6. 周期性提升系统中进程的优先级，避免低优先级进程长期等待。

一个具体状态变化

考虑一个长时间计算的进程 P0 和一个交互式进程 P1。假设每层时间片为 50 ms：

• P0 在时间 0 到达，连续消耗高优先级队列的 50 ms，然后降级；
• 它再次消耗 50 ms 后继续降级；
• P1 在时间 200 ms 到达，进入高优先级队列；
• P1 运行 20 ms 后发起 I/O，进入阻塞状态；
• I/O 完成后，P1 重新进入高优先级队列，并可以再次较快得到处理器。

MLFQ 的关键不是给每个进程永久贴标签，而是利用近期行为作出下一次决策。持续消耗 CPU 的进程会逐渐降低优先级，频繁阻塞的交互式进程则更容易保留较高优先级。

两个需要防止的问题

如果高优先级队列一直有进程，低优先级进程可能发生饥饿。周期性优先级提升可以让系统中的进程重新参与竞争。

另一个问题是“伪装”。进程可能在时间片即将耗尽前主动让出 CPU，以免被降级。解决方法是按队列层级累计处理器使用量，而不是只看某一次时间片是否主动结束。

公平份额调度

如果调度单位只是进程，一个用户可以创建大量进程来获得更多处理器时间。公平份额调度把用户、用户组或应用组作为资源分配单位。

Lottery Scheduling

假设系统共有 100 张彩票：

• A 持有 75 张，编号 0 到 74；
• B 持有 25 张，编号 75 到 99。

每次调度随机抽取一张彩票，持有该彩票的进程运行。一次抽签不能保证 A 获胜，但在较长时间内，A 获得约 75% 处理器时间的概率更高。

例如抽取序列：

63  85  70  39  76  17  29  41  36  39  10  99  68  83  63
 A   B   A   A   B   A   A   A   A   A   A   B   A   B   A

Lottery Scheduling 的比例保证是统计意义上的，短时间窗口内仍然会出现波动。

Stride Scheduling

Stride Scheduling 把随机选择改为确定性选择。每个进程维护：

• stride：通常与彩票数量成反比；
• pass：每次运行后增加本进程的 stride。

令常数 $L=400$。若 A 有 4 张彩票，B 有 2 张，C 有 10 张：

每次选择 pass 最小的进程：

C 的 stride 最小，所以在短时间内会更频繁地被选择；长期选择比例接近彩票比例。与 Lottery Scheduling 相比，Stride Scheduling 不依赖随机数，但需要维护全局的 pass 状态。

多核调度

多核系统还要决定任务队列如何组织。两种基本设计如下。

一个共享队列

各核心从一个就绪队列中取任务。它便于全局平衡，但多个核心同时访问队列需要锁或其他同步机制。核心数量增加后，队列竞争可能成为瓶颈；任务在核心之间迁移时，也可能损失缓存亲和性。

每个核心一个队列

每个核心维护自己的队列。这样可以减少共享锁竞争，并让任务尽量留在原来的核心上，但容易出现负载不平衡：一个核心空闲，另一个核心的队列却很长。

工作窃取要在三个因素之间取舍：

• 迁移开销；
• 缓存亲和性；
• 核心之间的负载差异。

Linux 中的联系

Linux 的实时调度类包括 SCHED_FIFO 和 SCHED_RR。SCHED_FIFO 让同一优先级的任务按先到先服务运行，SCHED_RR 则在同一优先级内使用时间片轮转。实时任务如果长期不阻塞，可能推迟普通任务，因此系统会限制普通用户创建任意实时任务的能力。

对于普通任务，可以用 CFS（Completely Fair Scheduler）的模型理解公平调度。调度器维护每个任务的虚拟运行时间 vruntime，优先选择 vruntime 较小的任务，因为它相对获得的处理器时间更少。任务权重受 niceness 影响：

在简化模型中，运行相同的实际时间后，高权重任务的 vruntime 增长较慢，因此更容易再次被选中。实际 Linux 版本的调度实现会随版本和调度类变化，这里只保留公平份额、权重和有序选择这几个核心概念。

小结

用同一组进程计算后，可以清楚看到各算法的取舍：

• FIFO 实现简单，但长任务可能阻塞后续短任务；
• SJF 在已知 CPU burst 时能降低平均周转时间，但无法处理未知的未来运行时间；
• HRRN 把等待时间加入优先级，降低长任务被无限推迟的风险；
• STCF 允许抢占，通常能较快完成短任务，但会增加长任务的等待波动；
• RR 用时间片改善响应性，时间片过小则增加上下文切换；
• MLFQ 通过运行历史估计任务类型，并用优先级提升处理饥饿；
• Lottery 和 Stride Scheduling 把公平性表达为处理器时间份额；
• 多核调度还要处理队列竞争、缓存亲和性、负载平衡和任务迁移。

因此，调度策略的评价必须同时说明工作负载、抢占规则、时间片和评价指标。只给出一个算法名称，无法判断它在具体系统中的行为。

返回目录

• 回到 COMP3230 课程笔记目录