3、Linux内核数据结构概览：list_head、rb_root、rb_node结构体定义

Linux内核进程调度器（CFS）的核心数据结构是红黑树，而红黑树的实现又依赖于内核中两个基础的数据结构：双向循环链表（list_head）和红黑树节点/根节点（rb_node / rb_root）。理解这三个结构体的定义，是掌握调度器运行机制的基石。

本章将逐一剖析这三个结构体的内核源码定义、内存布局以及它们在调度器中的角色。

3.1 双向循环链表：struct list_head

在Linux内核中，list_head 是最基础、使用最广泛的数据结构。它不存储业务数据，仅包含两个指针，用于将任意结构体串联成双向循环链表。

3.1.1 结构体定义

// 定义于 include/linux/types.h
struct list_head {
    struct list_head *next, *prev;
};
  • next：指向链表中的下一个节点。
  • prev：指向链表中的上一个节点。

当链表为空时，next 和 prev 均指向自身（即 head->next = head->prev = head）。

3.1.2 在调度器中的角色

调度器使用 list_head 管理两类关键对象：

用途 宿主结构体 说明
运行队列链表 struct rq 管理所有就绪进程的调度实体（CFS、RT、DL 各有一个链表）
等待队列 struct wait_queue_head 管理因等待事件而阻塞的进程
进程组链表 struct task_struct 将同一线程组或进程组的 task_struct 串联起来
设计哲学： list_head 采用“侵入式”设计，即链表节点直接嵌入到宿主结构体中，而不是由宿主结构体指向链表节点。这种方式减少了内存分配次数，提高了缓存局部性。

3.1.3 内存布局示意图

下图展示了一个包含两个节点的双向循环链表的内存结构：

struct list_head 双向循环链表内存布局 struct list_head 双向循环链表内存布局 list_head (头) next | prev list_head (节点1) next | prev list_head (节点2) next | prev next next prev (循环) 特点：无头节点概念，头节点也是普通节点；遍历时从 head->next 开始，回到 head 结束。

3.2 红黑树根节点：struct rb_root

rb_root 是红黑树的入口，结构极其精简，仅包含一个指向根节点的指针。

3.2.1 结构体定义

// 定义于 include/linux/rbtree.h
struct rb_root {
    struct rb_node *rb_node;
};
  • rb_node：指向红黑树的根节点。如果树为空，该指针为 NULL。

3.2.2 在调度器中的角色

每个 CPU 的运行队列（struct rq）中，CFS 调度类维护一个 rb_root 类型的成员 cfs_rq->tasks_timeline，用于组织所有 CFS 就绪进程的调度实体（struct sched_entity）。

字段 所属结构体 说明
tasks_timeline struct cfs_rq 红黑树根，按虚拟运行时间（vruntime）排序
rb_leftmost struct cfs_rq 缓存树中最左侧节点（即 vruntime 最小的进程），用于快速获取下一个调度实体
关键优化： 调度器通过 rb_leftmost 缓存最左节点，避免了每次调度时都从根节点遍历到最左叶子节点，将“查找最小 vruntime 进程”的时间复杂度从 O(log n) 降为 O(1)。

3.2.3 根节点与运行队列的关系图

rb_root 与 CFS 运行队列的关系 rb_root 与 CFS 运行队列的关系 struct rq (每个CPU一个) struct cfs_rq tasks_timeline rb_leftmost rb_node rb_root (根节点指针) N1 N2 N3 每个 CPU 的 rq 包含一个 cfs_rq，cfs_rq 中的 tasks_timeline 是红黑树根，管理所有 CFS 调度实体。

3.3 红黑树节点：struct rb_node

rb_node 是红黑树的节点结构体，包含指向父子节点的指针以及表示节点颜色的标志位。

3.3.1 结构体定义

