上一章我们解决了 CPU 怎么从 Process A 真正切换到 Process B：Context Switch 提供 Mechanism，保存 A 的 Execution Context，再恢复 B 的 Context。但是会切还不够，因为 Kernel 每次拿回 CPU 以后还必须回答一个问题：下一个到底应该运行谁？

这就是 Processor Scheduling。Scheduler 负责从能够运行的 Process / Thread 中选出下一位，并决定它什么时候运行、运行多久。Scheduling Policy 会直接影响用户感受到的响应速度、CPU 利用效率，以及整个系统单位时间内能完成多少工作；更重要的是，上一章已经知道 Process Switching 并不是免费的，所以“什么时候换人、换给谁”本身也会影响整体性能。

可以继续沿用之前的 Mechanism / Policy 区别：

Context Switch
→ Mechanism
→ “怎么从A切到B？”

Scheduling
→ Policy
→ “为什么下一位偏偏是B？”

Scheduling 有不止一层

不是所有 Process 创建之后都会直接扔进 Ready Queue 等 CPU。OS 里面实际上可以把 Scheduling 分成三个层级。

Long-term / Job Scheduling 负责决定新的 Job / Process 是否应该进入系统，因此它控制同一时间系统里有多少 Process，也就是 Degree of Multiprogramming。Medium-term Scheduling 则决定哪些 Process 暂时可以继续参与 CPU 竞争，并涉及 Process 的 swapping in/out，用来响应系统负载变化。最后才是这一章真正重点研究的 Short-term Scheduling：当前有一堆 Ready Process，下一个到底跑谁。所以后面的 FIFO、SJF、RR、MLFQ，基本都属于最后这一层。

Scheduling 的基础概念

CPU-bound 和 I/O-bound

不同 Process 使用 CPU 的行为差异很大。CPU-bound / Compute-bound Process 拿到 CPU 以后通常会把分给自己的 Processor Time 几乎全部吃完，只有到了 Quantum 结束、完成计算或者其他原因才释放 CPU。另一边的 I/O-bound Process 通常只运行很短一段时间，就会发起 I/O Request 然后 Blocked，把 CPU 交出去。换一个更直观的说法：

CPU-bound
→ CPU 更快，它会明显更快

I/O-bound
→ I/O subsystem 更快，它会明显更快

这个区别后面尤其重要，因为 Interactive / I/O-bound Process 通常更加在乎“你能不能赶紧让我运行一下”，而 Long CPU-bound Process 更关心的往往是“最后到底多久能把我的活全部做完”。这两个目标不是同一个东西。

Turnaround Time

Turnaround Time 衡量一个 Process 从进入系统到彻底完成一共经历了多久：

$$
T_{turnaround}=T_{completion}-T_{arrival}
$$

例如某 Process 在 t=2 到达，在 t=10 完成，那么：

$$
T_{turnaround}=10-2=8
$$

这个 8 里面可能包含真正使用 CPU 的时间，也包含各种等待，所以它衡量的是从来了到干完，总共多久。Scheduling 一般希望尽可能降低 Average Turnaround Time。

Waiting Time

Waiting Time 专门指 Process 在 Ready Queue 里等待 CPU 的累计时间，也就是：

1 2	Ready，但是没有拿到 CPU → Waiting Time

如果 Process 已经 Blocked，在等 Disk I/O，那么这不是“等 Scheduler 给 CPU”，所以不算这里的 Ready Queue Waiting Time。

Response Time

Response Time 衡量的是从 Process 到达，到它第一次真正拿到 CPU 之间隔了多久：

$$
T_{response}=T_{first\ run}-T_{arrival}
$$

这个 Metric 对于 Interactive Task 特别重要。例如一个程序可能 Response Time 只有 0.1s，Turnaround Time 却有 30s：虽然整个任务需要 30 秒才结束，但你点下按钮 0.1 秒就开始有反应，用户依然会感觉系统很流畅。反过来，一个任务可能总共 20 秒完成，但前 10 秒完全没反应，用户首先会怀疑软件已经寄了。所以不要混：

