Linux内核进程调度器深度实战：从CFS完全公平调度到EEVDF的全链路剖析

15 阅读 0 评论 0 点赞

Linux内核进程调度器深度实战：从CFS完全公平调度到EEVDF的全链路剖析

引言

进程调度是操作系统的核心功能之一，直接决定了系统的吞吐量、响应时间和公平性。Linux内核的调度器经历了多次重大演进：从早期的O(n)调度器，到O(1)调度器，再到2.6.23版本引入的CFS（Completely Fair Scheduler，完全公平调度器），以及6.6版本正式合并的EEVDF（Earliest Eligible Virtual Deadline First，最早合格虚拟截止时间优先调度器）。

本文将深入剖析Linux内核进程调度的完整架构，从调度器类体系、CFS红黑树核心算法、vruntime计算机制，到EEVDF对CFS延迟问题的改进，结合内核源码、cgroup调优参数和生产环境排障案例，帮你彻底理解Linux进程调度的底层逻辑。

一、Linux调度器整体架构

1.1 调度器类（Scheduler Class）

Linux内核采用调度器类（sched_class）的优先级链表结构，支持多种调度策略并存：

stop_sched_class      → 最高优先级，用于CPU热插拔、migration
dl_sched_class        → SCHED_DEADLINE，EDF实时调度
rt_sched_class        → SCHED_FIFO / SCHED_RR，实时调度
fair_sched_class      → SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE，CFS/EEVDF
idle_sched_class      → 最低优先级，空转

关键数据结构sched_class定义了调度器的核心操作接口：

struct sched_class {
    void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*pick_next_task)(struct rq *rq, struct task_struct *p);
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*update_curr)(struct rq *rq);
    // ...
};

1.2 调度策略与优先级

用户空间通过sched_setscheduler()设置调度策略：

策略	类型	时间片	说明
SCHED_NORMAL	CFS	动态	普通分时进程（等同于SCHED_OTHER）
SCHED_BATCH	CFS	动态	批处理任务，降低唤醒抢占优先级
SCHED_IDLE	CFS	极低	极低优先级，仅在没有其他任务时运行
SCHED_FIFO	RT	无限	先进先出实时任务，运行到主动让出
SCHED_RR	RT	有	轮转实时任务，用尽时间片后排到队尾
SCHED_DEADLINE	Deadline	EDF	基于截止时间的实时调度

1.3 运行队列与每CPU调度

每个CPU核心拥有自己的运行队列（per-CPU runqueue），调度在选择下一个进程时优先从本地队列选取，减少跨CPU缓存失效。关键结构体：

struct rq {
    raw_spinlock_t lock;
    unsigned int nr_running;       // 可运行进程数
    unsigned long cpu_load[CPU_LOAD_IDX_MAX];
    struct cfs_rq cfs;             // CFS运行队列
    struct rt_rq rt;               // 实时运行队列
    struct dl_rq dl;               // Deadline运行队列
    struct task_struct *curr;      // 当前运行进程
    struct task_struct *idle;      // idle进程
    int cpu;
    // ...
};

二、CFS完全公平调度器核心算法

2.1 核心思想：虚拟运行时间（vruntime）

CFS的设计哲学是"理想多任务处理器"——如果有N个可运行进程，每个进程理论上应获得1/N的CPU时间。CFS不分配固定时间片，而是通过虚拟运行时间（virtual runtime）来度量每个进程已获得的CPU份额：

vruntime = 实际运行时间 × (NICE_0_LOAD / 进程权重)

其中：

NICE_0_LOAD 是nice值为0的进程权重（默认1024）
优先级越高（nice越小）的进程，权重越大，vruntime增长越慢
vruntime最小的进程最"亏欠"CPU时间，应当优先被调度

2.2 红黑树（RB-Tree）数据结构

CFS使用红黑树来管理所有可运行进程，以vruntime为key：

最左侧节点 = vruntime最小 = 最应被调度的进程
enqueue_task：进程唤醒时插入红黑树（__enqueue_entity）
pick_next_task：取出最左侧节点（__pick_first_entity）
树操作复杂度：O(log n)，即使数千进程依然高效

// kernel/sched/fair.c
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;
    // 红黑树插入逻辑，以vruntime比较
    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;
        }
    }
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

