Linux 内核 CFS 调度器深度工程实战：从红黑树时间片到 cgroup 带宽控制

1 阅读 0 评论 0 点赞

Linux 内核 CFS 调度器深度工程实战：从红黑树时间片到 cgroup 带宽控制

摘要

完全公平调度器（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 系统调优的半壁江山。

点赞(0) 打赏

本文分类：编程技术
本文标签：Linux 内核 CFS 调度器进程管理 cgroup 性能调优
浏览次数：1 次浏览
发布日期：2026-10-01 09:38:41
本文链接：https://www.ybb.press/programming/10528.html

Linux 内核 CFS 调度器深度工程实战：从红黑树时间片到 cgroup 带宽控制

Linux 内核 CFS 调度器深度工程实战：从红黑树时间片到 cgroup 带宽控制

摘要

一、CFS 设计哲学

1.1 理想多任务处理器模型

1.2 CFS 的三条公理

1.3 与 O(1) 调度器的本质区别

二、核心数据结构

2.1 struct sched_entity —— 调度实体

2.2 struct cfs_rq —— CFS 运行队列

2.3 struct rq —— 每个 CPU 的运行队列

三、虚拟运行时间机制

3.1 vruntime 计算公式

3.2 vruntime 更新的时机

3.3 min_vruntime 的意义

四、红黑树调度算法

4.1 选择下一个进程

4.2 红黑树插入与删除

4.3 缓存优化：O(1) 取最左

五、调度时机与抢占机制

5.1 触发调度的条件

5.2 唤醒抢占（Wake Preempt）

5.3 理想运行时间（ideal_runtime）计算

六、Nice 值与权重映射

6.1 sched_prio_to_weight 数组

6.2 权重比例效应

七、组调度（Group Scheduling）

7.1 层级化调度模型

7.2 带宽控制（CPU Bandwidth）

7.3 节流恢复机制

八、NUMA 感知与负载均衡

8.1 调度域层级

8.2 PELT（Per-Entity Load Tracking）

8.3 负载均衡触发时机

九、CFS 与实时调度的协同

9.1 调度类优先级

9.2 SCHED_IDLE 的实现原理

十、CFS 调优参数全解析

10.1 sysctl 核心参数

10.2 推荐调优场景

十一、cgroup v2 中的 CPU 控制器

11.1 cpu.weight 与 cpu.max

11.2 对比表

十二、生产环境实战案例

案例 1：游戏服务器帧率不稳问题

案例 2：容器 CPU 争抢导致 SLA 下降

案例 3：大数据批处理与在线服务混部

十三、调试与观测工具

13.1 sched_debug

13.2 perf sched

13.3 BPF 跟踪

13.4 cgroup 监控

十四、CFS 的未来演进

14.1 EEVDF 调度器

14.2 其他演进方向

十五、总结

Linux I/O 栈与块层架构深度实战：从 VFS 到 io_uring 的全链路透视

Linux 用户命名空间深度实战：UID映射、Capabilities边界与容器隔离的工程真相

Linux 内核进程调度器深度实战：从 CFS 到 EEVDF 的演进之路

Linux 内核网络栈深度实战：从 Socket 到网卡驱动的完整数据路径

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复