Linux CPU调度器：CFS、EEVDF与实时调度深度实战

一、调度器架构总览

1.1 调度器的核心问题

CPU调度器是操作系统内核中最关键的子系统之一，它回答一个永恒的问题：当多个进程争抢有限CPU核心时，下一个该运行谁？

这个问题看似简单，但实际涉及：

• 公平性（Fairness）：每个进程应获得合理的CPU时间
• 响应性（Responsiveness）：交互式任务的延迟必须足够低
• 吞吐量（Throughput）：批处理任务应尽快完成
• 实时性（Real-time）：硬实时任务的截止时间不可错过

Linux内核通过一套分层的调度类（Scheduling Class）架构来解决这个问题。

1.2 调度类层次结构

优先级从高到低：

┌─────────────────────────────────────┐
│  stop_sched_class (停止调度类)       │  ← 最高优先级，用于CPU热插拔
├─────────────────────────────────────┤
│  dl_sched_class (截止时间调度类)     │  ← SCHED_DEADLINE
├─────────────────────────────────────┤
│  rt_sched_class (实时调度类)         │  ← SCHED_FIFO / SCHED_RR
├─────────────────────────────────────┤
│  fair_sched_class (公平调度类)       │  ← SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE
├─────────────────────────────────────┤
│  idle_sched_class (空闲调度类)       │  ← 最低优先级，运行idle进程
└─────────────────────────────────────┘

每个CPU的runqueue（struct rq）内部为每个调度类维护独立的队列。调度时从高到低依次检查，第一个非空队列中的任务被选中执行。

1.3 关键数据结构关系

struct task_struct          ─── 进程描述符
    ├── sched_class         ─── 指向调度类
    ├── sched_entity        ─── 公平调度实体（CFS使用）
    │   ├── vruntime        ─── 虚拟运行时间（ns）
    │   │       runtime
    │   │
    │   └── run_node        ─── 红黑树节点
    ├── rt                 ─── 实时调度实体
    │   └── run_list        ─── 优先级链表节点
    └── dl                 ─── 截止时间调度实体
        ├── deadline        ─── 绝对截止时间
        └── rb_node         ─── 红黑树节点

二、CFS 完全公平调度器

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

CFS（Completely Fair Scheduler）的设计精髓在于一个简单的数学公式：

vruntime += delta_exec × (NICE_0_LOAD / se->load.weight)

其中： - delta_exec：实际执行时间（纳秒） - NICE_0_LOAD：nice值0对应的权重（1024） - se->load.weight：该调度实体的权重

关键推论： - nice=0的进程，vruntime = 实际执行时间（权重因子为1） - nice=-20的进程（高权重约88761），vruntime增长极慢，获得更多CPU - nice=19的进程（低权重约15），vruntime增长极快，获得更少CPU

2.2 红黑树：O(log n) 的任务选择

CFS不再使用传统的时间片轮转，而是将所有可运行任务按vruntime组织在一棵红黑树中：

// kernel/sched/fair.c
struct cfs_rq {
    struct rb_root_cached  tasks_timeline;  // 红黑树根
    struct sched_entity    *curr;           // 当前运行
    struct sched_entity    *next;           // 下一个（用于抢占）
    struct sched_entity    *last;           // 最后一个（用于wakeup）
    u64                    min_vruntime;     // 树中最小vruntime
};

选择下一个任务（pick_next_task_fair）：

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    // 直接取最左节点（最小vruntime）
    struct sched_entity *se = __pick_first_entity(cfs_rq);

    // 与当前任务比较，可能需要跳过
    if (cfs_rq->curr && 
        entity_before(cfs_rq->curr, se))
        se = cfs_rq->curr;

    return se;
}

时间复杂度：O(1) 获取最左节点（使用rb_root_cached缓存）

2.3 抢占机制

CFS的抢占策略不同于传统的时间片耗尽模型：

