Linux CFS调度器：vruntime与红黑树

可视化演示

展示vruntime公平调度、红黑树组织、权重换算与调度延迟调优。

公平调度理念

回到幼儿园的滑梯。假如老师规定“按名单循环，每人滑一次就换人”，动作慢的孩子会拖垮整条队伍；假如只看谁哭得最凶，场面迟早失控。老师真正需要的，是一把让所有人都服气的“公平尺子”——它不搞平均主义，而是承认每个孩子的不同，同时保证没人被饿着。

Linux 的 CFS（完全公平调度器，Completely Fair Scheduler）面对的是同一个难题：CPU 只有那么一两个核，可运行进程却有几十上百个。CFS 给出的公平定义是：在一段足够长的时间里，每个进程获得的 CPU 时间，应当与其权重（weight）成正比。权重越高的进程，理应分得越多的计算资源。

这个“按权重分时间”的理想，最早来自“理想多任务处理器”（Ideal Multi-Processing）：假设有无限核，每个进程都能同时以自己应有的速度前进。CFS 在单核上做不到“同时”，却可以用时间上的轮换来逼近这种公平。每个进程应得的 CPU 份额，写出来就是：

份额公式是老师心里的分配蓝图，但蓝图不能直接拿给孩子看——老师需要的是“实地记账”：每滑一次记一笔，账本上数字最小的孩子优先。从蓝图到账本，中间还差一枚决定“记多少墨水”的徽章，也就是下一节的权重。

调度实体与权重

幼儿园里，每个孩子胸前都别着一枚徽章，徽章亮度由“nice 老师”评定：越是被照顾的孩子，徽章越亮，滑一次在账本上“抵扣”的墨水越多。在 CFS 的世界里，徽章就是权重（weight），而发放规则来自一个叫 nice 值的数字。

nice 值范围是 -20 到 19，默认 0。数值越大，代表进程越“谦让”，权重越低；数值越小，权重越高。需要注意的是，权重不直接挂在进程上，而是挂在“调度实体”（sched_entity）上——调度实体可以是线程，也可以是一整组进程，只要是内核需要单独排队、单独记账的对象都算。这个抽象，为后面的组调度埋下了伏笔。

nice 值到权重的换算，内核用一张预计算好的表（sched_prio_to_weight）查出来，相邻 nice 等级之间大约相差 1.25 倍。写成近似公式就是：

把徽章亮度和份额公式合在一起，老师就能算出每个孩子在一次轮换中该滑多久。但记账本上的数字怎么记，才能让 VIP 孩子“滑得多却记得少”？这就需要一本会“变魔术”的账——vruntime。

vruntime计算

老师发下了记账本：每个孩子一页，每次滑完就记一笔“已滑次数”。但记法有讲究——徽章越亮的孩子，记一笔用的墨水越少。普通孩子滑 1 秒记 1 格，而徽章亮度 2048 的孩子滑 1 秒只记 0.5 格。这样 VIP 孩子即使滑得久，账本数字也可能不高，下次依然轮得到他。

这本记账就是 vruntime（虚拟运行时间）。它衡量的是进程“在公平标尺下已经消耗的 CPU”，而不是墙上的钟表时间。“虚拟”二字是灵魂：同样的真实运行时长，经过权重修正后，记到不同进程账上就变成不同的数字。

CFS 在时钟 tick、进程入队、出队、唤醒等时机调用 update_curr() 累计 vruntime，核心公式是：

有个反直觉但极其重要的细节：睡眠中的进程不累计 vruntime。一个进程睡 1 秒再醒来，账本数字还停在原处，而运行队列里其他进程的账本已经往前走了一段，于是它一醒来就是“账上最少的人”，会立刻被选中运行。这正是交互式程序（比如编辑器、聊天框）能保持丝滑响应的原因。

记账哲学一句话：账上数字越小，代表在公平尺度下“欠”得越多，下一次就该优先补偿。CFS 每时每刻都要找到账上最小的那个孩子——几十个孩子还好说，几百上千个孩子时，老师怎么保证翻账本不花时间？答案是一本神奇的活页夹：红黑树。

红黑树组织

老师的记账本不是普通本子，而是一个“永远按已滑次数从小到大排列”的魔法活页夹。孩子滑完一次，老师涂改数字，再把那页插回正确位置。无论什么时候翻开第一页，看到的永远是“最该滑的孩子”，不用从头一页页比较。

这个魔法活页夹，在 CFS 里就是红黑树（Red-Black Tree）。每个 CPU 的运行队列（cfs_rq）维护一棵红黑树，以每个进程的 vruntime 为键值。进程该运行时，直接取最左叶子——它就是 vruntime 最小的进程。

红黑树保证插入、删除、查找都在对数时间内完成：

为了更快，内核还专门缓存了最左节点指针（rb_leftmost），让“找下一个运行进程”在绝大多数情况下几乎是 O(1) 的；只有插入、删除新节点后，才需要沿着树做几次旋转来维持平衡。左旋、右旋、变色这些动作听起来玄，本质就是老师整理活页夹时做的“厚度调整”，保证翻书永远不慢。