Turnaround
→ “多久全部做完？”

Response
→ “多久第一次理我？”

Throughput 和 Fairness

Throughput 就是单位时间平均完成多少 Job：

1 2	10 秒完成 5 个 Job → 0.5 jobs/sec

目标自然是越高越好。另外还有 Fairness：类似等级的 Process 应该被类似对待，即使 Process Priority 不同，也不能让某个 Process 永远等不到 CPU。这种无限期推迟就是 Starvation。所以一个 Scheduler 即使 Average Turnaround 非常漂亮，也不能说“那几个倒霉蛋永远跑不到就算了，平均数还是很好看的”。OS 的 Scheduling 从来不是只优化一个 Metric，而是在多个目标之间 Trade-off。

Scheduler 什么时候出来干活

Scheduler 并不是 CPU 每执行一条 Instruction 就重新算一次。它通常在系统状态发生某些重要变化时获得 Scheduling 机会，比如创建 Process、Process 退出、Process 因为 I/O 或其他 Event 进入 Blocked、Process 进行 System Call，以及发生 Interrupt。尤其是上一章刚学完的两个：

I/O Interrupt
→ 原本 Blocked 的 Process 可能变成 Ready

Clock Interrupt
→ Kernel 周期性拿回 CPU
→ Scheduler 重新考虑谁应该运行

所以现在整条链条可以写成：

Timer Interrupt
→ Mechanism：OS 重新拿回 CPU

Scheduler
→ Policy：下一位给谁？

Context Switch
→ Mechanism：真的从 A 切到 B

Deterministic Modeling

后面的算法比较使用 Deterministic Modeling：给定一组事先确定好的 Workload，再比较不同算法的 Performance。为了避免 I/O 等额外变量干扰，Lecture 先假设所有 Job 只使用 CPU，而且每个 Job 的 CPU Burst / Runtime 事先已知；虽然现实并不成立，但是带 I/O 的 Process 也可以暂时把每一段 CPU Burst 拆开分析。

后面大部分算法都用同一组 Process：

Process	Arrival Time	CPU Burst
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

这样很好，因为 Workload 完全没变，我们只要观察换一个 Scheduling Policy，执行顺序和 Performance 为什么就变了。

经典 Scheduling 算法

FIFO / FCFS

最简单的想法当然是：谁先来谁先跑。这就是 First-In-First-Out (FIFO)，也叫 First Come First Serve (FCFS)。Process 按照 Arrival Time 进入 Queue，Scheduler 每次取 Queue 最前面那个；它是 Non-preemptive 的，一个 Process 一旦获得 CPU，会一直运行到完成或者主动释放 CPU。

在上面的 Workload 中，执行顺序是：

1 2	0---3---------9----13-----18--20 \| A \| B \| C \| D \| E \|

于是 $T_A=3$、$T_B=7$、$T_C=9$、$T_D=12$、$T_E=12$，Average Turnaround 为：

$$
\frac{3+7+9+12+12}{5}=8.6
$$

FIFO 最大的优点就是简单、容易实现，而且大家严格按照 Arrival Order，看起来也很公平。但是问题也非常明显：Short Job 可能被 Long CPU-bound Job 堵在后面。 比如 E 只需要 2 个 CPU Time Unit，却从 t=8 一直等到 t=18 才第一次运行，于是 $T_{response,E}=18-8=10$，这种对 Interactive Process 的体验非常差。

所以 FIFO 的问题不是“不公平”，而是它只知道谁先来，完全不知道前面这个人到底要占 CPU 多久。

Shortest Job First

既然问题是 Long Job 堵着一堆 Short Job，那最自然的修法就是：每次 CPU 空下来以后，从当前 Ready Processes 里面选 CPU Burst 最短的那个。这就是 Shortest-Job-First (SJF)。它仍然是 Non-preemptive：已经上 CPU 的 Process 不会因为后来出现更短的 Job 而被赶下来。