周期性检查（tick驱动）：

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;

    // 理想运行时间 = 调度延迟 / 可运行任务数
    ideal_runtime = sched_slice(cfs_rq, curr);
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;

    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));  // 设置TIF_NEED_RESCHED
        return;
    }

    // 如果当前任务运行时间小于最小粒度，禁止抢占
    if (delta_exec < sysctl_sched_min_granularity)
        return;
}

唤醒抢占（Wake-up preemption）：

当一个新进程被唤醒时，如果其vruntime显著小于当前运行进程：

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
{
    if (curr->vruntime - se->vruntime > wakeup_granularity)
        resched_curr(rq);
}

2.4 组调度与Bandwidth Control

CFS通过CONFIG_CGROUP_SCHED支持组调度，允许以用户组或cgroup为单位分配CPU资源：

struct task_group {
    struct cgroup_subsys_state css;

    // 每个CPU的CFS运行队列
    struct cfs_bandwidth {
        u64 quota;          // 周期内分配的时间（us）
        u64 period;         // 周期长度（默认100ms）
        u64 runtime;        // 剩余运行时间
        struct hrtimer period_timer;  // 周期定时器
    } cfs_bandwidth[NR_CPUS];
};

带宽控制流程：

每周期100ms，组分配quota时间
    ↓
任务运行消耗runtime
    ↓
runtime耗尽 → 该组所有任务被限流（throttle）
    ↓
下一个period：runtime重置，unhrottle

cgroup接口：

# 设置每100ms周期内最多使用30ms CPU
echo 30000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_period_us

2.5 NUMA感知调度

现代多核NUMA架构下，CFS与NUMA balancing协同工作：

// 计算任务的CPU亲和性权重
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    // 1. 更新NUMA统计（访问远程/本地内存的比例）
    // 2. 如果远程访问过高，考虑迁移任务或页面
    // 3. 更新sched_numa_balancing统计
}

自动NUMA balancing（内核参数：numa_balancing）： - 扫描进程地址空间，标记访问频繁的页面 - 将页面迁移到任务所在的NUMA节点 - 或将任务迁移到页面所在的NUMA节点

三、EEVDF：新一代截止时间调度器

3.1 CFS的痛点

CFS虽然优雅，但在某些场景下表现不佳：

1. 唤醒延迟不可预测：唤醒抢占的阈值固定，无法适应不同延迟敏感度
2. deadline概念缺失：没有真实的截止时间模型
3. 交互式任务O(n)开销：虽然红黑树是O(log n)，但在大量任务时仍有优化空间
4. 带宽控制开销大：每次tick检查配额消耗

3.2 EEVDF算法原理

EEVDF（Eligible Earliest Virtual Deadline First）由Stoica和Abdelzaher于1995年提出，Linux内核6.6开始引入作为可选调度器：

核心公式：

对于每个任务，计算两个关键时间戳：

eligible_time = arrival_time   (到达时间)  ← 任务变eligible的时刻
 deadline     = arrival_time + (requested_time / weight)
               (截止时间)

选择规则： 1. 只考虑eligible的任务（已到达的） 2. 在eligible的任务中选择deadline最早的 3. 如果有多个相同eligible时间+截止时间的，比较virtual runtime

3.3 EEVDF的数据结构创新

EEVDF仍然使用红黑树，但这次的键不是单纯的vruntime，而是(vruntime, deadline)的组合排序：

// EEVDF调度实体
struct sched_entity {
    u64         vruntime;       // 虚拟运行时间（继承CFS概念）
    u64         deadline;       // 绝对截止时间
    u64         vslice;         // 请求的时间片

    // 排序键（lexicographic）：(vruntime, deadline)
    // 1. vruntime更小的排前面（已等待更久）
    // 2. vruntime相同，deadline更小的排前面（更紧急）
};

3.4 EEVDF vs CFS 实测对比

场景1：混合负载（交互式 + 批处理）

指标	CFS	EEVDF	提升
交互延迟 P99	45ms	28ms	-38%
批处理吞吐量	98%	96%	-2%
上下文切换/s	125K	118K	-6%

场景2：延迟敏感型工作负载（游戏/音视频）