红黑树操作由内核的rbtree模块提供，CFS直接使用其通用实现。

2.3 vruntime的更新与时钟滴答

每次时钟中断（tick），调度器调用task_tick_fair→update_curr更新当前进程的vruntime：

static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;
    
    delta_exec = now - curr->exec_start;  // 实际执行时间
    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;
    
    // 核心：虚拟运行时间 = 实际时间 × 权重因子
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    
    // 更新整个cfs_rq的最小vruntime（用于新进程初始化）
    update_min_vruntime(cfs_rq);
}

2.4 新进程的vruntime初始化

为避免新创建进程（或刚唤醒的进程）因vruntime过小而"饿死"其他进程，CFS使用min_vruntime进行校准：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;
    
    if (initial)  // 新进程启动
        vruntime += sched_vslice(cfs_rq, se);  // 惩罚：加上一个时间片
    else
        vruntime = max_vruntime(cfs_rq->min_vruntime, se->vruntime);
    
    se->vruntime = vruntime;
}

2.5 调度延迟与粒度参数

CFS通过sysctl_sched_min_granularity和sysctl_sched_latency控制调度质量：

参数	默认值	含义
`sched_min_granularity_ns`	750,000 ns (0.75ms)	最小调度粒度，每个进程至少运行这么久
`sched_latency_ns`	6,000,000 ns (6ms)	调度周期，理想情况下所有可运行进程在此周期内轮转一次
`sched_wakeup_granularity_ns`	1,000,000 ns (1ms)	唤醒抢占粒度

当可运行进程数 > sched_latency_ns / sched_min_granularity_ns时，调度周期自动延长（__sched_period函数）。

2.6 组调度与cgroup支持

CFS通过sched_entity的嵌套实现组调度（Group Scheduling）：

每个cgroup有自己的cfs_rq和sched_entity
组内的进程先在自己的cfs_rq中竞争，赢得的组再在父cfs_q中竞争
/sys/fs/cgroup/cpu/下每个目录代表一个cpu cgroup

CPU带宽控制参数：

cpu.cfs_quota_us = 50000   → 每周期内最多使用50ms
cpu.cfs_period_us = 100000  → 周期100ms
cpu.shares = 1024           → 相对权重（默认值）

三、EEVDF调度器——CFS的继任者

3.1 CFS的痛点

尽管CFS在大多数场景表现优异，但存在一些长期被诟病的问题：

唤醒抢占延迟：CFS的WAKEUP_PREEMPTION优化导致高优先级交互式进程唤醒时抢占延迟难以控制
vruntime不可预测：在NUMA系统中，跨节点迁移后vruntime的重新校准引发延迟抖动
延迟敏感型负载不友好：数据库、实时音视频等需要严格延迟保证的负载，CFS难以提供可预测的延迟上界
min_vruntime的"不公平"：新进程的vruntime初始化为min_vruntime+latency，导致新进程抢占老进程

3.2 EEVDF核心概念

EEVDF（Earliest Eligible Virtual Deadline First）是2023年并入内核6.6的调度器，由kernel开发人员Stefan Eßer提出，专门解决CFS的延迟问题。

EEVDF引入了三个关键概念：

eligible time（合格时间）：进程从阻塞中醒来后，需要等待到vruntime追赶到合格时间才具备调度资格
virtual deadline（虚拟截止时间）：deadline = vruntime + 请求调度延迟，deadline最小的进程优先运行
requestable scheduling latency（可请求调度延迟）：用户/系统指定每个进程期望的最大调度延迟

核心调度逻辑：

进程按deadline排序（红黑树，key=deadline）
只有eligible的进程参与调度
deadline最小的eligible进程获得CPU

3.3 EEVDF与CFS的关键对比

特性	CFS	EEVDF
调度依据	vruntime最小优先	deadline最小优先
抢占策略	立即抢占（wakeup preemption）	延迟类似，但通过eligible机制控制
延迟保证	无显式保证	通过deadline提供软上界
新进程处理	min_vruntime + 惩罚	eligible时间 = max(vruntime, eligible)
红黑树key	vruntime	deadline
复杂度	O(log n)	O(log n)
平均延迟	较高	降低40-60%（Phoronix测试）

3.4 EEVDF数据结构与算法