这组 Workload 里，A 在 t=0 运行到 3；t=3 时只有 B 已经到达，所以 B 只能运行到 9。虽然 C、D、E 在 B 运行期间陆续到达，但是 SJF 不能 Preempt B。到了 t=9，Ready Queue 里有 C: 4、D: 5、E: 2，于是 E 先上：

A: 0 → 3
B: 3 → 9
E: 9 → 11
C: 11 → 15
D: 15 → 20

Average Turnaround：

$$
\frac{3+7+11+14+3}{5}=7.6
$$

比 FIFO 的 8.6 更好。所以 SJF 对 Average Waiting Time / Turnaround Time 很有优势，因为它倾向于快速把 Short Job 清掉。但是不要因此理解成 Response Time 一定很好：它仍然是 Non-preemptive，如果一个 Long CPU-bound Process 已经开始运行，新来的 Interactive Job 还是只能等它结束。

另外还有一个更严重的问题：Starvation。如果 Short Job 一直不断到达：

Long Job L 一直在等
↓
Short A 来了
→ 跑 A

Short B 来了
→ 跑 B

Short C 来了
→ 跑 C
...

那么 L 理论上可能一直等不到 CPU。所以 SJF 可以简单理解成平均效率很好，但是太偏爱 Short Job。

Highest Response Ratio Next

SJF 的问题之一是 Long Job 等得再久也没有额外补偿，于是 Highest-Response-Ratio-Next (HRRN) 给它加了一个很漂亮的 Aging 机制。HRRN 依然是 Non-preemptive，但在每次 Scheduling Decision 时计算：

$$
Priority=\frac{Waiting\ Time+Service\ Time}{Service\ Time}=1+\frac{Waiting\ Time}{Service\ Time}
$$

然后选择 Priority 最高的 Process。这个公式本身已经把思想说完了：Short Job 因为 Service Time 小，本身容易得到比较高的 Ratio；但是一个 Job 如果等了非常久，Waiting Time 一涨，Priority 也跟着涨，于是最终会越来越难继续被忽略。这就是 Aging Effect，用来防止 Indefinite Postponement。

例如 t=9 时，C 的 priority 是 $(5+4)/4=2.25$，D 是 $(3+5)/5=1.6$，E 是 $(1+2)/2=1.5$。所以虽然 E 最短，HRRN 还是先选已经等更久的 C。等 C 在 t=13 完成后，D 变成 $(7+5)/5=2.4$，E 变成 $(5+2)/2=3.5$，于是再跑 E。最后顺序是：

1	A → B → C → E → D

Average Turnaround = 8。HRRN 并不是说“Average Turnaround 一定比 SJF 更好”，而是愿意牺牲一点纯粹的 Short Job 优先，换取等待时间上的公平性。不过它仍然保留 SJF 的一个大问题：Non-preemptive，一旦选中了一个 Long Job，哪怕下一秒来了一个超级短的 Interactive Job，也得等。

Shortest Time-to-Completion First

既然SJF最大的问题之一是不能抢占，那我们干脆做一个 Preemptive SJF。

这就是 Shortest Time-to-Completion First (STCF)。新的 Process 到达时，Scheduler 会比较当前 Running Process 和新 Process 的 Remaining Time：

$$
Remaining=CPU\ Burst-Elapsed\ Service\ Time
$$

谁距离完成更近，就让谁运行。

例如 A 在 t=0 开始，需要 3；t=2 时 B 到达，需要 6，但是 A 已经跑了 2，A remaining = 1、B remaining = 6，所以继续 A。t=3 B 开始，到了 t=4 C 到达，B remaining = 5、C remaining = 4，于是 Preempt B，B 从 Running 回到 Ready，C 从 Ready 变成 Running。C 跑到 t=8 时 E 到达，只需要 2，于是 E 运行到 10，后面再继续 B 和 D：