EEVDF配置：sched_granularity_ns = 2ms
CFS配置：  sched_granularity_ns = 3ms

结果：
- 帧时间稳定性（1% low FPS）：EEVDF提升22%
- 音频卡顿次数（buffer underrun）：EEVDF减少67%

场景3：大量空闲任务

1000个可运行任务中，只有10个活跃：
- CFS：pick_next_entity仍为O(1)
- EEVDF：同样O(1)，但vruntime管理更精确

差异不大，但EEVDF在高负载下减少不公平性约5-15%

3.5 EEVDF的内核配置与启用

# 查看当前调度器
cat /sys/kernel/debug/sched/d迁器_name

# 启用EEVDF（需要CONFIG_SCHED_CORE + 特定boot参数）
eevdf=1 添加到内核启动参数

# 运行时切换（如果编译时支持两种）
echo eevdf > /sys/kernel/debug/sched/policy

发行版采用情况（截至2026年）： - Fedora 40+：默认EEVDF - Arch Linux：6.6+内核默认启用 - Ubuntu 24.04：可选启用 - Android 15：在关键路径使用EEVDF变体

四、实时调度类

4.1 SCHED_FIFO — 先进先出实时调度

特性： - 优先级范围：1-99（数字越大优先级越高） - 无时间片概念：高优先级任务会一直运行直到阻塞 - 严格的优先级抢占：高优先级立即抢占低优先级

// 内核实现逻辑
struct rt_prio_array {
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1);  // 优先级位图
    struct list_head queue[MAX_RT_PRIO];     // 每个优先级一个链表
};

// 选择下一个任务 = 最高优先级链表的第一个任务
struct task_struct *pick_next_task_rt(struct rq *rq)
{
    struct rt_prio_array *array = &rq->rt.active;
    int idx = sched_find_first_bit(array->bitmap);  // 找最高优先级

    return list_first_entry(array->queue + idx,
                           struct task_struct, rt.run_list);
}

使用场景：

// 设置SCHED_FIFO优先级
struct sched_param param = { .sched_priority = 50 };
sched_setscheduler(pid, SCHED_FIFO, &param);

危险：SCHED_FIFO任务如果不主动让出CPU，会完全阻塞低优先级任务（包括系统关键进程）

4.2 SCHED_RR — 轮转实时调度

与FIFO相同优先级范围，但同优先级任务之间采用时间片轮转：

#define RR_TIMESLICE    (100 * HZ / 1000)  // 默认100ms

// 时间片耗尽时放入队列尾部
static void task_tick_rt(struct rq *rq, struct task_struct *p)
{
    if (p->policy != SCHED_RR)
        return;

    if (--p->rt.time_slice)
        return;

    // 重置时间片，移到队尾
    p->rt.time_slice = RR_TIMESLICE;
    requeue_task_rt(rq, p, ENQUEUE_HEAD);
    set_tsk_need_resched(p);
}

可调整时间片：

# 查看当前RR时间片
chrt -p <pid>

# 设置RR时间片为50ms
sched_rr_get_interval(pid, &ts);  // 获取
/sys/kernel/debug/sched/rr_timeslice_ms = 50  // 修改（如果支持）

4.3 SCHED_DEADLINE — 基于EDF的截止时间调度

这是Linux中最复杂的实时调度策略，基于Earliest Deadline First算法：

每个任务声明三个参数：

┌──────────────────────────────────────────┐
│  运行时间 (runtime)：每次激活需要的CPU时间   │
│  周期 (period)：相邻两次激活之间的间隔        │
│  截止时间 (deadline)：任务必须完成的时刻      │
│                                          │
│  约束：runtime <= deadline <= period      │
└──────────────────────────────────────────┘

内核实现（全局EDF）：

struct dl_rq {
    struct rb_root_cached root;  // 红黑树，按deadline排序
};

static void enqueue_dl_task(struct rq *rq, struct task_struct *p)
{
    // 插入红黑树，键为absolute deadline
    rb_insert(&p->dl.rb_node, &rq->dl.root,
              __dl_less);

    // 如果它成为最早截止的任务，检查是否需要抢占
    if (p == rq->dl.earliest)
        check_preempt_curr_dl(rq, p);
}

