摘要

完全公平调度器(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 调度类优先级

  1. SCHED_DEADLINE(dl_sched_class):基于 EDF + CBS,最高优先级
  2. SCHED_FIFO/SCHED_RR(rt_sched_class):固定优先级实时
  3. SCHED_NORMAL(fair_sched_class):CFS,处理分时任务
  4. SCHED_IDLE:极低优先级(权重=3),仅空闲时运行

9.2 SCHED_IDLE 的实现原理

SCHED_IDLE 通过极低的权重(=3)实现。当系统有其他进程时,SCHED_IDLE 进程的 vruntime 增长极慢(vruntime = delta_exec * 1024 / 3),因此几乎不会被选中。

十、CFS 调优参数全解析

10.1 sysctl 核心参数

参数默认值含义
sched_latency_ns24 ms目标调度延迟(所有进程至少跑一遍的时间)
sched_min_granularity_ns3 ms最小调度粒度(时间片下限)
sched_wakeup_granularity_ns4 ms唤醒抢占粒度(防止唤醒时过度抢占)
sched_migration_cost_ns500 μs进程迁移成本(高于此值才考虑迁移)
sched_nr_migrate32单次负载均衡最大迁移进程数
sched_time_avg_ms1000PELT 负载平均窗口
sched_shares_window10 msCFS 组调度份额计算窗口

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 cpucgroup v2 cpu.max
接口名cfs_quota_us / cfs_period_uscpu.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 系统调优的半壁江山。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论
立即
投稿

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部