0–3   A
3–4   B
4–8   C
8–10  E
10–15 B
15–20 D

Average Turnaround：

$$
\frac{3+13+4+14+2}{5}=7.2
$$

Response Time 也相当好：A=0、B=1、C=0、D=9、E=0。但 STCF 同样没有免费午餐，因为 Long Process 不仅可能一直等，还可能反复被新来的 Short Job 抢走：

终于开始跑
↓
Short Job 来了
→ 被抢

又开始跑
↓
又来一个 Short Job
→ 再被抢

所以 Long Job 的 Waiting Time Variance 可能比 SJF 还大。另外每一次 Preemption 都有可能带来新的 Context Switch，而上一章已经告诉我们 Context Switch 并不是零成本。课件甚至指出，一个新来的 Short Job 可能去抢占一个马上就要结束的 Process，结果为了省一点 Runtime 反而多付了一次 Switch Cost。

Round Robin

前面 SJF / STCF 都建立在一个非常强的假设上：我们提前知道 Process 还需要多少 CPU Time。现实里 OS 通常并不知道。于是 Round Robin (RR) 换了一个完全不同的思路：既然不知道你还要多久，那就所有人轮流来。

Ready Queue 仍然按照 FIFO 组织，新 Process 放到队尾，但是每个 Process 一次最多只能运行固定长度的 Time Quantum / Time Slice。如果 Quantum 用完 Process 还没完成，就 Preempt 它并放回 Ready Queue 尾部，接下来运行下一个。所以调度从：

1	A 跑完 → B 跑完 → C 跑完

变成：

A 跑 1 个 Quantum
→ B 跑 1 个 Quantum
→ C 跑 1 个 Quantum
→ A 再回来
...

课件的例子设置 Quantum=1，最后 RR 的 Average Turnaround 反而到了 10.8，比 FIFO、SJF、HRRN 和 STCF 都差，但是 Average Response Time 只有 0.8，是这几个例子里面最漂亮的。这正好说明 RR 的目标不同：它愿意牺牲 Turnaround，换 Responsiveness 和 Fairness。 大家不一定很快做完，但是几乎所有人都能很快摸到 CPU。

Quantum 的大小

RR 真正的难点不是算法，而是 Quantum Size。如果 Quantum 非常大，大部分 Process 一次上 CPU 就直接跑完，RR 最终会退化成 FIFO。反过来，如果 Quantum 特别小：

A
→ switch
B
→ switch
C
→ switch
A
→ switch
...

Response 非常漂亮，但是系统大量时间都花在 Context Switching，而不是 Application 真正的 Useful Computation。所以 Quantum 需要一个 Middle Ground：够短，使 Interactive Request 尽快得到响应；也要够长，不至于整个 CPU 都在 Save / Restore Context。课件的思路是，Quantum 最好长到 Interactive Process 通常有机会在用完之前发出 I/O Request，而 Long Process 仍然能获得大部分 Processor Time。

SJF 和 RR 的两难

到现在为止我们手里有两条路线：

SJF / STCF
→ Turnaround 很好
→ 但是需要提前知道 CPU Burst

RR
→ Response 很好
→ 不需要提前知道 CPU Burst
→ 但是 Turnaround 不漂亮

于是课件第 26 页提出真正的 Crux：有没有一种 Scheduler 能够像 RR 一样给 Interactive Job 很好的 Response，同时像 SJF / STCF 一样偏爱 Short Job，而且还不需要事先知道 CPU Burst？ 答案就是 MLFQ。

MLFQ

Priority

在进入 MLFQ 之前，先补一个概念：Priority Scheduling。可以给每个 Process / Thread 一个 Priority Number，Scheduler 优先选择更高 Priority 的 Task。Priority 可以是 Static，也可以是 Dynamic。Static Priority 在生命周期内不改变，实现简单、Overhead 低，但是无法响应环境变化，而且 Low-priority Process 可能 Starvation；Dynamic Priority 可以跟着系统状态变化，但是 Scheduler 每次做决定时要重新维护 Priority，因此 Overhead 更高。MLFQ 接下来做的，就是一个很典型的 Dynamic Priority 系统。