// 定义于 include/linux/rbtree.h
struct rb_node {
    unsigned long  __rb_parent_color;  // 父节点指针 + 颜色标志位
    struct rb_node *rb_right;          // 右子节点
    struct rb_node *rb_left;           // 左子节点
} __attribute__((aligned(sizeof(long))));
  • __rb_parent_color：这是一个“技巧性”字段，在同一个 unsigned long 变量中同时存储了父节点指针和节点颜色（红/黑）。由于指针通常按 4 或 8 字节对齐，最低 1~2 位始终为 0，内核利用这些空闲位来存储颜色信息。
  • rb_right：指向右子节点。
  • rb_left：指向左子节点。

3.3.2 颜色编码技巧

位域 含义 说明
低 1 位 颜色标志 0 = 红色，1 = 黑色
高 (BITS_PER_LONG-1) 位 父节点指针 存储父节点的内存地址（已对齐，低 1 位为 0）
注意： 由于颜色位与父节点指针共享存储空间，在访问父节点时必须使用辅助宏 rb_parent() 来屏蔽颜色位；在设置颜色时必须使用 rb_set_parent_color() 等内联函数。直接操作 __rb_parent_color 可能导致指针错误。

3.3.3 辅助宏与内联函数

// 获取父节点指针（屏蔽低 1 位）
#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

// 获取节点颜色
#define rb_color(r)    ((r)->__rb_parent_color & 1)

// 判断是否为红色
#define rb_is_red(r)   (!rb_color(r))

// 判断是否为黑色
#define rb_is_black(r)  rb_color(r)

// 设置父节点和颜色
static inline void rb_set_parent_color(struct rb_node *rb,
                                       struct rb_node *p, int color)
{
    rb->__rb_parent_color = (unsigned long)p | color;
}

3.3.4 节点在调度实体中的嵌入

调度实体 struct sched_entity 将 rb_node 作为成员嵌入其中：

// 定义于 include/linux/sched.h
struct sched_entity {
    struct load_weight      load;           // 调度实体权重
    struct rb_node          run_node;       // 红黑树节点（嵌入）
    struct list_head        group_node;     // 组调度链表节点
    unsigned int            on_rq;          // 是否在运行队列上
    u64                     vruntime;       // 虚拟运行时间
    // ... 其他字段
};

调度器通过 container_of 宏从 rb_node 获取宿主 sched_entity：

struct sched_entity *se = container_of(rb_node, struct sched_entity, run_node);

3.4 三种数据结构对比总结

结构体 核心字段 组织方式 在调度器中的用途 时间复杂度
list_head next, prev 双向循环链表 管理等待队列、进程组、运行队列链表 O(1) 插入/删除
rb_root rb_node 红黑树根 CFS 就绪队列的入口 —
rb_node __rb_parent_color, rb_left, rb_right 红黑树节点 按 vruntime 排序的调度实体节点 O(log n) 插入/查找

3.5 数据结构关系总览图

Linux 内核调度器核心数据结构关系总览 Linux 内核调度器核心数据结构关系总览 struct rq (运行队列) struct cfs_rq struct rt_rq struct dl_rq tasks_timeline rb_leftmost 红黑树 (RB-Tree) 按 vruntime 排序 根节点: rb_root struct sched_entity 嵌入 struct rb_node run_node 嵌入 struct list_head group_node container_of struct task_struct 包含 se list_head 用于管理等待队列和进程组链表；rb_root / rb_node 用于 CFS 调度实体的有序组织。

3.6 小结

  • list_head：双向循环链表，O(1) 插入/删除，用于管理等待队列、进程组等线性结构。
  • rb_root：红黑树根节点，仅包含一个指向根节点的指针，是 CFS 就绪队列的入口。
  • rb_node：红黑树节点，通过 __rb_parent_color 技巧将父节点指针与颜色标志位合并存储，节省内存。
  • 调度实体 struct sched_entity 将 rb_node 嵌入自身，通过 container_of 实现从树节点到调度实体的反向查找。

理解这三个基础结构体的定义和内存布局，为后续学习红黑树的插入、查找、左旋、右旋以及 CFS 调度器的具体实现奠定了坚实的数据结构基础。

← 上一章 📖 返回目录 下一章 →