Linux内核进程调度与CFS完全公平调度器深度实战：从vruntime到NUMA感知全链路

引言

进程调度是操作系统的核心组件之一，它决定了哪个进程在何时获得CPU时间。从早期的O(n)调度器到O(1)调度器，Linux内核在2.6.23版本中引入了完全公平调度器（Completely Fair Scheduler，CFS），这一革新性的设计彻底改变了Linux进程调度的范式。CFS的核心思想不是传统意义上的时间片分配，而是追求CPU时间的绝对公平分配——让每个进程获得的CPU时间与系统中总进程数成正比。

本文将从CFS的设计理念出发，深入剖析其红黑树数据结构、虚拟运行时（vruntime）机制、调度延迟控制、组调度（cgroup）支持，并结合proc文件系统调优与perf工具实战，帮助读者构建完整的Linux进程调度知识体系。

一、CFS的设计哲学——"理想多任务处理器"模型

CFS的设计基于一个理论模型：如果系统中有N个可运行进程，每个进程应该获得1/N的CPU时间。在现实中，真正的"同时执行"只存在于多核系统中，单核需要通过快速切换来模拟并行。CFS将这个理想模型进行数学建模：

核心概念：虚拟运行时（vruntime）

每个进程维护一个vruntime值，表示该进程在"理想处理器"上已经运行的时间。调度器总是选择vruntime最小的进程执行，从而保证所有进程的vruntime尽可能接近，实现数学意义上的公平。

关键公式：

实际运行时间 = 权值因子 × 虚拟运行时间

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

其中：
- NICE_0_LOAD = 1024（nice值为0时的权重基准）
- 进程权重由static_prio决定
- 高权重进程的vruntime增长更慢（获得更多CPU）

这意味着优先级高的进程（nice值低）其vruntime增长更慢，因此能更频繁地被调度。当nice值从0降到-1时，进程获得的CPU时间增加约10%；当nice值从0升到1时，CPU时间减少约10%。

二、红黑树数据结构——O(log n)的高效调度

CFS使用红黑树（Red-Black Tree）来组织所有可运行进程。红黑树是一种自平衡二叉搜索树，CFS利用它按vruntime值对进程进行排序。

关键数据结构关系：

struct cfs_rq {                    // CFS运行队列
    struct rb_root_cached  tasks_timeline;  // 红黑树根节点
    struct rb_node        *rb_leftmost;     // 缓存最左节点（最小vruntime）
    u64                    min_vruntime;    // 最小vruntime基准值
    unsigned long          nr_running;      // 可运行进程数
    struct load_weight     load;           // 队列总权重
};

struct sched_entity {              // 调度实体（嵌入在task_struct中）
    struct run_node        run_node;       // 红黑树节点
    u64                    vruntime;       // 虚拟运行时间
    u64                    exec_start;     // 本次执行开始时间
    u64                    sum_exec_runtime; // 总实际运行时间
    u64                    prev_sum_exec_runtime; // 上次切换时的总运行时间
    u64                    vdiskruntime;   // 磁盘I/O虚拟时间（用于组调度）
};

红黑树的关键优势在于：

• 插入操作：O(log n)，新唤醒的进程根据其vruntime插入到树中合适位置
• 最小值查找：O(1)，通过缓存的rb_leftmost指针直接获取
• 删除操作：O(log n)，进程阻塞或被抢占时从树中移除
• 中序遍历：vruntime从小到大的进程序列

底层的vruntime缓存机制（min_vruntime）确保即使长时间阻塞的进程被唤醒时也不会因为vruntime过小而"饿死"其他进程——CFS会将新唤醒进程的vruntime最小值限制为cfs_rq->min_vruntime - sysctl_sched_latency，防止饥饿调度。

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

理解CFS的实际调度流程需要追踪从时钟中断到最终上下文切换的完整路径。

3.1 时钟中断触发路径

每个tick时钟中断到来时，硬件定时器触发local_timer_interrupt，最终调用scheduler_tick()函数：

 scheduler_tick()
   └─> task_tick_fair(rq, current, 0)
        └─> entity_tick(cfs_rq, curr, queue)
             ├─ update_curr(cfs_rq)          // 更新当前进程的统计
             │    ├─ calc_delta_fair()        // 计算vruntime增量
             │    └─ update_min_vruntime()    // 更新队列基准值
             │
             └─ check_preempt_tick(cfs_rq, curr) // 检查是否需要抢占

