Linux内核CFS调度器深度实战：完全公平调度算法与进程管理架构全景解析

一、调度器演进：从O(n)到CFS的三次范式革命

Linux内核调度器经历了三次重大架构演进，每一次变革都是对前一次设计的根本性重构。理解这段历史，才能真正领会CFS为何被设计成今天的模样。

1.1 O(n)调度器（Linux 2.4时代）

O(n)调度器的核心数据结构是一个运行队列（runqueue），所有可运行进程串在同一个链表中。每次调度决策都需要遍历整个链表，找到优先级最高的进程。这种方法在进程数量增多时，调度延迟线性增长——当系统中有1000个进程时，一次调度决策需要检查1000个进程的优先级。

O(n)调度器还有一个致命缺陷：它在时钟中断中递减当前进程的时间片。这意味着即使系统不那么繁忙，调度器也会频繁打断正在运行的进程来检查时间片，造成了不必要的开销。

1.2 O(1)调度器（Linux 2.6.0 ~ 2.6.22）

Ingo Molnár设计的O(1)调度器引入了两个关键创新：优先级数组（priority array）和每CPU运行队列。每个优先级对应一个链表，调度时只需从高优先级向低优先级扫描，找到第一个非空链表即可。由于优先级范围固定（0~139），这个操作是常数时间O(1)的。

然而O(1)调度器引入了极为复杂的交互检测算法和"饥饿奖罚"机制，代码维护困难。更根本的是，它仍然依赖静态时间片分配，对交互式进程和批处理进程的区分依赖于启发式的sleep_avg计算，不够优雅。

1.3 CFS调度器（Linux 2.6.23至今）

Con Kolivas在尝试改进O(1)调度器时，提出了一个革命性思想：不用时间片。他不给进程分配固定的时间片，而是让每个进程按照"虚拟运行时间"（virtual runtime, vruntime）的方式公平竞争CPU时间。这就是CFS（Completely Fair Scheduler，完全公平调度器）的核心哲学。

二、CFS核心原理：虚拟运行时间与理想多任务模型

2.1 理想多任务处理器模型

CFS建立在一个理论模型之上：假设有n个进程，一个理想的、完美的多任务并行处理器会让每个进程获得1/n的CPU时间。如果有4个进程，每个应该获得25%的CPU。

现实中，处理器是单核串行执行的，所以CFS的目标是：尽可能模拟这个理想模型——让每个进程的虚拟运行时间以相同的速率增长，哪个进程的vruntime最小，就说明它"欠"的CPU时间最多，应该获得执行机会。

2.2 vruntime计算公式

虚拟运行时间是CFS的核心度量标准，其计算公式为：

vruntime += delta_exec × (NICE_0_LOAD / weight)

其中：

• delta_exec：进程实际执行的时间（物理时间）
• NICE_0_LOAD：nice值为0时的权重基准值（定义为1024）
• weight：进程的实际权重，取决于nice值

这个公式的精妙之处在于：nice值越高（权重越小）的进程，vruntime增长越快，从而更快地被排到红黑树右边，获得更少的CPU时间。nice值为0的进程，vruntime与物理时间同步增长；nice值为+5的进程，vruntime增长速率是nice值0的1.25倍；nice值为-5的进程，vruntime增长速率是nice值0的0.8倍。

2.3 权重表与nice值映射

内核使用一个预计算的权重数组（sched_prio_to_weight[40]），将-20到+19的nice值映射到权重。映射关系以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,
};

这意味着nice值每降低1级，进程获得的CPU时间增加约10%（1024/820 ≈ 1.249）。这个10%的步长是精心选择的：太小则优先级差异不明显，太大则会导致优先级反转问题。

三、数据结构：红黑树与CFS运行队列

3.1 核心数据结构关系

CFS调度器涉及三个核心数据结构，它们之间的关系如下：

• task_struct：进程控制块，包含指向sched_entity的指针
• sched_entity：调度实体，每个可调度对象（包括进程和调度组）都有一个
• cfs_rq：CFS运行队列，每个CPU、每个调度组都有一个，包含红黑树根节点
• rq：每个CPU的物理运行队列，包含cfs_rq、rt_rq、dl_rq三个调度器队列

3.2 cfs_rq结构详解

struct cfs_rq {
    struct load_load load;          // 该队列的总权重（用于负载均衡）
    unsigned long runnable_weight;  // 可运行进程的总权重
    unsigned int nr_running;       // 当前可运行进程数
    unsigned int h_nr_running;     // 包括调度组嵌套层级的总数
    
