Linux 6.6 完全公平调度器(CFS)深度解析

前言：为什么需要CFS？

在 CFS 出现之前，Linux使用的是 O(1) 调度器，它为每个优先级维护一个运行队列，并使用固定的时间片。这种方式虽然高效，但存在两个主要问题：不公平性：高优先级任务可以长时间独占CPU，低优先级任务可能“饿死”。交互性差：新唤醒的交互式任务（如点击鼠标）必须等待当前任务用完时间片才能运行，导致响应延迟。

CFS（Completely Fair Scheduler）应运而生，其核心目标是实现完全公平——让系统中的每个可运行任务都能获得相等的 CPU 时间份额，同时保证优秀的交互性能。

1. 概述：CFS的哲学与架构

核心思想：“给每个任务公平的CPU时间份额”。

CFS 抛弃了传统“时间片”的概念。它不关心一个任务能运行多久，而是关心一个任务已经运行了多久。为了衡量这个“运行了多久”，CFS引入了一个天才的概念：虚拟运行时间（vruntime）。

• 物理时间 vs 虚拟时间：

• 物理时间：任务在 CPU 上实际执行的真实时间。

• 虚拟时间：一个经过加权处理的时间。权重由任务的 nice 值决定。nice值越低（优先级越高），其权重越大，同样的物理时间转换成的虚拟时间就越短。

想象一下，CPU时间就像一块蛋糕。CFS的目标不是给每个人切同样大小的一块（固定时间片），而是确保每个人吃到的“满足感”（虚拟时间）是相同的。一个胃口小的人（高优先级任务）吃一小口就饱了（vruntime增长慢），而一个胃口大的人（低优先级任务）需要吃很多口才饱（vruntime增长快）。这样，大家在“满足感”上就是公平的。

数据结构：为了高效地找到那个“最饿”（即 vruntime 最小）的任务，CFS使用红黑树（Red-BlackTree）来组织所有可运行的任务。红黑树是一种自平衡的二叉搜索树，其插入、删除和查找操作的时间复杂度都是 O(log n)，这对于拥有大量进程的系统至关重要。

代码位置：CFS的主体实现在 kernel/sched/fair.c 文件中，这是一个庞大而复杂的文件，包含了从核心调度逻辑到负载均衡、带宽控制等高级特性的全部代码。

2. CFS核心概念

2.1 vruntime（虚拟运行时间）

vruntime 是 CFS 的灵魂。它是任务调度的唯一依据。

计算公式： delta_vruntime = (delta_exec * NICE_0_LOAD) / weight

其中：

• delta_exec：任务本次在 CPU 上运行的实际时间（物理时间）。

• weight：任务的权重，由 nice 值映射而来。

• NICE_0_LOAD是 nice=0 时的标准权重（值为1024）。 NICE_0_LOAD / weight 这个因子决定了物理时间到虚拟时间的转换速率。

解读：

• 对于nice=0的任务，weight = NICE_0_LOAD，所以 delta_vruntime = delta_exec。它的虚拟时间增长速度等于物理时间。

• 对于nice=-20（最高优先级）的任务，weight很大（88761），所以 delta_vruntime 非常小。这意味着它运行很长时间，vruntime也只增加一点点，在红黑树中会一直保持靠左的位置，从而获得更多的 CPU 时间。

• 对于nice=19（最低优先级）的任务，weight很小（15），所以 delta_vruntime 非常大。它运行很短时间，vruntime就会猛增，很快就会被移到红黑树的右边，从而减少 CPU 占用。

min_vruntime：这是 CFS 运行队列（cfs_rq）的一个关键字段。它代表了该队列中所有任务的 vruntime 的下界（通常是红黑树最左节点的vruntime）。它的作用是：

1. 防止任务饿死：当一个睡眠很久的任务被唤醒时，它的 vruntime 可能远小于当前的min_vruntime。如果直接把它插入红黑树最左边，它会立刻抢占 CPU 并运行非常久，这对其他任务不公平。因此，CFS会将新唤醒任务的 vruntime 设置为min_vruntime，让它从“公平起点”开始竞争。

2. 迁移任务的参考：在负载均衡时，用于计算跨 CPU 迁移任务的 vruntime 偏移量，以保证全局公平性。

2.2 红黑树调度队列

CFS 将所有处于 TASK_RUNNING 状态的任务，以其 vruntime 为键值，组织成一棵红黑树。

• 排序规则：vruntime小的任务在树的左侧，vruntime大的任务在右侧。

• 调度决策：CFS调度器总是选择红黑树最左边的节点（即 vruntime 最小的任务）来运行。这完美体现了“谁最饿，谁先吃”的公平原则。

