Linux 内核调度子系统剖析:策略、调度类与运行队列

Linux 内核调度子系统包含三个核心概念：调度策略、调度类与运行队列。本文用完整案例系统阐述其层次架构、状态迁移、优先级链式组织与 schedule() 执行流程。

1. 调度核心对象的分层抽象

Linux 内核调度子系统包含三个易混淆但层次分明的核心概念：调度策略（Scheduling Policy）、调度类（Scheduling Class）与运行队列（Run Queue）。三者构成用户接口、内核实现与数据容器之间的三层架构。

1.1 调度策略（用户态接口层）

调度策略是内核向用户进程暴露的调度语义接口，通过 sched_setscheduler() 系统调用设置。主要策略包括：

• SCHED_FIFO / SCHED_RR：实时调度策略，基于固定优先级与时间片轮转（RR）
• SCHED_DEADLINE：限期调度策略，基于最早截止时间优先（EDF）算法
• SCHED_NORMAL / SCHED_BATCH：普通调度策略，基于完全公平调度（CFS）算法
• SCHED_IDLE：优先级最低的普通调度策略，仅在系统空闲时获得 CPU 时间

注意：SCHED_IDLE 策略依然归属于 CFS 调度类（fair_sched_class），而非内核的 idle_sched_class。后者专用于每个 CPU 上的 PID=0 空闲线程，用户态进程无法与之关联。

1.2 调度类（内核实现层）

每个调度策略在内核中对应一个具体的调度类（struct sched_class），负责实现该策略的队列管理逻辑。调度类定义了一组标准操作函数指针：

• enqueue_task：将进程加入运行队列
• dequeue_task：将进程移出运行队列
• pick_next_task：从队列中选取下一个待执行的进程
• put_prev_task：将当前进程放回队列（抢占路径）
• task_tick：时钟滴答处理，用于时间片更新与抢占判断

策略与调度类的映射关系：

• SCHED_FIFO / SCHED_RR → rt_sched_class
• SCHED_DEADLINE → dl_sched_class
• SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE → fair_sched_class
• （内核空闲线程专用）→ idle_sched_class

1.3 运行队列（数据容器层）

运行队列（struct rq）是存放进程控制块（task_struct）指针的容器。内核为每个 CPU 核心独立维护一个 rq 实例，通过 cpu_rq(cpu) 宏获取，以实现缓存局部性并避免跨 CPU 锁竞争。每个 rq 内细分为各调度类的子队列：cfs_rq（红黑树）、rt_rq（优先级位图链表）等。

策略是申请，类是实现，队列是容器。

2. 运行队列的数据结构设计

2.1 Per-CPU 实例化

运行队列 struct rq 在系统初始化时为每个逻辑 CPU 分配独立内存空间。rq->nr_running 字段实时统计该 CPU 上处于可运行状态（TASK_RUNNING）的进程数量，是调度器进行负载均衡和 idle 判断的核心依据。

2.2 入队条件：仅限 TASK_RUNNING 状态

只有 TASK_RUNNING 的进程才会出现在 rq 里。其他状态——TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、TASK_STOPPED、EXIT_ZOMBIE——均不在 rq 中。

状态迁移驱动 enqueue/dequeue 操作：

• wake_up() → 置 TASK_RUNNING → enqueue_task() 入队
• 阻塞系统调用（read()、futex_wait()）→ dequeue_task() 出队 → 置非运行状态
• 被抢占（时间片耗尽）→ 保持 TASK_RUNNING 且不出队，仅 put_prev_task() 放回红黑树（实际按 vruntime 动态选择插入位置）

3. 调度类的优先级链式组织

内核中的调度类构成静态优先级的单向链表，按调度优先级从高到低排列：

stop_sched_class → dl_sched_class → rt_sched_class → fair_sched_class → idle_sched_class

pick_next_task() 从链表头部开始遍历，返回第一个 nr_running > 0 的调度类所选取的进程。这一设计保证了实时进程始终优先于普通进程获得 CPU 资源，idle 类仅在无任何可运行进程时接管。

4. 主调度入口函数 schedule() 的执行流程

所有抢占与主动调度最终均汇聚于 schedule()，其标准执行序列如下：

① 临界区保护：关闭本地中断并获取 rq->lock，防止并发修改。

② 当前进程（prev）的分类处理：

• 抢占路径（时间片耗尽）：调用 put_prev_task()，进程保持 TASK_RUNNING，不出队，仅放回调度类子队列。
• 阻塞路径（主动 sleep/futex_wait）：调用 dequeue_task()，进程彻底移出运行队列，状态改为 TASK_INTERRUPTIBLE。

③ 下一进程（next）的选择：调用 pick_next_task()，按 stop → dl → rt → fair → idle 顺序遍历调度类链表，返回优先级最高的可运行进程。

④ 原子更新当前进程指针：将 rq->curr 原子切换为 next。该操作在上下文切换之前完成，确保 NMI 或 perf 事件触发时能正确获取当前 task_struct 指针（配合 RCU 锁机制）。

⑤ 硬件上下文切换：switch_mm() 切换页表，switch_to() 切换内核栈与寄存器上下文，CPU 执行流转至 next。

⑥ 释放锁与恢复中断：rq->lock 解锁并开启本地中断，新进程开始运行。

5. 典型场景：阻塞 I/O 进程的全生命周期调度迁移

通过 cat 命令读取磁盘文件的完整过程串联上述机制：

阶段 1：进程创建与入队

bash 调用 fork() 创建子进程，内核分配 task_struct 并置状态为 TASK_RUNNING，调用 enqueue_task_fair() 将进程插入 cfs_rq 红黑树，nr_running 从 0 变为 1。

阶段 2：I/O 阻塞与出队

cat 执行 read()，页缓存无数据，内核调用 dequeue_task_fair() 将 cat 移出 cfs_rq，状态改为 TASK_INTERRUPTIBLE，挂入磁盘设备等待队列。nr_running 减至 0，pick_next_task() 返回 idle_sched_class 的空闲线程。

阶段 3：I/O 完成与唤醒入队

磁盘控制器发起中断，ISR 调用 try_to_wake_up(cat)，将进程状态重置为 TASK_RUNNING，enqueue_task_fair() 重新插入 cfs_rq，nr_running 恢复为 1，同时设置 TIF_NEED_RESCHED 标志。

阶段 4：抢占调度与上下文恢复

时钟中断触发 scheduler_tick()，检测到 TIF_NEED_RESCHED 后在中断返回前调用 schedule()。prev（cat）状态为 0，走 put_prev_task 路径——进程留在队列中，TASK_RUNNING 状态不变。pick_next_task() 选中 cat，context_switch() 恢复其内核栈和页表。read() 从系统调用处继续执行。

阶段 5：进程退出

cat 调用 exit_group()，do_exit() 将状态置为 EXIT_ZOMBIE，dequeue_task() 移出运行队列。父进程 bash 接收 SIGCHLD，调用 wait() 回收 task_struct。

整个流程的状态变迁回顾：

fork()  → TASK_RUNNING → 入 rq
read()  → TASK_INTERRUPTIBLE → 出 rq，进等待队列
wake_up → TASK_RUNNING → 入 rq，设 TIF_NEED_RESCHED
schedule() → cat 上 CPU；上一个进程被 put_prev 留在 rq
exit()  → EXIT_ZOMBIE → 出 rq，父进程回收