    u64 min_vruntime;              // 队列中最小的vruntime（单调递增的基准点）
    struct rb_root_cached tasks_timeline; // 红黑树根节点（按vruntime排序）
    
    struct sched_entity *curr;     // 当前正在运行的实体
    struct sched_entity *next;     // 抢占后下一个要运行的实体
    struct sched_entity *last;     // 上次运行的实体（用于上下文切换后连续性）
    // ...
};

min_vruntime是CFS中最容易被忽略但最为关键的字段之一。它记录了该队列曾经分配给进程的最小vruntime值，并且是单调递增的（只增不减）。当新进程创建时，它的vruntime会被设置为当前的min_vruntime，这保证了新进程不会因为它刚创建而获得不公平的优势。

3.3 sched_entity与红黑树节点

struct sched_entity {
    struct load_weight load;       // 进程权重
    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;             // 迁移次数统计
    // ...
};

每个sched_entity通过run_node嵌入到红黑树中。CFS使用红黑树（而非AVL树或其他平衡树）的原因是：红黑树的插入和删除操作效率更高（最多三次旋转），而CFS调度器每秒可能执行数百万次入队和出队操作。

3.4 红黑树操作复杂度

其中__pick_first_entity之所以是O(1)，是因为cfs_rq结构中使用了rb_root_cached——它在红黑树根节点上额外缓存了最左节点（rb_leftmost），使得获取vruntime最小的进程不需要遍历红黑树。

四、调度流程：从时钟中断到上下文切换

4.1 主调度器入口

调度器的入口点有两个：主动调度（进程主动调用schedule()让出CPU）和抢占式调度（时钟中断中发现需要抢占）。两者的区别在于调用路径，但最终都会收敛到同一个上下文切换点。

// 时钟中断 -> scheduler_tick -> task_tick_fair -> entity_tick
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    // 1. 更新当前进程的vruntime和统计信息
    update_curr(cfs_rq);
    
    // 2. 检查是否需要抢占（与红黑树最左节点比较vruntime）
    if (sched_feat(RESPONSIVE) && cfs_rq->nr_running > 1) {
        check_preempt_tick(cfs_rq, curr);
    }
}// check_preempt_tick核心逻辑
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
    s64 delta;
    
    // 计算当前进程应该运行的理想时间（按权重比例分配sched_latency）
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    ideal_runtime = sched_slice(cfs_rq, curr);
    
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq)); // 当前进程已超额运行，标记抢占
        return;
    }

    // 如果最左节点的vruntime远小于当前进程，也应该抢占
    if (delta_exec < sysctl_sched_min_granularity)
        return;
        
    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;
    if (delta > 0)
        resched_curr(rq_of(cfs_rq));
}

4.2 sched_slice与sched_latency

CFS引入了两个关键的时间参数来平衡响应性和吞吐量：

• sched_latency：调度周期，目标是在这段时间内让所有可运行进程都获得至少一次执行机会。默认值通常为6ms（可配置为/proc/sys/kernel/sched_latency_ns）
• min_granularity：最小运行粒度，进程被抢占前至少运行这么长时间。默认值0.75ms（/proc/sys/kernel/sched_min_granularity_ns）
• sched_slice：每个进程在调度周期内获得的实际时间片

// sched_slice计算：按权重比例分摊sched_latency
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
    // slice = sched_latency（如果nr_running <= sched_latency/min_granularity）
    // 否则 slice = nr_running * min_granularity
    
    slice *= se->load.weight;  // 乘以当前进程权重
    do_div(slice, cfs_rq->load.weight); // 除以队列总权重
    return slice;
}

// sched_wakeup_granularity：唤醒抢占的阈值
// 当新唤醒进程的vruntime比当前进程小超过此值时，才允许唤醒抢占

当系统中有超过sched_latency/min_granularity个进程时（即6ms/0.75ms=8个以上进程），调度周期会自动延长为nr_running × min_granularity，确保每个进程至少运行0.75ms后才被抢占。这意味着在高负载下，CFS牺牲了部分响应性来保证吞吐量。

4.3 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;
    
    if (unlikely(!curr)) return;
    
    // 计算本次已执行的物理时间
    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0)) return;
    
    curr->exec_start = now;
    
    // 更新统计信息
    curr->sum_exec_runtime += delta_exec;
    
    // 核心：计算vruntime增量
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    
    // 更新cfs_rq的min_vruntime（单调递增）
    update_min_vruntime(cfs_rq);
}

