【操作系统百科】CFS 内部：vruntime 与红黑树

从 2007 年 2.6.23 合入到 2023 年被 EEVDF 取代，CFS 统治 Linux 主流调度路径 16 年。即使今天仍是 SCHED_NORMAL（与 EEVDF 共享基础设施）的核心词汇。懂 CFS 就懂 Linux 交互式调度器 80% 的机制。

一、先看图：核心数据结构

flowchart TB
    PT[per-CPU rq] --> CFS[cfs_rq]
    CFS --> RT[runqueue 红黑树<br/>按 vruntime 排序]
    RT --> L[最左节点<br/>= 下一个选中]
    RT --> N1[node]
    RT --> N2[node]
    RT --> N3[node]
    N1 --> SE[sched_entity]
    SE --> T[task_struct]
    SE -. group .-> GSE[sched_entity<br/>表示一个 group]
    GSE --> SUBCFS[sub cfs_rq<br/>递归调度]
    CFS --> MIN[min_vruntime<br/>单调递增]
    classDef k fill:#388bfd22,stroke:#388bfd,color:#adbac7;
    classDef h fill:#3fb95022,stroke:#3fb950,color:#adbac7;
    class PT,CFS,RT,N1,N2,N3,SE,T,GSE,SUBCFS k
    class L,MIN h

要点：

每 CPU 一个 cfs_rq，不共享
红黑树键是 vruntime - cfs_rq->min_vruntime
pick_next_task_fair = 最左节点 O(log n)
组调度：sched_entity 可以是 task 也可以是 group，group 里又有 sub cfs_rq

二、vruntime 的公式

每 ns 真实运行，vruntime 增加：

delta_vruntime = delta_exec * NICE_0_LOAD / se->load.weight

NICE_0_LOAD = 1024（nice 0 的权重）。权重表按 nice 级别：nice 每减 1，权重 × 1.25（粗略）。

结果：nice 0 的 vruntime 按真实时间 1:1 涨；nice -5 的 vruntime 涨得更慢（权重大），因此总被选；nice 19 的 vruntime 涨得飞快。

这样”公平”被重新定义为：按权重比例分配 CPU。

三、min_vruntime 与新任务

min_vruntime 记录本 cfs_rq 里最小 vruntime，且单调不减（防倒退）。

新 fork 的 task：se->vruntime = cfs_rq->min_vruntime + sched_vslice(cfs_rq, se)。这样新任务不会立刻抢占大家（加一段 slack），也不会被老任务饿（有个合理起点）。

migration 进来的任务也要调整：从源 CPU 的 min_vruntime 体系换到目标 CPU，不然会”白吃便宜”。

四、sched_latency_ns：调度周期

CFS 的”周期”目标：所有 runnable 任务应在 sched_latency_ns（默认 6ms，有 sched_latency_ns/sched_tunable_scaling sysctls）内都跑一次。

但 runnable 数量多时每人分到的变短。下限是 sched_min_granularity_ns（默认 0.75ms），避免切换太频繁。

任务数 n > sched_nr_latency（= latency / min_gran ≈ 8）时，周期变为 n * min_gran。

实践：服务器调 kernel.sched_latency_ns = 24ms（大周期）降 context switch；桌面保默认。6.6+ EEVDF 把这些 tunable 改名 / 淘汰。

五、wake-up preemption

新任务唤醒时，是否立刻抢当前 running？

规则（简化）：

如果唤醒任务 vruntime + sched_wakeup_granularity_ns < current vruntime → 抢
否则等下次 tick

sched_wakeup_granularity_ns 默认 1ms——避免乒乓。

WAKE_AFFINE 启发式：唤醒者和被唤醒者之间的亲和性（I/O 完成唤醒生产者，希望在同 CPU 利用 cache）。sysctl kernel.sched_wakeup_granularity_ns 可调。

六、group scheduling 与 autogroup

6.1 task group

struct task_group 把一批进程放在同一层，对外表现为一个 sched_entity 与其他 group/task 公平。

开启 CONFIG_FAIR_GROUP_SCHED，每个 cgroup 对应一个 task_group，cgroup 间按 cpu.weight 公平。

6.2 autogroup

桌面场景：bash 里并发编译 make -j100，全部进程权重相当 → 其他单进程应用（浏览器）被饿。

