Linux 进程管理深度剖析（二）：CFS 完全公平调度器源码分析

Posted on 2026-04-14 In Linux Kernel , Process Management

本文基于 Linux 6.4-rc1（commit ac9a78681b92）源码，所有代码片段均直接来自内核源文件。主要参考文件：kernel/sched/fair.c、kernel/sched/sched.h、kernel/sched/core.c、kernel/sched/rt.c。

Linux 调度器是内核中最核心也最复杂的子系统之一。自 2.6.23 版本引入 CFS（Completely Fair Scheduler，完全公平调度器）以来，它已成为处理普通进程（SCHED_NORMAL、SCHED_BATCH）调度的主要机制。本文将从数据结构出发，深入分析 CFS 的每一个核心算法，揭示”公平”背后的工程实现。

一、调度器框架：调度类与运行队列

1.1 调度类层次（`struct sched_class`）

Linux 调度器采用面向对象的设计，通过 struct sched_class 抽象出调度策略接口。每种调度策略实现一套方法，调度器核心代码通过函数指针调用。

// kernel/sched/sched.h:2169
struct sched_class {

#ifdef CONFIG_UCLAMP_TASK
    int uclamp_enabled;
#endif

    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 (*yield_task)   (struct rq *rq);
    bool (*yield_to_task)(struct rq *rq, struct task_struct *p);

    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);

    struct task_struct *(*pick_next_task)(struct rq *rq);

    void (*put_prev_task)(struct rq *rq, struct task_struct *p);
    void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);

    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*task_fork)(struct task_struct *p);
    void (*task_dead)(struct task_struct *p);

    void (*update_curr)(struct rq *rq);
    /* ... */
};

各调度类按优先级从高到低排列，链接器脚本将它们放置在连续内存区域，for_each_class 宏按顺序遍历：

1	stop > dl > rt > fair > idle

stop：停止机器专用（CPU 热插拔、内核调试），优先级最高，永远抢占其他任务
dl：Deadline 调度（SCHED_DEADLINE），按截止时间调度实时任务
rt：实时调度（SCHED_FIFO、SCHED_RR），基于优先级位图
fair：CFS 公平调度（SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE），本文主角
idle：CPU 空闲时运行 idle 线程

// kernel/sched/sched.h:2272
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

1.2 运行队列 `struct rq`

每个 CPU 有一个全局运行队列 struct rq，所有调度类的队列都嵌入其中：

// kernel/sched/sched.h:957
struct rq {
    raw_spinlock_t      __lock;

    unsigned int        nr_running;     // 当前 CPU 可运行任务总数

    struct cfs_rq       cfs;            // CFS 运行队列
    struct rt_rq        rt;             // RT 运行队列
    struct dl_rq        dl;             // DL 运行队列

    struct task_struct __rcu    *curr;  // 当前正在运行的任务
    struct task_struct          *idle;  // idle 任务
    struct task_struct          *stop;  // stop 任务

    u64                 clock;          // 队列时钟（纳秒）
    u64                 clock_task;     // 任务时钟（排除 irq/steal）

    atomic_t            nr_iowait;      // 等待 I/O 的任务数

    /* SMP 负载均衡 */
    unsigned long       next_balance;
    /* ... */
};

通过 cpu_rq(cpu) 宏获取指定 CPU 的 rq，通过 this_rq() 获取当前 CPU 的 rq。

1.3 CFS 运行队列 `struct cfs_rq`

CFS 的核心数据结构，管理所有可运行的 CFS 调度实体：

// kernel/sched/sched.h:550
struct cfs_rq {
    struct load_weight  load;           // 队列总权重
    unsigned int        nr_running;     // 直接成员数
    unsigned int        h_nr_running;   // 递归成员总数（组调度）

    u64                 exec_clock;     // 已执行的 CPU 时间
    u64                 min_vruntime;   // 队列中最小 vruntime（单调递增）

    struct rb_root_cached tasks_timeline; // 红黑树（按 vruntime 排序）

    struct sched_entity *curr;          // 当前运行的调度实体
    struct sched_entity *next;          // 被标记为"优先运行"的实体
    struct sched_entity *last;          // 刚被抢占的实体（尽量恢复）
    struct sched_entity *skip;          // 应跳过的实体

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct rq           *rq;            // 所属 CPU 运行队列
    struct task_group   *tg;            // 所属任务组
#endif
};

min_vruntime 是一个单调递增的基准线，代表队列中”最公平”的进度时间点，用于新进程 vruntime 初始化和跨 CPU 迁移时的规范化。

1.4 调度实体 `struct sched_entity`

每个普通进程（以及组调度中的任务组）都有一个 struct sched_entity，嵌入在 task_struct 中：

