深入理解Linux内核CFS调度器：完全公平调度算法全解析

一、调度器概述

Linux内核的进程调度器是操作系统的核心组件之一，它负责决定哪个进程在何时获得CPU时间。从早期的O(n)调度器到O(1)调度器，直至目前广泛使用的CFS（Completely Fair Scheduler，完全公平调度器），Linux调度算法经历了深刻的演进。

CFS由Ingo Molnar在2007年引入内核2.6.23版本，其核心理念的革命性之处在于：CFS不再跟踪传统的sleep/run状态，而是直接建模一个"理想多任务处理器"——它假设如果有N个可运行进程，那么每个进程应该获得1/N的CPU时间。

1.1 调度对象与调度类

Linux调度器采用调度类（sched_class）的层次化架构：

stop_sched_class      (最高优先级，停机调度类)
dl_sched_class        (限期调度类，SCHED_DEADLINE)
rt_sched_class        (实时调度类，SCHED_FIFO/SCHED_RR)
fair_sched_class      (公平调度类，SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE)
idle_sched_class      (最低优先级，空闲调度类)

每个调度类通过一系列回调函数注册到内核中，形成链表。调度器自上而下遍历各调度类，首先检查高优先级类中是否有可运行任务。

CFS主要服务于SCHED_NORMAL（普通分时进程）和SCHED_BATCH（后台批处理进程），是桌面和服务器系统中最重要的调度策略。

1.2 关键数据结构

struct sched_entity {
    struct load_weight  load;        // 调度实体的权重
    struct rb_node      run_node;    // 红黑树节点
    struct list_head    group_node;  // 组调度链表
    u64                 vruntime;     // 虚拟运行时
    u64                 exec_start;   // 本次执行开始时间
    u64                 sum_exec_runtime;  // 累计运行时间
    u64                 prev_sum_exec_runtime; // 上次切换前的累计时间
    u64                 nr_migrations; // 迁移次数
};

struct cfs_rq {
    struct load_weight  load;        // 队列总权重
    unsigned long       nr_running;  // 可运行进程数
    u64                 min_vruntime; // 队列最小vruntime
    struct rb_root      tasks_timeline; // 红黑树根
    struct rb_node      *rb_leftmost;  // 最左节点缓存
    struct sched_entity *curr;       // 当前运行实体
    struct rq           *rq;         // 关联的运行队列
};

二、虚拟运行时（vruntime）：CFS的核心

2.1 概念与公式

虚拟运行时（Virtual Runtime） 是CFS的灵魂。它度量了每个进程"应该已经运行了多久"（如果运行在理想多任务处理器上）。核心公式如下：

delta_exec = current->sum_exec_runtime - current->prev_sum_exec_runtime
delta_exec_weighted = delta_exec * NICE_0_LOAD / current->load.weight
current->vruntime += delta_exec_weighted

其中NICE_0_LOAD是nice值为0时的权重（1024）。nice值每降低1级（优先级提高），权重增加约25%；每升高1级，权重减少约20%。

2.2 权重表

内核预定义了nice值与权重的映射表：

static const int 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值-20的权重约为nice值19的58倍，这意味着高优先级进程的vruntime增长更慢，从而更频繁地被调度。

2.3 何时更新vruntime

vruntime在以下时机更新：

三、红黑树：调度数据结构

3.1 为什么使用红黑树

CFS选择红黑树（rbtree）作为调度队列的数据结构，原因在于：

CFS并不跟踪sleep和run状态，而是将所有可运行进程维护在一棵以vruntime为key的红黑树中：

          [vruntime=50]
          /          \
   [vruntime=30]   [vruntime=80]
      /    \            \
[vruntime=15] [vruntime=42]  [vruntime=100]

3.2 最左节点优化

CFS缓存了红黑树的最左节点（cfs_rq->rb_leftmost），这使得选取下一个要运行的进程变为O(1)操作：

static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq)
{
    return cfs_rq->rb_leftmost;
}

仅在最左节点被移除后，才需要O(log n)更新rb_leftmost指针。

3.3 enqueue与dequeue

static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    // 如果是唤醒而来的，补偿vruntime（防止饥饿）
    if (flags & ENQUEUE_WAKEUP)
        place_entity(cfs_rq, se, 0);
    
    update_curr(cfs_rq);
    account_entity_enqueue(cfs_rq, se);
    if (flags & ENQUEUE_WAKEUP)
        place_entity(cfs_rq, se, 0);
    
    // 插入红黑树
    __enqueue_entity(cfs_rq, se);
    update_load_avg(cfs_rq, se, UPDATE_TG);
    
    // 如果新节点成为最左节点，设置抢占
    if (leftmost)
        resched_curr(rq_of(cfs_rq));
}

四、调度时机与抢占

4.1 调度时机

CFS在以下情况下触发调度：

4.2 时间片分配

CFS没有传统意义上的"固定时间片"。 sched_period（调度周期）默认为6ms（当运行进程数<=8时，否则为0.75ms * nr_running）：

static u64 sched_period(int nr_running)
{
    if (nr_running > 8)
        return sysctl_sched_latency * nr_running / 8;
    return sysctl_sched_latency;
}

每个进程获得的时间片为：

time_slice = sched_period / nr_running * (se->load.weight / cfs_rq->load.weight)

这意味着：进程数少时每个进程获得更长时间片（减少上下文切换开销），进程多时缩短时间片以提高响应性。

4.3 最小粒度（sched_min_granularity）

为防止过度切换开销，CFS定义了一个最小时间粒度（默认0.75ms）。这意味着即使在高负载场景下，进程也至少运行这么长时间才能被抢占。当：

sysctl_sched_wakeup_granularity > sysctl_sched_latency / nr_running