• 操作：

  入队(enqueue_entity)：当一个任务变为可运行状态（如被唤醒），CFS会计算其合适的vruntime（通常为min_vruntime），然后将其插入红黑树的正确位置。

  出队(dequeue_entity)：当一个任务被阻塞或终止，它会从红黑树中被移除。

• 更新：任务每次被调度出去时，其 vruntime 会根据本次运行的物理时间进行更新，然后重新插入树中（实际上是在下次入队时体现）。

2.3 时间片计算

虽然CFS不依赖固定时间片，但它仍然需要一个目标延迟（targetedlatency）来决定何时检查是否需要切换任务，以保证良好的交互性。

• 基础时间片(sysctl_sched_base_slice)：默认为0.75ms。这是单个任务在一个只有两个可运行任务的系统中期望获得的最小时间片。

• 自适应缩放：为了在多核系统上保持良好的调度粒度，基础时间片会根据在线 CPU 的数量进行缩放。Linux 6.6 默认采用对数缩放方式。

• 公式：base_slice = 0.75ms * (1 + log2(number_of_cpus)) 

• 例子：在 8 核 CPU 上，base_slice = 0.75ms * (1 + 3) = 3ms。这意味着 CFS 会尝试让每个任务至少运行 3ms 才考虑切换，以减少上下文切换的开销。

这个计算出的时间片主要用于 task_tick_fair 函数中，判断当前运行的任务是否已经运行了足够长的时间，从而触发一次重新调度（resched_curr）。

3. CFS调度类的实现

Linux 内核的调度器是一个模块化的设计，不同的调度策略（如CFS、RT、Deadline）通过 sched_class 结构体向内核注册自己的回调函数。

3.1 调度类结构(fair_sched_class)

fair_sched_class 是 CFS 的“名片”，它定义了 CFS 如何响应内核调度器的各种事件。

例如：

• enqueue_task：当任务入队时调用 enqueue_task_fair。 

• pick_next_task：当需要选择下一个运行的任务时调用 pick_next_task_fair。 

• task_tick：在每个时钟滴答（tick）发生时调用 task_tick_fair。 

• yield_task：当任务主动调用 sched_yield() 时调用 yield_task_fair。

3.2 核心调度函数enqueue_task_fair

这是任务进入 CFS 调度世界的入口。它会遍历任务的调度实体（支持 cgroup 组调度），将每个实体插入到对应层级的红黑树中，并更新运行队列的统计信息。如果是唤醒操作，还会调用 check_preempt_wakeup 检查是否需要立即抢占当前任务。

• pick_next_task_fair：这是调度器的心脏。它简单而高效地调用 __pick_first_entity 获取红黑树最左边的实体，然后将其设置为下一个要运行的任务。

• task_tick_fair：在每个时钟中断，此函数被调用。它的主要工作是：

1. 更新vruntime：调用update_curr_fair，根据自上次更新以来的物理执行时间，增加当前任务的 vruntime。 

2. 检查抢占：如果系统中有多个可运行任务，它会计算当前任务的理想时间片。如果任务已经运行超过了这个时间片，就标记当前 CPU 需要重新调度（resched_curr），以便在下一次内核返回用户态时切换任务。

• yield_task_fair：当任务主动让出 CPU 时，CFS会给它的 vruntime 加上一个惩罚值（通常是base_slice），这样它在重新入队后会被放到红黑树更靠右的位置，让其他任务有机会先运行。

3.3 Preemption（抢占）机制

CFS 的抢占机制是其保证交互性的关键。

• Wakeup Preemption（唤醒抢占）：当一个新任务被唤醒时，CFS会立即将其与当前正在运行的任务进行比较。

• 如果新任务的 vruntime 小于当前任务的vruntime，说明新任务“更饿”，应该立即抢占。

• 为了防止过于频繁的抢占（例如，一个刚启动的任务 vruntime 为0，会立刻抢占一切），内核引入了wakeup_granularity（唤醒粒度，默认1ms）。只有当新旧任务的 vruntime 差值大于这个粒度时，才会发生抢占。这为新任务提供了一个短暂的“启动窗口”。

• 运行时抢占：除了唤醒抢占，task_tick_fair中的时间片检查也是一种运行时抢占机制，确保没有任务能长时间霸占 CPU。

4. 负载跟踪（PELT）

CFS 不仅要公平，还要智能。它需要知道每个任务、每个CPU、每个调度组的负载和利用率，以便做出更好的调度决策（如负载均衡）。

PELT（Per-Entity Load Tracking）是 Linux 6.6 中用于精确跟踪负载的算法。

• 核心思想：负载不是瞬时的，而是随时间衰减的。PELT将时间划分为 1024us 的周期。在每个周期内，任务的负载贡献会被累加到一个总和（load_sum）中。每当跨过一个完整的周期边界，旧的负载总和会乘以一个衰减因子（约为0.5），然后再累加新的贡献。

