在 Linux 内核面试中，进程调度器是一个绕不开的高频考点。自 2.6.23 版本引入以来，CFS（Completely Fair Scheduler，完全公平调度器） 取代了此前的 O(1) 调度器，成为 Linux 默认的普通进程调度算法。面试官常常会从设计理念问到具体实现，尤其是 vruntime 的计算方式。本文将从核心思想出发，逐步拆解 CFS 的关键机制，并给出 vruntime 的完整计算逻辑，帮助你在面试中从容应对。
一、为什么需要 CFS？
在 CFS 出现之前，Linux 使用 O(1) 调度器。它虽然能在常数时间内完成调度决策，但存在一个根本问题：公平性难以保证。O(1) 调度器依赖优先级数组和复杂的启发式规则，导致交互式进程和 CPU 密集型进程之间的平衡不够理想，用户常感觉系统“卡顿”。
CFS 的设计目标非常明确：让每个进程都能获得公平的 CPU 时间份额。这里的“公平”不是绝对平均，而是按权重分配——权重越大的进程，获得的 CPU 时间比例越高。CFS 不再使用固定时间片，而是追踪每个进程已经运行了多久，并总是选择“运行最少”的那个进程来执行。
二、CFS 的核心思想
CFS 的核心可以概括为一句话：维护一个以 vruntime 为键的红黑树，每次选择 vruntime 最小的进程运行。
具体来说：
- 虚拟运行时间（vruntime）：每个进程都有一个 vruntime，它表示该进程已经消耗的 CPU 时间，但经过了权重调整。权重高的进程 vruntime 增长慢，权重低的进程 vruntime 增长快。
- 红黑树（rb-tree）：所有可运行进程按 vruntime 排序，存放在一棵红黑树中。最左侧节点就是 vruntime 最小的进程，也就是下一个应该被调度的进程。
- 调度时机：当进程被唤醒、时间片用完或主动让出 CPU 时，调度器会更新其 vruntime，然后重新插入红黑树，并选择最左侧节点运行。
- 时间片动态计算：CFS 没有固定时间片，而是根据进程权重和调度延迟（
sched_latency）动态计算每个进程应运行的时间。
这种设计使得 CFS 在大多数场景下都能提供良好的公平性和交互响应速度。
三、vruntime 的计算公式
vruntime 是 CFS 的灵魂。它的计算公式如下：
vruntime += delta_exec * (NICE_0_LOAD / weight)
其中：
delta_exec：进程本次实际运行的物理时间（纳秒）。NICE_0_LOAD：nice 为 0 的进程权重，通常为 1024。weight：当前进程的权重，由 nice 值映射而来。
这个公式的含义是：实际运行时间相同的情况下，权重越大的进程，vruntime 增长越少。因此，高权重进程在红黑树中更容易处于左侧，从而获得更多调度机会。
权重与 nice 值的映射
Linux 内核维护了一个 prio_to_weight 数组，将 nice 值（-20 到 19）映射为权重。nice 值每降低 1（优先级提高），权重约增加 25%。例如：
| nice 值 | 权重 |
|---|---|
| -20 | 88761 |
| -10 | 9548 |
| 0 | 1024 |
| 10 | 110 |
| 19 | 15 |
可以看到，nice 为 -20 的进程权重是 nice 为 0 的约 86 倍，是 nice 为 19 的约 5900 倍。这意味着在相同物理运行时间下，高优先级进程的 vruntime 增长极慢，从而获得远超低优先级进程的 CPU 份额。
四、vruntime 计算实例
假设系统中有两个进程 A 和 B：
- 进程 A：nice = 0，权重 = 1024
- 进程 B：nice = 10，权重 = 110
两者都运行了 10ms 的物理时间。根据公式：
- A 的 vruntime 增量 = 10ms × (1024 / 1024) = 10ms
- B 的 vruntime 增量 = 10ms × (1024 / 110) ≈ 93.09ms
结果非常明显：B 的 vruntime 增长远快于 A。在红黑树中，A 会长期处于左侧，获得更多 CPU 时间。这正是 CFS 实现“按权重公平”的方式。
五、调度延迟与时间片
CFS 中还有一个重要概念：调度延迟（sched_latency）。它表示一个调度周期内，所有可运行进程至少各运行一次的总时间。默认值通常为 6ms（可调）。
每个进程的时间片计算公式为：
time_slice = sched_latency * (weight / total_weight)
其中 total_weight 是所有可运行进程的权重之和。如果进程数量过多，导致每个进程的时间片小于最小粒度（min_granularity，通常为 0.75ms），则 CFS 会调整调度延迟，保证每个进程至少运行 min_granularity 的时间。
六、面试常见追问
1. vruntime 会溢出吗？
会。vruntime 是 64 位无符号整数，理论上会溢出，但实际中几乎不可能达到。内核通过 sched_vslice 和 min_vruntime 等机制进行补偿，确保公平性。
2. 新进程的 vruntime 初始值是多少？
新进程的 vruntime 通常初始化为当前红黑树中最小 vruntime 减去一个偏移量，或者直接设为 min_vruntime，以保证新进程不会被饿死，也不会立刻抢占过多 CPU。
3. CFS 如何处理睡眠进程？
进程睡眠时，其 vruntime 保持不变。当它被唤醒时，如果 vruntime 远小于当前 min_vruntime，内核会将其 vruntime 调整为 min_vruntime - 补偿值，防止睡眠进程醒来后长时间霸占 CPU。
4. CFS 是实时调度器吗？
不是。CFS 只负责普通进程（SCHED_NORMAL 和 SCHED_BATCH）。实时进程由 SCHED_FIFO 和 SCHED_RR 调度器处理，优先级始终高于 CFS。
七、总结
CFS 的核心思想可以浓缩为：用 vruntime 衡量进程的“应得 CPU 时间”，用红黑树快速找到最该运行的进程。vruntime 的计算公式 delta_exec * (NICE_0_LOAD / weight) 是理解 CFS 公平性的关键。掌握这些内容，不仅能应对面试中的基础问题，还能深入讨论调度延迟、权重映射、睡眠补偿等高级话题。
在面试中，建议先讲清楚设计目标，再展开 vruntime 的计算逻辑，最后用具体数值举例说明。这样既有理论高度，又有实践细节，能给面试官留下深刻印象。
未经允许不得转载：任鹏个人博客 » Linux 面试题：进程调度器 CFS 的核心思想与 vruntime 计算