// include/linux/sched.h:549
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;       // 虚拟运行时间（CFS 核心）
    u64                     prev_sum_exec_runtime; // 上次切换时的累计时间

    u64                     nr_migrations;  // 跨 CPU 迁移次数

#ifdef CONFIG_FAIR_GROUP_SCHED
    int                     depth;          // 层级深度
    struct sched_entity     *parent;        // 父调度实体
    struct cfs_rq           *cfs_rq;        // 所在 cfs_rq
    struct cfs_rq           *my_q;          // 若为 group，则为其拥有的 cfs_rq
    unsigned long           runnable_weight;
#endif
};

vruntime 是 CFS 的核心字段，代表该实体”虚拟时间维度”上的运行进度。CFS 始终选择 vruntime 最小的实体运行，以维护公平性。

二、CFS 核心算法：vruntime 与权重归一化

2.1 vruntime 的概念

CFS 的核心思想是：如果有 N 个相同权重的进程，每个进程应该获得 1/N 的 CPU 时间。为了跟踪”公平进度”，引入 vruntime（虚拟运行时间）：

1	vruntime += delta_exec × (NICE_0_LOAD / weight)

对于 nice=0 的进程（权重 1024），vruntime 增长速度等于真实时间。权重越大（nice 值越低），vruntime 增长越慢，因此会更频繁地被调度；权重越小（nice 值越高），vruntime 增长越快，被调度的频率越低。

2.2 权重表 `sched_prio_to_weight`

nice 值到权重的映射通过预计算表实现，相邻 nice 值之间权重比约为 1.25：

// kernel/sched/core.c:11459
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=0 对应权重 1024（NICE_0_LOAD），这是归一化的基准值。nice=-20 的权重（88761）约是 nice=0（1024）的 86 倍，意味着 nice=-20 的进程能获得近 86 倍于 nice=0 进程的 CPU 时间。

2.3 `calc_delta_fair`：vruntime 增量计算

// kernel/sched/fair.c:709
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;
}

__calc_delta 的计算公式为：

1 2	delta_vruntime = delta_exec × NICE_0_LOAD / weight = delta_exec × 1024 / se->load.weight

为了避免浮点运算，内核通过预计算的逆权重表（sched_prio_to_wmult）将除法转化为乘法：delta × wmult >> 32。

2.4 `update_curr`：实时更新 vruntime

每次时钟中断、调度切换时都会调用 update_curr 更新当前进程的运行统计：

// kernel/sched/fair.c:897
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;  // 累加真实运行时间

    curr->vruntime += calc_delta_fair(delta_exec, curr);  // 更新虚拟时间
    update_min_vruntime(cfs_rq);           // 更新队列基准线

    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);
        cgroup_account_cputime(curtask, delta_exec);  // cgroup 计费
    }

    account_cfs_rq_runtime(cfs_rq, delta_exec);  // 带宽控制计费
}

update_min_vruntime 维护 cfs_rq->min_vruntime 单调递增：它取当前运行实体的 vruntime 和红黑树中最左节点的 vruntime 二者中的较小值，但保证不回退。

2.5 CFS 红黑树操作

CFS 使用红黑树（struct rb_root_cached）以 vruntime 为键组织所有可运行实体。rb_root_cached 额外缓存了最左节点，使得 O(1) 时间内找到 vruntime 最小的实体。

// kernel/sched/fair.c:643
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
}

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);

    if (!left)
        return NULL;

    return __node_2_se(left);
}

__entity_less 比较两个实体的 vruntime，确保红黑树按 vruntime 升序排列。最左节点始终是 vruntime 最小的实体，即最应被调度的进程。

注意：当前正在运行的实体（cfs_rq->curr）不在红黑树中，只有就绪但未运行的实体才在树中。当前实体被切换出去时，才通过 put_prev_entity 重新插入树中。

2.6 `pick_next_entity`：选择下一个运行实体

// kernel/sched/fair.c:5084
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;

    /*
     * 若 curr 仍在队列中且其 vruntime 小于树中最左节点，优先考虑 curr
     */
    if (!left || (curr && entity_before(curr, left)))
        left = curr;

    se = left;  /* 理想情况下运行最左实体 */

    /* 避免运行 skip buddy（主动 yield 时标记）*/
    if (cfs_rq->skip && cfs_rq->skip == se) {
        struct sched_entity *second;
        /* 尝试选次优实体 */
        if (se == curr) {
            second = __pick_first_entity(cfs_rq);
        } else {
            second = __pick_next_entity(se);
            if (!second || (curr && entity_before(curr, second)))
                second = curr;
        }
        if (second && wakeup_preempt_entity(second, left) < 1)
            se = second;
    }

    /* next buddy：被标记为"下一个应运行"（wakeup 抢占提名） */
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
        se = cfs_rq->next;
    } else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
        /* last buddy：尽量恢复刚被抢占的任务，减少上下文切换 */
        se = cfs_rq->last;
    }

    return se;
}