// calc_delta_fair：delta_exec × (NICE_0_LOAD / weight)
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

注意update_min_vruntime的关键行为：它始终将min_vruntime向当前进程的vruntime靠拢（取(max)值），但有1个单位的偏移（sysctl_sched_child_runs_first可能导致的问题）。同时，如果一个进程的vruntime小于min_v-runtime，min_vruntime不会回退——这保证了min_vruntime的单调递增性。

五、新进程的vruntime初始化

5.1 place_entity函数

当一个新进程被创建时（fork），它的vruntime不能简单地设为0（否则它会不公平地获得大量CPU时间），也不能直接设为当前min_vruntime（否则频繁创建新进程会导致老进程饥饿）。CFS使用place_entity函数来处理这个问题：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;
    
    if (initial) {
        // 新进程：给一个小于min_vruntime的初始vruntime
        // 新进程"迟到"了，需要在初始阶段稍微补偿
        vruntime += sched_vslice(cfs_rq, se);
    }
    
    // 延迟补偿：对睡眠刚醒来的进程（非initial），考虑减半vruntime
    // 这防止了长时间睡眠的进程醒来后被饥饿
    vruntime = max_vruntime(vruntime, se->vruntime);
    se->vruntime = vruntime;
}

这个设计的微妙之处在于：新进程的vruntime被设置为min_vruntime加上一个"虚拟时间片"，这意味着新进程到达红黑树时，它的vruntime比min_vruntime大，会被放在树的最右半边，不会立刻抢占当前进程。但随着时间推移，当前进程的vruntime增长，新进程自然会轮到。

六、调度类体系：CFS与RT/Deadline的协同

6.1 调度类优先级

Linux内核使用调度类体系来支持多种调度策略，按优先级从高到低排列：

总是选择优先级最高的、非空的、有可运行进程的调度类来执行。这意味着RT进程总是优先于CFS进程运行——如果RT队列不为空，CFS进程不会获得CPU时间，无论它的vruntime有多小。

6.2 RT调度器的throttling机制

如果RT进程陷入死循环，所有CFS进程将永远得不到执行。sched_rt_runtime_us（默认950ms/秒）限制了RT进程在1秒内最多运行的累计时间。当RT配额用完后，即使RT进程可运行，调度器也会降级到CFS调度类。

6.3 SCHED_DEADLINE：基于时间约束的精确调度

SCHED_DEADLINE是基于EDF（Earliest Deadline First）算法的调度策略，它使用时间三元组（runtime, period, deadline）来描述任务需求。每个截止时间调度任务的sched_dl_entity也是通过红黑树组织的，但排序依据是绝对截止时间（absolute deadline），而不是vruntime。

struct sched_dl_entity {
    // 当前任务实例的绝对截止时间
    u64 deadline;                 // 下次deadline
    
    // 任务参数
    u64 runtime;                  // 每个周期内的运行时间预算
    u64 period;                   // 周期长度
    u64 deadline;                 // 截止时间（通常等于period）
    
    // 当前实例的剩余运行时间预算
    u64 dl_runtime;
    
    // Core scheduling properties
    int dl_throttled;             // 预算用完被限流
    int dl_yielded;               // 主动让出deadline
    int dl_overrun;               // deadline过期
    // ...
};

CFS与SCHED_DEADLINE的共存策略：当一个DEADLINE任务的deadline到来时，它会抢占CFS进程；当它的runtime预算被耗尽时，内核会将其throttled（dl_timer降级到CFS）。这种预算机制确保了CFS进程不会因为DEADLINE进程的bug而被完全饿死。

七、负载均衡：SMP与NUMA场景下的CFS策略

7.1 负载均衡的触发时机

CFS的负载均衡在以下场景触发：

• IDLE_BALANCE：目标CPU空闲时，从最繁忙的CPU拉取进程
• PERIODIC_BALANCE：tick负载均衡，定期检查CPU负载差异
• NEWIDLE_BALANCE：CPU刚从idle被唤醒时
• NOHZ_IDLE：动态tick模式下tick到来时

7.2 负载计算：PELT（Per-Entity Load Tracking）

Linux 4.8之后引入了PELT替代之前的runnable_avg，以更精确地追踪每个调度实体的负载贡献：