Multilevel Feedback Queue

Multilevel Feedback Queue (MLFQ) 有多个不同 Priority 的 Ready Queue。Scheduler 永远先选择最高 Priority 的非空 Queue，只有上层全部为空才会运行下面的 Queue；同一个 Priority Queue 内部使用 Round Robin。Process 的 Priority 不是固定的，而是根据 Runtime Behavior 动态调整，课件图里画成：

High Priority
Q8
Q7
Q6
Q5
Q4
Q3
Q2
Q1
Low Priority

不过“8 层”只是这个例子，不是 MLFQ 规定必须有 8 层，Queue 数量本身就是后面要配置的参数。MLFQ 真正聪明的地方是：我不知道你未来需要多少 CPU，但我可以根据你过去怎么使用 CPU 来猜你是什么 Process。

基本 Priority Rule

新 Process 刚进系统时直接放到最高 Priority Queue。如果一个 Process 把整个 Quantum 全部用完，就 Preempt 它并降到下一层 Queue；如果 Process 在 Quantum 结束前主动 Relinquish CPU，例如去等待 I/O，就留在当前 Priority。这其实是在根据行为分类。

一个 Process 每次拿到 CPU 都是给多少吃多少，那它很像 Long / CPU-bound Job，Priority 会越来越低；另一个 Process 拿到 CPU 只跑 20ms 就请求 I/O 然后 Blocked，那它很像 Interactive / I/O-bound Process，所以系统不惩罚它，让它继续留在 High Priority。MLFQ 并不直接问“你是不是 Interactive”，而是在观察“你过去拿到 CPU 之后是什么行为”，然后用 History 预测 Future Behavior。

MLFQ in Action

课件给了两个 Process。P0 是 Long Process，在 t=0 到达；P1 是 Interactive Process，在 t=200 到达，每次只使用 CPU 20 Time Units，然后 Blocked 等待 I/O 100 Time Units。每层 Quantum = 50。

P0 从最高 Priority 开始，连续用满 50 就被逐层降下去：

Q8
↓ 用满 50
Q7
↓ 用满 50
Q6
↓
Q5
...

因为它一直表现得“给我多少 CPU 我都吃掉”，所以系统逐渐把它识别成 Long CPU-bound Process。P1 后来进入 Q8，拿到 CPU 只用 20 就去 I/O，因为 $20 < Quantum\ 50$，所以 P1 不会被 Demote，I/O 完成回来以后仍然处于 High Priority，于是它每次醒来都能很快得到 CPU。最终效果就是：

Interactive / short-burst Job
→ 倾向停留在 High Priority

Long CPU-bound Job
→ 逐步沉到 Low Priority

于是 MLFQ 在不知道 CPU Burst 的情况下，试图近似出 SJF / STCF “偏爱 Short Job”的效果，同时保留 Interactive Responsiveness。

MLFQ 也会被玩坏

第一个问题还是 Starvation。如果 High-priority Queue 永远有大量 Interactive Process，也就是 Q8 一直非空，那最下面的 CPU-bound Job 可能永远没有机会运行。

第二个问题更搞笑：Process 可能 Game the Scheduler。如果 Quantum = 50，而且规则只是“用完整个 50 就降级、没用完就不降级”，那一个坏 Process 完全可以跑 49 就主动放 CPU，下次再跑 49 再放，一直假装自己是 Interactive Process，从而偷走大量 High-priority CPU Time。

第三个问题是 Process Behavior 会变化。一个 Process 前半生可能是 CPU-bound，因此早就沉到 Lowest Queue，后来却突然进入 Interactive Phase；但是如果 Scheduler 只记住它过去很 CPU-hungry，那它就很难重新被当成 Interactive Process。

