📚 课程目录第2章 CFS调度器核心原理回顾

2. CFS调度器核心原理回顾：虚拟时钟(vruntime)、红黑树、调度实体(sched_entity)与调度类

在深入分析从 x86 到 RISC-V 的移植改动之前，必须牢固掌握 CFS（Completely Fair Scheduler）的核心设计原理。CFS 抛弃了传统基于固定时间片和优先级权重的调度模型，转而采用一种基于“虚拟运行时间”的精确公平模型。其核心由四个关键概念构成：调度实体 (sched_entity)、虚拟时钟 (vruntime)、红黑树 (Red-Black Tree) 和 调度类 (sched_class)。

移植视角提示： 这四个概念在 x86 和 RISC-V 架构下的逻辑语义完全一致，但它们的底层实现——特别是时间戳精度、寄存器访问、原子操作和内存屏障——存在架构差异。理解这些差异是后续章节分析具体代码改动的基石。

2.1 调度实体 (struct sched_entity)

调度实体是 CFS 调度的基本单位。它不再直接调度进程（task_struct），而是调度一个抽象的“实体”。一个进程可以包含一个主调度实体（用于普通调度），也可以包含多个组调度实体（用于实现控制组 CGroup 的 CPU 带宽控制）。

核心数据结构定义在 include/linux/sched.h 中，其关键字段如下：

字段名	类型	说明
`load`	`struct load_weight`	调度实体的权重，由进程优先级（nice值）计算得出，影响虚拟时间推进速度。
`run_node`	`struct rb_node`	红黑树节点，用于将该实体插入到 CFS 运行队列的红黑树中。
`vruntime`	`u64`	虚拟运行时间，CFS 公平调度的核心度量指标。
`on_rq`	`int`	标志位，指示该实体当前是否在运行队列上。
`exec_start`	`u64`	当前调度实体开始执行的时间戳（实际时间，用于计算 delta 后更新 vruntime）。
`sum_exec_runtime`	`u64`	该实体累计消耗的实际 CPU 执行时间。
`prev_sum_exec_runtime`	`u64`	上次被切换出去时的累计执行时间，用于统计。
`nr_migrations`	`u64`	实体在不同 CPU 之间迁移的次数。

  架构差异关注点： vruntime 和 exec_start 都是 u64 类型，存储的是纳秒级时间戳。在 x86 上，获取高精度时间戳通常使用 rdtsc 指令；而在 RISC-V 上，则通过读取 time CSR（Control and Status Register）或调用 get_cycles() 函数。时间源的精度和读取开销直接影响调度器的性能。

2.2 虚拟时钟 (vruntime) 与红黑树

CFS 的核心思想是：在一个无限小的调度周期内，让每个调度实体获得完全平等的 CPU 时间。为了实现这一点，CFS 引入了“虚拟时钟”的概念。

vruntime 的计算公式：
```
vruntime += delta_exec * (NICE_0_LOAD / se->load.weight)
```
其中 delta_exec 是实际执行时间，NICE_0_LOAD 是 nice 值为 0 时的权重（基准权重）。权重越高的进程（优先级高），其 load.weight 越大，导致 vruntime 增长越慢；反之，权重低的进程 vruntime 增长更快。
红黑树的作用： CFS 将所有可运行的调度实体（on_rq == 1）按 vruntime 作为键值插入到一棵红黑树中。红黑树的最左节点（rb_leftmost）就是 vruntime 最小的实体，也就是“最需要被调度”的实体。
调度决策： 每次调度时，CFS 直接从红黑树中摘取最左节点作为下一个要运行的进程。这保证了所有进程在虚拟时间轴上尽可能公平地向前推进。

2.3 调度类 (struct sched_class)

调度类是 Linux 内核实现调度策略多态性的关键机制。它将不同调度策略（如 CFS、实时调度 RT、空闲调度 IDLE）抽象为统一的接口。内核通过 sched_class 的优先级链表来选择合适的调度器。

调度类定义在 kernel/sched/sched.h 中，其核心函数指针表如下：

函数指针	功能描述	移植关注点
`enqueue_task`	将任务加入运行队列（插入红黑树）	涉及红黑树操作，架构无关
`dequeue_task`	将任务移出运行队列	涉及红黑树操作，架构无关
`yield_task`	任务主动让出 CPU	可能涉及架构特定的上下文切换
`check_preempt_curr`	检查新唤醒的任务是否需要抢占当前任务	需要比较 vruntime，架构无关
`pick_next_task`	选择下一个要运行的任务（核心调度入口）	返回最左节点，架构无关
`put_prev_task`	将当前任务放回运行队列	更新 vruntime，需要读取时间戳
`set_curr_task`	设置当前任务	架构无关
`task_tick`	周期性调度器 tick 处理	关键移植点：调用 `update_curr()` 更新 vruntime，需要架构特定的时间戳读取
`update_curr`	更新当前任务的 vruntime	关键移植点：调用 `sched_clock()` 或 `rq_clock_task()` 获取当前时间

架构差异关键点： task_tick 和 update_curr 是 CFS 调度器中最依赖底层架构的两个函数。在 x86 上，sched_clock() 通常基于 TSC（时间戳计数器）；在 RISC-V 上，则基于 mtime 或 cycle CSR。时间戳的精度、单调性保证和读取开销，直接影响 CFS 的公平性判断和调度延迟。

2.4 核心数据结构关系总览

以下 SVG 图展示了 task_struct、sched_entity、cfs_rq 和 sched_class 之间的整体关系：

2.5 关键函数调用链：update_curr

update_curr() 是 CFS 调度器中最频繁调用的函数之一，它负责更新当前运行任务的 vruntime。理解其调用链对于后续分析 RISC-V 移植至关重要。

// kernel/sched/fair.c (简化逻辑)
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));  // <-- 架构相关: 获取当前时间
    u64 delta_exec;

    if (unlikely(!curr))
        return;

    // 计算自上次更新以来的实际执行时间
    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0))
        return;

    // 更新累计执行时间
    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;

    // 根据权重计算虚拟运行时间增量
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    // ... 后续检查是否需要进行抢占或周期更新
}

  移植关键点： 函数 rq_clock_task() 最终会调用到架构特定的时间戳读取函数。在 x86 上，这通常是 sched_clock()，它基于 TSC 实现；在 RISC-V 上，我们需要确保 sched_clock() 能够正确、高效地读取 mtime 寄存器或 cycle CSR，并且保证在多核环境下时间戳的单调性和一致性。

2.6 本章小结

调度实体 (sched_entity) 是 CFS 调度的基本单元，封装了权重、虚拟时间和红黑树节点。
虚拟时钟 (vruntime) 是公平调度的核心度量，通过权重调整实际执行时间，确保所有实体在虚拟时间轴上公平推进。
红黑树 以 vruntime 为键值组织所有可运行实体，最左节点即为下一个调度候选，提供 O(log N) 的调度效率。
调度类 (sched_class) 实现了调度策略的多态性，CFS 通过 fair_sched_class 暴露其接口。
移植核心矛盾： 上述逻辑在 x86 和 RISC-V 上完全一致，但 update_curr() 和 task_tick() 中依赖的 时间戳读取函数 是架构相关的，这是后续章节分析具体代码改动的切入点。