2. CFS调度器原理：完全公平调度器（CFS）的红黑树数据结构、虚拟运行时间（vruntime）计算、调度周期与最小粒度

完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本引入的默认调度类，用于普通（SCHED_NORMAL / SCHED_OTHER）进程的 CPU 时间分配。CFS 的核心设计理念是：为每个进程提供 CPU 时间的“理想多任务处理器”模型，即假设存在一个无限快的 CPU，所有进程在同一时刻并行运行。在实际物理 CPU 上，CFS 通过精确的虚拟运行时间（vruntime）和红黑树数据结构，以 O(log n) 的复杂度选择下一个最需要 CPU 的进程。

2.1 红黑树数据结构：CFS 的运行队列

CFS 为每个 CPU 维护一个红黑树（Red-Black Tree），作为其就绪队列（cfs_rq）。红黑树是一种自平衡的二叉搜索树，其插入、删除和查找操作的时间复杂度均为 O(log n)。CFS 使用红黑树来组织所有可运行的 SCHED_NORMAL 进程，以进程的 vruntime 作为键值。

• 树节点：每个节点对应一个调度实体（struct sched_entity），通常内嵌在 task_struct 中。
• 排序规则：左子树的 vruntime 小于父节点，右子树的 vruntime 大于父节点。
• 最左节点：红黑树中最左侧的节点（vruntime 最小）即为下一个被调度执行的进程。
• 缓存指针：cfs_rq 中缓存了指向最左节点的指针（rb_leftmost），使得选择下一个进程的操作在大多数情况下为 O(1)。

2.2 虚拟运行时间（vruntime）计算

vruntime 是 CFS 调度决策的核心度量。它表示一个进程在理想多任务处理器上应该获得的运行时间。实际运行时间通过 权重（weight） 进行归一化，使得高优先级（低 nice 值）进程的 vruntime 增长更慢，从而获得更多 CPU 时间。

vruntime 的更新公式：

vruntime += delta_exec * (NICE_0_LOAD / se->load.weight)

• delta_exec：进程本次实际运行的物理时间（单位：ns）。
• NICE_0_LOAD：nice 值为 0 时的默认负载权重（1024）。
• se->load.weight：当前进程的调度实体权重，由 nice 值映射得到。

权重映射表（部分）：

2.3 调度周期与最小粒度

CFS 通过 调度周期（sched_latency） 和 最小粒度（min_granularity） 两个参数来控制进程切换的频率和公平性。

2.3.1 调度周期（sched_latency）

调度周期是 CFS 保证每个可运行进程至少获得一次 CPU 执行的时间窗口。在默认配置下，sched_latency 为 6ms（可通过内核参数 kernel.sched_latency_ns 调整）。

时间片计算：

timeslice = sched_latency * (se->load.weight / cfs_rq->load.weight)

• 当可运行进程数量较少时，每个进程获得的时间片较大，减少切换开销。
• 当进程数量增多时，CFS 会启用 nice 0 负载倍数（nr_running > sched_nr_latency） 机制，将调度周期按比例放大，避免时间片过小导致频繁切换。

2.3.2 最小粒度（min_granularity）

最小粒度是 CFS 允许进程连续运行的最小时间单位，默认值为 0.75ms（可通过 kernel.sched_min_granularity_ns 调整）。

• 作用：防止调度器过于频繁地抢占进程，避免上下文切换开销超过实际计算收益。
• 抢占条件：当当前进程的运行时间超过其时间片，或者新唤醒进程的 vruntime 比当前进程的 vruntime 小至少 min_granularity 时，触发调度。
• 边界情况：在实时性要求极高的场景（如音频处理），可以适当减小 min_granularity，但会增加 CPU 开销。

2.4 关键数据结构与代码路径

CFS 的核心数据结构定义在 kernel/sched/sched.h 和 kernel/sched/fair.c 中。以下是最关键的几个结构体：

核心函数调用链（选择下一个进程）：

pick_next_task_fair()
  ├── __pick_first_entity()    // 获取 rb_leftmost 节点
  ├── set_next_entity()        // 更新调度实体状态
  │     └── __dequeue_entity() // 从红黑树中移除当前进程
  └── return se->task          // 返回 task_struct

2.5 总结：CFS 调度器的核心机制