3.2 update_curr()——vruntime实时更新

该函数在每次tick被调用，它：

• 获取当前时间now
• 计算delta_exec = now - curr->exec_start（本次已运行时间）
• 通过__update_curr()转换为vruntime增量（考虑权重和nice值）
• 更新curr->vruntime，并维护cfs_rq->min_vruntime
• 设置exec_start = now（为下一次tick做准备）

3.3 check_preempt_tick()——抢占决策

这是CFS中"是否应该调度"的关键判断点：

// Linux 6.x 代码片段（简化版）
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;

    // 计算当前进程应该获得的理想运行时间
    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));
        clear_buddies(cfs_rq, curr);
        return;
    }
    
    // 如果调度延迟已经过半，也允许抢占
    if (delta_exec < sysctl_sched_min_granularity)
        return;
        
    // 检查最左节点进程的vruntime是否显著更小
    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;
    if (delta > 0)
        resched_curr(rq_of(cfs_rq));
}

sysctl_sched_min_granularity（默认0.75ms）是当前进程被抢占前必须运行的最小时间，防止过于频繁的上下文切换。sched_slice()是进程在一个调度周期内分得的份额。

3.4 pick_next_task_fair()——选择下一个进程

当调度器需要选择下一个运行的进程时：

pick_next_task_fair()
   ├─ 如果nr_running == 0，返回NULL（无进程可运行）
   ├─ 删除当前进程（阻塞时）
   └─ set_next_entity()
        ├─ 从红黑树中取出最左节点（最小vruntime）
        ├─ 从树中删除该节点
        ├─ 设置cfs_rq->curr = se
        └─ 记录exec_start = rq_clock_task(rq)

当新进程被选中时，数据结构上的移除（非内存释放）避免了该进程后续被重复选中。

四、调度延迟与粒度的精细控制

CFS通过两个核心参数平衡公平性和切换开销：

4.1 sched_latency_ns（调度延迟）

默认值为6ms（CONFIG_HZ=250时），表示一个完整调度周期内所有可运行进程都应该至少被调度一次的时间。如果进程数过多，一个周期的总时间会超过sched_latency_ns，CFS通过sched_slice()确保每个进程在这段时间内的运行时间不短于min_granularity。

// 每个进程的调度片时间
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 *= se->load.weight;
    do_div(slice, cfs_rq->load.weight);
    return slice;
}

// 调度周期计算
static u64 __sched_period(unsigned long nr_running)
{
    if (nr_running > sysctl_sched_nr_latency)
        return nr_running * sysctl_sched_min_granularity;
    return sysctl_sched_latency;
}

// nr_latency = sched_latency / min_granularity = 6ms / 0.75ms = 8

4.2 min_granularity_ns（最小粒度）

默认值为0.75ms，当可运行进程超过8个时（sched_latency / min_granularity），调度周期会膨胀到nr_running × min_granularity。这保证了即使在100个进程的系统中，每个进程也能获得至少0.75ms的连续运行时间。

4.3 相关proc参数调优

/proc/sys/kernel/sched_latency_ns        # 调度延迟 (默认6000000ns)
/proc/sys/kernel/sched_min_granularity_ns # 最小粒度 (默认750000ns)
/proc/sys/kernel/sched_wakeup_granularity_ns # 唤醒抢占粒度 (默认1000000ns)
/proc/sys/kernel/sched_migration_cost_ns # 进程迁移开销估算 (默认500000ns)

对于桌面交互场景，可以适当减小sched_latency_ns提升响应性；对于服务器吞吐场景，增大它可以减少切换开销。

五、唤醒抢占机制

新进程被唤醒（从阻塞状态变为可运行）时，CFS需要判断是否应该立即抢占当前进程。这是平衡响应性和系统吞吐的关键点。

5.1 check_preempt_curr()唤醒抢占检查

// 简化逻辑
void check_preempt_curr(struct rq *rq, struct task_struct *p, int 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);
    
    // 如果新唤醒的vruntime比当前进程小超过wakeup_granularity
    if (delta_exec(se, pse) > sysctl_sched_wakeup_granularity) {
        // 允许抢占
    } else {
        // 不抢占，避免频繁切换
    }
}

5.2 唤醒时的vruntime补偿