这里引入了三个”buddy”机制：

skip：主动 sched_yield 的实体，本轮跳过
next：因 wakeup 抢占而被提名的实体，优先运行
last：刚刚被抢占的实体，若成本可接受则优先恢复，减少上下文切换开销

wakeup_preempt_entity 判断候选实体相对于最优实体的 vruntime 差距是否在允许范围内（wakeup_gran，基于 sysctl_sched_wakeup_granularity）。

三、进程入队与出队

3.1 `enqueue_task_fair`：进程变为 RUNNABLE 时入队

当进程从睡眠唤醒或新建进程时，enqueue_task_fair 被调用：

// kernel/sched/fair.c:6291
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;
    int task_new = !(flags & ENQUEUE_WAKEUP);

    util_est_enqueue(&rq->cfs, p);  // 更新利用率估计

    for_each_sched_entity(se) {
        if (se->on_rq)
            break;
        cfs_rq = cfs_rq_of(se);
        enqueue_entity(cfs_rq, se, flags);  // 插入 cfs_rq

        cfs_rq->h_nr_running++;

        if (cfs_rq_throttled(cfs_rq))  // 若队列被限流则停止向上传播
            goto enqueue_throttle;

        flags = ENQUEUE_WAKEUP;
    }

    /* 更新父层级的统计（组调度） */
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        update_load_avg(cfs_rq, se, UPDATE_TG);
        update_cfs_group(se);
        cfs_rq->h_nr_running++;
        if (cfs_rq_throttled(cfs_rq))
            goto enqueue_throttle;
    }

    add_nr_running(rq, 1);  // 全局 nr_running +1
    /* ... */
}

for_each_sched_entity 在非组调度情况下只迭代一次（直接返回进程本身），在组调度下则会沿父链向上遍历，将每一层的 cfs_rq 都更新。

内层的 enqueue_entity 完成实际插入：

// kernel/sched/fair.c:4823
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);

    if (renorm && cfs_rq->curr == se)
        se->vruntime += cfs_rq->min_vruntime;  // 规范化（迁移后）

    update_curr(cfs_rq);  // 先更新当前进程的 vruntime

    if (renorm && cfs_rq->curr != se)
        se->vruntime += cfs_rq->min_vruntime;

    update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
    account_entity_enqueue(cfs_rq, se);  // 加入队列权重

    if (flags & ENQUEUE_WAKEUP)
        place_entity(cfs_rq, se, 0);  // 设置唤醒进程的初始 vruntime

    if (!curr)
        __enqueue_entity(cfs_rq, se);  // 插入红黑树
    se->on_rq = 1;
}

3.2 `place_entity`：防止饥饿的 vruntime 初始化

新创建的进程或长期睡眠后唤醒的进程，其 vruntime 可能远小于 min_vruntime，若直接放入队列会持续抢占其他进程（因为它的 vruntime 最小）。place_entity 通过调整 vruntime 来防止这种情况：

// kernel/sched/fair.c:4732
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;  // 以队列基准线为起点

    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);  // 新进程：额外惩罚一个 vslice

    if (!initial) {
        unsigned long thresh;

        if (se_is_idle(se))
            thresh = sysctl_sched_min_granularity;
        else
            thresh = sysctl_sched_latency;  // 唤醒进程：补偿最多一个调度周期

        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;  // 只补偿一半，避免 sleeper 占便宜

        vruntime -= thresh;
    }

    /* 确保不倒退（防止 vruntime 溢出边界情况） */
    if (entity_is_long_sleeper(se))
        se->vruntime = vruntime;
    else
        se->vruntime = max_vruntime(se->vruntime, vruntime);
}

这里有两种场景：

新进程（initial=1）：vruntime = min_vruntime + sched_vslice。新进程不能直接从 min_vruntime 起跑，需要额外支付一个”虚拟时间片”的”入场费”，防止 fork 炸弹抢占所有 CPU。
唤醒进程（initial=0）：vruntime = min_vruntime - thresh。睡眠进程被唤醒时，允许其 vruntime 比当前基准线略小（补偿其等待时间），但最多补偿一个调度周期（sysctl_sched_latency），避免长期睡眠者无限期抢占。

3.3 `dequeue_task_fair`：进程阻塞或被抢占时出队