解决：每个 session leader（shell）开自己的 autogroup。同一 shell 里 100 个 gcc 在这个 autogroup 里内部竞争，autogroup 作为整体跟浏览器 session 的 autogroup 公平。

效果：桌面响应显著改善。默认开（/proc/sys/kernel/sched_autogroup_enabled = 1）。

七、load tracking：PELT

PELT（Per-Entity Load Tracking）给每个 sched_entity 一个 load_avg 和 util_avg，指数移动平均：

load_avg_n+1 = load_avg_n * y + delta_load
   其中 y = 0.97857206 (半衰期 32ms)

用途：

负载均衡：CPU 间比较 load_avg
频率调节：schedutil 用 util_avg 预测所需频率
异构：util_avg / capacity 判断是否”跑不动”，触发 misfit migration（C-25）

八、常用 sysctl（旧 CFS，EEVDF 重命名部分）

kernel.sched_latency_ns          # 调度周期目标
kernel.sched_min_granularity_ns  # 最小时间片
kernel.sched_wakeup_granularity_ns
kernel.sched_migration_cost_ns   # 迁移代价
kernel.sched_autogroup_enabled
kernel.sched_child_runs_first

/sys/kernel/debug/sched/* 提供更多（feature flags 如 WAKEUP_PREEMPTION、GENTLE_FAIR_SLEEPERS）。

九、CFS 的 pain points（促成 EEVDF）

CFS 的公平是”长期均匀”但短期无延迟保证：

交互式任务”感觉慢”：公平性保证了份额，但 tail latency 无界
sched_latency_ns 是全局旋钮，无法 per-task 调
vruntime 飙升的任务（long sleep）需要 min_vruntime “保底”，启发式多
GROUP fairness 与 per-task latency 冲突

EEVDF（C-21）引入”eligible + deadline”把延迟当第一等公民，latency-nice 让用户控制。

十、诊断 CFS 行为

cat /proc/<pid>/sched
# 看 se.vruntime、sum_exec_runtime、wait_sum、nr_wakeups_migrate

trace-cmd record -e sched_switch,sched_wakeup 抓事件。perf sched latency 给统计。

bpftrace -e 'tracepoint:sched:sched_stat_runtime { @[comm] = sum(args->runtime); }' 看哪进程吃 CPU。

十一、常见问题

问题 A：跑 yes > /dev/null & 三份，CPU 为什么不严格三等分？原因：nr_running < nr_latency，每个拿 latency/3 ≈ 2ms 时间片；tick 粒度 1ms，round-robin 粒度影响解：加大任务数量或减小 min_gran

问题 B：nice -n 19 tar ... 还是挤掉了我的 IDE 原因：autogroup 不同时 nice 只在 group 内；调整顺序或用 SCHED_IDLE

问题 C：容器里 cpu.weight 设了没效果原因：容器进程都跑在不同 CPU，负载不均；或 cpu.cfs_quota 硬限制先触发

问题 D：sched_latency 调大吞吐涨、但桌面卡原因：长周期意味着单次运行时间长，其他任务等得久解：生产服务器用长周期，桌面不要动

十二、小结

CFS 的三个核心：vruntime、红黑树、min_vruntime
权重决定 vruntime 涨速 → 决定被选频率
sched_latency_ns 是周期目标，sched_min_granularity_ns 是下限
autogroup 把桌面交互性拉回来
PELT 给负载均衡、频率调节统一的信号源

下一篇 C-21 讲 EEVDF——如何在”公平”里加上”延迟”这一维，成为 6.6 的新主力。

参考文献

Molnár, I. “CFS internals” 原始设计文档（kernel.org）
Jones, M.T. “Inside the Linux 2.6 Completely Fair Scheduler.” IBM developerWorks 2009
Documentation/scheduler/sched-design-CFS.rst
Corbet, J. “Per-entity load tracking.” LWN.net 2013
Corbet, J. “The CFS scheduler.” LWN.net 2007

工具

cat /proc/<pid>/sched /proc/<pid>/schedstat
perf sched record/latency
trace-cmd record -e sched
bpftrace sched tracepoints
/sys/kernel/debug/sched/ — feature flags

上一篇：调度理论 下一篇：EEVDF：取代 CFS 的新算法

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-04-27 · os