// EEVDF的调度实体
struct sched_entity {
    struct rb_node      run_node;       // 红黑树节点，以deadline排序
    u64                 vruntime;
    u64                 deadline;       // vruntime + slice
    u64                 eligible_time;  // 可参与的最早时间
    // ...
};

EEVDF的pick_next逻辑：

// 选取deadline最小的eligible进程
static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    // 红黑树最左侧节点 = deadline最小
    // 需要检查eligible条件
}

3.5 EEVDF的优势场景

根据Phoronix的测试和社区反馈，EEVDF在以下场景表现突出：

游戏和视频播放：帧延迟降低20-40%
Web服务器：长尾延迟（P99/P999）改善显著
编译任务：在后台编译时前端应用响应不受影响
桌面交互：鼠标、键盘输入响应更平滑

四、实时调度类（RT Scheduler）

4.1 SCHED_FIFO与SCHED_RR

实时调度类优先于CFS，sched_class优先级高于fair_sched_class：

SCHED_FIFO：先进先出，高优先级进程可以抢占低优先级，同优先级运行到主动让出（sched_yield、阻塞、睡眠）
SCHED_RR：轮转，同优先级进程用尽时间片后排队尾部

实时优先级范围：1-99（越大优先级越高），通过sched_get_priority_max(SCHED_FIFO)获取。

4.2 SCHED_DEADLINE

基于EDF（Earliest Deadline First）算法，适用于硬实时场景：

struct sched_attr {
    __u32 size;
    __u32 sched_policy;     // SCHED_DEADLINE
    __u64 sched_runtime;    // 每次发布的运行时间
    __u64 sched_deadline;   // 截止时间
    __u64 sched_period;     // 发布周期
};

SCHED_DEADLINE保证：在满足 runtime ≤ deadline ≤ period 的条件下，每个周期内获得runtime的CPU时间。

4.3 实时调优注意事项

实时进程需配合chrt设置优先级
使用sched_rt_period_us和sched_rt_runtime_us限制RT进程CPU使用，防止普通进程饥饿
必须设置RLIMIT_RTPRIO或CAP_SYS_NICE权限

五、NUMA感知调度

5.1 NUMA架构下的调度策略

现代多路服务器部署在多NUMA节点上，本地内存访问延迟远低于跨节点访问。Linux调度器通过sched_domain层次感知NUMA拓扑：

SMT级别：同一物理核心的超线程共享执行单元
MC级别：同一CPU封装（Socket）的共享L3缓存
NUMA级别：不同节点，访问延迟差异显著
系统级别：最外层，所有CPU

5.2 NUMA Balancing

Linux的Automatic NUMA Balancing机制：

在进程运行期间周期性扫描页表，标记"mostly accessed from remote node"的页面
选择合适时机将页面迁移到访问最频繁的节点
在满足条件时迁移进程到数据所在节点

5.3 进程绑定（Affinity）

taskset或sched_setaffinity可将进程绑定到特定CPU核心集：

# 绑定到CPU 0-3
taskset -c 0-3 ./myapp

# 或绑定到NUMA节点0对应的所有CPU
numactl --cpunodebind=0 --membind=0 ./myapp

六、cgroup CPU资源控制

6.1 CPU权重与带宽

通过cpu.weight（cgroup v2）或cpu.shares（cgroup v1）控制CPU份额：

# cgroup v2
echo 200 > /sys/fs/cgroup/myapp/cpu.weight   # 默认100，越高份额越大

# cgroup v1（shares）
echo 2048 > /sys/fs/cgroup/cpu/myapp/cpu.shares  # 默认1024

6.2 CPU带宽限制（Bandwith Control）

CFS Bandwidth Control通过周期和配额限制CPU使用：

echo 50000 > /sys/fs/cgroup/myapp/cpu.max      # 每100ms内最多使用50ms
echo 100000 > /sys/fs/cgroup/myapp/cpu.max     # 第二个字段是周期

等效于50% CPU使用率限制。当进程用尽配额时，被"throttled"（节流）到下一个周期。

6.3 CPU Pressure Stall Information (PSI)

PSI提供细粒度的CPU压力监控：

cat /proc/pressure/cpu
# some avg10=5.23 avg60=3.45 avg300=2.12 total=123456789