// kernel/sched/fair.c:6384
static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;
    int task_sleep = flags & DEQUEUE_SLEEP;

    util_est_dequeue(&rq->cfs, p);

    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        dequeue_entity(cfs_rq, se, flags);

        cfs_rq->h_nr_running--;

        if (cfs_rq_throttled(cfs_rq))
            goto dequeue_throttle;

        /* 若父队列中还有其他实体，停止向上传播 */
        if (cfs_rq->load.weight) {
            se = parent_entity(se);
            /* 进程主动睡眠时，提名父实体为 next_buddy，提升同组任务的调度优先级 */
            if (task_sleep && se && !throttled_hierarchy(cfs_rq))
                set_next_buddy(se);
            break;
        }
        flags |= DEQUEUE_SLEEP;
    }

    /* 更新父层级统计 */
    for_each_sched_entity(se) { /* ... */ }

    sub_nr_running(rq, 1);  // 全局 nr_running -1
}

四、调度周期与抢占机制

4.1 `sched_slice`：计算进程的调度时间片

CFS 没有固定时间片，而是根据进程权重动态计算应得的 CPU 时间：

// kernel/sched/fair.c:741
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    unsigned int nr_running = cfs_rq->nr_running;
    u64 slice;

    /* 调度周期：nr_running <= sched_nr_latency 时固定为 sysctl_sched_latency
     * 超过时按比例拉伸：period = nr_running × min_granularity
     */
    slice = __sched_period(nr_running + !se->on_rq);

    /* 按权重比例分配：slice = period × (se->weight / cfs_rq->total_weight) */
    for_each_sched_entity(se) {
        struct load_weight *load;
        struct cfs_rq *qcfs_rq = cfs_rq_of(se);
        /* ... 计算权重比 ... */
        slice = __calc_delta(slice, se->load.weight, load);
    }

    /* 确保不低于最小粒度 */
    /* ... */
    return slice;
}

默认参数（可通过 /proc/sys/kernel/sched_* 调整）：

sysctl_sched_latency：调度周期，默认 6ms（nr_running <= 8 时）
sysctl_sched_min_granularity：最小运行粒度，默认 0.75ms
sysctl_sched_nr_latency：超过此值后拉伸周期，默认 8

举例：有 4 个相同 nice 值的进程，调度周期 6ms，每个进程的时间片为 6/4 = 1.5ms。若一个进程 nice=-5（权重 3121），另三个 nice=0（权重 1024），则 nice=-5 进程获得 6ms × 3121 / (3121 + 3×1024) ≈ 3ms。

4.2 时钟中断中的 CFS Tick：`task_tick_fair`

// kernel/sched/fair.c:12064
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;

    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued);  // 每层 cfs_rq 都更新
    }

    if (static_branch_unlikely(&sched_numa_balancing))
        task_tick_numa(rq, curr);  // NUMA 平衡检查

    update_misfit_status(curr, rq);
    update_overutilized_status(task_rq(curr));
}

entity_tick 中调用 check_preempt_tick 检查是否需要抢占：

// kernel/sched/fair.c:4993
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_slice 与 sysctl_sched_latency 取小） */
    ideal_runtime = min_t(u64, sched_slice(cfs_rq, curr), sysctl_sched_latency);

    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
        clear_buddies(cfs_rq, curr);
        return;
    }

    /* 若运行时间不足最小粒度，不抢占（避免频繁切换） */
    if (delta_exec < sysctl_sched_min_granularity)
        return;

    /* 若当前进程的 vruntime 已超过红黑树最左节点 delta > ideal_runtime，抢占 */
    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;
    if (delta < 0)
        return;
    if (delta > ideal_runtime)
        resched_curr(rq_of(cfs_rq));
}

4.3 调度器 tick 调用链

timer interrupt
    → scheduler_tick()                    [kernel/sched/core.c]
        → curr->sched_class->task_tick()
            → task_tick_fair()            [kernel/sched/fair.c]
                → entity_tick()
                    → update_curr()       // 更新 vruntime
                    → check_preempt_tick() // 检查是否超时
                        → resched_curr()  // 设置 TIF_NEED_RESCHED
    → trigger_load_balance()              // 触发负载均衡

scheduler_tick 的核心路径：

// kernel/sched/core.c:5602
void scheduler_tick(void)
{
    int cpu = smp_processor_id();
    struct rq *rq = cpu_rq(cpu);
    struct task_struct *curr = rq->curr;

    rq_lock(rq, &rf);
    update_rq_clock(rq);
    curr->sched_class->task_tick(rq, curr, 0);  // 调用调度类的 tick 方法
    calc_global_load_tick(rq);

    rq_unlock(rq, &rf);

#ifdef CONFIG_SMP
    rq->idle_balance = idle_cpu(cpu);
    trigger_load_balance(rq);  // 触发 SMP 负载均衡
#endif
}

