“想揭开Linux如何“公平”分配CPU的神秘面纱？CFS调度器正是幕后核心！本教材深入浅出，带你从原理到实现，彻底掌握这一精妙设计”
前言：为什么需要CFS？
在 CFS 出现之前，Linux使用的是 O(1) 调度器，它为每个优先级维护一个运行队列，并使用固定的时间片。这种方式虽然高效，但存在两个主要问题：不公平性：高优先级任务可以长时间独占CPU，低优先级任务可能“饿死”。交互性差：新唤醒的交互式任务（如点击鼠标）必须等待当前任务用完时间片才能运行，导致响应延迟。
CFS（Completely Fair Scheduler）应运而生，其核心目标是实现完全公平——让系统中的每个可运行任务都能获得相等的 CPU 时间份额，同时保证优秀的交互性能。
1. 概述：CFS的哲学与架构
核心思想：“给每个任务公平的CPU时间份额”。
CFS 抛弃了传统“时间片”的概念。它不关心一个任务能运行多久，而是关心一个任务已经运行了多久。为了衡量这个“运行了多久”，CFS引入了一个天才的概念：虚拟运行时间（vruntime）。
想象一下，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）。它的作用是：
防止任务饿死：当一个睡眠很久的任务被唤醒时，它的 vruntime 可能远小于当前的min_vruntime。如果直接把它插入红黑树最左边，它会立刻抢占 CPU 并运行非常久，这对其他任务不公平。因此，CFS会将新唤醒任务的 vruntime 设置为min_vruntime，让它从“公平起点”开始竞争。
迁移任务的参考：在负载均衡时，用于计算跨 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）来决定何时检查是否需要切换任务，以保证良好的交互性。
这个计算出的时间片主要用于 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 检查是否需要立即抢占当前任务。
更新vruntime：调用update_curr_fair，根据自上次更新以来的物理执行时间，增加当前任务的 vruntime。
检查抢占：如果系统中有多个可运行任务，它会计算当前任务的理想时间片。如果任务已经运行超过了这个时间片，就标记当前 CPU 需要重新调度（resched_curr），以便在下一次内核返回用户态时切换任务。
3.3 Preemption（抢占）机制
CFS 的抢占机制是其保证交互性的关键。
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 核心的负载是均衡的，避免出现一些核心过载而另一些核心空闲的情况。
均衡过程：
find_busiest_group：在当前调度域中找到负载最重的 CPU 组。
calculate_imbalance：计算需要从最忙的组迁移到最闲的组的任务量（imbalance）。
detach_tasks / attach_tasks：选择合适的任务进行迁移。选择标准包括任务的缓存亲和性、迁移代价等。select_task_rq_fair：当一个任务被唤醒时，此函数负责为其选择一个最合适的CPU。它会优先考虑任务之前的CPU（缓存亲和性），但如果该 CPU 负载过高，或者有更空闲且符合亲和性要求的CPU，它会选择迁移。
6. CFS带宽控制
CFS 带宽控制允许管理员限制一个 cgroup 中所有任务的 CPU 使用率，防止单个 cgroup 耗尽整个系统的 CPU 资源。
每个受控的 cfs_rq 都有一个 runtime 计数器，初始值等于 quota。
任务运行时，会不断消耗 runtime。
当 runtime 耗尽时，该 cfs_rq 会被throttled（限流），其中的所有任务都无法再被调度，即使它们的 vruntime 很小。
当周期结束时，period_timer会触发，为 cfs_rq 补充 quota 的runtime，并unthrottle（解除限流），任务恢复运行。
7. NUMA平衡与能耗感知调度
现代服务器通常是 NUMA 架构，不同 CPU 访问本地内存和远程内存的延迟差异巨大。同时，移动设备和数据中心都对功耗极其敏感。
8. 调优参数与总结
调优参数：
CFS提供了大量的 /proc/sys/kernel/sched_* 参数，允许系统管理员根据具体工作负载进行微调，例如调整 base_slice、migration_cost、wakeup_granularity 等。
总结：
CFS 是一个精妙而强大的调度器。它通过 vruntime 和红黑树实现了理论上的完全公平；通过唤醒抢占和自适应时间片保证了卓越的交互性；通过 PELT、SMP 负载均衡、NUMA平衡和能耗感知调度等高级特性，使其能够适应从嵌入式设备到大型服务器等各种复杂场景。理解 CFS 的工作原理，对于系统性能分析、调优和开发高性能应用都具有重要意义。
下一步学习建议：深入理解了 CFS 之后，可以继续学习实时（RT）和截止时间（Deadline）调度器，它们是如何在 CFS 的基础上，为有严格时间要求的任务提供保障的。
