2. Linux调度器基础：CFS调度器原理、调度实体与运行队列、调度类与调度策略

调度器是Linux内核最核心的组件之一，它决定了哪个进程在何时获得CPU执行权。本章深入剖析完全公平调度器（CFS）的设计原理、调度实体与运行队列的组织结构，以及调度类与调度策略的层次关系。理解这些基础是分析调度延迟、优化交互性能的前提。

2.1 CFS调度器核心原理

CFS（Completely Fair Scheduler）自Linux 2.6.23引入，取代了O(1)调度器。其设计哲学是：为每个进程分配CPU时间的“公平”比例，而非追求绝对的公平时间片。CFS使用红黑树（Red-Black Tree）来管理可运行进程，以vruntime（虚拟运行时间）作为排序键值。

2.1.1 vruntime与权重

vruntime是CFS的核心度量，它记录了进程的虚拟运行时间。实际运行时间通过进程权重（weight）转换为vruntime，公式如下：

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

其中NICE_0_LOAD是nice值为0时的基准权重（1024）。权重越高（优先级越高），vruntime增长越慢，从而获得更多CPU时间。

2.1.2 调度延迟与最小粒度

CFS引入了两个关键参数来控制调度行为：

• 调度延迟（sysctl_sched_latency）：默认6ms（可配置），表示CFS保证所有可运行进程在一个周期内至少被调度一次的目标延迟。
• 最小粒度（sysctl_sched_min_granularity）：默认0.75ms，防止进程切换过于频繁，导致上下文切换开销过大。

当可运行进程数量增多时，CFS会动态调整时间片：时间片 = max(最小粒度, 调度延迟 / 进程数)。这保证了在进程数较少时，调度延迟可控；进程数较多时，避免时间片过小。

2.2 调度实体与运行队列

调度实体（struct sched_entity）是CFS调度的基本单位，它嵌入在task_struct中，代表一个可被调度的任务（进程或线程）。运行队列（struct cfs_rq）则管理着同一调度类下的所有可运行调度实体。

2.2.1 调度实体结构

调度实体包含CFS调度所需的核心字段：

struct sched_entity {
    struct load_weight      load;           // 进程权重
    struct rb_node          run_node;       // 红黑树节点
    struct list_head        group_node;     // 组调度链表节点
    unsigned int            on_rq;          // 是否在运行队列中
    u64                     vruntime;       // 虚拟运行时间
    u64                     prev_sum_exec_runtime; // 上次调度时的总执行时间
    u64                     sum_exec_runtime;      // 总执行时间
    struct sched_statistics statistics;     // 调度统计信息
};

2.2.2 运行队列与红黑树

每个CPU都有一个独立的cfs_rq，管理该CPU上所有CFS调度类的可运行进程。红黑树是cfs_rq的核心数据结构：

• 插入：进程变为可运行时，根据其vruntime插入红黑树。
• 选择：始终选择最左侧节点（vruntime最小）作为下一个运行进程。
• 更新：时钟中断或进程切换时，更新当前进程的vruntime，并可能触发红黑树的重新平衡。

2.3 调度类与调度策略

Linux内核使用调度类（sched_class）实现可扩展的调度架构。每个调度类实现一组统一的调度接口，内核通过pick_next_task等函数按优先级遍历调度类，选择下一个运行的任务。

2.3.1 调度类层次

内核定义了5个调度类，按优先级从高到低排列：

2.3.2 调度策略详解

用户态通过sched_setscheduler()系统调用为进程设置调度策略。不同策略对应不同的调度类和行为：

• SCHED_NORMAL（SCHED_OTHER）：默认策略，使用CFS调度类。基于vruntime公平分配CPU时间，适合大多数应用。
• SCHED_BATCH：类似SCHED_NORMAL，但调度器会假设进程是CPU密集型的，减少唤醒抢占，适合批处理任务。
• SCHED_IDLE：极低优先级，仅在CPU空闲时运行，适合后台低优先级任务。
• SCHED_FIFO：实时先进先出策略。一旦获得CPU，除非主动让出或被更高优先级实时任务抢占，否则一直运行。
• SCHED_RR：实时轮转策略。类似SCHED_FIFO，但增加了时间片限制，时间片用完后同优先级任务轮转。
• SCHED_DEADLINE：基于Earliest Deadline First（EDF）算法，为任务指定运行周期、执行时间和截止时间，适合硬实时场景。

2.4 调度延迟的关键影响因素

从CFS调度器原理出发，调度延迟（即进程从可运行到实际获得CPU的时间）受以下因素影响：

• 运行队列长度：进程数越多，每个进程的时间片越小，但调度延迟可能因排队而增加。
• 进程优先级（nice值）：高优先级进程（低nice值）的vruntime增长慢，更容易被选中，调度延迟更低。
• 调度类抢占：实时调度类（SCHED_FIFO/RR）的进程会抢占CFS进程，导致普通进程的调度延迟不可预测。
• CPU负载均衡：当某个CPU过载而其他CPU空闲时，负载均衡会迁移进程，迁移过程可能引入额外延迟。
• 内核抢占点：CFS的调度决策发生在时钟中断、进程唤醒、系统调用返回等抢占点。抢占点密度影响调度响应的及时性。