1. 课程导论：红黑树在Linux内核进程调度器（CFS）中的核心作用与历史背景

1.1 为什么是红黑树？——CFS调度器的数据结构之选

Linux内核的完全公平调度器（CFS，Completely Fair Scheduler）自2.6.23版本引入以来，一直是主流调度方案。CFS的核心目标是在O(log n)时间内完成“下一个运行进程”的选取，同时支持高效的进程插入与删除。红黑树（Red-Black Tree）因其自平衡特性与严格的时间复杂度保证，成为CFS虚拟运行时间（vruntime）组织的不二之选。

1.2 红黑树在CFS中的具体角色

CFS为每个调度实体（struct sched_entity）维护一个虚拟运行时间（vruntime）。所有可运行进程按vruntime组织在一棵红黑树中：

• 键值： 进程的 vruntime，值越小表示该进程获得的CPU时间越少，越应被优先调度。
• 最左节点： 红黑树中vruntime最小的节点，即下一个被调度运行的进程。
• 插入时机： 进程变为可运行状态（如唤醒、fork新进程、时间片耗尽后重新入队）。
• 删除时机： 进程进入睡眠、退出或被迁移到其他CPU。
• 查找操作： 每次时钟tick或调度点触发时，通过 __pick_next_entity() 获取最左节点。

1.3 历史背景：从O(1)调度器到CFS

Linux调度器经历了三次重大演进，红黑树的引入是其中最关键的数据结构变革：

1. 早期调度器（v2.4及之前）： 基于循环链表，O(n)复杂度，多CPU扩展性差。
2. O(1)调度器（v2.6.0~v2.6.22）： 引入优先级数组（bitmap + 多级队列），O(1)时间复杂度，但交互式进程识别启发式算法复杂，公平性不足。
3. CFS + 红黑树（v2.6.23至今）： 由Ingo Molnár设计，彻底抛弃优先级数组，改用红黑树按vruntime排序，实现真正的“完全公平”。

1.4 红黑树在Linux内核中的实现架构

Linux内核的红黑树实现位于 lib/rbtree.c 和 include/linux/rbtree.h，CFS调度器通过以下接口与红黑树交互：

/* 红黑树核心结构（简化） */
struct rb_node {
    unsigned long  __rb_parent_color;  /* 父节点指针 + 颜色位 */
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

/* CFS 调度实体嵌入 rb_node */
struct sched_entity {
    struct rb_node      run_node;       /* 红黑树节点 */
    unsigned long       vruntime;       /* 虚拟运行时间（排序键） */
    struct sched_entity *parent;        /* 调度组父实体 */
    /* ... 其他字段 ... */
};

/* 核心操作函数 */
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
extern struct rb_node *rb_first(const struct rb_root *);

1.5 本课程学习路径

本课程将围绕红黑树在CFS中的插入与查找算法展开，共30章，覆盖以下核心模块：

• 红黑树基础（第2~8章）： 五条性质、旋转操作、插入修复、删除修复，附带完整代码实现。
• CFS调度器深度解析（第9~18章）： vruntime计算、enqueue_entity/dequeue_entity源码分析、pick_next_entity红黑树查找优化。
• 红黑树查找算法专项（第19~24章）： 最左节点查找、区间查找、范围查询在调度组（task group）中的应用。
• 性能调优与实战（第25~30章）： 红黑树自旋锁优化、NUMA感知调度、实时进程与红黑树的共存策略。