📚 课程目录第1章调度器概述

Linux内核进程调度器runqueue就绪队列深度解析 - 第1节

1.1 Linux调度器发展历史

Linux内核调度器经历了从简单到复杂、从低效到高效的演进过程。理解这段历史有助于把握当前CFS调度器的设计取舍。下表总结了三个主要阶段的对比：

版本	内核版本	时间复杂度	核心数据结构	主要问题
O(n)调度器	Linux 2.4及之前	O(n)	全局链表	多核扩展性差、交互体验不佳
O(1)调度器	Linux 2.6.0~2.6.22	O(1)	140个优先级位图+数组	交互进程响应不够平滑、调参复杂
CFS调度器	Linux 2.6.23至今	O(log n)	红黑树	——（当前标准）

1.1.1 O(n)调度器：简单但低效

早期Linux使用基于全局循环链表的调度器。每次调度时，内核需要遍历所有就绪进程，计算每个进程的优先级动态修正值，选择“最好”的进程执行。

性能瓶颈：当系统中存在1000个进程时，每次调度都需要扫描整个链表，时间复杂度为O(n)。多核处理器下，全局链表成为锁竞争热点，扩展性极差。

/* O(n)调度器核心选择逻辑（简化示意） */
for_each_process(p) {
    goodness = p->counter + p->priority;
    if (goodness > best_goodness) {
        best_goodness = goodness;
        next = p;
    }
}

1.1.2 O(1)调度器：位图加速的里程碑

O(1)调度器由Ingo Molnár设计，引入优先级位图和双数组结构（active/expired），将调度决策时间降为常数级。每个CPU维护独立的运行队列，大幅提升多核性能。

设计亮点：使用find_first_bit()位图操作在140个优先级中快速定位最高优先级队列，时间复杂度恒定为O(1)，不受进程数量影响。

/* O(1)调度器优先级位图查找（简化） */
struct prio_array {
    unsigned long bitmap[BITMAP_SIZE];  /* 140位位图 */
    struct list_head queue[MAX_PRIO];   /* 140个链表 */
};

/* 查找最高优先级非空队列 */
idx = sched_find_first_bit(array->bitmap);
next = list_entry(array->queue[idx].next, task_t, run_list);

然而O(1)调度器存在交互进程识别不准的问题，导致桌面响应出现“卡顿”或“抖动”，最终被CFS取代。

1.1.3 CFS调度器：公平与效率的统一

CFS（Completely Fair Scheduler）由Con Kolivas的楼梯调度器和RSDL启发，由Ingo Molnár在Linux 2.6.23中合入。它摒弃了固定时间片和优先级数组，改用红黑树组织就绪队列，以虚拟运行时间（vruntime）作为调度依据。

  核心思想：CFS模拟“理想多任务处理器”——假设一个CPU能同时运行所有进程，每个进程获得1/N的CPU时间。实际调度时，选择vruntime最小的进程执行，使所有进程的vruntime尽可能接近。

/* CFS调度器核心选择逻辑（简化） */
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;
    struct sched_entity *se = rb_entry(left, struct sched_entity, run_node);
    return se;  /* 红黑树最左节点 = vruntime最小 */
}

1.2 调度器核心目标与设计哲学

无论调度器如何演进，其核心目标始终围绕以下三个维度展开。CFS的设计哲学正是对这些目标的重新诠释和平衡。

1.2.1 三大核心目标

目标	定义	CFS实现方式	衡量指标
公平性	每个进程获得与其权重成比例的CPU时间	vruntime单调递增，红黑树保证最小vruntime优先	最大vruntime差距 < sysctl_sched_latency
吞吐量	单位时间内完成的工作量最大化	调度粒度（min_granularity）防止频繁切换	上下文切换次数/秒
响应延迟	交互进程从就绪到获得CPU的时间最小化	唤醒抢占、nice值映射到权重	调度延迟 < 4ms（桌面场景）

设计哲学：CFS不追求“最优”而追求“足够好”。它通过权重分配（而非固定优先级）实现公平，通过调度粒度控制平衡吞吐与延迟，通过唤醒抢占保证交互响应。

1.2.2 CFS设计哲学：完全公平的数学建模

CFS将调度问题抽象为：在时间区间[0, T]内，N个进程应各自获得T/N的CPU时间。实际运行时，进程可能因I/O阻塞、睡眠等原因未用完时间片，CFS通过虚拟运行时间记录每个进程的“已消耗CPU时间”，并选择消耗最少的进程运行。

/* vruntime更新核心公式 */
vruntime += delta_exec * (NICE_0_LOAD / se->load.weight);

/* 其中：
 * delta_exec  —— 实际执行时间（ns）
 * NICE_0_LOAD —— nice=0时的权重（1024）
 * load.weight —— 当前进程的权重（由nice值映射）
 */

权重映射表（部分）：

nice值	权重（weight）	CPU占比（相对nice=0）
-20	88761	约86.7倍
-10	9548	约9.3倍
0	1024	1倍（基准）
10	110	约0.11倍
19	15	约0.015倍

1.2.3 调度类与调度策略

Linux内核通过调度类（sched_class）实现多态调度，CFS是其中之一。每个进程关联一个调度策略，决定其所属的调度类：

调度类	调度策略	优先级范围	典型用途
stop_sched_class	——	最高（内核内部）	CPU停止、热插拔
dl_sched_class	SCHED_DEADLINE	实时（0~99）	硬实时任务
rt_sched_class	SCHED_FIFO / SCHED_RR	实时（0~99）	软实时任务
fair_sched_class	SCHED_NORMAL / SCHED_BATCH	普通（100~139）	普通进程、批处理
idle_sched_class	SCHED_IDLE	最低	低优先级后台任务

  重点理解：CFS只负责fair_sched_class（即SCHED_NORMAL/SCHED_BATCH策略）的调度。实时进程由rt_sched_class处理，优先级高于CFS。当系统中存在实时进程时，CFS进程只有在实时进程阻塞后才有机会运行。

1.2.4 调度器核心数据结构关系

每个CPU维护一个运行队列（struct rq），其中包含多个调度类的子队列。CFS对应的子队列是struct cfs_rq，其核心是红黑树根节点和调度实体链表。

/* 每个CPU的运行队列结构（简化） */
struct rq {
    struct cfs_rq    cfs;        /* CFS就绪队列 */
    struct rt_rq     rt;         /* 实时就绪队列 */
    struct dl_rq     dl;         /* Deadline就绪队列 */
    struct task_struct *curr;    /* 当前正在运行的进程 */
    u64              nr_running; /* 就绪进程总数 */
    u64              nr_switches;/* 上下文切换计数 */
};

/* CFS就绪队列核心字段（简化） */
struct cfs_rq {
    struct rb_root   tasks_timeline;  /* 红黑树根节点 */
    struct rb_node   *rb_leftmost;    /* 最左节点（vruntime最小） */
    struct sched_entity *curr;        /* 当前正在运行的调度实体 */
    u64              min_vruntime;    /* 队列最小虚拟运行时间 */
    u64              nr_running;      /* 就绪实体数量 */
    u64              exec_clock;      /* 执行时钟 */
};