长时间睡眠的进程vruntime远小于当前运行进程，如果直接参与调度会导致其他进程被"饿死"。CFS通过在place_entity()中对唤醒进程的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 = min_vruntime
        vruntime += sched_vslice(cfs_rq, se);
    else          // 唤醒进程补偿：vruntime最小不低于min_vruntime - latency
        vruntime -= sysctl_sched_latency;
    
    se->vruntime = max_vruntime(se->vrruntime, vruntime);
}

这个机制轻微惩罚了睡眠进程，但避免了长时间睡眠进程醒来后大量抢占CPU的异常行为。

六、组调度与cgroup支持

CFS通过组调度（Group Scheduling）机制实现了cgroup对CPU资源的限制与分配，这是容器化基础设施的根基。

6.1 层次化调度模型

                        cfs_rq (根)
                       /           \
                  cgroup A          cgroup B
                 /       \          /       \
              task1    task2    task3     task4
              
每个层级都有自己的cfs_rq和红黑树
层间调度和层内调度使用相同的CFS算法

组调度的核心思想是：先在不同cgroup之间执行CFS调度（按组的总vruntime比较），然后在选中的cgroup内部再对组内进程执行CFS调度。这种层级嵌套保证了组间公平和组内公平的统一。

6.2 cpu.shares——组间比例分配

通过cgroup的cpu.shares文件控制不同cgroup的CPU份额比例：

# 创建两个cgroup
mkdir /sys/fs/cgroup/cpu/group_a
mkdir /sys/fs/cgroup/cpu/group_b

# 设置份额比例（默认1024）
echo 2048 > /sys/fs/cgroup/cpu/group_a/cpu.shares  # 获得2/3 CPU
echo 1024 > /sys/fs/cgroup/cpu/group_b/cpu.shares  # 获得1/3 CPU

# 将进程加入对应cgroup
echo $PID_A > /sys/fs/cgroup/cpu/group_a/cgroup.procs
echo $PID_B > /sys/fs/cgroup/cpu/group_b/cgroup.procs

6.3 cpu.cfs_quota_us——绝对带宽限制

cgroup v1使用cpu.cfs_period_us和cpu.cfs_quota_us实现硬性的CPU使用上限：

# 限制该cgroup在100ms周期内最多使用50ms（即半个CPU核）
echo 100000 > /sys/fs/cgroup/cpu/group_a/cpu.cfs_period_us
echo 50000 > /sys/fs/cgroup/cpu/group_a/cpu.cfs_quota_us

# 多核限制：quota = period × 核数
# 例如限制使用2个核：quota=200000, period=100000

cgroup v2使用cpu.max以更简洁的方式表达相同的限制。

6.4 CPU带宽控制实现原理

cfs_bandwidth机制跟踪每个cgroup内的CPU使用时间，当quota耗尽时将组内所有进程从CFS运行队列中"解挂"（dequeue），直到下一个period恢复quota。关键函数throttle_cfs_rq()和unthrottle_cfs_rq()分别完成这两个操作，通过hrtimer在period切换时自动恢复。

CPU0  CPU1  |  CPU2  CPU3
MC domain (SMT)  MC domain
\         /       \         /
LLC domain (LLC)  LLC domain
  \                /
   DIE domain (NUMA node)
   \              /
    NODE domain (全局)

stop_sched_class      → 最高优先级（停止任务，用于CPU热插迁等）
dl_sched_class         → 截止期限调度（SCHED_DEADLINE，EDF算法）
rt_sched_class         → 实时调度（SCHED_FIFO/SCHED_RR）
fair_sched_class       → CFS（SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE）
idle_sched_class       → 最低优先级（无任务时运行idle进程）

# 查看进程的实际运行时间和被抢占次数
cat /proc/[pid]/sched

# 示例输出（关键字段）：
se.vruntime                    :              1234567.8901234
se.sum_exec_runtime            :              98765.4321000 (纳秒)
nr_switches                    :              15234
nr_voluntary_switches          :              14900  (主动放弃CPU)
nr_involuntary_switches        :              334    (被抢占)
se.load.weight                 :              1024
policy                         :              0       (SCHED_NORMAL)
prio                           :              120     (nice 0)

# 记录调度事件（捕获调度切换上下文）
perf sched record -a sleep 5

# 生成调度时间线
perf sched latency --sort max

# 输出示例：
 Task              |   Average waiting-time | Max waiting-time
 systemd           |       12.345 ms        |   89.012 ms
 kworker/0:1       |        5.678 ms        |   45.678 ms
 chrome             |       15.123 ms        |  234.567 ms  ← 响应延迟高

