【操作系统百科】调度理论：为什么”完美调度器”不存在

“好调度器”是个伪命题——你总能构造一个场景让任何算法表现糟糕。调度器设计是在一堆互相冲突的目标里找折衷，而不是”最优化”。本文把教科书上的经典算法过一遍，讲清楚每个算法解决了什么、付出了什么。这是 C 子系列后续讨论 CFS、EEVDF、DEADLINE 的共同语言。

一、先看图：目标冲突三角

flowchart TB
    R[响应延迟<br/>latency] ---|互斥| T[吞吐<br/>throughput]
    T ---|互斥| F[公平<br/>fairness]
    F ---|互斥| R
    N[能耗 / 温度] --- R
    N --- T
    P[优先级尊重] --- F
    classDef g fill:#3fb95022,stroke:#3fb950,color:#adbac7;
    classDef w fill:#f0883e22,stroke:#f0883e,color:#adbac7;
    classDef b fill:#388bfd22,stroke:#388bfd,color:#adbac7;
    class R,T,F g
    class N w
    class P b

• 低延迟要求频繁抢占 → 上下文切换多 → 吞吐下降
• 严格公平要求等额时间片 → 关键路径被慢任务拖垮 → 延迟敏感任务变慢
• 高优先级插队 → 低优先级饥饿

任何”统一调度器”都是这些极端之间的插值。

二、批处理时代：FCFS、SJF、HRRN

FCFS（First-Come-First-Served）

先到先服务。唯一优点：实现简单。致命缺点：convoy effect——一个长任务卡在前面，后面全部等。

SJF / SRTF（Shortest Job First / Shortest Remaining Time First）

选执行时间最短的跑。理论最优（对平均等待时间而言）。不可实现：你不知道一个任务要跑多久。副作用：长任务饥饿。

HRRN（Highest Response Ratio Next）

响应比 = (等待时间 + 服务时间) / 服务时间。等得久的任务响应比变大，最终会被选中。缓解 SJF 饥饿。

这三者在现代交互式系统里都不能直接用，但思想留存——知道任务多长能跳过公平约束，这是后来 Linux sched_autogroup、容器 I/O 调度器做”长短任务分离”的起源。

三、分时时代：RR、MLFQ

RR（Round-Robin）

每任务固定 quantum（时间片），轮转。quantum 大 → 接近 FCFS；quantum 小 → 上下文切换开销占比大。

实现上就是 runqueue FIFO + timer。至今所有”交互式 OS”都以 RR 为起点。

MLFQ（Multi-Level Feedback Queue）

多条优先级队列，任务新入最高级；用完 quantum 没自愿让出 → 降级。I/O 后自动升级。

思想：用历史行为推测未来类型——I/O bound 任务短用 CPU，放高优先级保响应；CPU bound 任务长用，放低优先级不影响交互。

Solaris、早期 Linux O(1) 调度器、Windows 都是 MLFQ 家族。

缺点：可被”欺骗”——任务快用完 quantum 前主动 sleep 1μs → 永远升优先级。后来引入 aging、allotment 总时间 补丁。

四、公平时代：Fair-share、Lottery、Stride、CFS

Fair-share（UNIX 起源）

按用户 / 组分配”份额”。一个用户跑 100 个进程不会挤掉另一个用户单个进程。

Lottery Scheduling（Waldspurger 1994）

每任务有若干”彩票”，每次中奖者被调度。概率保证长期份额，短期有方差。简单、可组合（转让彩票 = 授权）。

Stride Scheduling（Waldspurger 1995）

lottery 的确定性版：每任务有 stride = N/tickets，当前 pass 最小者被选；选中后 pass += stride。无方差。

stride 是 CFS vruntime 的灵感源头。

CFS / vruntime（Linux 2.6.23 起，18 年主力）

“虚拟运行时间”——每 ns 真实运行对应 1/weight 的 vruntime 增量。选最小 vruntime 的跑。红黑树存所有 runnable。详见 C-20。

思想核心：vruntime 把”nice 级别 + 运行时间”统一成一个单维指标。

五、实时时代：RMS、EDF、CBS

RMS（Rate Monotonic Scheduling）

周期任务，周期短的优先级高。Liu & Layland 1973 证明：若总利用率 ≤ n(2^(1/n) - 1)（n→∞ 趋于 ln 2 ≈ 69%），RMS 可保证所有 deadline。

EDF（Earliest Deadline First）

每次选最近 deadline 的任务。单核 EDF 100% 利用率最优。

