1. CFS 调度器概述
1.1 CFS 的设计哲学
完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核 2.6.23 版本引入的默认调度器，由 Ingo Molnár 设计实现。其核心设计哲学可以概括为：“模拟理想、精确的多任务 CPU”。
CFS 摒弃了传统调度器基于固定时间片和优先级队列的“时间片轮转”模型，转而采用基于“虚拟运行时间”（vruntime）的模型。它试图让每个可运行的任务都能获得处理器时间的“公平份额”，而不是简单地给每个任务分配一个固定的时间片。
核心思想： 如果系统中有 N 个可运行的任务，CFS 的理想目标是让每个任务都获得 1/N 的处理器时间。当任务数量变化时，CFS 会动态调整每个任务的运行时间，以维持这种公平性。
1.2 核心目标
CFS 的设计围绕以下几个关键目标展开：
- 公平性（Fairness）： 确保所有可运行的任务在统计意义上获得与其权重成比例的 CPU 时间。
- 交互性（Interactivity）： 对 I/O 密集型任务（如键盘输入、鼠标移动）给予快速响应，避免系统“卡顿”。
- 低延迟（Low Latency）： 减少调度延迟，特别是对于需要快速响应的任务。
- 可扩展性（Scalability）： 在多核、多处理器系统上高效运行，支持大量任务。
- 复杂度可控（Complexity Control）： 调度操作（如选择下一个运行的任务）的时间复杂度为 O(log N)，其中 N 是任务数量。
1.3 CFS 与 O(1) 调度器的区别
O(1) 调度器是 Linux 2.6.0 至 2.6.22 版本的默认调度器。CFS 在多个方面对其进行了根本性的改进。下表详细对比了两者的核心差异：
| 对比维度 | O(1) 调度器 | CFS 调度器 |
|---|---|---|
| 核心模型 | 基于固定时间片 + 优先级数组（active/expired） | 基于虚拟运行时间（vruntime）的公平队列模型 |
| 数据结构 | 每个优先级一个链表（140个优先级队列） | 红黑树（Red-Black Tree），以 vruntime 为键值 |
| 时间复杂度 | O(1) 常数时间（选择任务和入队） | O(log N)（红黑树插入、删除、查找最左节点） |
| 时间片分配 | 静态、固定的时间片（由优先级决定） | 动态、按权重比例分配（目标延迟 / 任务数） |
| 交互性处理 | 启发式“交互性”评分，复杂且易出错 | 通过睡眠时间补偿（增加 vruntime）自然实现 |
| 优先级映射 | nice 值直接映射到时间片长度 | nice 值映射为权重（weight），影响 vruntime 增长速率 |
| 负载均衡 | 基于负载统计的周期性均衡 | 基于“调度域”和“负载权重”的精细均衡 |
面试要点： 面试官常问“为什么 CFS 要放弃 O(1) 调度器？” 核心原因在于 O(1) 调度器的交互性启发式算法过于复杂且不可靠，而 CFS 通过 vruntime 模型优雅地解决了这个问题。此外，O(1) 调度器在多核扩展性和大型服务器场景下表现不佳。
1.4 CFS 调度器核心架构图
下图展示了 CFS 调度器的核心组件及其工作流程。每个 CPU 都有一个自己的运行队列（cfs_rq），其中包含一棵红黑树。调度器通过选择红黑树中最左侧的节点（即 vruntime 最小的任务）来获得下一个运行的任务。
1.5 CFS 工作流程简述
CFS 的调度循环可以概括为以下几个步骤：
- 时钟中断触发： 周期性时钟中断（tick）调用
scheduler_tick()函数。 - 更新当前任务：
update_curr()函数更新当前正在运行的任务的vruntime，增加其值。 - 检查是否需要抢占： 如果当前任务的
vruntime超过了红黑树中最左节点的vruntime，则设置重新调度标志（TIF_NEED_RESCHED）。 - 选择下一个任务： 在调度点（如系统调用返回、中断返回），
pick_next_task_fair()从红黑树中选择vruntime最小的任务（最左节点）。 - 上下文切换： 执行
context_switch()，保存当前任务状态，恢复新任务状态，开始运行新任务。
常见误解： CFS 并不是“完全公平”到让每个任务都获得完全相同的 CPU 时间。它通过权重（weight）机制实现了“按比例公平”。高优先级（低 nice 值）的任务具有更高的权重，其 vruntime 增长更慢，从而获得更多的 CPU 时间。这是下一节“权重计算”的核心内容。