给 MLFQ 打补丁

首先解决 Starvation 和 Behavior Change，办法是 Periodic Priority Boost：每隔固定时间 S，就把所有 Process 全部送回最高 Priority Queue。这样 Bottom Queue 里的 Long Job 至少周期性得到机会，同时一个以前 CPU-bound、后来变 Interactive 的 Process 也可以重新证明自己。

然后解决 Gaming。不能只判断“这一次有没有用完整个 Quantum”，而是要累计这个 Process 在某一 Priority Level 已经使用了多少 CPU Time：

Process 在这一层的 CPU Usage
→ 累计

达到这一层 Time Allotment
→ Demote

于是跑 49 再 yield 再跑 1，总共还是 50，照样降级。没有达到 Allotment 的 Process 则继续留在当前 Priority，并不是自动 Upgrade。

另外，不同 Priority Level 还可以设置不同长度的 Quantum。High-priority Queue 使用 Short Time Slice，保证 Interactive Response；越往低 Priority，Quantum 越长，让 Long CPU-bound Process 一次多跑一点，减少 Context Switch Overhead。课件给的思路就是 Lower Queue 逐层增加 Quantum。所以 MLFQ 最终形成：

High Priority
→ Short Quantum
→ Interactive Response

Low Priority
→ Long Quantum
→ Long-job Efficiency

它是一个典型的 Adaptive Mechanism：根据 Process 行为不断调整 Priority，因此对 Environment 变化更加敏感，但当然也付出更多 Scheduling Overhead。与此同时它留下很多 Configuration Problem：到底几层 Queue？每层 Quantum 多长？多久 Boost 一次？这些没有天然唯一答案。

顺带一提，MLFQ 最早由 Corbató 等人在 1962 年的 CTSS 中描述，相关的 Time-sharing / Multics 工作后来使 Fernando Corbató 获得 ACM Turing Award，不是诺贝尔奖。

到这里前面的算法基本都在做 Process 和 Process 之间怎么公平。但如果 User A 只开 1 个 Process，User B 开 100 个 Process，然后 Scheduler 公平地给 101 个 Process 一人一份 CPU：

User A
→ 1/101

User B
→ 100/101

那 B 只需要疯狂开 Process，就可以把系统抢走。所以 Fair Share Scheduling (FSS) 把 Fairness 的单位从 Process 提升到了 User / Group。不同 User / Group 被分配 Weight，代表它们应该获得总 CPU Resource 的多少比例；Scheduler 监控实际 Resource Usage，已经超过 Fair Share 的后面少给一点，低于 Fair Share 的则多给一点。例如 User A 和 User B 的 weight 都是 1，那 A 应该长期得到 50%，B 也应该长期得到 50%；B 内部就算开 10 个 Process，也只是 10 个人瓜分 B 自己的 50%，而不是凭空把 CPU Share 放大 10 倍。

Lottery Scheduling

一个很有意思的 Proportional Share 实现是 Lottery Scheduling，核心思想是给 Process / User / Group 分配 Lottery Tickets。例如 A 的 fair share 是 75%，那就给 A 75 张 ticket；B 的 fair share 是 25%，就给 B 25 张。每次 Scheduling 时随机抽一张 Ticket，谁拿着 Winning Ticket 谁获得 CPU。单次当然不保证 A 一定 75%、B 一定 25%，可能连续五次都是 B，但是长期来看：

$$
P(A)=0.75,\qquad P(B)=0.25
$$

所以 Resource Consumption 会逐渐趋近 Ticket Ratio。课件的例子就是 A 有 75 张、B 有 25 张，Scheduler 每次在 0–99 中产生 Random Number，根据号码落在哪个区间决定赢家。这里需要注意，Random 不是 Fairness 的来源，Ticket Distribution 才是，Random Lottery 只是实现预定 Share 的一种机制。

Multiprocessor Scheduling

