4. 调度实体（sched_entity）：CFS 调度的核心载体

在 Linux CFS 调度器中，调度的基本单位不再是进程描述符 task_struct，而是调度实体 struct sched_entity。这种设计使得 CFS 能够统一调度普通进程、线程以及组调度（Group Scheduling）中的任务组。每个 task_struct 内部都内嵌了一个 sched_entity 实例，作为参与红黑树调度的“入场券”。

核心概念：调度实体是 CFS 调度器眼中“可被调度的对象”。它剥离了进程的其他属性（如内存、文件描述符），只保留与 CPU 时间分配直接相关的调度元数据。

4.1 struct sched_entity 结构体全景

该结构体定义在 include/linux/sched.h 中，是 CFS 调度器操作的核心数据结构。以下列出其关键字段：

字段名 类型 作用与说明
load struct load_weight 调度实体的权重，决定其获得 CPU 时间的比例。
run_node struct rb_node 红黑树节点，用于将调度实体插入 CFS 运行队列的红黑树中。
on_rq unsigned int 标志位，表示该实体当前是否在运行队列上（1 表示在队列，0 表示已出队）。
exec_start u64 当前调度实体开始执行的时间戳（基于 rq 时钟）。
sum_exec_runtime u64 该实体在 CPU 上执行的总物理时间（纳秒）。
vruntime u64 虚拟运行时间，CFS 调度的核心排序依据。
prev_sum_exec_runtime u64 上一次被切换出去时保存的 sum_exec_runtime，用于计算本次运行时长。
nr_migrations u64 调度实体在不同 CPU 之间迁移的次数。
statistics struct sched_statistics 调度统计信息（如睡眠时间、等待时间等）。
depth int 调度实体在组调度层级中的深度。
parent struct cfs_rq * 指向该实体所属的 CFS 运行队列。
my_q struct cfs_rq * 如果该实体代表一个任务组，则指向其自身的 CFS 运行队列。
设计意图：通过 my_q 和 depth 字段，CFS 实现了调度实体的层级嵌套，使得一个任务组可以作为一个整体参与调度，组内的进程再通过组内的红黑树进行二次调度。

4.2 vruntime：虚拟运行时间——公平的标尺

vruntime 是 CFS 调度器最核心的字段，它记录了调度实体的“虚拟运行时间”。CFS 的公平性体现在：它总是选择 vruntime 最小的调度实体来运行。

vruntime 的计算与更新：

  • 基础公式： vruntime += 实际运行时间 * (NICE_0_LOAD / 当前实体权重)
  • 物理时间到虚拟时间的转换： 权重越大的进程（优先级高），其 vruntime 增长得越慢；权重越小的进程（优先级低），其 vruntime 增长得越快。
  • 时钟中断更新： 每次时钟 tick 到来时，内核调用 update_curr() 函数，计算当前进程自上次更新以来执行的物理时间，并按上述公式累加到 vruntime 上。
  • 调度点更新： 在进程主动让出 CPU（如调用 schedule()）或发生抢占时，也会触发 vruntime 的更新。
关键理解：vruntime 不是真实的时间，而是一个经过权重归一化后的“虚拟时间戳”。它使得不同优先级的进程在红黑树中拥有一个统一的比较基准。

vruntime 的校正（Placement）：

当新进程被创建或进程从睡眠中唤醒时，内核会为其设置一个初始的 vruntime，这个过程称为“虚拟时间放置”。

  • 新进程： 通常将其 vruntime 设置为当前运行队列中最小的 vruntime，防止新进程因为 vruntime 过小（初始为 0）而长时间抢占 CPU。
  • 唤醒进程： 如果进程睡眠时间较长，其 vruntime 会远小于当前运行队列中的最小值。内核会对其进行补偿，适当增加其 vruntime，避免其“饥饿”其他进程。
vruntime 增长速率与权重关系 vruntime 增长速率对比（权重 vs 虚拟时间） 物理运行时间 vruntime 高权重（nice -20） 中等权重（nice 0） 低权重（nice 19） 斜率 = NICE_0_LOAD / 当前权重。权重越大，vruntime 增长越慢，在红黑树中越靠左，获得更多 CPU 时间。

4.3 load 权重字段：CPU 时间的分配比例

load 字段的类型是 struct load_weight，它决定了调度实体在竞争 CPU 时间时的“话语权”。

// 内核源码：include/linux/sched.h
struct load_weight {
    unsigned long   weight;   // 权重值，用于计算 vruntime 和 shares
    u32             inv_weight; // weight 的倒数，用于快速除法
};

权重与 nice 值的映射：

内核维护了一个全局的权重表 sched_prio_to_weight[40]，将用户空间的 nice 值（-20 到 19）映射到对应的权重值。

nice 值 权重 (weight) 说明
-20 88761 最高优先级，权重最大，获得 CPU 时间最多
-10 29154 高优先级
0 1024 默认优先级（NICE_0_LOAD）
10 335 低优先级
19 15 最低优先级，权重最小，获得 CPU 时间最少
权重的作用域：在组调度场景下，一个任务组的 load.weight 是其内部所有活跃调度实体权重的总和。CFS 通过比较不同组的权重，来决定将多少 CPU 时间分配给这个组。

权重在 CFS 中的两个关键作用：

  1. 计算 vruntime 增量： 如前所述，权重越大，相同物理时间下 vruntime 的增加量越小。
  2. 计算调度延迟和最小粒度： 在计算一个调度实体应该运行多久（targeted_latency 和 min_granularity）时，会考虑其权重占运行队列总权重的比例。