• 结果：load_avg = load_sum / LOAD_AVG_MAX。这个 load_avg 是一个平滑的、指数衰减的平均值，能很好地反映任务的历史负载情况。

• 用途：PELT提供的util_avg（平均利用率）是能耗感知调度（EAS）和负载均衡的核心输入。调度器可以根据 CPU 的利用率来决定是否迁移任务，或者选择哪个 CPU 更适合运行一个新任务。

5. SMP负载均衡

在多核（SMP）系统中，CFS需要确保各个 CPU 核心的负载是均衡的，避免出现一些核心过载而另一些核心空闲的情况。

• 触发时机：负载均衡可以在多种情况下触发，例如：

• 定期触发：通过 NOHZ_BALANCE_KICK 在空闲核心上定期检查。

• 任务入队/出队：当一个任务被加入或移出运行队列时，可能会触 发 trigger_load_balance。 

• 新任务fork：子进程创建时会尝试寻找一个负载较轻的 CPU。 

• 调度域（SchedDomain）：内核将 CPU 按照拓扑结构（如 SMT 超线程、Core核心、Package插槽、NUMA节点）组织成层次化的调度域。负载均衡会从最底层的域（如SMT）开始，逐层向上检查。

均衡过程：

1. find_busiest_group：在当前调度域中找到负载最重的 CPU 组。

2. calculate_imbalance：计算需要从最忙的组迁移到最闲的组的任务量（imbalance）。

3. detach_tasks / attach_tasks：选择合适的任务进行迁移。选择标准包括任务的缓存亲和性、迁移代价等。select_task_rq_fair：当一个任务被唤醒时，此函数负责为其选择一个最合适的CPU。它会优先考虑任务之前的CPU（缓存亲和性），但如果该 CPU 负载过高，或者有更空闲且符合亲和性要求的CPU，它会选择迁移。

6. CFS带宽控制

CFS 带宽控制允许管理员限制一个 cgroup 中所有任务的 CPU 使用率，防止单个 cgroup 耗尽整个系统的 CPU 资源。

• 核心概念：

• Period（周期）：默认100ms。带宽控制在这个周期内生效。

• Quota（配额）：在一个周期内，该 cgroup 允许使用的 CPU 时间（纳秒）。例如，quota=20ms意味着该 cgroup 最多只能使用 20% 的 CPU。 

• 工作原理：

• 每个受控的 cfs_rq 都有一个 runtime 计数器，初始值等于 quota。 

• 任务运行时，会不断消耗 runtime。 

• 当 runtime 耗尽时，该 cfs_rq 会被throttled（限流），其中的所有任务都无法再被调度，即使它们的 vruntime 很小。

• 当周期结束时，period_timer会触发，为 cfs_rq 补充 quota 的runtime，并unthrottle（解除限流），任务恢复运行。

7. NUMA平衡与能耗感知调度

现代服务器通常是 NUMA 架构，不同 CPU 访问本地内存和远程内存的延迟差异巨大。同时，移动设备和数据中心都对功耗极其敏感。

• NUMA 平衡：CFS会监控任务的内存访问模式。如果发现一个任务频繁访问另一个 NUMA 节点的内存，它会尝试将该任务迁移到内存所在的节点上，或者将内存迁移到任务所在的节点上，以减少远程内存访问的开销。

• 能耗感知调度（EAS）：在支持 EAS 的异构多核平台（如big.LITTLE）上，CFS会利用 PELT 提供的 util_avg 信息。

• fits_capacity：在选择 CPU 时，不仅看负载，还要看该 CPU 的算力（capacity）是否足以承载任务的利用率。避免将一个小任务放到一个大核上，造成“杀鸡用牛刀”的功耗浪费。

• cpufreq_update_util：CFS会将 CPU 的实时利用率反馈给 CPUFreq 子系统，以便动态调整 CPU 频率，在性能和功耗之间取得最佳平衡。

8. 调优参数与总结

调优参数：

CFS提供了大量的 /proc/sys/kernel/sched_* 参数，允许系统管理员根据具体工作负载进行微调，例如调整 base_slice、migration_cost、wakeup_granularity 等。

总结：

CFS 是一个精妙而强大的调度器。它通过 vruntime 和红黑树实现了理论上的完全公平；通过唤醒抢占和自适应时间片保证了卓越的交互性；通过 PELT、SMP 负载均衡、NUMA平衡和能耗感知调度等高级特性，使其能够适应从嵌入式设备到大型服务器等各种复杂场景。理解 CFS 的工作原理，对于系统性能分析、调优和开发高性能应用都具有重要意义。

下一步学习建议：深入理解了 CFS 之后，可以继续学习实时（RT）和截止时间（Deadline）调度器，它们是如何在 CFS 的基础上，为有严格时间要求的任务提供保障的。