新唤醒的进程必须等待更长时间才能抢占当前进程，以避免过度频繁的唤醒抢占。

五、唤醒抢占与补偿机制

5.1 place_entity补偿策略

当一个睡眠进程被唤醒时，如果直接以当前vruntime插入红黑树，它将排在极右位置——因为长时间睡眠使其vruntime远远落后于其他进程。这会导致刚唤醒的进程长时间得不到调度（饥饿）。

CFS的解决方案是将唤醒进程的vruntime设置为(cfs_rq->min_vruntime - thresh)，其中thresh默认为sysctl_sched_latency（对低优先级进程再减半）：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;
    
    if (initial) // 新进程给予额外延迟
        vruntime += sched_vslice_add(cfs_rq, se);
    else {
        // 补偿：给予一个时间片的偏移
        vruntime -= sysctl_sched_latency;
        
        // 低优先级进程补偿更多（公平性考虑）
        if (!task_policy(se, SCHED_NORMAL) || task_nice(se) > 0)
            vruntime <<= 1;
    }
    
    // 确保不低于min_vruntime - 2*latency
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

这种设计巧妙地平衡了两个目标：既不让睡眠进程过度抢占（限制偏移量），又防止它被严重不公平地惩罚。

5.2 唤醒抢占条件

新唤醒的进程在满足以下条件时会立即抢占当前进程：

static int 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(curr, se);
    if (vdiff > gran)
        return 1;   // 差距超过粒度阈值，允许抢占
    
    return 0;       // 不抢占
}

六、CFS组调度

6.1 组调度的动机

系统管理员经常需要对一组进程（如一个用户的全部进程，或一个容器中的进程）进行CPU资源配额限制。传统Unix分组基于rlimit或nice值，粒度不足。CFS组调度通过将每个用户/组映射到一个调度实体，实现了组间公平。

6.2 组调度架构

全局CFS RQ
├── 用户A的CFS RQ (weight=512)
│   ├── Task A1 (weight=1024) → vruntime
│   ├── Task A2 (weight=512)  → vruntime
│   └── ...
├── 用户B的CFS RQ (weight=512)
│   ├── Task B1 (weight=1024) → vruntime
│   └── ...
└── 未分组Task (weight=1024)   → vruntime

两个用户之间按照权重分配CPU，每个用户内部再按照子任务的vruntime公平分配。

6.3 通过cgroup配置

# 创建cgroup
mkdir /sys/fs/cgroup/cpu/group_a
echo 512 > /sys/fs/cgroup/cpu/group_a/cpu.shares

# 限制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  # 限制到0.5核

# 将进程移入组
echo $PID > /sys/fs/cgroup/cpu/group_a/tasks

七、NUMA感知与负载均衡

7.1 NUMA拓扑的影响

在多处理器系统中，内存访问存在NUMA（非统一内存访问）特性：访问"远端"内存的延迟可能是本地内存的2-3倍。CFS的负载均衡器需要考虑NUMA拓扑，尽量在本地节点内寻找空闲CPU。

7.2 负载均衡策略

Linux的调度域（sched_domain）定义了一个层次化负载均衡系统：

DIE (物理芯片)
├── MC (多核层)  
│   └── SMT (超线程层)
└── ...

当负载均衡器发现空闲CPU时，按照以下域的优先级处理：

SMT域 → MC域 → DIE域 → NUMA域 → ALLDOMAINS

八、CFS与实时调度器的协同

8.1 抢占优先级链表

当实时进程变为可运行时，它会无条件抢占CFS管理的普通进程。内核通过sched_class链表保证这一点：

for_each_class(class) {
    next = class->pick_next_task(rq, prev, rf);
    if (next)
        return next;
}

实时调度类（rt_sched_class）排在fair_sched_class之前，因此只要rt_rq中有可运行进程，就永远不会轮到CFS。

8.2 RT throttling

为了防止实时进程完全饿死CFS进程，内核默认保留了5%的CPU时间给非RT进程：

/proc/sys/kernel/sched_rt_period_us = 1000000 (1秒)
/proc/sys/kernel/sched_rt_runtime_us = 950000  (可用950ms)

超过配额后，即使有RT进程也不允许抢占，直到下一周期开始。

九、实践调优

9.1 关键sysctl参数

| 参数 | 默认值 | 含义 |

|------|--------|------|

| sched_latency_ns | 24000000 (24ms) | 调度周期基准 |

| sched_min_granularity_ns | 3000000 (3ms) | 最小运行时间 |

| sched_wakeup_granularity_ns | 4000000 (4ms) | 唤醒抢占阈值 |

| sched_migration_cost_ns | 500000 (0.5ms) | 迁移缓存热阈值 |

9.2 服务器场景调优

对于延迟敏感的数据库服务：

sysctl -w kernel.sched_min_granularity_ns=10000000
sysctl -w kernel.sched_wakeup_granularity_ns=15000000

对于高吞吐批处理场景（减少切换开销）：

sysctl -w kernel.sched_min_granularity_ns=1000000
sysctl -w kernel.sched_latency_ns=12000000

9.3 性能分析工具

# 查看进程调度统计
cat /proc/<PID>/sched

# 使用perf跟踪调度事件
perf sched record -a sleep 10
perf sched latency

# 查看调度器分布
cat /proc/schedstat

十、总结

CFS通过虚拟运行时和红黑树这一精妙组合，在不跟踪时间片的条件下实现了近似完全公平的调度。其关键设计思想：

从2007年至今，CFS虽有持续改进（如EEVDF提案），但其核心vruntime + 红黑树的设计哲学始终是Linux调度器的基石。理解CFS是深入Linux性能优化和实时系统开发的必经之路。