CPU 调度
概念
CPU 调度是操作系统内核的核心功能之一：当多个进程（或线程）同时处于就绪状态时，调度器决定下一个获得 CPU 时间片的是谁。
调度器分为两层：
- 长期调度器（作业调度器）：控制多少进程进入内存，影响系统并发度。
- 短期调度器（CPU 调度器）：从就绪队列中选出下一个要运行的进程，频率极高（毫秒级）。
调度时机：进程从运行态切换到等待态、就绪态，或进程终止时，调度器介入。
核心原理
1. 调度基本概念
抢占式 vs 非抢占式
| 类型 | 描述 | 代表算法 |
|---|---|---|
| 非抢占式 | 进程一旦获得 CPU，只有主动放弃（等待 I/O 或退出）才会让出 | FCFS、非抢占 SJF |
| 抢占式 | 调度器可在任意时刻强制剥夺当前进程的 CPU | RR、SRTF、优先级抢占 |
抢占式调度响应性更好，适合交互式和实时系统；但引入了上下文切换开销和竞态条件。
CPU 密集型 vs I/O 密集型
- CPU 密集型：大部分时间在做计算，I/O 少（如视频编码、矩阵运算）。
- I/O 密集型：频繁发起 I/O 请求，大部分时间在等待（如 Web 服务器、数据库查询）。
好的调度策略会优先调度 I/O 密集型进程，让其尽快发起 I/O，同时让 CPU 密集型进程在后台占满 CPU。
调度指标
| 指标 | 含义 |
|---|---|
| 周转时间（Turnaround Time） | 进程从提交到完成的总时间 |
| 等待时间（Waiting Time） | 进程在就绪队列中等待的累计时间 |
| 响应时间（Response Time） | 提交请求到首次得到响应的时间 |
| 吞吐量（Throughput） | 单位时间内完成的进程数 |
| CPU 利用率（CPU Utilization） | CPU 处于忙碌状态的时间比例 |
不同场景的优化目标不同：批处理系统追求吞吐量和周转时间；交互式系统追求响应时间；实时系统追求截止期满足率。
2. 经典调度算法
FCFS（先来先服务，First-Come First-Served）
按到达顺序排队，非抢占式。
示例：进程 P1（运行 24ms）、P2（3ms）、P3（3ms）按顺序到达。
| 进程 | 到达时间 | 运行时间 | 完成时间 | 周转时间 | 等待时间 |
|---|---|---|---|---|---|
| P1 | 0 | 24 | 24 | 24 | 0 |
| P2 | 0 | 3 | 27 | 27 | 24 |
| P3 | 0 | 3 | 30 | 30 | 27 |
平均等待时间 = (0 + 24 + 27) / 3 = 17ms
护航效应（Convoy Effect）：一个长进程阻塞后面所有短进程，导致整体性能下降。
SJF / SRTF（最短作业优先 / 最短剩余时间优先）
- SJF：非抢占，选择预计运行时间最短的进程。
- SRTF：抢占式版本，若新到进程的剩余时间更短，立即抢占当前进程。
理论上 SJF 给出最优平均等待时间，但实际问题在于：
- 无法准确预知运行时间（通常用历史均值指数平均估算）。
- 饥饿（Starvation）：长进程可能永远得不到 CPU，因为不断有短进程插入。
RR（时间片轮转，Round Robin）
每个进程分配固定时间片（quantum），时间片用完后强制切换到下一个就绪进程，循环执行。
时间片大小的权衡：
| 时间片过小 | 时间片过大 |
|---|---|
| 响应时间好 | 上下文切换开销小 |
| 上下文切换频繁，CPU 利用率下降 | 退化为 FCFS，响应时间差 |
经验值：时间片通常设为 10～100ms，上下文切换时间约 0.1ms，开销占比控制在 1% 以内。
优先级调度
每个进程附带优先级，调度器始终选择优先级最高的进程（可抢占或非抢占）。
问题：优先级反转（Priority Inversion）
高优先级进程 H 等待低优先级进程 L 持有的锁，而中优先级进程 M 抢占了 L，导致 H 间接被 M 阻塞。
解决方案：
- 优先级继承协议（Priority Inheritance Protocol, PIP）：L 持有锁期间临时继承 H 的优先级，阻止 M 插队。
- 优先级天花板协议（Priority Ceiling Protocol）：锁的优先级上限等于所有可能持有该锁的进程中最高优先级，获取锁时直接提升至该上限。
- 老化（Aging）：随时间推移逐渐提升低优先级进程的优先级，防止饥饿。
MLFQ（多级反馈队列，Multi-Level Feedback Queue）
综合了 RR 与优先级调度，是现代通用操作系统调度的基础思想。
规则：
- 多条队列，优先级从高到低，高优先级队列时间片短。
- 新进程进入最高优先级队列。
- 若一个进程用完时间片仍未完成，降级到下一优先级队列。
- 若一个进程在时间片内主动放弃 CPU（等待 I/O），保持当前优先级。
- 定期将所有进程提升到最高优先级（防止饥饿）。
效果：短进程（I/O 密集型）始终在高优先级队列获得快速响应；长进程（CPU 密集型）自然沉降到低优先级队列。无需提前知道运行时间，自适应性强。
调度算法对比表
| 算法 | 抢占性 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| FCFS | 非抢占 | 实现简单，公平 | 护航效应，平均等待时间长 | 批处理系统 |
| SJF | 非抢占 | 最优平均等待时间 | 需预知运行时间，长进程饥饿 | 批处理系统 |
| SRTF | 抢占 | 最优平均等待时间 | 切换开销大，饥饿 | 理论最优基准 |
| RR | 抢占 | 响应时间均匀，无饥饿 | 时间片设置敏感，上下文切换多 | 交互式系统 |
| 优先级 | 两者皆可 | 支持差异化服务 | 优先级反转，低优先级饥饿 | 实时 / 嵌入式 |
| MLFQ | 抢占 | 自适应，兼顾吞吐与响应 | 实现复杂，参数调优难 | 通用操作系统 |
3. Linux CFS（完全公平调度器）
Linux 内核（2.6.23+）的默认调度器，用于普通（SCHED_NORMAL/SCHED_BATCH）进程。
核心思想：不分配固定时间片，而是让每个进程获得等比例的 CPU 时间——即"完全公平"。
vruntime（虚拟运行时间）
每个进程维护一个 vruntime 值，表示该进程已经消耗的"加权虚拟时间"：
- ：实际运行时间。
weight：由 nice 值映射而来，nice 值越低（优先级越高），weight 越大，vruntime 增长越慢，因而获得更多 CPU 时间。
红黑树（Red-Black Tree）组织就绪队列
CFS 用红黑树按 vruntime 排序所有可运行进程，最左节点就是 vruntime 最小的进程，即下一个应该运行的进程。选择复杂度为 ，插入/删除同为 。
nice 值与权重映射
nice 值范围 -20（最高优先级）到 +19（最低优先级）。内核维护一张预计算的 prio_to_weight 表，相邻 nice 值之间权重比约为 1.25，使得 nice 值差 1 对应约 10% 的 CPU 时间差异。
为什么叫"完全公平"？
理想情况下，n 个权重相同的进程各获得 的 CPU 时间。CFS 通过不断调度 vruntime 最小的进程，使所有进程的 vruntime 趋于相等，在宏观上实现了按权重比例的公平分配。
4. 实时调度
硬实时 vs 软实时
| 类型 | 描述 | 示例 |
|---|---|---|
| 硬实时 | 必须在截止期内完成，错过即系统失效 | 汽车 ABS、飞控系统 |
| 软实时 | 尽量在截止期内完成，偶尔错过可接受 | 视频播放、音频流 |
Linux 实时调度策略
Linux 提供两种实时调度策略，优先级高于 CFS：
SCHED_FIFO：实时 FCFS，无时间片。进程一旦运行，除非主动放弃或被更高优先级进程抢占，否则一直运行。SCHED_RR：实时 RR，有时间片。时间片用完后，同优先级的实时进程间轮转。
实时优先级范围为 1～99（数字越大优先级越高），均高于所有普通进程（优先级为 0）。
优先级反转与优先级继承协议
Linux POSIX 互斥锁支持 PTHREAD_PRIO_INHERIT 属性，启用后实现优先级继承：当高优先级线程等待锁时，持锁的低优先级线程临时提升至高优先级，确保其尽快释放锁，避免中间优先级线程横插。
面试常问 & 怎么答
Q1：常见的 CPU 调度算法有哪些？各有什么优缺点？
先列举算法名称，再抓核心特点：FCFS 简单但有护航效应；SJF 理论最优但无法预知运行时间且有饥饿；RR 响应均匀但时间片选择敏感；优先级调度灵活但有优先级反转风险；MLFQ 综合最优，现代 OS 的基础。面试时重点展开 MLFQ 的设计思路（多队列 + 反馈降级 + 定期提升）和 RR 的时间片权衡，体现系统性思维。
Q2：Linux 用的是什么调度算法？CFS 是怎么工作的？
回答分三层：① 背景——Linux 2.6.23 引入 CFS 替代旧的 O(1) 调度器；② 核心机制——vruntime 记录加权虚拟时间，红黑树排序就绪队列，始终调度 vruntime 最小的进程；③ 公平性——nice 值通过 prio_to_weight 表映射权重，权重影响 vruntime 增长速率，从而按比例分配 CPU。能画出红黑树示意图或写出 vruntime 公式会加分。
Q3：什么是优先级反转？怎么解决？
先描述场景：高优先级进程 H 因等待低优先级进程 L 持有的共享资源而阻塞，中优先级进程 M 抢占 L，导致 H 间接等待 M——这就是优先级反转。然后给出解决方案：优先级继承协议（L 临时继承 H 的优先级）和优先级天花板协议（获锁时提升至预设上限）。可以提 Mars Pathfinder 真实案例（1997 年 NASA 火星探路者遭遇优先级反转导致系统重启），展示工程经验。
看到什么就先想到这类
| 关键词 / 场景 | 联想到 |
|---|---|
| 进程等待时间长、短进程被阻塞 | FCFS 护航效应 |
| 调度算法理论最优 | SJF/SRTF，但注意饥饿 |
| 交互式系统、响应时间均匀 | RR 时间片轮转 |
| 高优先级进程莫名阻塞 | 优先级反转，考虑优先级继承 |
| Linux 普通进程调度 | CFS + vruntime + 红黑树 |
| Linux 实时进程 | SCHED_FIFO / SCHED_RR，优先级 1～99 |
| 系统需要同时兼顾响应和吞吐 | MLFQ 多级反馈队列 |
| nice 值 / 进程优先级调整 | CFS 权重映射，影响 vruntime 增长速率 |