Linux内核进程调度器深度实战：CFS与实时调度全解析

二、CFS调度器的设计哲学

2.1 核心思路：虚拟运行时间

CFS摒弃了传统调度器的时间片和固定优先级概念，引入了一个革命性的概念：虚拟运行时间（vruntime, Virtual Runtime）。

每个进程维护一个vruntime值，表示该进程在"虚拟世界"中已经运行的时间。CFS的目标是让所有可运行进程的vruntime尽可能相等，也就是说每个进程获得"完全公平"的CPU时间。

vruntime的计算公式：

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

其中NICE_0_LOAD是nice值为0的进程权重基准值（1024）。进程权重越大（即nice值越小），vruntime增长越慢，认为该进程"应该"运行更久。

2.2 红黑树数据结构

CFS使用红黑树（Red-Black Tree）作为其核心数据结构。红黑树以vruntime为key，组织所有可运行进程。

关键特性：

• 最左侧节点（最小vruntime）总是下一个被选中的进程
• 树操作（插入/删除/查找）的时间复杂度为O(log n)
• 相比O(1)调度器的140个优先级队列，CFS可以处理任意数量的可运行进程

三、CFS核心数据结构详解

3.1 task_struct中的调度相关字段

struct task_struct {
    struct sched_entity    se;       // CFS调度实体
    struct sched_rt_entity rt;       // 实时调度实体
    const struct sched_class *sched_class; // 调度类
    int                    policy;   // 调度策略
    int                    prio;     // 动态优先级
    int                    static_prio; // 静态优先级(nice值)
    int                    normal_prio; // 基于static_prio计算
    unsigned int           rt_priority; // 实时优先级
    struct list_head       tasks;    // 链表节点
    ...
};

3.2 sched_entity（调度实体）

struct sched_entity {
    struct load_weight  load;      // 进程权重
    struct rb_node      run_node;  // 红黑树节点
    struct list_head    group_node; // CFS组调度链表
    unsigned int        on_rq;     // 是否在运行队列
    
    u64   exec_start;              // 本次调度开始时间
    u64   sum_exec_runtime;        // 总运行时间统计
    u64   vruntime;                // 虚拟运行时间（核心字段）
    u64   prev_sum_exec_runtime;   // 上次切换时总运行时间
    
    u64   nr_migrations;           // 跨CPU迁移次数
    ...
};

3.3 cfs_rq（CFS运行队列）

struct cfs_rq {
    struct load_weight load;       // 队列总权重
    unsigned int nr_running;       // 可运行进程数
    unsigned int h_nr_running;     // 包含组调度的总数
    
    u64 min_vruntime;              // 队列最小vruntime
    struct rb_root_cached tasks_timeline; // 红黑树根节点
    
    struct sched_entity *curr;     // 当前运行的调度实体
    struct sched_entity *next;     // 下一个将运行的实体
    struct sched_entity *last;     // 上次运行的实体
    
    u64 avg_load[CALC_LOAD_IDX_MAX]; // 负载跟踪
    unsigned long runnable_load_avg;  // 平均可运行负载
    ...
};

四、CFS调度算法实现

4.1 入队操作（enqueue_entity）

当进程变为可运行状态或新创建时，加入到CFS红黑树：

static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
    bool curr = cfs_rq->curr == se;
    
    // 更新当前实体的统计
    update_curr(cfs_rq);
    
    // 重新归一化vruntime
    if (renorm)
        se->vruntime += cfs_rq->min_vruntime;
    
    // 如果实体之前在运行队列上，回退补偿
    if (flags & ENQUEUE_WAKEUP)
        placeness_sice(cfs_rq, se, 0);
    
    // 更新统计
    update_load_avg(cfs_rq, se, se->on_rq ? UPDATE_TG : 0);
    update_cfs_group(se);
    account_entity_enqueue(cfs_rq, se);
    
    // 如果当前不是正在运行的进程
    if (!curr)
        __enqueue_entity(cfs_rq, se);
    se->on_rq = 1;
}

4.2 出队操作（dequeue_entity）