4.4 唤醒抢占：`check_preempt_wakeup`

当一个进程被唤醒（wake_up_process）时，内核会检查是否应该抢占当前进程：

// kernel/sched/fair.c:7855
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &curr->se, *pse = &p->se;
    struct cfs_rq *cfs_rq = task_cfs_rq(curr);

    /* SCHED_BATCH/SCHED_IDLE 进程不会通过 wakeup 抢占 */
    if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
        return;

    find_matching_se(&se, &pse);  // 找到公共祖先层级

    update_curr(cfs_rq_of(se));
    if (wakeup_preempt_entity(se, pse) == 1) {
        if (!next_buddy_marked)
            set_next_buddy(pse);  // 提名新任务为 next buddy
        goto preempt;
    }
    return;

preempt:
    resched_curr(rq);  // 设置重调度标志
}

wakeup_preempt_entity 判断逻辑：

// kernel/sched/fair.c:7810
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
    s64 gran, vdiff = curr->vruntime - se->vruntime;

    if (vdiff <= 0)
        return -1;  // 新任务 vruntime 更大，不抢占

    gran = wakeup_gran(se);  // 基于 sysctl_sched_wakeup_granularity 计算
    if (vdiff > gran)
        return 1;  // 差距超过粒度阈值，触发抢占

    return 0;
}

只有当当前进程的 vruntime 超过唤醒进程 vruntime 一个 wakeup_gran 时才触发抢占，避免因微小的 vruntime 差异导致频繁切换。

五、组调度（Group Scheduling）与 cgroup

5.1 `struct task_group`：cgroup CPU 调度组

// kernel/sched/sched.h:369
struct task_group {
    struct cgroup_subsys_state css;  // cgroup 子系统状态

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity **se;        // 每个 CPU 的调度实体（该组在父队列中的代表）
    struct cfs_rq       **cfs_rq;   // 每个 CPU 的 CFS 运行队列
    unsigned long        shares;    // cpu.shares（cgroup v1）/ cpu.weight（v2）
#endif

    struct task_group   *parent;
    struct list_head     siblings;
    struct list_head     children;

    struct cfs_bandwidth cfs_bandwidth;  // CPU 带宽控制（quota/period）
};

5.2 层次化调度结构

组调度的核心思想是：每个 task_group 在每个 CPU 上都有独立的 cfs_rq 和 sched_entity。

root task_group
├── se[0] ← 在 CPU 0 的 root cfs_rq 中代表整个组
│   my_q → task_group A 的 CPU 0 cfs_rq
│           ├── task1->se
│           └── task2->se
└── se[1] ← 在 CPU 1 的 root cfs_rq 中代表整个组
    my_q → task_group A 的 CPU 1 cfs_rq
            └── task3->se

pick_next_task_fair 通过 do { se = pick_next_entity(cfs_rq); cfs_rq = group_cfs_rq(se); } while (cfs_rq) 循环，从根 cfs_rq 向下穿透，直到找到一个叶子级别的 sched_entity（即真正的进程）。

5.3 cpu.shares 与 cpu.weight

cgroup v1：cpu.shares（默认 1024），等比例分配 CPU。两个组分别设置 512 和 1024，则第二个组能获得约两倍 CPU 时间。
cgroup v2：cpu.weight（默认 100，范围 1-10000），语义相同但取值范围不同。

对应内核中的 task_group->shares 字段，通过 sched_group_set_shares 更新，最终调整 se->load.weight，从而影响 sched_slice 的计算。

5.4 CPU 带宽控制：`cpu.cfs_quota_us` / `cpu.cfs_period_us`

带宽控制允许限制一个 cgroup 在一个周期内最多使用多少 CPU 时间，超出即被限流（throttle）直到下一个周期。

5.5 `throttle_cfs_rq` / `unthrottle_cfs_rq`

当 cgroup 消耗完配额时触发限流：

// kernel/sched/fair.c:5400
static bool throttle_cfs_rq(struct cfs_rq *cfs_rq)
{
    struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);

    raw_spin_lock(&cfs_b->lock);
    if (__assign_cfs_rq_runtime(cfs_b, cfs_rq, 1)) {
        /* 有新配额分配，不需要限流 */
        dequeue = 0;
    } else {
        /* 将 cfs_rq 加入限流链表 */
        list_add_tail_rcu(&cfs_rq->throttled_list,
                          &cfs_b->throttled_cfs_rq);
    }
    raw_spin_unlock(&cfs_b->lock);

    if (!dequeue)
        return false;

    /* 从父 cfs_rq 中移除该组的调度实体 */
    se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
    for_each_sched_entity(se) {
        dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
        /* ... */
    }
    sub_nr_running(rq, task_delta);
    /* ... */
}