有了这本活页夹，老师可以瞬间找到最该滑的孩子。但新的麻烦来了：如果每次都只滑 0.1 秒就换人，孩子们光爬上爬下就耗光了时间。老师必须定两条班规：多久必须轮到一次，一次最少滑多久——这就是调度延迟与最小粒度。

调度延迟参数

老师宣布两条班规。第一条：“任何等待的孩子，最多等一轮，就一定能滑上一次。”这个承诺的时间窗口，就叫调度延迟。第二条：“一次滑行最短也得满 0.75 秒。”因为爬上滑梯、系好坐垫都要开销，换人太勤反而浪费，这一条叫最小粒度。

内核里这两个参数分别是 sysctl_sched_latency（默认 6ms）和 sysctl_sched_min_granularity（默认 0.75ms）。当就绪进程很少时，老师可以直接兑现 6ms 的承诺；可一旦等待的孩子超过 8 个（6ms ÷ 0.75ms），再坚持 6ms 就没人能滑满 0.75 秒，周期只好随人数线性增长：

周期定了，再套用份额公式，每个进程在一个周期内能分到的运行时间就是：

班规的本质是在两个目标之间走钢丝：等待时间短（响应性好）与切换开销小（吞吐量大）。6ms 和 0.75ms 不是拍脑袋定的，而是“每轮最多等 6ms、每人至少滑 0.75ms”这两条朴素承诺的平衡点。听懂这两条班规，就听懂了 CFS 一切调参行为的底层逻辑。

组调度公平性

幼儿园里还有班级。如果只盯着每个孩子记账，一个班 40 个孩子就天然比 10 个孩子的班“人均吃亏”。老师说：先保证每个班的总滑行时间公平，再在班里按徽章公平分配。于是记账本不再只有孩子这一层，班级本身也开了一本账。

这正对应内核的组调度（CONFIG_FAIR_GROUP_SCHED）：cgroup 把进程组织成树形层级，每一层都是一个调度实体。组先作为整体参与上一层 CFS 竞争，赢得的 CPU 时间再在组内按 vruntime 重新分配。公平因此有了递归结构——组间公平套着组内公平，层层嵌套。

组调度还带了“限流”功能：管理员可以给某个 cgroup 设定 CPU 带宽上限，参数是一对微秒值：

这套机制离 AI 和云原生一点都不远：Kubernetes 里给 Pod 设 CPU limit=2，底层写的就是 cfs_quota_us=200000、cfs_period_us=100000。你写下的每个资源请求，最终都变成 CFS 教室里的一次记账。幼儿园老师当年那本活页夹，如今撑起了整个容器世界的资源公平。

AI 应用场景

Python 演示

class SchedEntity:    """一个可被调度的实体: 线程或进程组."""    def __init__(self, name, weight):        self.name = name        self.weight = weight        self.vruntime = 0.0        self.actual_runtime = 0.0     def __repr__(self):        return "{}: vr={:.2f} runtime={:.1f}ms".format(            self.name, self.vruntime, self.actual_runtime)  def pick_next(entities):    """红黑树最左节点: 返回 vruntime 最小的实体."""    return min(entities, key=lambda e: e.vruntime)  def run_one_tick(entities, current, tick_ms):    """当前进程运行 tick_ms 毫秒, 并按权重更新 vruntime."""    base_load = 1024.0    current.actual_runtime += tick_ms    current.vruntime += tick_ms * base_load / current.weight    return current  def simulate(entities, total_ms=60.0, tick_ms=1.0):    timeline = []    now = 0.0    while now < total_ms - 1e-9:        current = pick_next(entities)        run_one_tick(entities, current, tick_ms)        now += tick_ms        timeline.append((round(now, 1), current.name, round(current.vruntime, 3)))    return timeline  def main():    kids = [        SchedEntity("P0", 1024),        SchedEntity("P1", 2048),        SchedEntity("P2", 512),        SchedEntity("P3", 3072),    ]    total_ms = 60.0    timeline = simulate(kids, total_ms=total_ms, tick_ms=1.0)    for t, name, vr in timeline:        print("t={:>4.1f}ms  run={}  vruntime={:.3f}".format(t, name, vr))    print("\n===== 公平性统计 (60ms) =====")    weight_sum = sum(k.weight for k in kids)    for k in kids:        ideal = total_ms * k.weight / weight_sum        print("{}: 实际={:.1f}ms 理论={:.1f}ms 偏差={:+.1f}ms".format(            k.name, k.actual_runtime, ideal, k.actual_runtime - ideal))  if __name__ == "__main__":    main()

1. base_load = 1024.0nice=0 的基准权重，对应 CFS 公式里的 1024。
2. current.vruntime += tick_ms * base_load / current.weight核心的 vruntime 累计公式，权重越高增量越小。
3. min(entities, key=lambda e: e.vruntime)模拟红黑树“取最左节点”，选出 vruntime 最小的进程。
4. ideal = total_ms * k.weight / weight_sum用份额公式算出理论公平时间，用来衡量模拟是否公平。
5. timeline = simulate(kids, total_ms=total_ms, tick_ms=1.0)以 1ms 为最小粒度跑完 60ms，输出每一步的调度日志。

常见误区

面试题