static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    update_curr(cfs_rq);
    
    // 更新统计
    update_load_avg(cfs_rq, se, UPDATE_TG);
    update_cfs_group(se);
    
    // 如果是唤醒休眠，不需要从树中删除
    if (!(flags & DEQUEUE_SLEEP))
        update_stats_dequeue(cfs_rq, se, flags);
    
    clear_buddies(cfs_rq, se);
    
    if (se != cfs_rq->curr)
        __dequeue_entity(cfs_rq, se);
    
    se->on_rq = 0;
    account_entity_dequeue(cfs_rq, se);
    
    // 当唤醒时，调整vruntime为最小
    if (flags & DEQUEUE_SLEEP) {
        cfs_rq->min_vruntime = se->vruntime;
    }
}

4.3 选一个下一个进程（pick_next_entity）

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    // 取红黑树最左侧节点（最小vruntime）
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    
    // 比较当前进程和最左节点，选vruntime更小的
    if (!left || (curr && entity_before(curr, left)))
        left = curr;
    
    return left;
}

4.4 当前实体更新（update_curr）

这个函数每次tick都会调用，是CFS核心逻辑：

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));
    unsigned long delta_exec;
    
    if (unlikely(!curr))
        return;
    
    // 计算自上次调度后实际运行时间
    delta_exec = (unsigned long)(now - curr->exec_start);
    if (unlikely(!delta_exec))
        return;
    
    curr->exec_start = now;
    
    // 更新统计
    schedstat_set(curr->statistics.exec_max, max(delta_exec, curr->statistics.exec_max));
    curr->sum_exec_runtime += delta_exec;
    
    // 核心：更新vruntime
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    
    // 更新队列的min_vruntime（用于新进程/唤醒进程的vruntime初始化）
    update_min_vruntime(cfs_rq);
}

五、实时调度类

5.1 SCHED_FIFO（先进先出）

SCHED_FIFO是Linux最基本的实时调度策略。其特点：

• 不使用时间片，运行直到阻塞、主动让出或被更高优先级抢占
• 优先级范围：1-99（99最高）
• 同优先级按FIFO顺序运行
• 高优先级可以抢占低优先级
• 风险：高优先级SCHED_FIFO进程可能饿死低优先级进程和所有CFS进程

5.2 SCHED_RR（Round-Robin 时间片轮转）

SCHED_RR是SCHED_FIFO的改进版：

• 同优先级进程按时间片（默认100ms）轮转执行
• 时间片用完后，排到同优先级队列末尾
• 高优先级仍可以抢占

// Linux内核默认的RR时间片
#define RR_TIMESLICE    (100 * HZ / 1000)  // 100ms

5.3 SCHED_DEADLINE（截止时间调度）

自Linux 3.14引入，基于Earliest Deadline First (EDF)算法：

• 每个任务声明三个参数：运行时间Q、周期P、截止时间D
• 满足 Q ≤ D ≤ P 的约束
• 内核在准入阶段用EDF利用率测试判断可行性
• 使用全局EDF算法在异构多核间分配任务
• 适合硬实时控制系统

// 设置Deadline调度参数示例
struct sched_attr attr = {
    .size = sizeof(attr),
    .sched_policy = SCHED_DEADLINE,
    .sched_runtime  =  30000000,  // 30ms (纳秒)
    .sched_deadline = 100000000,  // 100ms
    .sched_period   = 100000000,  // 100ms
};

六、多核调度与负载均衡

6.1 运行队列（rq）与域（sched_domain）

多核系统中，每个CPU有独立的运行队列，调度域形成层级结构：

sched_domain层级：
┌─────────────────────────────┐
│ DIE Domain (Die级别)         │ 同一Die内的CPU共享
├────────┬────────┬───────────┤
│ MC Dom │ MC Dom │ MC Dom ... │ 同一核心内的硬件线程
├────────┼────────┼───────────┤
│ SMT    │ SMT    │ SMT        │ 同一物理核的超线程
└────────┴────────┴───────────┘

6.2 负载均衡策略

Linux内核通过以下机制实现CPU间的负载均衡：

