2. Linux标准内核调度器：CFS调度器原理、O(1)调度器回顾、调度类与调度策略

在深入实时化改造之前，必须透彻理解Linux标准内核的调度体系。本章从历史演进出发，回顾O(1)调度器的设计动机与局限，然后重点剖析当前完全公平调度器（CFS）的核心原理，最后梳理调度类与调度策略的层次关系。这些知识是理解PREEMPT_RT补丁为何以及如何改造调度器的基石。

2.1 调度器演进：从O(1)到CFS

Linux内核调度器经历了三个主要阶段：早期的O(n)调度器（2.4内核及之前）、O(1)调度器（2.6.0~2.6.22）以及完全公平调度器CFS（2.6.23至今）。O(1)调度器解决了O(n)在大负载下的性能瓶颈，但其交互式优化策略复杂且难以预测。

O(1)调度器的主要问题在于交互性启发式算法过于复杂，导致调度行为难以预测，且在高负载下交互式进程可能被误判。CFS调度器彻底放弃了固定时间片和优先级队列的设计，转而采用基于虚拟运行时间（vruntime）的红黑树模型。

2.2 CFS调度器核心原理

CFS（Completely Fair Scheduler）由Con Kolivas开发，于内核2.6.23合入主线。其核心思想是模拟“理想的多任务处理器”——假设一个CPU可以同时运行所有任务，每个任务获得1/N的CPU时间。CFS通过红黑树维护就绪队列，选择vruntime最小的进程运行。

2.2.1 vruntime与权重

vruntime是CFS的核心度量，表示进程的虚拟运行时间。其计算考虑了进程的优先级权重：

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

其中NICE_0_LOAD是nice值为0时的基准权重（1024）。权重表由内核预计算，nice值每降低1（优先级提升），权重约增加10%。

2.2.2 调度粒度与延迟目标

CFS引入了调度延迟（sched_latency）和最小粒度（min_granularity）两个参数来控制调度频率：

• 调度延迟（sysctl_sched_latency）：默认6ms，表示CFS保证每个就绪进程在6ms内至少获得一次运行机会。
• 最小粒度（sysctl_sched_min_granularity）：默认0.75ms，进程一次运行的最短时间，防止过于频繁的上下文切换。
• 时间片计算：当就绪进程数N较小时，时间片 = sched_latency / N；当N较大时，时间片固定为min_granularity。

2.3 调度类与调度策略

Linux内核使用调度类（sched_class）实现多态调度架构。每个调度类实现一组统一的接口（如enqueue_task、dequeue_task、pick_next_task等），内核在调度时按优先级顺序遍历调度类，选择最高优先级的任务。

2.3.1 SCHED_OTHER（普通分时调度）

SCHED_OTHER是默认调度策略，映射到fair_sched_class，由CFS管理。适用于大多数用户态进程，强调公平性和交互响应。进程优先级通过nice值调整（-20~19），nice值越低，获得的CPU时间比例越高。

2.3.2 SCHED_FIFO（先进先出实时调度）

SCHED_FIFO是POSIX实时调度策略之一，映射到rt_sched_class。其核心特性：

• 静态优先级：范围1~99（数值越大优先级越高），优先级一旦设定不会动态调整。
• 运行规则：SCHED_FIFO进程会一直运行，直到被更高优先级的实时进程抢占、主动睡眠（如等待I/O）、或调用sched_yield()主动让出CPU。
• 无时间片：相同优先级的SCHED_FIFO进程之间不会自动轮转，除非高优先级进程阻塞，否则低优先级进程无法运行。
• 优先级继承：当实时进程持有互斥锁时，如果被低优先级进程阻塞，内核通过优先级继承协议临时提升阻塞进程的优先级，防止优先级反转。

2.3.3 SCHED_RR（时间片轮转实时调度）

SCHED_RR与SCHED_FIFO共享相同的优先级空间（1~99），但增加了时间片轮转机制：

• 时间片：相同优先级的SCHED_RR进程按时间片轮转执行，默认时间片为100ms（可通过sched_rr_get_interval()查询）。
• 自动让出：当进程用尽时间片，被移到同优先级队列的尾部，调度器选择下一个同优先级进程运行。
• 优先级抢占：高优先级的SCHED_RR或SCHED_FIFO进程仍然可以抢占低优先级的SCHED_RR进程。

2.4 调度类与调度策略的交互机制

内核调度器的主入口是__schedule()函数，它按照以下顺序遍历调度类：

// 简化后的调度主路径
static void __schedule(unsigned int sched_mode)
{
    struct task_struct *prev, *next;
    struct rq *rq;
    int cpu;

    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr;

    // 1. 检查是否需要抢占当前进程
    // 2. 按优先级顺序遍历调度类，选择下一个任务
    next = pick_next_task(rq, prev, sched_mode);
    // 3. 如果next != prev，执行上下文切换
    context_switch(rq, prev, next);
}

// pick_next_task 遍历调度类
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, unsigned int sched_mode)
{
    const struct sched_class *class;
    struct task_struct *p;

    // 优化路径：如果所有任务都是fair_sched_class，直接调用CFS
    // 否则按优先级顺序遍历
    for_each_class(class) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
    }
    // 如果没有可运行任务，返回idle任务
    return rq->idle;
}

2.5 标准内核调度器对实时性的限制

尽管标准内核提供了SCHED_FIFO和SCHED_RR实时调度策略，但其实时能力仍然受到以下根本性限制：

• 内核抢占点不足：标准内核是自愿抢占（voluntary preemption）模型，内核态代码只有在明确的抢占点（如系统调用返回、中断返回、显式调用schedule()）才能被抢占。这意味着实时进程无法立即抢占正在执行内核代码的非实时进程。
• 中断关闭区域：内核中存在大量使用local_irq_disable()/local_irq_save()的临界区，在这些区域内，即使是最高优先级的实时任务也无法响应中断和调度。
• 自旋锁持有期间不可抢占：持有自旋锁的代码路径不能被调度，导致优先级反转问题在标准内核中难以完全解决。
• 中断线程化缺失：标准内核的中断处理程序运行在中断上下文，优先级高于任何进程，且不可被调度。这导致中断处理延迟不可控，且中断处理程序无法使用阻塞操作。