多核 EDF 难：全局 EDF 有 Dhall effect——小核心机组合下利用率可以任意低。实用上多用分区 EDF 或 BFS/GlobalEDF-变种。

CBS（Constant Bandwidth Server）

Abeni-Buttazzo 1998。给每个任务一个”带宽” (runtime, period)。超时消耗完即降级，不会干扰其他 deadline。

Linux SCHED_DEADLINE = EDF + CBS，详见 C-23。

六、多处理器扩展

单核调度是 P-hard 边界；多核更糟：

• 全局 (global) 调度：一个全局 runqueue，锁争用严重
• 分区 (partitioned)：每 CPU 一个队列，负载均衡是 offline / 周期性动作
• 聚簇 (clustered)：socket/NUMA 级全局，跨 socket 分区

Linux 当前是”分区为主 + 定期 migration”（C-24）。

七、调度相关的经典问题

7.1 Convoy / starvation

Convoy 是锁上的队伍效应——第一个释放锁的任务很快拿回来，让人觉得”轮转不公”。解法：queue lock（MCS）；见 H 子系列。

Starvation 是”永远被饿着”。所有非 FIFO 调度都要证明 有界等待 或 aging。

7.2 优先级反转（priority inversion）

低优先级任务 L 持锁 → 中 M 来抢 CPU → 高 H 要锁却等着 L，L 却被 M 挤着跑不了。1997 火星车 Pathfinder 就被这个坑。

解决：

• 优先级继承（PI）：L 持 H 要的锁时临时继承 H 的优先级
• 优先级天花板（PCP）：L 拿锁时即升到锁的天花板级

Linux PREEMPT_RT 的 rt_mutex 用 PI。详见 C-22、H-63。

7.3 Bufferbloat / 调度器版本

调度也有 bufferbloat：runqueue 太深 → 延迟大。CFS 的 sched_latency_ns 限制总”周期”——所有 runnable 应在 sched_latency_ns 内各跑一次。负载高时单任务分到的时间片收缩。

7.4 Gang scheduling

多线程要同时运行（spinlock 间等）。OS 层 gang scheduling 几乎没进主线 Linux（复杂、与公平性冲突）。用户态近似：sched_setaffinity + sched_yield + 协程。

八、调度的不可能定理们

• 无免费午餐：通用调度下任何算法都有 worst case 明显差于另一算法
• CFS 与实时冲突：CFS 保公平 → 无法保最坏延迟 → 实时任务必须用 SCHED_FIFO/RR/DEADLINE
• EDF 多核不可行性（精确 EDF-globally-optimal 是 NP-hard）
• 能量感知调度非凸：把任务挪到大核省的时间 vs 换核的迁移代价，需要在线估计

所以现代 Linux 用分层策略：

1. SCHED_DEADLINE（最高）→ CBS 限带宽 EDF
2. SCHED_FIFO/RR → 严格优先级
3. SCHED_NORMAL → EEVDF（6.6+）/ CFS
4. SCHED_BATCH → 非交互，长时间片
5. SCHED_IDLE → 仅在 CPU 空闲时跑

policy 和权重一起决定结果。

九、小结

• 调度是多目标折衷，不是最优化
• FCFS → RR → MLFQ → Fair share → CFS 是”交互式”一条线
• RMS → EDF → CBS 是”实时”一条线
• 多核让一切加难；Linux 用分区+迁移
• 优先级反转、饥饿、convoy 是永恒的陷阱

下一篇 C-20 走进 CFS 内部——看 vruntime、红黑树、sched_entity 如何把这套公平模型在内核里具体实现。

参考文献

• Arpaci-Dusseau, Operating Systems: Three Easy Pieces, Ch. 7-10
• Liu, C.L.; Layland, J.W. “Scheduling algorithms for multiprogramming in a hard-real-time environment.” JACM 1973
• Waldspurger, C.A.; Weihl, W.E. “Lottery scheduling” OSDI 1994；“Stride scheduling” MIT LCS 1995
• Abeni, L.; Buttazzo, G. “Integrating multimedia applications in hard real-time systems.” RTSS 1998
• Molnár, I. “CFS design notes”, Linux kernel docs
• Corbet, J. “Multiprocessor scheduling is hard.” LWN.net 2011（Dhall effect）

工具

• chrt —— 查看/设置 policy 与优先级
• schedtool —— 便捷 CLI
• taskset —— CPU affinity
• sched_setattr —— 设置 DEADLINE 参数

上一篇：cgroup v2：资源控制的统一模型 下一篇：CFS 内部：vruntime 与红黑树