• IDLE BALANCE：CPU空闲时从其他CPU拉取任务
• PERIODIC BALANCE：通过tick周期性检查
• NEWIDLE BALANCE：唤醒新任务时选择最佳CPU

6.3 调度组与负载追踪（PELT）

自Linux 4.5引入了Per-Entity Load Tracking（PELT）：

使用指数移动平均算法追踪每个调度实体的历史负载：

负载计算公式：
y^n = y^(n-1) × y + load × (1 - y)
其中 y = 0.5 的半衰期衰减因子

32ms半衰期系数：y ≈ 0.978
1024ms半衰期系数（4倍）：反映长期趋势

七、进程的优先级与nice值

Nice值到权重的转换使用内核的sched_prio_to_weight数组，按照1.25倍的比例递增：

static 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,
};

八、性能调优与调试实践

8.1 查看进程调度策略

$ chrt -p 1234
pid 1234 current scheduling policy: SCHED_OTHER
pid 1234 current scheduling priority: 0

# 设置为实时调度
$ sudo chrt -f -p 50 1234   # SCHED_FIFO, 优先级50
$ sudo chrt -r -p 30 1234   # SCHED_RR, 优先级30

8.2 CFS调优参数

8.3 使用sched_features调整行为

$ cat /proc/sys/kernel/sched_features
# 常见feature标志：
#  GENTLE_FAIR_SLEEPERS  - 对休眠进程更友善
#  NO_WAKEUP_PREEMPTION  - 禁用唤醒抢占
#  TTWU_QUEUE             - 唤醒队列化以减少锁争用
#  NO_NEXT_BUDDY          - 不使用左倾优化

8.4 perf sched工具分析调度性能

# 录制调度事件
$ sudo perf sched record -a sleep 10

# 分析调度延迟
$ perf sched latency

# 查看调度时间线
$ perf sched map

# 调度统计摘要
$ perf sched stat

8.5 eBPF调度跟踪

// 使用bpftrace跟踪任务切换
$ sudo bpftrace -e 'tracepoint:sched:sched_switch {
    printf("prev=%s pid=%d → next=%s pid=%d\n",
           args->prev_comm, args->prev_pid,
           args->next_comm, args->next_pid);
}'

// 跟踪调度延迟（runqlat）
$ sudo /usr/share/bcc/tools/runqlat 1 5

九、CFS组调度（cgroups）

Linux的组调度允许将CPU资源按比例分配给不同用户组或cgroup：

# 创建cgroup并设置CPU份额
$ sudo mkdir /sys/fs/cgroup/cpu/mygroup
$ echo 512 > /sys/fs/cgroup/cpu/mygroup/cpu.shares  # 相对权重
$ echo 100000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_quota_us  # 配额
$ echo 100000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_period_us  # 周期

Docker等容器系统利用CFS组和cgroups实现资源隔离，每个容器默认cpu.shares=1024。

十、Linux 5.x/6.x调度器新特性

• Core Scheduling（5.14+）：解决SMT侧信道安全问题
• Scheduler Tickless：减少无意义的中断，提升能效
• NUMA Balancing改进：自动迁移进程到就近内存节点
• starvation avoidance增强：防止长时间运行的进程饿死交互式任务
• RT throttling改进：实时任务全局带宽限制调整
• sched_ext（6.12+）：允许用户空间通过BPF自定义调度器

十一、总结

Linux的CFS调度器是一种优雅的工程实现，它通过虚拟运行时间和红黑树数据结构，在理论上和实践中都实现了"完全公平"的目标。理解CFS对于系统调优、性能分析、以及实时应用开发至关重要。

关键要点回顾：

1. CFS使用vruntime衡量进程的"应得"资源，所有可运行进程vruntime趋近相等
2. 红黑树提供O(log n)的插入和查找效率
3. 实时调度（RT/Deadline）优先级高于普通CFS，且有不同行为语义
4. 多核系统中通过sched_domain层级实现高效负载均衡
5. 通过cgroups可以进行分组资源配额管理
6. 性能调优应结合perf sched、bpftrace等工具进行数据驱动分析