Linux 调度器的红黑树：CFS 如何用一棵树做到"绝对公平"
早年的 Linux 调度器管理进程的方式很粗暴——把所有可运行进程串在链表里，要找下一个谁跑就从头扫到尾。进程少的时候没问题，一旦服务器上跑了几千个进程，每次调度都在做无用功。2007年，这个矛盾终于激化：社区推出了好几种替代方案，最终 Ingo Molnar 的 CFS（完全公平调度器）被合入主线。
CFS 的设计哲学干净得令人愉悦。它抛弃了传统的时间片概念，只维护一个量：每个进程的 vruntime（虚拟运行时间）。逻辑再简单不过——谁累积的 vruntime 最小，谁就最"亏"，就该下一个跑。你不需要优先级数组，不需要过期队列，不需要一堆 if-else。但问题来了：怎么在一个动态变化的集合里始终快速拿到最小值？唤醒的进程要插入，阻塞的进程要删除，每一微秒都在发生。
CFS 的答案是一棵红黑树。所有处于可运行状态的进程以 vruntime 为 key 挂在红黑树上。红黑树的自平衡特性保证了查找、插入、删除都是 O(log n)。而最左节点永远是 vruntime 最小的那个——取下一个进程只需 O(1)，沿着 tree->rb_leftbost 往左走一步就行。相比之下，旧调度器的代码里维护着活跃数组和过期数组两套链表，还得在它们之间做转移，充满了边界条件。CFS 用一棵树把这些特殊情况全部消除了。
值得一说的是为什么选红黑树而不是堆。堆找最小值确实是 O(1)，但进程不光是从队列头部离开——一个进程可能因为等待 I/O 从树的任何位置被移走。堆删除中间节点是 O(n)，而红黑树删除任意位置节点是 O(log n)。
#CS
早年的 Linux 调度器管理进程的方式很粗暴——把所有可运行进程串在链表里，要找下一个谁跑就从头扫到尾。进程少的时候没问题，一旦服务器上跑了几千个进程，每次调度都在做无用功。2007年，这个矛盾终于激化：社区推出了好几种替代方案，最终 Ingo Molnar 的 CFS（完全公平调度器）被合入主线。
CFS 的设计哲学干净得令人愉悦。它抛弃了传统的时间片概念，只维护一个量：每个进程的 vruntime（虚拟运行时间）。逻辑再简单不过——谁累积的 vruntime 最小，谁就最"亏"，就该下一个跑。你不需要优先级数组，不需要过期队列，不需要一堆 if-else。但问题来了：怎么在一个动态变化的集合里始终快速拿到最小值？唤醒的进程要插入，阻塞的进程要删除，每一微秒都在发生。
CFS 的答案是一棵红黑树。所有处于可运行状态的进程以 vruntime 为 key 挂在红黑树上。红黑树的自平衡特性保证了查找、插入、删除都是 O(log n)。而最左节点永远是 vruntime 最小的那个——取下一个进程只需 O(1)，沿着 tree->rb_leftbost 往左走一步就行。相比之下，旧调度器的代码里维护着活跃数组和过期数组两套链表，还得在它们之间做转移，充满了边界条件。CFS 用一棵树把这些特殊情况全部消除了。
值得一说的是为什么选红黑树而不是堆。堆找最小值确实是 O(1)，但进程不光是从队列头部离开——一个进程可能因为等待 I/O 从树的任何位置被移走。堆删除中间节点是 O(n)，而红黑树删除任意位置节点是 O(log n)。
#CS
