参考：调度算法对比、计算模板与易错点
基于通用操作系统概念 · 核于 2026-08
速查
- CPU 调度：在就绪进程间分配 CPU——调度器选进程（策略），分发器切上下文（机制）。
- 抢占式 vs 非抢占式：抢占式可强抢 CPU（响应好但开销大，现代通用 OS 用）；非抢占式靠进程自愿让出（简单但有死循环风险，协程用）。
- 五种算法：FCFS（先来先服务，公平但护航效应）、SJF（短作业优先，平均等待最优但饥饿）、RR（轮转，交互响应最优）、优先级（按优先级，低优先级饥饿需老化）、MLFQ（多级反馈，自适应，现代 OS 鼻祖）。
- 三大指标：等待时间（= 开始 − 到达，非抢占）、周转时间（= 完成 − 到达）、响应时间（= 首次调度 − 到达）。
- 护航效应：FCFS 下长作业先到拖累所有短作业，平均等待暴涨。
- 饥饿与老化：SJF/优先级下某些进程永远等不到 CPU；老化随等待时间提升优先级解决。
- 时间片：RR 经验值 10-100ms，应远大于上下文切换时间（μs 级），过大退化为 FCFS。
- CPU vs IO 密集型：CPU 密集型偏好长时间片（少切换），IO 密集型偏好短时片频切换（高并发）。
- Linux CFS：用 vruntime + 红黑树实现"完全公平"，是 MLFQ 思想的现代演进。
一、五种算法对比大表
| 算法 | 抢占 | 选择依据 | 平均等待 | 响应 | 公平 | 饥饿 | 预估需求 | 复杂度 | 适用 |
|---|---|---|---|---|---|---|---|---|---|
| FCFS | 否 | 到达顺序 | 差（护航效应） | 差 | 顺序公平 | 无 | 无 | O(n) 队列 | 批处理、CPU 密集 |
| SJF | 否 | 突发时间最短 | 最优 | 差 | 不公平 | 有（长作业） | 需预估 | O(n log n) 排序 | 批处理 |
| SRTF | 是 | 剩余时间最短 | 比 SJF 更优 | 中 | 不公平 | 严重 | 需预估 | O(n) 优先队列 | 批处理 |
| RR | 是 | 时间片轮转 | 中 | 最优 | 绝对公平 | 无 | 无 | O(n) 队列 | 分时、交互式 |
| 优先级 | 可选 | 优先级数字 | 看分布 | 中 | 不公平 | 有（低优先级） | 需设优先级 | O(n) 优先队列 | 实时、关键任务 |
| MLFQ | 是 | 多队列+反馈 | 较优 | 好 | 动态公平 | 需老化防 | 无需（自适应） | O(队列数) | 现代通用 OS |
二、性能指标计算模板
通用步骤（任何算法）：
- 画甘特图：横轴时间，标注每个进程的运行段（抢占式会有多段）。
- 列表：每个进程的到达时间、突发时间、（从甘特图读）开始时间、完成时间。
- 算单项：
- 等待 = 完成 − 到达 − 突发（通用，抢占式也适用）；非抢占式简化为 开始 − 到达。
- 周转 = 完成 − 到达。
- 响应 = 首次调度 − 到达。
- 平均：求和 / 进程数。
FCFS 示例（P1 到达 0 突发 24，P2 到达 0 突发 3，P3 到达 0 突发 3）：
甘特图：|P1(0-24)|P2(24-27)|P3(27-30)|
平均等待 = (0 + 24 + 27)/3 = 17 ← 护航效应（短作业等了 24/27）SJF 示例（同上进程）：
顺序：P2(3)→P3(3)→P1(24) （按突发升序）
甘特图：|P2(0-3)|P3(3-6)|P1(6-30)|
平均等待 = (3 + 0 + 6)/3 = 3 ← 远优于 FCFS 的 17RR 示例（同上，q=4）：
轮转：P1(4)→P2(3)→P3(3)→P1(4)→P1(4)→P1(4)→P1(4)→P1(4)
甘特图：|P1(0-4)|P2(4-7)|P3(7-10)|P1(10-14)|P1(14-18)|P1(18-22)|P1(22-26)|P1(26-30)|
平均等待 = (P1:6 + P2:4 + P3:7)/3 = 5.67
平均响应 = (0 + 4 + 7)/3 = 3.67 ← RR 响应最优三、调度器与分发器对比
| 维度 | 调度器（Scheduler） | 分发器（Dispatcher） |
|---|---|---|
| 层次 | 策略（选谁） | 机制（怎么交接） |
| 职责 | 从就绪队列选下一个进程 | 把 CPU 控制权交给选中进程 |
| 输入 | 就绪队列 + 算法 | 选中进程的 PCB |
| 输出 | 选中进程 | 进程在 CPU 上运行 |
| 开销 | 决策（遍历/排序，O(n)~O(log n)） | 上下文切换（保存/恢复寄存器，μs 级） |
| 可换 | 算法可换（FCFS↔CFS） | 机制稳定（少改） |
| 代表 | schedule() 函数（Linux） | switch_to() 宏（Linux） |
四、CPU 密集型 vs IO 密集型对比
| 维度 | CPU 密集型 | IO 密集型 |
|---|---|---|
| 突发特点 | 长（连续算） | 短（算一下就 IO） |
| 时间片偏好 | 长（少切换） | 短而频（快响应） |
| 调度优先级 | 一般较低（Linux CFS 看 vruntime） | 一般较高（照顾交互） |
| 系统角色 | 吞吐瓶颈 | 并发度提升者 |
| 调度策略 | FCFS/SJF/低优先级长队列 | RR/高优先级短队列（MLFQ 顶层） |
| 例子 | 编译、编码、计算 | 编辑器、浏览器、shell |
五、易错点清单
- "FCFS 最公平"：错。FCFS 是顺序公平（先来先得），但结果不公平——护航效应让短作业被长作业拖累。RR 才是绝对公平（每进程等量时间片）。
- "SJF 总是最优"：SJF 在平均等待/周转时间最优，但响应时间差（短作业前的长作业要先做完），且有饥饿。RR 响应最优。
- "RR 时间片越小越好"：错。时间片太小切换开销占比过高（CPU 光切换不干活），CPU 利用率低。经验值 10-100ms，应远大于上下文切换时间。
- "RR 时间片越大吞吐越高"：q→∞ 退化为 FCFS，吞吐未必高（护航效应）。需平衡。
- "抢占式一定比非抢占式好"：错。抢占式响应好但有切换开销和竞态（需同步），非抢占式简单无竞态。协程用非抢占式是有意为之。
- "优先级数字越大优先级越高"：约定不同——Unix/Linux 数字越小优先级越高（nice 值 -20 最高），Windows 数字越大优先级越高。做题要看题意。
- "老化就是降低优先级"：反了。老化是提升等待久的进程的优先级（让它能被执行），消除饥饿。
- "MLFQ 不会饥饿"：错。无老化时，低优先级队列被高优先级源源抢占会饥饿。现代 MLFQ 加定期优先级提升防饥饿。
- "等待时间 = 开始 − 到达"：仅非抢占式成立。抢占式（RR/SRTF）进程被切多段，等待 = 完成 − 到达 − 突发（周转减实际运行）。
- "调度器和分发器是一回事"：错。调度器是策略（选谁），分发器是机制（怎么切上下文）。
- "CFS 是 RR"：不完全。CFS 借鉴 RR 的公平思想，但用 vruntime + 红黑树实现"按权重完全公平"，比 RR 的固定时间片更精细。
- "CPU 密集型进程应给短时间片"：反了。CPU 密集型应给长时间片减少切换开销；IO 密集型给短时间片提升并发。
- "非抢占式下时间片到就调度"：错。非抢占式不抢占，进程自愿让出（IO/结束）才调度。时间片到抢占是抢占式的特征。
- "SJF 能实际用"：实际很难——进程的 CPU 突发时间事先不知道，需用指数加权平均预估，估错则性能退化。所以实际系统多用 MLFQ/CFS（自适应无需预估）。