// PELT衰减公式：load_avg = load_avg × y + load × (1 - y)
// 其中 y = (1/2)^(1/32)，即32ms半衰期
static __always_inline u64 decay_load(u64 val, u64 n)
{
    unsigned int local_n = n;
    
    if (unlikely(n > LOAD_AVG_PERIOD * 63))
        return 0;
    
    while (local_n >= LOAD_AVG_PERIOD) {
        val >>= 3;                    // 每32个周期衰减一半
        local_n -= LOAD_AVG_PERIOD;
    }
    // 使用预计算表处理剩余的不足32个周期
    val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
    return val;
}

PELT的32ms半衰期意味着：一个进程当前的负载贡献100%，在32ms后会衰减到50%，64ms后到25%。这个时间常数平衡了短期负载波动和长期趋势。

7.3 NUMA感知调度

在NUMA架构下，CFS负载均衡需要考虑内存访问延迟的成本差异，包含多级决策：

1. Same Node Balancing：在同一NUMA节点内迁移进程（开销最小）
2. Remote Node Balancing：跨NUMA节点迁移（需考虑内存带宽和QPI链路开销）
3. NUMA Balancing（AutoNUMA）：通过页访问采样，发现远程访问的页面，将进程迁移到页面所在的NUMA节点

AutoNUMA的工作流程：

• 内核定期对进程的内存区域设置PROT_NONE保护
• 当进程访问这些页面时触发缺页异常
• 内核记录访问CPU和页面所在的NUMA节点
• 如果一个进程的页面主要在另一个节点上，考虑迁移整个进程

迁移决策基于扫描速率（numa_balancing_scan_delay_ms）和迁移速率限制（numa_balancing_scan_period_min_ms、numa_balancing_scan_period_max_ms），默认扫描周期从1000ms逐渐增加到60秒。

7.4 迁移的代价模型

负载均衡不是免费的。迁移一个进程的成本包括：

• TLB刷新（如果目标CPU的旧TLB中有进程的映射）
• Cache冷启动（目标CPU的Cache中没有进程的数据）
• NUMA远程访问延迟（页面仍然在原NUMA节点上）

为了避免过度迁移，CFS引入了migration_cost阈值：只有当目标CPU的负载优势超过migration_cost × 某个因子时，才触发迁移。

八、组调度（Group Scheduling）

8.1 两层调度架构

组调度的核心思想是将调度粒度从"进程"扩展到"进程组"。在cgroup v1中，每个cgroup都可以有自己的运行队列。调度器实际上执行两个层次的调度：

1. 内部调度：在cgroup内部，各进程（或子cgroup）之间公平竞争
2. 外部调度：不同cgroup之间按权重比例分配CPU时间

实现的关键是sched_entity可以同时作为被调度对象（参与红黑树竞争）和调度队列（拥有子红黑树）。这种递归结构使得一个cgroup的调度实体既是父cfs_rq中的一个红黑树节点，又拥有自己的cfs_rq来管理其内部的进程。

// 带宽控制的核心数据结构
struct cfs_bandwidth {
    raw_spinlock_t lock;
    ktime_t period;                  // 周期长度（默认100ms）
    u64 quota;                       // 配额
    u64 runtime;                     // 剩余配额（可能被借用的）
    
    struct hlist_head throttled_cfs_rq; // 被限流的cfs_rq链表
    int nr_throttled;                // 被限流的队列数
    
    // 高精度定时器，用于恢复被限流的cfs_rq
    struct hrtimer period_timer;
    struct hrtimer slack_timer;
    // ...
};

// 带宽检查流程：account_cfs_rq_runtime
static int account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
{
    struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq_tg(cfs_rq));
    int ret;
    
    raw_spin_lock(&cfs_b->lock);
    ret = assign_cfs_rq_runtime(cfs_rq);  // 尝试从全局借用
    if (ret && cfs_b->quota == RUNTIME_INF)
        return ret;
    
    // 从剩余配额中扣除
    cfs_b->runtime -= min(cfs_b->runtime, delta_exec);
    
    if (cfs_b->runtime <= 0) {
        // 配额用完，限流该cgroup中所有cfs_rq
        throttle_cfs_rq(cfs_rq);
        raw_spin_unlock(&cfs_b->lock);
        return 1;
    }
    raw_spin_unlock(&cfs_b->lock);
    return 0;
}

# 查看容器级cgroup throttled时间
cat /sys/fs/cgroup/system.slice/docker-.scope/cpu.stat
# nr_throttled: 被限流次数
# throttled_time: 总限流时间（纳秒）

# perf sched record：记录调度事件
# perf sched latency：显示每个进程的最大/平均调度延迟
# perf sched map：CPU时间线视图
# perf sched script：原始事件输出