摘要
完全公平调度器(Completely Fair Scheduler, CFS)是 Linux 内核自 2.6.23 版本起取代 O(1) 调度器的默认进程调度器。CFS 以其独特的"理想多任务处理器"模型和基于虚拟运行时间(vruntime)的红黑树调度算法,彻底改变了 Linux 的进程调度方式。本文将从 CFS 的设计哲学出发,深入剖析其内核实现架构、核心数据结构、调度策略以及与 cgroup 的集成,并结合生产环境中的调优实战案例,帮助读者全面掌握 CFS 的工程实践。
一、CFS 设计哲学
1.1 理想多任务处理器模型
CFS 的核心思想来源于一个理论模型——理想多任务处理器(Ideal Multitasking Processor)。在理想处理器上,每个进程在任意时刻都能获得 1/N 的 CPU 时间(N 为可运行进程数),实现完美的时间片分配。
然而现实中单核 CPU 同一时刻只能执行一个进程,CFS 通过追踪每个进程的虚拟运行时间(virtual runtime, vruntime),选择 vruntime 最小的进程执行,从而在宏观上逼近理想处理器的公平性。
1.2 CFS 的三条公理
- 公平性公理:所有可运行进程在任意时间段内获得的 CPU 时间与其权重成正比
- 连续性公理:进程在满足条件时应能连续运行,避免不必要的上下文切换
- 延迟公理:调度延迟(从唤醒到首次运行的时间)应尽可能小且可预测
1.3 与 O(1) 调度器的本质区别
| 对比维度 | O(1) 调度器 | CFS |
|---|---|---|
| 时间片计算 | 固定时间片 + 动态优先级 | 基于 vruntime 的连续时间核算 |
| 数据结构 | 140 级优先级数组 | 红黑树(按 vruntime 排序) |
| 复杂度 | O(1) 选择 | O(log N) 插入/删除 |
| 交互性启发 | 复杂睡眠评分(bonus/penalty) | 简单公平原则(vruntime 单调递增) |
| NUMA 友好 | 差(硬亲和队列) | 良好(per-runqueue + load balancing) |
二、核心数据结构
2.1 struct sched_entity —— 调度实体
// include/linux/sched.h
struct sched_entity {
struct load_weight load; // 负载权重(基于 nice 值)
struct rb_node run_node; // 红黑树节点
struct list_head group_node; // 调度组链表
unsigned int on_rq; // 是否在运行队列上
u64 exec_start; // 本次执行开始时间
u64 sum_exec_runtime; // 累计实际运行时间
u64 vruntime; // 虚拟运行时间
u64 prev_sum_exec_runtime; // 切换前累计时间
u64 nr_migrations; // 迁移次数
struct sched_statistics statistics; // 调度统计
};
2.2 struct cfs_rq —— CFS 运行队列
// kernel/sched/sched.h
struct cfs_rq {
struct load_weight load; // 总权重
unsigned long runnable_weight; // 可运行权重总和
unsigned int nr_running; // 运行进程数
unsigned int h_nr_running; // 层级总数(含组调度)
u64 exec_clock; // 执行时钟(per-cpu)
u64 min_vruntime; // 队列最小 vruntime(单调递增)
u64 rq_clock_task; // 任务时钟(处理空闲时间扣除)
struct rb_root_cached tasks_timeline; // 红黑树根(cached = 最左节点指针)
struct sched_entity *curr, *next, *last, *skip;
int runtime_enabled;
s64 runtime_remaining;
struct cfs_bandwidth *cfs_bandwidth;
u64 throttled_clock, throttled_clock_task;
u64 throttled_clock_task_time;
int throttled, throttle_count;
};
2.3 struct rq —— 每个 CPU 的运行队列
struct rq {
raw_spinlock_t lock;
unsigned int nr_running;
struct cfs_rq cfs; // CFS 运行队列(普通进程)
struct rt_rq rt; // 实时运行队列
struct dl_rq dl; // Deadline 运行队列
struct task_struct *curr, *idle, *stop;
struct mm_struct *prev_mm;
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
unsigned long last_load_update_tick;
u64 nr_switches;
u64 nr_load_updates;
struct sched_avg avg; // PELT 负载跟踪
};
三、虚拟运行时间机制
3.1 vruntime 计算公式
// 核心计算:将实际运行时间按权重归一化
delta_vruntime = (delta_exec * NICE_0_LOAD) / se->load.weight;
// NICE_0_LOAD = 1024(对应 nice=0 的权重)
3.2 vruntime 更新的时机
- 时钟 tick 中断:task_tick_fair() 周期性更新当前进程的 vruntime,并检查是否需要抢占
- 进程唤醒:enqueue_entity() 时将唤醒进程的 vruntime 与 min_vruntime 对齐,防止饥饿
- 进程切换:put_prev_entity() 时更新离开进程的 prev_sum_exec_runtime
- 进程创建:子进程继承父进程或 cfs_rq 的 min_vruntime
3.3 min_vruntime 的意义
min_vruntime 是 cfs_rq 中所有进程 vruntime 的单调递增下限。唤醒新进程时,vruntime = max(se.vruntime, min_vruntime),防止进程通过长时间睡眠获得不公平的优势。同时作为跨 CPU 迁移时的 vruntime 校准基准。
四、红黑树调度算法
4.1 选择下一个进程
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
struct cfs_rq *cfs_rq = &rq->cfs;
struct sched_entity *se;
// 红黑树最左节点(vruntime 最小)即为下一个调度目标
se = pick_next_entity(cfs_rq);
if (!se)
return NULL;
return task_of(se);
}
4.2 红黑树插入与删除
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
bool leftmost = true;
while (*link) {
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
if (entity_before(se, entry)) {
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = false;
}
}
rb_link_node(&se->run_node, parent, link);
rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost);
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
if (cfs_rq->tasks_timeline.rb_leftmost == &se->run_node) {
struct rb_node *next_node = rb_next(&se->run_node);
cfs_rq->tasks_timeline.rb_leftmost = next_node;
}
}
4.3 缓存优化:O(1) 取最左
CFS 在 cfs_rq->tasks_timeline 中存储了 rb_leftmost 指针,直接指向 vruntime 最小的节点,因此 pick_next_entity() 的复杂度为 O(1)。
五、调度时机与抢占机制
5.1 触发调度的条件
- 时间片耗尽:task_tick_fair() 中检查 if (delta_exec > ideal_runtime) 后调用 resched_curr(rq)
- 唤醒抢占:新唤醒进程的 vruntime 显著小于当前进程时,触发抢占
- yield/syscall:进程调用 sched_yield() 主动让出
- IO 阻塞:进程进入睡眠后,原来占用 CPU 的机会释放
5.2 唤醒抢占(Wake Preempt)
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
{
struct task_struct *curr = rq->curr;
struct sched_entity *se = &curr->se, *pse = &p->se;
// 抢占粒度阈值检查
if (delta < sysctl_sched_min_granularity)
return;
if (wakeup_preempt_entity(se, pse) == 1)
resched_curr(rq);
}
5.3 理想运行时间(ideal_runtime)计算
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
// sched_period = nr_running * sysctl_sched_latency(最小 6ms)
return slice;
}
六、Nice 值与权重映射
6.1 sched_prio_to_weight 数组
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
6.2 权重比例效应
- nice=0 vs nice=1: 1024:820 ≈ 1.25:1,前者多获得约 25% CPU
- nice=-5 vs nice=5: 3121:335 ≈ 9.3:1,前者是后者的近 10 倍
- nice=-20 vs nice=19: 88761:15 ≈ 5917:1
七、组调度(Group Scheduling)
7.1 层级化调度模型
struct task_group {
struct sched_entity **se; // 每个 CPU 一个 se
struct cfs_rq **cfs_rq; // 每 CPU 一个 cfs_rq
struct rcu_head rcu;
struct list_head list;
struct task_group *parent;
struct list_head siblings;
struct list_head children;
unsigned long shares; // CPU 份额权重
atomic_long_t load_avg;
};
7.2 带宽控制(CPU Bandwidth)
struct cfs_bandwidth {
raw_spinlock_t lock;
ktime_t period; // 周期(默认 100ms)
u64 quota; // 每周期配额(微秒)
u64 runtime; // 剩余配额
struct hlist_head throttled_cfs_rq;
u64 nr_periods, nr_throttled;
u64 throttled_time;
};
7.3 节流恢复机制
当 cgroup 的 runtime_remaining 耗尽时触发节流(throttle),将 cfs_rq 从红黑树移除。下一个 period 到来时,unthrottle 恢复调度。
八、NUMA 感知与负载均衡
8.1 调度域层级
- MC 域:同一物理芯片内核心间均衡
- SIBLING 域:同一核心的超线程兄弟间均衡
- DIE 域:同一封装内芯片间均衡
- NUMA 域:跨 NUMA 节点间的均衡(代价最高)
8.2 PELT(Per-Entity Load Tracking)
// 衰减公式:y^n = y^(n-1) * y + load * (1 - y)
// 其中 y = 0.5^(1/32) ≈ 0.979,32ms 半衰期
// PELT 使用指数衰减移动平均估算每个 se 的负载贡献
8.3 负载均衡触发时机
- IDLE 均衡:CPU 即将空闲时,从其他 CPU 拉取任务
- SCHED_TICK 均衡:tick 中周期性不平衡检查
- NEWIDLE 均衡:从空闲状态被唤醒时立即均衡
九、CFS 与实时调度的协同
9.1 调度类优先级
- SCHED_DEADLINE(dl_sched_class):基于 EDF + CBS,最高优先级
- SCHED_FIFO/SCHED_RR(rt_sched_class):固定优先级实时
- SCHED_NORMAL(fair_sched_class):CFS,处理分时任务
- SCHED_IDLE:极低优先级(权重=3),仅空闲时运行
9.2 SCHED_IDLE 的实现原理
SCHED_IDLE 通过极低的权重(=3)实现。当系统有其他进程时,SCHED_IDLE 进程的 vruntime 增长极慢(vruntime = delta_exec * 1024 / 3),因此几乎不会被选中。
十、CFS 调优参数全解析
10.1 sysctl 核心参数
| 参数 | 默认值 | 含义 |
|---|---|---|
| sched_latency_ns | 24 ms | 目标调度延迟(所有进程至少跑一遍的时间) |
| sched_min_granularity_ns | 3 ms | 最小调度粒度(时间片下限) |
| sched_wakeup_granularity_ns | 4 ms | 唤醒抢占粒度(防止唤醒时过度抢占) |
| sched_migration_cost_ns | 500 μs | 进程迁移成本(高于此值才考虑迁移) |
| sched_nr_migrate | 32 | 单次负载均衡最大迁移进程数 |
| sched_time_avg_ms | 1000 | PELT 负载平均窗口 |
| sched_shares_window | 10 ms | CFS 组调度份额计算窗口 |
10.2 推荐调优场景
场景 1:低延迟交易系统
sysctl -w kernel.sched_latency_ns=4000000
sysctl -w kernel.sched_min_granularity_ns=500000
sysctl -w kernel.sched_wakeup_granularity_ns=1000000
场景 2:高吞吐批处理
sysctl -w kernel.sched_latency_ns=48000000
sysctl -w kernel.sched_min_granularity_ns=6000000
场景 3:Web 服务器
sysctl -w kernel.sched_latency_ns=12000000
sysctl -w kernel.sched_wakeup_granularity_ns=1500000
十一、cgroup v2 中的 CPU 控制器
11.1 cpu.weight 与 cpu.max
# 设置 CPU 权重(范围 1-10000)
echo "5000" > /sys/fs/cgroup/mygroup/cpu.weight
# 设置带宽上限
echo "50000 100000" > /sys/fs/cgroup/mygroup/cpu.max
# 状态查看
cat /sys/fs/cgroup/mygroup/cpu.stat
11.2 对比表
| 对比维度 | cgroup v1 cpu | cgroup v2 cpu.max |
|---|---|---|
| 接口名 | cfs_quota_us / cfs_period_us | cpu.max(配额 周期) |
| 默认行为 | 无限制 | 无限制 |
| 节流粒度 | 1 ms 精度 | 1 μs 精度 |
| 多层控制 | 继承但独立 | 严格嵌套约束 |
十二、生产环境实战案例
案例 1:游戏服务器帧率不稳问题
问题:游戏逻辑线程因频繁被网络线程抢占导致帧率不稳定。
诊断:通过 perf sched latency 发现调度延迟峰值达 8ms。
解决:
taskset -cp 2,3 game_logic_pid
chrt -r 50 network_io_pid
sysctl -w kernel.sched_min_granularity_ns=200000
sysctl -w kernel.sched_latency_ns=8000000
案例 2:容器 CPU 争抢导致 SLA 下降
问题:Kubernetes 集群中某节点上的 Pod 因 CPU 争抢导致 p99 延迟飙升。
诊断:cfs_throttled_usec 持续增长。
解决:精确设定 CPU limit + Burstable QoS + 节点亲和。
案例 3:大数据批处理与在线服务混部
systemctl set-property online-service.service CPUShares=1024
chrt -i 0 batch_task_pid
echo 100 > /sys/fs/cgroup/batch/cpu.weight
十三、调试与观测工具
13.1 sched_debug
cat /proc/sched_debug | grep -A 20 "cfs_rq"
cat /proc/[pid]/sched
13.2 perf sched
perf sched record -a sleep 30
perf sched latency --sort max
perf sched map
perf sched replay
13.3 BPF 跟踪
SEC("tp_btf/sched_switch")
int BPF_PROG(trace_sched_switch, bool preempt,
struct task_struct *prev,
struct task_struct *next)
{
u32 prev_pid = BPF_CORE_READ(prev, pid);
u32 next_pid = BPF_CORE_READ(next, pid);
u64 prev_vruntime = BPF_CORE_READ(prev, se.vruntime);
bpf_printk("CFS: switch PID/%d vruntime=%lu -> PID/%d preempt=%d",
prev_pid, prev_vruntime, next_pid, preempt);
return 0;
}
13.4 cgroup 监控
watch -n 1 'cat /sys/fs/cgroup/*/cpu.stat | grep throttled'
systemd-cgtop --depth=3
十四、CFS 的未来演进
14.1 EEVDF 调度器
Linux 6.6+ 引入了 EEVDF(Earliest Eligible Virtual Deadline First)作为 CFS 的替代选项。EEVDF 通过为每个调度实体计算明确的截止时间来解决 CFS 在高负载下的延迟问题:
- 优势:消除 sched_latency_ns 的可调性依赖,自动适应负载变化
- 核心改进:使用 deadline 替代 vruntime 作为调度决策依据
- 兼容性:保留完全相同的用户态接口
14.2 其他演进方向
- 延迟敏感型 PSI(Pressure Stall Information)感知调度
- 热页感知的 NUMA 平衡与 sched_migrate_numa
- 与 io_uring 的异步 IO 协同调度优化
- 能源感知调度(EAS)对 CFS 负载均衡的影响
十五、总结
CFS 以其优雅的"理想多任务处理器"模型,成功平衡了公平性、吞吐量和响应延迟三大调度目标。其核心设计——虚拟运行时间追踪 + 红黑树优先级管理 + PELT 负载估算——不仅提供了理论上的最优公平性证明,更在工程实践中展现出卓越的可调性和鲁棒性。
对于系统工程师而言,深入理解 CFS 不仅是内核调优的基础,更是构建高性能、可预测系统的关键。从 SCHED_IDLE 的极低优先级保证、到 cgroup v2 cpu.max 的精微带宽控制、再到 NUMA 感知的多级负载均衡,CFS 提供的工具链覆盖了从嵌入式到数据中心的全场景需求。
掌握 CFS,就掌握了 Linux 系统调优的半壁江山。

发表评论 取消回复