被限流的 cfs_rq 中的所有任务实际上被”虚拟阻塞”——它们仍在 cfs_rq 中，但其父调度实体已被从父 cfs_rq 移除，因此不会被调度。

配额补充由高精度定时器（hrtimer）在每个 cfs_period 结束时触发 sched_cfs_period_timer，调用 unthrottle_cfs_rq 解除限流，重新将组的调度实体加入父 cfs_rq。

六、负载均衡（Load Balance）

6.1 整体框架

SMP 系统中，CFS 通过周期性负载均衡将任务从繁忙 CPU 迁移到空闲 CPU，以实现全局公平性。触发时机：

周期性均衡：scheduler_tick → trigger_load_balance → 软中断 SCHED_SOFTIRQ → run_rebalance_domains → load_balance
空闲时均衡：CPU 进入 idle 时调用 load_balance 主动拉取任务
新任务唤醒：select_task_rq_fair 选择负载最轻的 CPU

6.2 `load_balance` 主流程

// kernel/sched/fair.c:10733
static int load_balance(int this_cpu, struct rq *this_rq,
                        struct sched_domain *sd, enum cpu_idle_type idle,
                        int *continue_balancing)
{
    struct sched_group *group;
    struct rq *busiest;
    struct lb_env env = {
        .sd      = sd,
        .dst_cpu = this_cpu,
        .dst_rq  = this_rq,
        .idle    = idle,
        /* ... */
    };

    cpumask_and(cpus, sched_domain_span(sd), cpu_active_mask);

    group = find_busiest_group(&env);      // 在调度域中找最繁忙的组
    if (!group) goto out_balanced;

    busiest = find_busiest_queue(&env, group);  // 在组中找最繁忙的队列
    if (!busiest) goto out_balanced;

    env.src_cpu = busiest->cpu;
    env.src_rq  = busiest;

    /* 迁移任务 */
    ld_moved = detach_tasks(&env);
    if (ld_moved) {
        attach_tasks(&env);
        /* ... */
    }
    /* ... */
}

6.3 `find_busiest_group` 与 `find_busiest_queue`

// kernel/sched/fair.c:10361
static struct sched_group *find_busiest_group(struct lb_env *env)
{
    /* 统计每个 sched_group 的负载 */
    update_sd_lb_stats(env, &sds);

    /* 处理特殊情况：misfit task、asym packing、imbalanced group */
    if (busiest->group_type == group_misfit_task) goto force_balance;
    if (busiest->group_type == group_asym_packing)  goto force_balance;

    /* 计算不平衡量 */
    calculate_imbalance(env, &sds);
    return sds.busiest;
}

find_busiest_queue 在选定的 sched_group 中，选出运行队列权重最高（任务最重）的 CPU：

// kernel/sched/fair.c:10490
static struct rq *find_busiest_queue(struct lb_env *env,
                                     struct sched_group *group)
{
    /* 遍历组内各 CPU，找 runnable_load 最大且允许迁移的队列 */
    for_each_cpu_and(i, sched_group_span(group), env->cpus) {
        /* 计算 rq 的 runnable load，选择最大值 */
        /* 排除亲和性不允许迁移的情况 */
    }
    return busiest;
}

6.4 调度域（Scheduling Domain）层次

负载均衡在调度域（sched_domain）层次上进行，从低到高：

SMT（超线程，同一物理核的逻辑核）
  → MC（多核，同一物理 CPU 的多个核）
    → NUMA（跨 NUMA 节点）
      → 系统级

每一层的均衡间隔、迁移代价、不平衡阈值都可以单独配置。

6.5 NUMA 感知调度

// kernel/sched/fair.c:3188
static void task_tick_numa(struct rq *rq, struct task_struct *curr)
{
    /*
     * 周期性扫描任务的内存访问模式，
     * 通过页表保护位触发 NUMA hinting fault，
     * 统计各 NUMA 节点的访问热度，
     * 将任务迁移到访问最频繁的内存所在节点。
     */
    now = curr->se.sum_exec_runtime;
    period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;

    if (now > curr->node_stamp + period) {
        curr->node_stamp += period;
        if (!time_before(jiffies, curr->mm->numa_next_scan))
            task_work_add(curr, work, TWA_RESUME);  // 触发 NUMA 扫描
    }
}

NUMA 均衡通过 task_numa_migrate 实现，综合考虑任务的内存访问热度（NUMA faults）和 CPU 负载，将任务迁移到数据所在的 NUMA 节点，减少跨节点内存访问延迟。

七、实时调度（RT Scheduler）概述

CFS 处理普通进程，rt_sched_class 处理实时进程（SCHED_FIFO 和 SCHED_RR）。RT 任务永远优先于 CFS 任务运行。