前面基本都默认一个 Core 一次只有一个 Process。但是现实系统通常有多个 Core，于是 Scheduler 除了回答“下一位是谁”，还要多回答一个问题：它在哪颗 Core 上运行？

Single-Queue Scheduling

最简单的方法就是所有 Core 共用一个 Global Ready Queue：

Ready Queue:
A B C D E F G ...

CPU0
→ 从这里拿

CPU1
→ 也从这里拿

这个设计简单，但是有两个严重问题。

Shared Queue Contention

多个 Core 可能同时修改同一个 Ready Queue，比如 CPU0 和 CPU1 同时说要 dequeue head。如果没有 Synchronization，Queue Data Structure 可能直接损坏，所以对 Shared Queue 的 Access 必须保护。随着 Core 数量上升，同时抢 Queue 的人变多，Lock Contention 就会上升，Performance 随之下降，这就是课件说的 Poor Scalability。

注意这里 Lock 的核心对象是 Shared Scheduling Queue Data Structure，不是把整个 Process、Registers、Memory Space 全部锁起来。

Cache Affinity

另一个问题叫 Cache Affinity。假设 Process A 刚才一直在 Core 0 运行，那么 Core 0 的 CPU Cache 里通常已经有很多 A 最近执行的 Instructions 和最近使用的数据，所以 A 下一次继续跑 Core 0，很多内容可以直接 Cache Hit。但 Single Queue 可能让 A 从 Core0 跑到 Core1、Core3 再回到 Core0，这样 A 每次换 Core，新 Core 的 Cache 里可能都没有它的 Working Set，又得重新加载，增加 Cache Miss / Reload Overhead。所以这里讨论的不是“Register 内容更多”，也不是 Disk I/O，而是尽可能让 Process 继续使用已经对它比较热的 CPU Cache。

Multi-Queue Scheduling

为了减少 Shared Queue Contention 和改善 Cache Affinity，一个自然的办法是 One Scheduling Queue Per Core。例如 CPU0 的 Queue 放 A、C、E，CPU1 的 Queue 放 B、D、F。新 Job 进入系统以后，根据某个 Heuristic 分配到一个 Queue，例如 Random 或者选当前 Job 较少的 Queue。这样每个 Core 主要管理自己的 Queue，Shared Queue Contention 少很多，Process 也更容易留在同一个 Core，Cache Affinity 更好。但是这又引入一个经典问题。

这就是 Load Imbalance。

一核有难，多核围观

假设 CPU0 的 Queue 里只有 A，CPU1 的 Queue 里排着 B、D、F。A 跑完以后 CPU0 就 Idle 了，而 CPU1 从 B 到 D 再到 F 忙到爆，于是虽然系统还有空闲计算资源，却因为 Queue 之间不平衡而浪费掉。一个解决方案就是 Work Stealing：某个 Queue 发现自己没什么 Job 时，偶尔去看看别人的 Queue，如果发现别人明显更忙，就偷一个或多个 Job 回来运行，比如从 Q2 的 B、D、F、G 里偷走 F 放到 Q1，这样重新平衡各 Core 的 Load。但新的问题又来了：多久检查一次？多少 Job 算“负载低”？别人比我多多少才值得偷？检查太频繁，本身就有 Scheduling Overhead；检查太少，Load Imbalance 可能持续很久。所以课件最后直接说，Finding the right threshold remains a black art。

Linux Scheduler 案例

这一部分 Lecture 明确写了 Not for examination，所以理解思想即可，不需要背实现。

Linux Scheduling 本身是 Preemptive, Priority-based，并区分 Real-time 和 Non-real-time 两类 Priority Class。Real-time Priority 从 1 到 99，数值越高 Priority 越高。SCHED_FIFO 让同 Priority 下的 Real-time Process 按照 FIFO 运行；SCHED_RR 则让同 Priority Real-time Process 使用 Round Robin。课件还指出，Real-time Process 可能无限推迟 Normal Process，因此 Normal User 不能随意创建 Real-time Process。

