4. CFS 红黑树节点结构：struct sched_entity 关键字段解析
在 CFS 调度器中，每一个可被调度的实体（进程或线程）并不是直接挂在红黑树上的，而是通过内嵌一个 struct sched_entity 结构体来参与调度。这个结构体是 CFS 调度算法的核心数据载体，它记录了调度实体在红黑树中的位置、虚拟运行时间、负载权重等关键信息。理解这些字段是掌握 CFS 工作原理的基石。
4.1 核心数据结构总览
struct sched_entity 定义在 include/linux/sched.h 中。以下是其核心字段的简化定义与说明：
struct sched_entity {
/* 红黑树节点：用于将调度实体插入到 CFS 运行队列的红黑树中 */
struct rb_node run_node;
/* 虚拟运行时间：CFS 调度的核心度量，单位是 ns */
u64 vruntime;
/* 权重：用于计算虚拟运行时间的增量，反映调度实体的优先级 */
struct load_weight load;
/* 指向所属 task_struct 的指针 */
struct task_struct *task;
/* 标志位：表示该调度实体是否在运行队列上 */
unsigned int on_rq;
/* 统计信息：记录调度实体在 CPU 上的执行时间 */
u64 sum_exec_runtime;
u64 prev_sum_exec_runtime;
u64 exec_start;
/* 组调度相关：用于 task_group 的层级管理 */
struct sched_entity *parent;
struct cfs_rq *cfs_rq;
struct cfs_rq *my_q;
};
sched_entity 嵌入到 task_struct 中，而不是单独分配？” 答案：减少指针间接访问，利用局部性原理提升缓存命中率；同时便于通过 container_of 宏从调度实体快速找到对应的进程描述符。
4.2 关键字段深度解析
下表对 struct sched_entity 中的核心字段进行了分类与详细说明：
| 字段名 | 类型 | 核心作用 | 面试考点 |
|---|---|---|---|
run_node |
struct rb_node |
将调度实体链接到 CFS 红黑树中，用于按 vruntime 排序 |
红黑树的插入、删除、查找操作；rb_left/rb_right 指针 |
vruntime |
u64 |
虚拟运行时间，CFS 选择 最小 vruntime 的实体运行 | 计算公式：vruntime += delta_exec * NICE_0_LOAD / weight |
load |
struct load_weight |
包含 weight 和 inv_weight，用于权重计算 |
权重与 nice 值的映射表；inv_weight 用于加速除法 |
on_rq |
unsigned int |
标志位：1 表示在运行队列上，0 表示不在 | 调度实体状态切换；dequeue_entity/enqueue_entity 中的检查 |
sum_exec_runtime |
u64 |
该调度实体累计消耗的 CPU 实际执行时间 | 与 vruntime 的区别；用于统计和记账 |
exec_start |
u64 |
当前调度实体开始占用 CPU 的时间戳 | 用于计算本次调度周期内的 delta_exec |
4.3 vruntime：CFS 调度的“公平标尺”
vruntime 是 CFS 调度器中最核心的字段，它直接决定了下一个被调度执行的进程。CFS 的核心逻辑可以概括为：始终选择红黑树中 vruntime 最小的调度实体来运行。
vruntime 的增长速率与进程的权重成反比：
- 高优先级（低 nice 值，高 weight）：
vruntime增长慢，在红黑树中位置偏左，更容易被选中。 - 低优先级（高 nice 值，低 weight）：
vruntime增长快，在红黑树中位置偏右，被选中的机会减少。
其更新公式如下：
// 核心计算公式（简化版）
delta_exec = current_time - se->exec_start;
se->vruntime += delta_exec * NICE_0_LOAD / se->load.weight;
NICE_0_LOAD 是 nice 值为 0 时的权重（1024）。公式的本质是将实际运行时间 delta_exec 按照权重比例缩放为虚拟时间。权重越大的进程，其虚拟时间增长越慢，从而获得更多的 CPU 时间。
4.4 run_node：红黑树中的“身份证”
run_node 是一个标准的 struct rb_node，它包含三个关键部分：
__rb_parent_color：存储父节点指针和红黑颜色（红/黑）信息。rb_right：指向右子节点。rb_left：指向左子节点。
CFS 红黑树的排序键是 vruntime。当向树中插入新节点时，内核通过 __enqueue_entity() 函数，以 vruntime 为比较依据，找到合适的位置插入。
// 红黑树插入核心逻辑（伪代码）
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
int leftmost = 1;
while (*link) {
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
if (se->vruntime < entry->vruntime) {
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = 0;
}
}
rb_link_node(&se->run_node, parent, link);
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
if (leftmost)
cfs_rq->rb_leftmost = &se->run_node;
}
4.5 on_rq：调度实体的“在线状态”
on_rq 字段是一个简单的布尔标志，但它对于调度器的正确性至关重要：
- on_rq = 1：表示该调度实体当前正在 CFS 运行队列中（即挂在红黑树上），可以被调度。
- on_rq = 0：表示该调度实体不在运行队列中（例如正在睡眠、被停止或刚创建还未入队）。
这个字段主要用于防止重复入队或重复出队操作。在 enqueue_entity() 和 dequeue_entity() 函数中，内核会首先检查 on_rq 状态，避免对同一个实体进行重复操作导致红黑树结构损坏。
fork() 创建子进程时，子进程的 sched_entity 的 on_rq 初始化为 0。直到子进程被 wake_up_new_task() 唤醒并加入运行队列时，on_rq 才会被置为 1。面试中可能会问“为什么新创建的进程不会立即被调度？” 答案就是因为其 on_rq 为 0，尚未入队。
4.6 结构关系与数据流 SVG 图
下图展示了 struct sched_entity 如何通过 run_node 连接到 CFS 红黑树，以及 vruntime 如何作为排序键驱动调度决策：
4.7 字段生命周期与状态转换
调度实体的关键字段在进程的整个生命周期中不断变化。以下是一个典型的时间线：
- 进程创建（fork）：
sched_entity被初始化，vruntime被设置为cfs_rq->min_vruntime，on_rq = 0。 - 唤醒入队（wake_up_new_task）：
enqueue_entity()被调用，on_rq置为 1，run_node插入红黑树。 - 调度执行（context_switch）：
exec_start记录当前时间，进程开始运行。 - 时钟中断（tick）：
update_curr()更新vruntime和sum_exec_runtime。 - 进程睡眠（schedule）：
dequeue_entity()被调用，on_rq置为 0，run_node从红黑树移除。 - 进程退出（exit）：
sched_entity占用的资源被回收。
vruntime 在进程睡眠期间是否变化？答案：不变化。当进程被
dequeue_entity() 移出红黑树后，update_curr() 不再更新其 vruntime。当进程再次被唤醒时，其 vruntime 会与 cfs_rq->min_vruntime 进行比较，如果偏小，可能会被补偿（place_entity() 函数），以避免刚唤醒的进程因 vruntime 过小而长时间占用 CPU。
4.8 本章小结
struct sched_entity 是 CFS 调度器的微观基础。其关键字段构成了一个完整的调度闭环：
run_node提供了数据结构支撑，使调度实体能够被组织在红黑树中。vruntime提供了公平性度量，是 CFS 选择下一个运行进程的唯一依据。load提供了权重信息，决定了vruntime的增长速率。on_rq提供了状态保护，确保调度操作的正确性。
理解这些字段的语义和它们之间的交互关系，是深入分析 CFS 调度器行为的前提，也是面试中回答红黑树与权重计算相关问题的关键。