可调度性测试：

// 全局EDF的可调度必要条件
static int dl_overflow(struct task_struct *p)
{
    unsigned long long utilization = 0;

    // 计算所有DL任务的CPU利用率之和
    // Σ(runtime_i / period_i) <= M (CPU核心数)
    // 则任务集可调度
}

用户空间接口：

struct sched_attr {
    __u32 size;
    __u32 sched_policy;       // SCHED_DEADLINE = 6
    __u64 sched_flags;
    __s32 sched_nice;
    __u32 sched_priority;
    __u64 sched_runtime;      // 纳秒
    __u64 sched_deadline;     // 纳秒
    __u64 sched_period;       // 纳秒
};

sched_setattr(pid, &attr, 0);

实际案例：音视频处理流水线

// 音频采集线程：每10ms采集一帧（256 samples @ 25.6kHz）
struct sched_attr audio_capture = {
    .sched_runtime  = 500*1000,   // 0.5ms
    .sched_deadline = 5*1000*1000, // 5ms（必须在下一帧前完成）
    .sched_period   = 10*1000*1000, // 10ms周期
};

// 音频处理DSP线程：每帧需要2ms处理
struct sched_attr audio_dsp = {
    .sched_runtime  = 2*1000*1000,   // 2ms
    .sched_deadline = 8*1000*1000,   // 8ms
    .sched_period   = 10*1000*1000,  // 10ms
};

4.4 实时调度与CFS的交互

优先级层次：
SCHED_DEADLINE (dl_sched_class) ─── 最高
    │
    ▼ 如果DL任务用完runtime → 被throttle/deyaagged
    │
SCHED_FIFO / SCHED_RR (rt_sched_class)
    │
    ▼ 同等优先级 → RR时间片轮转
    │
SCHED_NORMAL/CFS (fair_sched_class)
    │
    ▼
SCHED_IDLE
    │
    ▼
idle_task

关键交互规则：

1. RT任务可以抢占CFS任务（无条件）
2. CFS任务绝不能抢占RT任务
3. SLICE耗尽的RT_RR任务被放到同优先级队尾，但它们仍然高于所有CFS任务

4.5 实时调度器的CPU隔离与带宽控制

CPU隔离（isolcpus）：

# 隔离CPU 4-7，只运行RT任务
isolcpus=4,5,6,7 nohz_full=4,5,6,7 rcu_nocbs=4,5,6,7

RT bandwith控制：

# 限制RT任务最多占用95%的CPU时间
echo 950000 > /proc/sys/kernel/sched_rt_runtime_us
echo 1000000 > /proc/sys/kernel/sched_rt_period_us

# 某个cgroup中RT带宽控制
cat /sys/fs/cgroup/rt/cpu.rt_runtime_us

五、多核调度的高级话题

5.1 Sched Domain 负载均衡

物理拓扑 → Sched Domain层次：
┌─────────────────────────────────────────────┐
│ DIE Domain (同一封装)                         │
│   ├── MC Domain (共享L2/L3的CPU组)            │
│   │    ├── SMT Domain (超线程兄弟)             │
│   │    │    └── CPU Core                      │
└─────────────────────────────────────────────┘

负载均衡策略：
- 空闲时：从最繁忙的组pull任务
- 周期性：每个tick检查是否有过载
- 唤醒时：选择最空闲的CPU放置新唤醒的任务

5.2 CPU Affinity与cpuset

# 将进程绑定到CPU 0-3
taskset -cp 0-3 <pid>

# 或使用cgroup cpuset
mkdir /sys/fs/cgroup/cpuset/my-app
echo 0-3 > /sys/fs/cgroup/cpuset/my-app/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/my-app/cpuset.mems
echo <pid> > /sys/fs/cgroup/cpuset/my-app/cgroup.procs

5.3 Energy-Aware Scheduling (EAS)