Completely Fair Scheduler

对于 Non-real-time Process，课件介绍了 Linux 的 Completely Fair Scheduler (CFS)。它不试图提前分类“你是 Interactive”还是“你是 CPU-bound”，而是假设大家一开始都一样，核心目标是尽可能公平地分 Processor Time。如果当前有 nr 个 Runnable Process，并且大家 Weight 一样，那么理想上每个 Process 应该获得大约：

$$
\frac{1}{nr}
$$

的 CPU 资源；更高 Priority 可以通过更大的 Weight 获得更大 Share。课件先想象一颗“不现实的完美 CPU”：所有 Process 可以同时运行，每个人直接获得自己那一部分 Processor Power。但真实 Core 一次只能跑一个 Process，所以 CFS 需要记录每个 Task 已经“公平地消费了多少 CPU”。

这个量叫 Virtual Runtime。Process 运行时，CFS 根据其 Execution Duration、Runnable Processes 和 Priority 等因素更新 Virtual Runtime，数值越大就可以理解为“你目前已经吃过比较多 CPU 了”。于是 Scheduling Decision 就非常直接：选择 Virtual Runtime 最小的 Runnable Process，也就是优先让“目前吃 CPU 最少的人”补回来。Runnable Tasks 按照 Virtual Runtime 存放在一个 Red-Black Tree 中，因为 Tree 按照 Virtual Runtime 排序，所以最左边就是当前 Virtual Runtime 最小、最需要 CPU 的 Task；Red-Black Tree 提供大约 $O(\log n)$ 的操作复杂度。

这一部分不用考试，所以知道 CFS 大致就是 Track virtual runtime、谁吃 CPU 最少优先补谁、并用 Red-Black Tree 快速找最小值，就已经够了。

总结

这一章实际上一直在围绕几个互相冲突的目标做 Trade-off：Turnaround 希望 Job 尽快完成，Response 希望 Interactive Job 赶紧得到 CPU，Throughput 希望单位时间完成更多 Job，Fairness 要求不能有人永远饿死，而 Overhead 又提醒我们不能为了调度本身浪费太多 CPU。不同算法只是在这些目标里选了不同的立场。

FIFO 最简单，只按 Arrival Order 排队，于是 Short Job 可能被前面的 Long Job 堵死。SJF 把 Short Job 提前，Average Waiting / Turnaround 很好看，代价是 Long Job 可能 Starvation，而且必须知道 Burst。HRRN 相当于 SJF 加上 Aging，把 Waiting Time 也算进 Priority，缓解了 Starvation，但它仍然是 Non-preemptive。STCF 则把 SJF 变成 Preemptive，新来的 Short Job 可以直接抢 CPU，Response 和 Turnaround 可能更好，代价是 Context Switch 更多、Long Job 更惨。

RR 换了一条路，用固定的 Time Quantum 轮流跑，Response 和 Fairness 很好，但 Turnaround 可能变差，Quantum 太小 Switch 爆炸、太大又退化回 FIFO。MLFQ 干脆用多级 Dynamic Priority Queue，根据 Runtime Behavior 猜 Process 类型，让 Interactive 留在高层、CPU-bound 逐渐下沉，再用 Priority Boost 防 Starvation、用 CPU Allotment 防 Gaming。

另外要记得，前面所有算法都把每个 Process 当作独立个体，所以当 Process 数量成为武器时，Fair Share 就把公平的单位提升到 User / Group；而当“每个 Job 应该拿多少”不想精确计算时，Lottery Scheduling 用 Ticket 的概率来实现长期 Proportional Share。到了 Multicore，问题进一步从“谁运行？”变成“谁运行，而且在哪颗 Core 运行？”。Single Queue 简单，但是有 Shared Queue Contention 和 Cache Affinity 问题；Multi Queue 改善 Scalability 和 Cache Locality，却产生 Load Imbalance，于是再通过 Work Stealing 重新平衡。

Chapter 4: 进程调度