Linux CFS：为什么调度器里长了一棵红黑树
Linux 2.6.23 之前的 O(1) 调度器给每个 CPU 维护一个优先级数组，任务按 nice 值分桶，时间复杂度确实是 O(1)——只要扫桶找非空位就行。但这套方案对交互型任务不太友好，"公平"只是名义上的。Ingo Molnar 重写调度器时把整个思路翻转了：不再问"谁优先级最高"，而是问"谁最近欠 CPU 时间最多"。
CFS 给每个任务维护一个 virtual runtime（vruntime），每次调度挑 vruntime 最小的那个跑，跑完按实际运行时间给 vruntime 加权增长——nice 值越低权重越小，vruntime 涨得慢，就能更频繁地被选中。问题来了：怎么快速找到 vruntime 最小的任务？答案就是红黑树。rbtree 的所有节点按 vruntime 排序，树的最左节点永远是"最欠 CPU 债"的那个，取 O(log N)，删除和插入也是 O(log N)。相比之下，有序链表查找要 O(N)，跳表虽然也是 O(log N) 但常数更大、缓存不友好。
红黑树还有个好处：它不会像 AVL 树那样追求绝对平衡，最多允许红黑违反，旋转次数更少。调度场景里任务频繁进出 runqueue，插入删除是热路径，少旋转就意味着少锁竞争。rb_leftmost 缓存了最左节点指针，所以"找下一个任务"实际上是 O(1)——sched.c 里的
一个容易忽略的细节：新 fork 出来的子进程 vruntime 设为父进程的 vruntime，但如果树为空它会变成最左节点被立刻调度。CFS 用
#CS
Linux 2.6.23 之前的 O(1) 调度器给每个 CPU 维护一个优先级数组，任务按 nice 值分桶，时间复杂度确实是 O(1)——只要扫桶找非空位就行。但这套方案对交互型任务不太友好，"公平"只是名义上的。Ingo Molnar 重写调度器时把整个思路翻转了：不再问"谁优先级最高"，而是问"谁最近欠 CPU 时间最多"。
CFS 给每个任务维护一个 virtual runtime（vruntime），每次调度挑 vruntime 最小的那个跑，跑完按实际运行时间给 vruntime 加权增长——nice 值越低权重越小，vruntime 涨得慢，就能更频繁地被选中。问题来了：怎么快速找到 vruntime 最小的任务？答案就是红黑树。rbtree 的所有节点按 vruntime 排序，树的最左节点永远是"最欠 CPU 债"的那个，取 O(log N)，删除和插入也是 O(log N)。相比之下，有序链表查找要 O(N)，跳表虽然也是 O(log N) 但常数更大、缓存不友好。
红黑树还有个好处：它不会像 AVL 树那样追求绝对平衡，最多允许红黑违反，旋转次数更少。调度场景里任务频繁进出 runqueue，插入删除是热路径，少旋转就意味着少锁竞争。rb_leftmost 缓存了最左节点指针，所以"找下一个任务"实际上是 O(1)——sched.c 里的
pick_next_task_fair() 直接读缓存，不用遍历树。一个容易忽略的细节：新 fork 出来的子进程 vruntime 设为父进程的 vruntime，但如果树为空它会变成最左节点被立刻调度。CFS 用
min_vruntime 做了个兜底——新任务的 vruntime 至少不小于 min_vruntime，防止刚创建就抢占。#CS