4.4 run_node 红黑树节点：排序与选择的基石

run_node 是 struct rb_node 类型，它将调度实体链接到 CFS 运行队列（struct cfs_rq）的红黑树中。红黑树以 vruntime 为键值进行排序。

红黑树操作流程：

  • 入队（enqueue）： 当调度实体变为可运行状态时，调用 enqueue_entity()，将其 run_node 插入到红黑树中，位置由 vruntime 决定。
  • 出队（dequeue）： 当调度实体变为不可运行状态（如睡眠、退出）时，调用 dequeue_entity()，将其从红黑树中移除。
  • 选择下一个（pick_next）： CFS 通过 first_fair() 函数获取红黑树中最左侧的节点，即 vruntime 最小的调度实体，作为下一个要运行的进程。
CFS 红黑树结构：以 vruntime 为键排序 CFS 红黑树结构（vruntime 最小者最左） vruntime: 200 vruntime: 100 vruntime: 300 vruntime: 50 vruntime: 150 vruntime: 250 红黑树选择逻辑 1. pick_next_task_fair() 调用 __pick_first_entity() 获取最左节点。 2. 最左节点（vruntime=50）被选中运行。运行后其 vruntime 增加，可能在树中向右移动。 3. 红黑树始终保持平衡，保证 O(log N) 的查找、插入和删除性能。

4.5 调度实体与 CFS 运行队列的协作

调度实体并非孤立存在，它与 CFS 运行队列（struct cfs_rq）紧密配合。每个 CPU 都有一个自己的 cfs_rq，它管理着该 CPU 上所有可运行的调度实体。

// 内核源码：kernel/sched/sched.h
struct cfs_rq {
    struct load_weight  load;           // 该队列上所有调度实体的总权重
    unsigned int        nr_running;     // 队列中可运行的调度实体数量
    u64                 min_vruntime;   // 队列中最小的 vruntime，用于新进程放置
    struct rb_root_cached   tasks_timeline; // 红黑树根节点（包含缓存）
    struct sched_entity *curr;          // 当前正在运行的调度实体
    struct sched_entity *next;          // 下一个要运行的调度实体（缓存）
    struct sched_entity *last;          // 上一个运行的调度实体
    // ... 其他字段
};
关键协作流程：
  1. cfs_rq 的 tasks_timeline 红黑树中存储了所有可运行的 sched_entity。
  2. 每次调度时，CFS 从红黑树中取出 vruntime 最小的实体，赋值给 curr。
  3. 当 curr 运行一段时间后，其 vruntime 增加，如果它不再是树中最小的，CFS 会设置 need_resched 标志，在下一个调度点触发抢占。
  4. min_vruntime 字段用于跟踪队列中最小的 vruntime，当新进程加入时，可以快速获得一个参考值。

调度实体生命周期中的关键函数调用链：

阶段 核心函数 对 sched_entity 的操作
进程创建 sched_fork() / task_fork_fair() 初始化 sched_entity，设置初始 vruntime
加入运行队列 enqueue_task_fair() 调用 enqueue_entity()，将 run_node 插入红黑树
时钟中断更新 scheduler_tick() → task_tick_fair() 调用 update_curr()，更新 vruntime 和 sum_exec_runtime
选择下一个进程 pick_next_task_fair() 从红黑树中获取最左节点，赋值给 cfs_rq->curr
进程切换 context_switch() 保存当前实体的 prev_sum_exec_runtime，恢复下一个实体的状态
离开运行队列 dequeue_task_fair() 调用 dequeue_entity()，从红黑树中移除 run_node
注意事项：在组调度（CONFIG_FAIR_GROUP_SCHED）开启时，一个 sched_entity 可能代表一个任务组。此时，该实体的 my_q 指向一个子 cfs_rq，子 cfs_rq 中又包含该组内进程的 sched_entity。这种层级结构使得 CFS 能够实现 CPU 时间在任务组之间的分配，以及组内进程之间的二次分配。
调度实体与 CFS 运行队列协作架构 sched_entity 与 cfs_rq 协作架构 CPU 0 的 cfs_rq tasks_timeline (RB Root) se: vruntime=50 se: vruntime=120 se: vruntime=200 se: vruntime=350 curr: 指向 vruntime=50 的 se load: 1024 nr_running: 4 task_struct 与 sched_entity 关系 task_struct A pid=1001, nice=0 sched_entity vruntime=50 task_struct B pid=1002, nice=5 sched_entity vruntime=120 task_struct C pid=1003, nice=10 sched_entity vruntime=200 每个 task_struct 内嵌一个 sched_entity 通过 se 的 run_node 插入 cfs_rq 的红黑树

4.6 本章小结

  • 调度实体（sched_entity）是 CFS 调度器操作的基本单元，它封装了调度所需的元数据，使得 CFS 可以统一调度进程和任务组。
  • vruntime 是 CFS 公平性的核心度量，通过权重归一化，使得不同优先级的进程可以在同一个红黑树中公平竞争。
  • load 权重 决定了进程获得 CPU 时间的比例，权重越大，vruntime 增长越慢，获得的 CPU 时间越多。
  • run_node 红黑树节点 是 CFS 实现 O(log N) 调度选择的数据结构基础，红黑树以 vruntime 为键值，始终选择最左侧（最小 vruntime）的实体运行。
  • 调度实体与 cfs_rq 的协作构成了 CFS 调度器的运行时骨架，理解这一协作关系是掌握 CFS 工作原理的关键。
← 上一章 📖 返回目录 下一章 →