Theory · OS · CPU Scheduling
从 FCFS/RR 到 MLFQ，再到 Linux 的 CFS 与 EEVDF —— 公平、延迟与吞吐的三方拉扯
每个算法都有一个致命缺陷，而下一个算法正是为修它而生：护航效应 → 短作业优先 → 饥饿 → 老化
调度类分层：实时类永远压过公平类；fair 类 2007 年用 CFS 的 vruntime 实现公平，6.6 起交给 EEVDF 表达延迟
GMP 是用户态的 MLFQ 变体：work stealing 求公平、sysmon 抢占防独占、netpoller 让 I/O 等待不占线程
The Scheduling Problem
就绪的进程数 > CPU 核数，CPU 必须在进程间时间复用（配合时钟中断的抢占）。调度器决定"下一个 CPU 给谁、给多久"——这是内核最热路径上的策略代码。
① 进程阻塞（等 I/O / 锁）或退出；② 时间片耗尽（时钟中断）；③ 更高优先级进程就绪（抢占）；④ I/O 完成唤醒。前两类是主动可预期的，后两类是事件驱动的。
CPU 密集型（编译、科学计算）：吃满时间片，在乎总完成时间；I/O 密集型（Web 服务、代理）：频繁阻塞让出，在乎单次响应延迟。真实系统永远是混合负载。
| 指标 | 定义 | 在乎它的是 |
|---|---|---|
| 周转时间 | 完成时刻 − 到达时刻 | 批处理 / 吞吐 |
| 响应时间 | 首次被调度 − 到达时刻（延迟） | 交互式 / 在线服务 |
| 吞吐量 | 单位时间完成任务数 | 后端系统容量 |
| 公平性 | 资源按权重 / 按需分配 | 多租户 / 防饥饿 |
FCFS · SJF · RR · Priority
| 算法 | 做法 | 优点 | 缺陷（= 下一算法的动机） |
|---|---|---|---|
| FCFS | 先来先服务的 FIFO 队列，非抢占 | 实现最简单，无饥饿 | 护航效应：一个长任务堵住后面所有短任务，平均周转崩坏 |
| SJF / SRTF | 优先跑（剩余）时间最短的；SRTF 是其抢占版 | 平均周转时间理论最优 | 需要预知未来（只能估计运行时长）；长任务饥饿 |
| RR | FIFO + 时间片 q，到点强制轮转 | 响应时间好，公平且无饥饿 | q 的两难：太大退化成 FCFS，太小切换开销吃掉 CPU |
| 优先级 | 按优先级挑最高者（可抢占） | 能表达重要性，实时场景必需 | 低优先级饥饿 → 老化 aging（等待越久提权越多）；还要防优先级反转 |
经验法则：上下文切换开销控制在 <1%——即切换成本（约 μs 级）相对 q 可忽略。Linux 的思路更进一步：由调度器按就绪任务数动态决定每次跑多久（CFS 的 sched_latency / min_granularity，EEVDF 的 slice），而不是固定 q。
Multi-Level Feedback Queue
Scheduling Classes
Completely Fair Scheduler · 2.6.23–6.5
理想多任务：每个任务同时平分 CPU。CFS 追踪每个任务的虚拟运行时间 vruntime——"最亏待的任务"（vruntime 最小）下一个上 CPU。公平 = 让所有任务的 vruntime 尽量同步增长。
vruntime += Δt × (NICE_0_LOAD / weight)。nice 0 的任务按真实速度走；nice 更低的任务权重大、vruntime 涨得慢（同样真实时间"折算"得少），于是能多占 CPU——权重的相对关系是 每差 1 档 nice，份额差约 1.25 倍。
按 vruntime 排序的红黑树：挑最左节点（最小 vruntime）O(log n)，缓存 leftmost 指针后近似 O(1)；跑完插回树里。就绪队列 = 每核一棵 cfs_rq。
// 教科书版的 CFS 心跳（简写） pick_next(): return rb_leftmost(cfs_rq) // vruntime 最小 // tick / 抢占点： curr->vruntime += delta × NICE_0_LOAD / curr->weight if leftmost(cfs_rq)->vruntime < curr->vruntime: resched // 被人亏待得更多 → 换人 // 新任务防捣乱： vruntime_new = max(min_vruntime, // 不许比谁都小 vruntime_new - sched_latency)
Earliest Eligible Virtual Deadline First · 6.6+
① lag（滞后量）：应得时间 − 实得时间。正 lag = 被亏待，负 lag = 多吃了。
② eligible（合格）：lag ≥ 0 才有资格上 CPU——多吃的任务先还债。
③ 虚拟截止期限：eligible_time + 时间片。调度规则一句话：合格者中，虚拟截止期限最早者优先。
任务的 slice 由 latency-nice 决定：想要低延迟 → 短时间片 → 截止期限更近 → 更先被调度。相同 nice 的任务总份额不变，只是"切得更碎、给得更快"。公平性由 lag 机制天然保证。
算法出自 1995 年论文，Peter Zijlstra 实现，Linux 6.6（2023-10）成为 fair 类默认。动机：删掉 CFS 时代成堆的脆弱启发式，"用更明确的策略替代猜测"；初步基准显示延迟一致性更好。
| 对比 | CFS | EEVDF |
|---|---|---|
| 公平实现 | vruntime 同步增长 | lag ≥ 0 才合格（等价公平） |
| 挑谁 | vruntime 最小者 | 合格者中虚拟截止期限最早者 |
| 延迟表达 | 无（靠启发式补丁） | latency-nice → slice → deadline |
| 数据结构 | 红黑树（vruntime 序） | 红黑树 ×2（按 eligible / deadline 两棵） |
| 地位 | 2.6.23–6.5 | 6.6+ 默认 |
RT Scheduling · Priority Inversion
SCHED_FIFO：同级不轮转，跑到阻塞或被更高优先级抢占；SCHED_RR：同级时间片轮转；SCHED_DEADLINE：任务声明 (runtime, deadline, period) 三元组，EDF + CBS 带宽预留，理论上可证明按时完成。
高优先级 H 等 L 持有的锁；L 又被中优先级 M 抢占 → H 间接被 M 卡住（优先级序完全颠倒）。1997 年火星车 Mars Pathfinder 在火星上反复重启，就是这种三体反转：最终靠远程启用互斥锁的优先级继承修复。
① 优先级继承：H 等 L 的锁时，L 临时继承 H 的优先级，尽快跑完临界区；② 优先级天花板：锁的优先级 = 所有潜在持有者的最高级，持锁即提权。Linux futex 的 FUTEX_LOCK_PI 与 Go 的 sync 均内置类似思路。
Go Runtime as a Scheduler
就绪队列：P 本地队列（无锁快路径）+ 全局队列（256 批量转移）；work stealing：本地空了就从别的 P 偷一半——分布式版本的负载均衡；抢占：sysmon 后台线程发现 G 运行超时（>10ms 量级）打抢占标志，1.14 起配合异步抢占信号，死循环不再拖死 P；I/O 让出：netpoller 把网络等待变成调度事件，不占 M。
① 无 nice/权重：Go 假设所有 goroutine 同等重要，公平靠队列顺序 + 抢占；② 协作优先：切换点在函数调用插入的检查点，代价远小于内核抢占；③ 调度对象超轻：gobuf 只有 PC/SP 等几个字段，vs task_struct 的庞大现场。
内核调度的切换成本（μs）对"百万并发"不可接受；且内核不知道"G 在等 channel"这类语言级语义。把调度搬进 runtime，语言才有 channel/defer/panic 的原语级配合——与第 7 页 EEVDF 的理念一致：调度策略要让需求方可表达。
| 调度要素 | 内核（CFS/EEVDF） | Go runtime |
|---|---|---|
| 调度对象 | task（进程/线程） | goroutine（G） |
| 公平度量 | vruntime / lag | 队列位置 + 抢占时限 |
| 抢占 | 时钟中断 + 抢占点 | 函数调用检查点 + sysmon 信号 |
| 负载均衡 | per-CPU 队列 + 周期均衡 | work stealing |
| I/O 等待 | 内核挂起任务 | netpoller 事件化 |
Interview QA · Part 1
按"缺陷链"答：FCFS 简单但有护航效应 → SJF 周转最优但要预知且饥饿 → RR 响应好在时间片两难 → 优先级能表达重要性但需 aging 防饥饿 → MLFQ 用历史预测未来 + boost 防饿。Linux 用调度类分层把公平与实时分开实现。
FCFS 下一个长任务把后面的短任务全堵住，像大货车护送车队。数字例子：100s 长任务先到，10 个 1s 短任务随后，短任务平均等 50s+；反过来先跑短任务平均只等约 6s。这就是 SJF/MLFQ 的动机。
太大退化成 FCFS（响应差）；太小则上下文切换开销占比过高（吞吐差）。经验：切换开销 <1%，量级在毫秒到几十毫秒。Linux 不用固定时间片：按就绪任务数动态切分目标延迟（CFS），或按 latency-nice 决定 slice（EEVDF）。
非抢占（协作式）：任务跑到主动让出才切换，一个死循环能拖死系统；抢占式：内核靠时钟中断随时收回 CPU。现代 OS 都是抢占式，代价是切换必须发生在内核态（中断 → schedule → context_switch）。
高优先级等低优先级持有的锁、低优先级又被中优先级抢占，形成倒挂。解法：优先级继承（持锁者临时继承等待者优先级）或优先级天花板（持锁即提权）。火星车 Pathfinder 是标准案例。
静态优先级/短作业优先策略下，低优先级或长任务永远排不上。避免：aging 老化（等待越久优先级越高）、MLFQ 的周期 boost、公平调度（CFS/EEVDF 的 vruntime/lag 机制天然防饿——亏待者终会被优先补偿）。
Interview QA · Part 2
vruntime = 真实运行时间 × (NICE_0_LOAD / 权重)，nice 越低权重越大、vruntime 涨越慢；调度永远挑 vruntime 最小（最亏待）者，红黑树 O(log n) 定位最左节点。1 档 nice 份额差约 1.25 倍。新任务 vruntime 钳位到 min_vruntime 防捣乱。
nice ∈ [-20, 19] 只在 fair 调度类内生效，映射到权重（0 → 1024）。它决定的是份额比例而非绝对时间；每差 1 档约 1.25 倍，两端差约 6000 倍。实时任务的优先级与 nice 无关（不同调度类）。
公平性等价（lag ≥ 0 才合格 vs vruntime 最小者），新增延迟表达：latency-nice 决定 slice，虚拟截止期限 = eligible + slice，最早 deadline 先跑。换它的动机是删掉 CFS 的脆弱启发式补丁、延迟表现更一致。Linux 6.6（2023-10）默认启用。
调度类是优先级链：stop → deadline → RT(FIFO/RR) → fair(CFS/EEVDF) → idle，pick_next_task 自上而下。实时优先级 1–99 永远压过 nice；内核用 rt_throttled（默认 95% 配额）防实时任务把 CPU 吃穿。
MLFQ 直觉的用户态实现：本地队列快路径 + work stealing 负载均衡 + sysmon 10ms 量级抢占防独占 + netpoller 让 I/O 等待事件化。区别：无 nice/权重（所有 G 平等）、切换在用户态只存 PC/SP（几十 ns）、调度对象与内核线程解耦（M:N）。
调度类严格分层，fair 类只有实时类全空才轮得到——一个 SCHED_FIFO 90 死循环理论能独占 CPU。兜底：rt_throttled 限制实时总配额（默认 95%）、SCHED_DEADLINE 的 CBS 带宽预留强制任务不超过声明的 runtime。
Related & References
操作系统总览 →（时钟中断与上下文切换的机制基础）
进程线程协程 →（调度对象的状态与切换成本）
同步与互斥 →（优先级反转的另一面：锁）
I/O 模型与 epoll →（阻塞唤醒与 netpoller 的内核侧）
GMP 调度模型 →（用户态调度的完整源码版）
sync 并发原语 →（mutex 饥饿模式与 futex）
Redis 线程模型 →（单线程事件循环为什么不需要调度器）
参考来源（本 deck 结论可溯源至下列一手材料）
| OSTEP ch.9–10（Scheduling） | FCFS/SJF/RR/MLFQ 的指标分析与规则口径 |
| LWN: The EEVDF CPU scheduler（lwn.net/Articles/925371） | lag / eligible / virtual deadline 定义与替换 CFS 的动机 |
| kernel Documentation/scheduler（sched-design-CFS / sched-eevdf） | vruntime 公式、nice 权重表、调度类层级 |
| Mars Pathfinder 事后报告（Mike Jones 整理） | 优先级反转真实案例与优先级继承修复 |
| Go src/runtime/proc.go / sysmon（本机 Go 版本） | work stealing、retake 抢占、netpoll 与调度的配合 |
| xiaolincoding.com《图解系统》schedule.html | 调度/页面置换/磁盘调度算法的中文综述 |