第三十八章：红黑树

结丹初期

涉及内核源码：

一

林小源在调度仙子的指引下，开始研究红黑树。

他蹲在红黑树的根部，伸手触摸那漆黑的树干。树干的质感很奇特——一半光滑如玉，一半粗糙如岩。红色的枝干上流淌着微弱的光芒，像血脉在跳动。黑色的枝干则沉默而厚重，像骨骼一样支撑着整棵树的结构。

"五条法则。"调度仙子站在他身旁，声音平静如诵经。

"第一，每个节点要么是红色，要么是黑色。第二，根节点永远是黑色。第三，所有叶子节点——也就是 NIL 节点——都是黑色。第四，红色节点的两个子节点必须是黑色。第五，从根到任何叶子的每条路径上，黑色节点的数量相同。"

林小源抬头看着这棵参天大树："这些法则保证了什么？"

"平衡。"调度仙子说，"最长路径不会超过最短路径的两倍。这意味着插入、删除、查找都是 O(log n)——即使树上有成千上万个节点。"

她指向树的最左侧，一个微微发亮的节点安静地悬在那里。

"那个是 ——最左节点，也就是 vruntime 最小的进程。我们缓存了它，所以 不需要遍历整棵树，直接返回最左节点即可。O(1)。"

林小源看着那个节点，突然注意到树干上刻着一些古老的符文。他凑近一看，发现那是内核的代码—— 和 。

"每次进程被唤醒或阻塞，"调度仙子解释道，"它的 就会从树上被取下或挂上。插入是 O(log n)，删除也是 O(log n)。"

二

林小源在树下坐了很久，观察着节点的移动。

他发现了一个有趣的现象：当一个进程的 vruntime 更新时，它需要在树中重新定位——先删除旧节点，再插入新节点。两次 O(log n) 操作。

"这不是很昂贵吗？"林小源问。

调度仙子摇头："CFS 有一个优化。如果进程只是继续运行——没有被抢占——它的 vruntime 更新不需要立即反映到红黑树中。只有当进程被抢占或主动让出 CPU 时，才需要更新红黑树。"

"延迟更新。"林小源喃喃道。

"对。"调度仙子说，"在内核中，'延迟'往往是一种优化。不是所有变化都需要立即生效——有时候，等到真正需要的时候再更新，效率更高。"

林小源想起了自己在炼气期学到的一个道理：不要每时每刻都检查自己的修为进度，而是在关键节点时才去审视。频繁的自我检查反而会消耗修炼的精力。

"不过，"调度仙子补充道，"红黑树的选择不是随意的。链表插入是 O(1)，但查找最左节点是 O(n)。堆插入是 O(log n)，查找最左是 O(1)，但它不支持高效的范围查询和前驱后继操作。红黑树在这些方面都有优势。"

三

就在这时，一个进程的光团从远处飞来，悬停在红黑树前。

"新进程，"调度仙子说，"它要入队了。"

林小源看到调度仙子的手指在空中划过，一道银光射向红黑树。树的结构开始调整——新节点被插入到正确的位置，红色和黑色的枝干重新排列，整棵树在几次微小的旋转后恢复了平衡。

"这就是 ，"调度仙子说，"插入一个节点，然后通过旋转和重新着色来维护红黑树的五条法则。整个过程是 O(log n)。"

林小源看着那棵重新平衡的树，突然意识到红黑树不仅仅是一个数据结构——它是调度仙子的天秤。每一个节点都在这把天秤上占据一个精确的位置，而天秤永远保持着平衡。

"如果有一天，"林小源问，"这棵树倒了呢？"

调度仙子看了他一眼，目光中带着一丝林小源读不懂的情绪。

"树不会倒，"她说，"只要五条法则还在，树就永远平衡。这是数学的保证，不是信仰。"

---

/*
 * 红黑树的性质：
 * 1. 每个节点是红色或黑色
 * 2. 根节点是黑色
 * 3. 所有叶子节点（NIL）是黑色
 * 4. 红色节点的两个子节点都是黑色
 * 5. 从根到叶子的每条路径上，黑色节点数相同
 *
 * 红黑树保证了：
 * - 最长路径 ≤ 2 × 最短路径
 * - 查找、插入、删除都是 O(log n)
 *
 * CFS 使用红黑树：
 * - 按 vruntime 排序
 * - 最左节点 = vruntime 最小 = 下一个运行的进程
 * - 缓存最左节点，O(1) 获取
 */

struct rb_node {
    unsigned long __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
};

struct sched_entity {
    struct rb_node run_node;
    unsigned long vruntime;
    int pid;
    char comm[16];
};

/* 简化的红黑树（用数组模拟中序遍历） */
struct rb_tree {
    int values[16];
    int count;
};

void rb_insert(struct rb_tree *tree, int value) {
    int i = tree->count;
    /* 简化：直接插入并排序 */
    tree->values[i] = value;
    tree->count++;
    /* 插入排序 */
    for (int j = i; j > 0 && tree->values[j] < tree->values[j-1]; j--) {
        int tmp = tree->values[j];
        tree->values[j] = tree->values[j-1];
        tree->values[j-1] = tmp;
    }
}

printf("=== 红黑树 — 调度的基石 ===\n\n");

/* 模拟几个进程的 vruntime */
struct rb_tree tree = { .count = 0 };

int vruntimes[] = { 1200, 800, 1500, 600, 1000, 900 };
const char *names[] = { "vim", "shell", "compiler", "cron", "ssh", "logger" };
int nr = sizeof(vruntimes) / sizeof(vruntimes[0]);

printf("插入进程到红黑树（按 vruntime 排序）：\n");
for (int i = 0; i < nr; i++) {
    rb_insert(&tree, vruntimes[i]);
    printf("  插入 %s (vruntime=%d)\n", names[i], vruntimes[i]);
}

printf("\n红黑树中序遍历（按 vruntime 排序）：\n");
for (int i = 0; i < tree.count; i++) {
    printf("  vruntime = %d", tree.values[i]);
    if (i == 0) printf("  ← 最左节点（下一个运行）");
    printf("\n");
}

printf("\n--- 红黑树的特性 ---\n");
printf("查找最左节点: O(1) — 缓存在 rb_leftmost\n");
printf("插入新节点:   O(log n)\n");
printf("删除节点:     O(log n)\n");
printf("更新 vruntime: O(log n) — 需要重新排序\n");

printf("\n--- 红黑树 vs 其他数据结构 ---\n");
printf("链表:   插入 O(1)，查找最左 O(n)\n");
printf("堆:     插入 O(log n)，查找最左 O(1)\n");
printf("红黑树: 插入 O(log n)，查找最左 O(1)\n");
printf("        额外支持范围查询、前驱后继\n");

---

道藏笔记

内核启示

红黑树是 CFS 的核心数据结构。

红黑树的性质：

• 自平衡二叉搜索树
• 最长路径 ≤ 2 × 最短路径
• 查找、插入、删除都是 O(log n)

CFS 中的红黑树：

• 按 排序
• 最左节点 = 最小的进程
• 缓存最左节点， 是 O(1)

红黑树的操作：

• — 插入调度实体
• — 删除调度实体
• — 获取最左节点

为什么选择红黑树：

• 有序性：最左节点总是 最小
• 平衡性：O(log n) 的插入和删除
• 额外功能：范围查询、前驱后继

红黑树是调度仙子的天秤——永远平衡，永远公平。

---

破关试炼

红黑树之试

本章讲红黑树收纳可运行任务时，负责把调度实体放入树中的函数是什么？

答对后才能继续滑动和进入下一章。

← 上一回下一回 →