# 映射调度事件延迟分布
perf sched map

# 可视化调度延迟热图
perf sched timehist

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

# 输出示例（每个CPU一行）：
cpu0 0 0 123456789 98765432 12345 67890 1234 567 12 3 0
#   ^----运行延迟贡献--^ ^--等待时间贡献--^
#        ^-调度尝试 ^-运行进程数 ^-时间片和等待时间

# 追踪调度器决策过程
cd /sys/kernel/debug/tracing
echo sched_switch > set_event
echo sched_wakeup > set_event
echo sched_migrate_task > set_event
echo 1 > tracing_on

# 查看追踪结果（在另一个终端）
cat trace | head -50

# 使用trace-cmd进行更高级的记录
trace-cmd start -e sched_switch -e sched_wakeup -e sched_migrate_task
sleep 5
trace-cmd stop
trace-cmd show | less

# 将进程绑定到特定CPU（利用缓存局部性）
taskset -c 0,2 ./my_program

# 或使用CPU列表（逗号分隔范围）
taskset -c 0-3,8-11 ./my_program

# cgroup方式绑定CPU
echo "0-3" > /sys/fs/cgroup/mygroup/cpuset.cpus
echo "0" > /sys/fs/cgroup/mygroup/cpuset.mems

# 减小调度延迟（更快切换 = 更流畅的UI）
echo 3000000 > /proc/sys/kernel/sched_latency_ns
echo 375000 > /proc/sys/kernel/sched_min_granularity_ns

# 增强唤醒抢占（UI事件更多更早地响应）
echo 4000000 > /proc/sys/kernel/sched_wakeup_granularity_ns

# 扩大调度周期（减少上下文切换开销）
echo 24000000 > /proc/sys/kernel/sched_latency_ns
echo 3000000 > /proc/sys/kernel/sched_min_granularity_ns

# 减少唤醒抢占（让批处理任务完成当前工作）
echo 15000000 > /proc/sys/kernel/sched_wakeup_granularity_ns

# 使用SCHED_DEADLINE确保实时任务
# 使用cgroup限制普通任务的CPU带宽
mkdir /sys/fs/cgroup/cpu/realtime
echo 100000 > /sys/fs/cgroup/cpu/realtime/cpu.cfs_period_us
echo 80000 > /sys/fs/cgroup/cpu/realtime/cpu.cfs_quota_us  # 最多80% CPU

mkdir /sys/fs/cgroup/cpu/batch
echo 100000 > /sys/fs/cgroup/cpu/batch/cpu.cfs_period_us
echo 20000 > /sys/fs/cgroup/cpu/batch/cpu.cfs_quota_us    # 最多20% CPU

# CPU request（对应cpu.shares）
# request.cpu = "100m" → cpu.shares = 1024 × (0.1 / 1.0) = 102.4 ≈ 102

# CPU limit（对应cpu.cfs_quota_us/cfs_period_us）
# limit.cpu = "500m" → quota = 50000, period = 100000

# Guaranteed QoS: request == limit
# Burstable QoS: request < limit
# BestEffort QoS: 无request/limit

# 1. 查看是否有大量进程竞争CPU
top -bn1 | grep "Cpu"
top -bn1 -o %CPU | head -20

# 2. 检查交互式进程的等待延迟
perf sched record -a sleep 3
perf sched latency --sort max | head -10

# 3. 查看是否有高优先级实时进程占用CPU
ps -eo pid,comm,pri,rtprio | grep -v " -"

# 4. 检查cgroup是否限制了CPU
cat /sys/fs/cgroup/cpu/user.slice/cpu.stat

# 查看上下文切换统计
vmstat 1 5
# 关注cs列（context switches per second）

# 如果cs > 50000/s，可能调度粒度太小
# 或使用perf查找频繁切换的原因
perf stat -e context-switches,cpu-migrations -a sleep 5

# 检查是否有过多唤醒事件
perf record -e sched:sched_wakeup -a sleep 3
perf report --sort=comm

# 查看NUMA节点内存分配
numastat -m
numastat -p [pid]

# 开启自动NUMA均衡
echo 1 > /proc/sys/kernel/numa_balancing

# 或使用numactl进行进程绑定
numactl --cpunodebind=0 --membind=0 ./my_program