avg10：最近10秒内部分任务等待CPU的时间百分比
total：累计等待时间（微秒）

七、性能调优与排障实战

7.1 系统级调度参数调优

# /etc/sysctl.d/99-sched-tuning.conf

# 缩短调度延迟（适合桌面/交互场景）
kernel.sched_min_granularity_ns = 1000000    # 1ms
kernel.sched_latency_ns = 4000000            # 4ms

# 增大调度周期（适合批处理/HPC）
# kernel.sched_min_granularity_ns = 10000000  # 10ms
# kernel.sched_latency_ns = 60000000          # 60ms

# 禁用唤醒抢占优化（某些数据库场景需要）
kernel.sched_wakeup_granularity_ns = 5000000

# 启用CFS带宽控制
kernel.sched_cfs_bandwidth_slice_us = 5000

7.2 进程调度状态诊断

# 查看进程调度信息
cat /proc/<pid>/sched

# 关键指标：
# se.vruntime          → 虚拟运行时间
# se.sum_exec_runtime  → 实际累积运行时间
# nr_switches          → 上下文切换次数
# nr_voluntary_switches → 自愿切换次数
# nr_involuntary_switches → 非自愿切换次数
# avg_atom             → 平均调度间隔（run_delay/nr_switches）
# policy               → 调度策略
# prio                 → 动态优先级

# 使用perf分析调度延迟
perf sched record -- sleep 10
perf sched latency --sort max

7.3 常见延迟排查工具链

工具	用途
`perf sched`	调度器性能分析，生成延迟直方图
`ftrace` sched_* events	跟踪调度事件流
`bpftrace`	动态探测，跟踪pick_next_task等函数
`proc/pressure/cpu`	CPU压力监控
`schedstat`	进程级调度统计
`perf c2c`	缓存伪共享检测

7.4 BPF追踪调度延迟示例

# 跟踪上下文切换延迟
bpftrace -e '
tracepoint:sched:sched_switch {
    @start_comm[arg0->comm] = nsecs;
}
tracepoint:sched:sched_wakeup {
    $start = @start_comm[args->comm];
    if ($start > 0) {
        $delay = (nsecs - $start) / 1000;
        @wakeup_latency_us = hist($delay);
        delete(@start_comm[args->comm]);
    }
}
'

7.5 数据库场景调度优化

数据库进程的关键需求：最小化上下文切换、绑定CPU亲和性、避免跨NUMA迁移。

典型优化步骤：

# 1. 绑定CPU亲和性
taskset -c 4-7 -- mysqld --daemonize

# 2. 设置CPU governor为performance
for cpu in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor; do
    echo performance > $cpu
done

# 3. 禁用NUMA balancing（数据库有自己的内存策略）
echo 0 > /proc/sys/kernel/numa_balancing

# 4. 提高MySQL进程优先级
chrt -r 50 --pid $(pidof mysqld)

# 5. 监控调度延迟
perf stat -e 'sched:sched_switch' -a sleep 1

八、内核源码中的关键函数

8.1 CFS路径追踪

schedule()                           → 入口
  → pick_next_task()                 → 遍历调度类，选择下一个任务
    → pick_next_task_fair()          → CFS选取
      → pick_next_entity()           → 红黑树最左侧（__pick_first_entity）
  → context_switch()                 → 上下文切换
      → switch_mm()                  → 切换地址空间
      → switch_to()                  → 切换寄存器和栈

__schedule()
  → update_rq_clock()                → 更新时间戳
  → pick_next_task()                 → 选下一个
  → put_prev_task()                  → 放回当前（更新vruntime）
  → set_next_task()                  → 设置下一个

8.2 EEVDF关键函数

pick_next_task_fair()
  → pick_next_entity()
    → 检查eligible条件
    → 选deadline最小的eligible进程

place_entity()
  → 计算deadline = vruntime + slice
  → 设置eligible_time = max(now, se->vruntime)

enqueue_entity()
  → 插入deadline红黑树

九、版本兼容性与迁移

9.1 EEVDF的渐进式部署

EEVDF在6.6内核中作为新调度器默认启用，但保留了CFS作为fallback：

如果遇到特定的性能退化场景，可以通过编译选项禁用EEVDF
6.6之前的内核（5.x系列）仍需使用CFS
容器化环境中，宿主机内核版本决定调度器类型