7.1 SCHED_FIFO vs SCHED_RR

策略	特点
`SCHED_FIFO`	先入先出。只有主动放弃 CPU（`sched_yield`）、阻塞或被更高优先级任务抢占时才切换。时间片无限。
`SCHED_RR`	轮转调度。有固定时间片（默认 100ms），时间片耗尽后轮转到同优先级队列末尾。

RT 进程优先级为 1-99（sched_priority），99 最高。CFS 进程等效 RT 优先级为 0。

7.2 `struct rt_prio_array`：优先级位图

// kernel/sched/sched.h:273
struct rt_prio_array {
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1);  // 位图：标记哪些优先级有任务
    struct list_head queue[MAX_RT_PRIO];    // 每个优先级对应一个 FIFO 链表
};

RT 运行队列通过位图实现 O(1) 找到最高优先级：sched_find_first_bit(bitmap) 立即定位第一个置位的优先级，然后从对应链表头取出任务。

7.3 `pick_next_task_rt`

// kernel/sched/rt.c:1787
static struct task_struct *_pick_next_task_rt(struct rq *rq)
{
    struct sched_rt_entity *rt_se;
    struct rt_rq *rt_rq = &rq->rt;

    do {
        rt_se = pick_next_rt_entity(rt_rq);  // 从位图找最高优先级任务
        if (unlikely(!rt_se))
            return NULL;
        rt_rq = group_rt_rq(rt_se);
    } while (rt_rq);

    return rt_task_of(rt_se);
}

pick_next_rt_entity 通过 sched_find_first_bit(array->bitmap) 找到最高优先级，然后返回对应链表的第一个实体，时间复杂度 O(1)。

八、调度诊断与调优

8.1 查看和修改调度策略

# 查看进程调度策略和优先级
chrt -p $PID

# 将进程设为 SCHED_FIFO，优先级 50
chrt -f -p 50 $PID

# 将进程设为 SCHED_RR，优先级 20
chrt -r -p 20 $PID

# 将进程重置为 SCHED_OTHER（CFS）
chrt -o -p 0 $PID

8.2 调整 nice 值

# 调整运行中进程的 nice 值（需要 CAP_SYS_NICE 或降低 nice 值）
renice -n -5 -p $PID

# 以指定 nice 值启动进程
nice -n 10 ./my_process

# 查看所有进程的 nice 值
ps -eo pid,ni,comm --sort=ni

8.3 `/proc/PID/sched`：CFS 调度统计

1	cat /proc/$(pidof nginx)/sched

输出示例：