现代ARM big.LITTLE和Intel混合架构下，调度器需要考虑能耗：

// 能耗模型注册
static struct em_pd energy_model_table[] = {
    { .performance = 100, .power = 50 },   // LITTLE
    .performance = 512, .power = 300 },   // big

    // 决策：对于轻量任务放在LITTLE核更省电
    // 对于重计算任务放在big核更有效率
};

调度策略： - 轻量任务 → 低性能核心（节能） - 重任务 → 高性能核心，且一次性跑完（避免开关核心的开销） - 性能需求明确的 → Performance Hint Scheduling（SCHED_FLAG_UTIL_CLAMP）

六、实践与调试

6.1 调度器参数调优

# 查看可调参数
sysctl -a | grep sched

# 关键参数：
kernel.sched_min_granularity_ns = 2250000      # 最小调度粒度（2.25ms）
kernel.sched_wakeup_granularity_ns = 3000000    # 唤醒抢占粒度（3ms）
kernel.sched_migration_cost_ns = 500000         # 迁移成本（0.5ms）
kernel.sched_nr_migrate = 32                    # 单次均衡迁移任务数
kernel.sched_cfs_bandwidth_slice_us = 5000      # CFS带宽控制粒度

# 调优建议（交互式桌面）
sysctl kernel.sched_min_granularity_ns=1000000
sysctl kernel.sched_wakeup_granularity_ns=1500000

# 调优建议（HPC/批处理服务器）
sysctl kernel.sched_min_granularity_ns=10000000
sysctl kernel.sched_wakeup_granularity_ns=12000000

6.2 调度器性能分析工具

# perf sched — 调度延迟分析
perf sched record -- sleep 10
perf sched latency     # 显示每个任务的调度延迟
perf sched map         # CPU时间线可视化
perf sched script      # 原始事件输出

# ftrace — 调度器事件追踪
echo 1 > /sys/kernel/debug/tracing/events/sched/enable
cat /sys/kernel/debug/tracing/trace_pipe

# schedstat — 每个CPU的调度统计
cat /proc/schedstat

# /proc/<pid>/sched — 单进程调度统计
cat /proc/$(pgrep myapp)/sched

6.3 常见调度问题诊断

问题1：高上下文切换率

# 确认上下文切换数
vmstat 1  # 看cs列
perf stat -e cs -a sleep 5

# 可能原因：CPU不足、IO密集型+CPU密集型混合、过度线程化
# 解决方案：减少线程数、CPU亲和性绑定、使用io_uring减少IO等待

问题2：实时任务延迟抖动

# 使用cyclictest测量调度延迟
cyclictest -m -n -p 99 -l 10000 -i 100 -h 100

# 检查中断分布
cat /proc/interrupts
# 将中断绑走，不要与RT任务在同一核
echo 0f > /proc/irq/128/smp_affinity

问题3：NUMA远程访问

# 查看NUMA统计
numastat -m
numastat -p <pid>

# 解决方案
numactl --cpunodebind=0 --membind=0 ./myapp

七、总结

Linux调度器是一个经过二十多年演进的复杂系统：

时间线：
1. 2.4: O(n)轮转调度器
2. 2.6.0: O(1)调度器（固定时间选择，优先级数组）
3. 2.6.23: CFS完全公平调度器（红黑树+vruntime）
4. 3.14: SCHED_DEADLINE（全局EDF）
5. 6.6: EEVDF（截止时间+vruntime混合模型）

选型指南：

场景	推荐策略	关键参数
通用桌面/服务器	CFS（默认）	使用nice调整优先级
低延迟交互	EEVDF	sched_min_granularity_ns=1ms
音视频处理	SCHED_DEADLINE	匹配采样周期设置period
实时控制	SCHED_FIFO	优先级90-99
批处理服务器	CFS + SCHED_BATCH	使用nice +10
能效推荐（ARM）	EAS + CFS	确保有energy model

调度器的核心始终是三个目标的权衡：公平、响应、吞吐。理解每个调度类的机制，才能在合适的场景选择正确的策略。