9.2 性能对比数据

Phoronix的多轮基准测试显示EEVDF在以下场景的改善：

工作负载	P50延迟改善	P99延迟改善
游戏（Factorio, CS2）	-15%	-35%
WebGL渲染	-10%	-25%
Web服务器（Nginx）	-5%	-15%
内核编译	0%	+2%（略差）
数据库OLTP	-8%	-20%

十、总结与展望

Linux进程调度器从CFS到EEVDF的演进，体现了内核社区在"公平性"与"低延迟"之间的持续权衡。关键要点回顾：

vruntime机制：CFS通过虚拟运行时间实现长期公平调度，nice值映射到权重
红黑树数据结构：O(log n)的高效选取和插入，保证大规模进程下的调度性能
EEVDF改进：引入deadline和eligible概念，降低延迟敏感型负载的延迟
实时调度：RT类和DEADLINE策略提供确定性延迟保证
cgroup集成：CPU带宽控制、权重分配、PSI压力监控
NUMA感知：跨节点迁移和网络感知调度

未来Linux调度器的发展方向可能包括：

EEVDF的进一步优化（slice计算、eligible条件调优）
更紧密的eBPF集成（用户自定义调度策略）
AI/ML辅助的调度决策
异构大小核（ARM big.LITTLE / Intel P+E cores）的智能调度

参考资料：

- Linux Kernel Source: kernel/sched/fair.c, kernel/sched/core.c

- "EEVDF Scheduler Merged Into Linux 6.6" — Phoronix, 2023

- Linux Kernel Documentation: Documentation/scheduler/

- "Completely Fair Scheduler" — M. Tim Jones, IBM DeveloperWorks

点赞(0) 打赏

本文分类：Linux内核
本文标签：Linux内核进程调度 CFS EEVDF vruntime 红黑树完全公平调度实时调度 NUMA cgroup 调度延迟 perf bpftrace 内核源码
浏览次数：15 次浏览
发布日期：2026-10-09 15:51:15
本文链接：https://ybb.press/linux-kernel/16291.html

Linux内核进程调度器深度实战：从CFS完全公平调度到EEVDF的全链路剖析

Linux内核进程调度器深度实战：从CFS完全公平调度到EEVDF的全链路剖析

引言

一、Linux调度器整体架构

1.1 调度器类（Scheduler Class）

1.2 调度策略与优先级

1.3 运行队列与每CPU调度

二、CFS完全公平调度器核心算法

2.1 核心思想：虚拟运行时间（vruntime）

2.2 红黑树（RB-Tree）数据结构

2.3 vruntime的更新与时钟滴答

2.4 新进程的vruntime初始化

2.5 调度延迟与粒度参数

2.6 组调度与cgroup支持

三、EEVDF调度器——CFS的继任者

3.1 CFS的痛点

3.2 EEVDF核心概念

3.3 EEVDF与CFS的关键对比

3.4 EEVDF数据结构与算法

3.5 EEVDF的优势场景

四、实时调度类（RT Scheduler）

4.1 SCHED_FIFO与SCHED_RR

4.2 SCHED_DEADLINE

4.3 实时调优注意事项

五、NUMA感知调度

5.1 NUMA架构下的调度策略

5.2 NUMA Balancing

5.3 进程绑定（Affinity）

六、cgroup CPU资源控制

6.1 CPU权重与带宽

6.2 CPU带宽限制（Bandwith Control）

6.3 CPU Pressure Stall Information (PSI)

七、性能调优与排障实战

7.1 系统级调度参数调优

7.2 进程调度状态诊断

7.3 常见延迟排查工具链

7.4 BPF追踪调度延迟示例

7.5 数据库场景调度优化

八、内核源码中的关键函数

8.1 CFS路径追踪

8.2 EEVDF关键函数

九、版本兼容性与迁移

9.1 EEVDF的渐进式部署

9.2 性能对比数据

十、总结与展望

Linux内核内存管理深度实战：从物理页面到虚拟空间

eBPF技术深度实战：从内核虚拟机到云原生可观测性

Linux 内核 eBPF 虚拟机原理与可观测性实战：从字节码到生产级追踪系统

Linux CFS 完全公平调度器：从红黑树到 vruntime 的深度解析

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复