nginx (12345, #threads: 4)
---------------------------------------------------------
se.exec_start                      :    1234567890.123456
se.vruntime                        :         12345.678901
se.sum_exec_runtime                :       1234567.890123
se.nr_migrations                   :               42
nr_switches                        :             1234
nr_voluntary_switches              :              980
nr_involuntary_switches            :              254
se.load.weight                     :             1024
se.avg.load_avg                    :              512
se.avg.util_avg                    :              256

关键字段：

vruntime：当前虚拟运行时间
sum_exec_runtime：累计实际 CPU 时间（ns）
nr_voluntary_switches：主动切换次数（I/O 等待等）
nr_involuntary_switches：被动抢占次数（时间片用完）
se.load.weight：当前权重（由 nice 值决定）

8.4 `/proc/schedstat`：全局调度统计

cat /proc/schedstat
# 每行对应一个 CPU
# 格式：cpu<N> 各种计数器...
# 字段含义参见 Documentation/scheduler/sched-stats.rst

结合 schedtool 或 tuna 可更方便地解析。

8.5 `perf sched`：调度延迟分析

# 录制调度事件（需要 root）
perf sched record -a sleep 10

# 分析调度延迟
perf sched latency

# 输出示例：
# Task                  |   Runtime ms  | Switches | Average delay ms | Maximum delay ms |
# nginx:12345           |     123.456   |     100  |         0.123    |         5.678    |

# 查看调度时间线
perf sched timehist

# 分析 map
perf sched map

8.6 bpftrace 追踪调度决策

# 追踪 pick_next_task_fair 调用，输出被选中的进程
bpftrace -e '
kprobe:pick_next_task_fair {
    $rq = (struct rq *)arg0;
    if ($rq->cfs.nr_running > 0) {
        printf("CPU %d: nr_running=%d\n",
               cpu, $rq->cfs.nr_running);
    }
}'

# 追踪调度延迟超过 1ms 的进程
bpftrace -e '
tracepoint:sched:sched_wakeup {
    @wake[args->pid] = nsecs;
}
tracepoint:sched:sched_switch {
    $prev_pid = args->prev_pid;
    if (@wake[$prev_pid]) {
        $latency = (nsecs - @wake[$prev_pid]) / 1000000;
        if ($latency > 1) {
            printf("pid %d comm %s latency %d ms\n",
                   $prev_pid, args->prev_comm, $latency);
        }
        delete(@wake[$prev_pid]);
    }
}'

# 统计 vruntime 分布（需要 BTF 支持）
bpftrace -e '
kprobe:enqueue_task_fair {
    $p = (struct task_struct *)arg1;
    @vruntime = hist($p->se.vruntime / 1000000);
}'

8.7 cgroup CPU 统计

# cgroup v2
cat /sys/fs/cgroup/my_service/cpu.stat
# 输出：
# usage_usec 12345678       # 累计 CPU 使用时间（微秒）
# user_usec  8765432
# system_usec 3580246
# nr_periods  100            # 经历的带宽周期数
# nr_throttled 5             # 被限流的周期数
# throttled_usec 50000       # 被限流的总时间（微秒）
# nr_bursts 0
# burst_usec 0

# 查看/设置带宽限制
cat /sys/fs/cgroup/my_service/cpu.max
# 输出：50000 100000    （quota=50ms, period=100ms）

# 设置为 0.5 CPU
echo "50000 100000" > /sys/fs/cgroup/my_service/cpu.max

# 查看 cpu.weight（cgroup v2，对应 cpu.shares / 10.24）
cat /sys/fs/cgroup/my_service/cpu.weight

# cgroup v1
cat /sys/fs/cgroup/cpu/my_service/cpu.stat
cat /sys/fs/cgroup/cpu/my_service/cpu.shares

8.8 调度参数调优

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

# 调度延迟周期（默认 6000000 ns = 6ms）
sysctl kernel.sched_latency_ns

# 最小运行粒度（默认 750000 ns = 0.75ms）
# 进程运行不足此时间不会被抢占
sysctl kernel.sched_min_granularity_ns

# 唤醒抢占粒度（默认 1000000 ns = 1ms）
# 唤醒进程 vruntime 优势需超过此值才触发抢占
sysctl kernel.sched_wakeup_granularity_ns

# 延迟敏感场景（如实时音视频）：降低粒度
sysctl -w kernel.sched_min_granularity_ns=500000
sysctl -w kernel.sched_wakeup_granularity_ns=500000
sysctl -w kernel.sched_latency_ns=3000000

# 吞吐量优先场景（如批处理）：增大粒度，减少切换
sysctl -w kernel.sched_min_granularity_ns=2000000
sysctl -w kernel.sched_latency_ns=12000000

小结

CFS 的设计哲学在于将抽象的”公平”转化为具体的可计算量——vruntime。通过这个虚拟时间轴，内核无需维护复杂的优先级队列逻辑，只需一棵以 vruntime 为键的红黑树，就能以 O(log n) 的复杂度实现近乎完美的公平调度。

核心设计要点回顾：

vruntime 归一化：calc_delta_fair 用权重对真实时间进行缩放，权重大的进程 vruntime 增长慢，因此获得更多 CPU 时间，这是 CFS”公平”的数学基础。
min_vruntime 锚点：单调递增的 min_vruntime 防止新进程/唤醒进程通过历史积累的低 vruntime 无限抢占，place_entity 在此基础上实现精细的”补偿-惩罚”策略。
**红黑树 O(log n)**：rb_root_cached 缓存最左节点实现 O(1) 选取，__enqueue_entity/__dequeue_entity 维护 O(log n) 插入删除。
组调度层次化：每个 task_group 在每个 CPU 上都有独立的 cfs_rq 和 sched_entity，通过多层遍历实现层次化公平，cgroup CPU 带宽控制基于此实现容器 CPU 限制。
SMP 负载均衡：通过调度域层次（SMT → MC → NUMA）实现多粒度的负载均衡，NUMA 感知调度进一步优化内存局部性。

理解 CFS 的源码不仅有助于诊断调度延迟问题，也为容器化环境下合理设置 cpu.shares/cpu.weight 和 cpu.cfs_quota_us 提供了理论基础。下一篇文章将深入分析 Linux 进程的内存管理机制，包括虚拟内存区域（VMA）、缺页异常处理和 OOM Killer 的实现。

一、调度器框架：调度类与运行队列

1.1 调度类层次（struct sched_class）

1.2 运行队列 struct rq

1.3 CFS 运行队列 struct cfs_rq

1.4 调度实体 struct sched_entity

二、CFS 核心算法：vruntime 与权重归一化

2.1 vruntime 的概念

2.2 权重表 sched_prio_to_weight

2.3 calc_delta_fair：vruntime 增量计算

2.4 update_curr：实时更新 vruntime