CPU 调度算法：FCFS、SJF、RR 与 MLFQ
CPU 调度器从就绪队列中选择下一个获得处理器的进程；经典算法谱系（FCFS、SJF、RR、优先级、MLFQ）是在周转时间、响应时间与公平性之间的不同取舍。
一句话定义
CPU 调度器从就绪队列中选择下一个获得处理器的进程；经典算法谱系（FCFS、SJF、RR、优先级、MLFQ）是在周转时间、响应时间与公平性之间的不同取舍。
为什么重要
调度器决定"谁在何时用 CPU"，直接塑造系统的手感：批处理看吞吐，交互系统看响应，服务器看尾延迟（kp-031）。它是操作系统中最典型的"指标驱动设计"，也是面试与论文中最常出现的算法族。
前置知识
kp-005（就绪队列与状态机）；kp-006（切换成本约束时间片下限）。
核心概念
- 周转时间：完成时间 − 到达时间，批处理核心指标。
- 响应时间：首次获得 CPU 的时间 − 到达时间，交互系统核心指标。
- FCFS（先来先服务）：队列顺序执行，简单但受"护航效应"拖累。
- SJF/SRTF（最短作业优先/抢占版）：平均周转最优，但需要预知未来。
- RR（时间片轮转）：按时间片轮流，公平且响应好，时间片是关键参数。
- 优先级调度：按优先级选取，需防饥饿（老化/aging）。
- MLFQ（多级反馈队列）：多队列 + 观测行为动态调级，无需先验知识。
- CFS（完全公平调度器）：Linux 的实践答案，用虚拟运行时间逼近理想公平。
原理与机制
用同一组作业对比三个算法（到达顺序 A(0,8ms)、B(1,4ms)、C(2,9ms)，格式：作业(到达, 时长)，时间片取 4ms）：
FCFS: |AAAAAAAABBBBCCCCCCCCC| 周转: A=8 B=11 C=20 平均=13.0
SJF : |AAAABBBBCCCCCCCCC....| 周转: A=8 B=11 C=20 (此例同序)
若 C 先到则 FCFS 平均暴涨为 16.7，SJF 仍保持最优 -> 护航效应
RR(4ms): |AAAA BBBB CCCC AA CC CC| 周转: A=17 B=13 C=20 平均=16.7, 但响应时间 A/B/C 全为 0~1 个时间片关键规律：FCFS 护航效应伤响应；SJF 理论最优但不可预知；RR 用小时间片买响应时间，但时间片小于切换成本（kp-006）就亏本。MLFQ 的解法是用历史预测未来：新任务进最高优先级队列；用满时间片者降级（疑似 CPU 密集），提前让出者留级（疑似交互）；周期性把所有任务抬回最高队列防饥饿。规则简单，却同时逼近了 SJF 的周转与 RR 的响应——这正是 Linux CFS 之前 BSD/Solaris 系调度器的思想骨架。
公式或模型
CFS 的理想公平模型：每个可运行任务按权重比例分享 CPU，用 vruntime += 实际运行时长 × (默认权重/该任务权重) 累计，调度器总是选择 vruntime 最小者，红黑树组织使选取为 O(log n)。
直观类比
RR 像幼儿园轮流玩滑梯（每人 30 秒，公平且都开心）；FCFS 像只有一个窗口的银行（前面一位办大额业务，全队陪等）；MLFQ 像驾校教练观察学员：总摸方向盘不松手的（CPU 密集）去慢车道，频繁看路况让车的（交互型）留快车道。
实例或案例
nice -n 10 cpu_burn & # 降低优先级运行
chrt -f 50 cpu_burn & # 实时 FIFO 策略（需权限）
taskset -c 0-3 stress-ng --cpu 4 # 限定核数观察调度行为
cat /proc/sys/kernel/sched_latency # 查看 CFS 调度周期（内核版本相关）常见误区
- 认为 RR 时间片越小越好：小于切换成本后 CPU 大量时间花在切换上，通常取切换成本的百倍量级（如 10ms 级）。
- 认为 SJF 不可实现就无意义：它是平均周转的理论下界，是评价一切实际调度器的标尺；CFS/MLFQ 都是在"无法预知未来"约束下逼近它。
- 混淆吞吐与响应：给交互任务让路常牺牲总吞吐，这是权衡不是 bug。
与其他知识点的关系
切换成本（kp-006）约束时间片下限；观测工具（kp-031）验证调度效果；多线程扩展现限（kp-032 的 Amdahl 定律）与调度器行为互相影响。
延伸阅读
《操作系统导论》调度章节对 MLFQ 的规则推演；《操作系统概念》第 5 章。
自测题
- 护航效应是什么，哪种算法最受害？
答：长作业先到导致后续短作业全部排队等待；FCFS 最受害，SJF 通过让短作业插队规避它。
- MLFQ 如何在不知道作业时长的情况下逼近 SJF？
答：用历史行为预测：短促让出 CPU 的任务保持高优先级（像交互任务），用满时间片的任务降级（像 CPU 密集任务），从而让短作业近似"最短优先"地先跑。
- 时间片轮转中时间片的选择要平衡哪两件事？
答：响应时间（片越小响应越快）与切换开销占比（片太小则切换成本失控），下限由上下文切换成本决定。