2. runqueue 数据结构：struct rq 核心字段解析
runqueue（就绪队列）是 Linux 内核调度器的核心数据结构，每个 CPU 都拥有一个独立的 runqueue 实例。struct rq 定义在 kernel/sched/sched.h 中，它聚合了该 CPU 上所有调度类（CFS、RT、DL）的队列、统计信息、负载跟踪以及调度控制所需的全部状态。理解 struct rq 的布局是掌握调度器运行机制的第一步。
2.1 struct rq 核心字段一览
下表列出了 struct rq 中最关键的字段及其作用：
| 字段名 | 类型 | 作用描述 |
|---|---|---|
| nr_running | unsigned int | 当前 CPU 上所有调度类中处于 TASK_RUNNING 状态的进程总数，是调度器判断是否空闲的首要指标。 |
| load | struct load_weight | 当前 CPU 的瞬时负载权重，由所有可运行进程的权重累加得到，用于负载均衡决策。 |
| cfs | struct cfs_rq | CFS 调度类的就绪队列，管理普通进程（SCHED_NORMAL/SCHED_BATCH）的红黑树和虚拟运行时间。 |
| rt | struct rt_rq | 实时调度类的就绪队列，管理实时进程（SCHED_FIFO/SCHED_RR）的优先级数组。 |
| dl | struct dl_rq | Deadline 调度类的就绪队列，管理截止时间调度进程的红黑树和带宽控制。 |
| curr | struct task_struct * | 指向当前正在 CPU 上执行的进程描述符。 |
| idle | struct task_struct * | 指向该 CPU 的空闲进程（idle task），当 nr_running 为 0 时运行。 |
| clock | u64 | 该 CPU 的调度时钟，用于计算进程运行时间和调度延迟。 |
| nr_switches | unsigned long | 该 CPU 上发生的上下文切换次数统计。 |
| pushable_tasks | struct list_head | 可被推送到其他 CPU 的实时/Deadline 任务链表，用于负载均衡。 |
关键理解： nr_running 和 load 是 runqueue 的"晴雨表"。调度器在每次 tick 中断和进程唤醒时都会更新这两个字段，负载均衡器则根据它们判断是否需要迁移任务。
2.2 per-CPU runqueue 布局
Linux 内核使用 per-CPU 变量机制为每个 CPU 分配独立的 struct rq 实例。这种设计避免了多核并发访问同一队列时的锁竞争，是调度器可扩展性的基石。
per-CPU runqueue 的布局特点：
- 独立存储： 每个 CPU 的 runqueue 存放在该 CPU 的本地内存（L1/L2 cache）附近，减少缓存一致性开销。
- 直接访问： 通过
this_rq()宏获取当前 CPU 的 runqueue，通过cpu_rq(cpu)获取指定 CPU 的 runqueue。 - 锁机制： 每个 runqueue 拥有自己的自旋锁（rq->lock），操作本 CPU 队列时只需锁定本地锁。
- 负载均衡例外： 当需要跨 CPU 迁移任务时，必须同时锁定源和目标 CPU 的 runqueue 锁，避免死锁。
per-CPU 声明方式（代码片段）：
// 定义 per-CPU runqueue 变量
DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
// 获取当前 CPU 的 runqueue
#define this_rq() this_cpu_ptr(&runqueues)
// 获取指定 CPU 的 runqueue
#define cpu_rq(cpu) per_cpu_ptr(&runqueues, cpu)下图展示了 per-CPU runqueue 在双核系统中的布局以及各调度子队列的关系：
2.3 nr_running 与 load 的更新机制
nr_running 和 load 是调度器最频繁更新的字段，它们的更新路径如下：
| 事件 | nr_running 变化 | load 变化 | 触发函数 |
|---|---|---|---|
| 进程被唤醒（wake_up） | +1 | 增加进程权重 | activate_task() → enqueue_task() |
| 进程主动睡眠（sleep） | -1 | 减少进程权重 | deactivate_task() → dequeue_task() |
| 进程被抢占（preempt） | 不变 | 不变 | 调度器 tick 检查 |
| 进程退出（exit） | -1 | 减少进程权重 | sched_exit() |
| 跨 CPU 迁移（migrate） | 源 -1，目标 +1 | 源减，目标加 | migrate_task() |
注意： nr_running 只统计 TASK_RUNNING 状态的进程，不包括 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 状态的进程。当 nr_running 为 0 时，调度器会切换到 idle 进程运行，CPU 进入低功耗状态。
2.4 调度子队列的协作关系
struct rq 中的 cfs、rt、dl 三个子队列并非独立运行，它们通过调度器核心的 pick_next_task() 函数按优先级顺序选择下一个要运行的进程：
- Deadline 优先： 首先检查 dl_rq 是否有可运行的 deadline 进程，如果有则优先选择。
- 实时进程次之： 如果 dl_rq 为空，则检查 rt_rq 中优先级最高的实时进程。
- CFS 兜底： 如果 dl_rq 和 rt_rq 都为空，则从 cfs_rq 的红黑树中选择虚拟运行时间最小的进程。
- 空闲进程： 如果所有子队列都为空，则运行 idle 进程。
下图展示了 pick_next_task 的决策流程：
2.5 runqueue 的锁保护与并发访问
在多核系统中，runqueue 的并发访问必须通过锁来保护。struct rq 包含一个自旋锁 rq->lock，其使用规则如下：
- 本地访问： 操作当前 CPU 的 runqueue 时，只需获取本地 rq->lock，开销较小。
- 跨 CPU 访问： 负载均衡或任务迁移时，需要同时锁定源和目标 CPU 的 runqueue，且必须按照 CPU 编号顺序加锁以避免死锁。
- 中断上下文： 在中断处理函数中访问 runqueue 时，需要关闭本地中断（local_irq_disable）并获取锁，防止中断嵌套导致死锁。
- 双锁协议： 使用
double_lock_balance()函数安全地获取两个 runqueue 的锁。
双锁加锁示例（代码片段）：
// 负载均衡时锁定两个 runqueue
static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
{
if (this_rq < busiest) {
raw_spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
raw_spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
} else {
raw_spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
raw_spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
}
return 0;
}2.6 本章小结
struct rq 是调度器在 per-CPU 粒度的核心数据结构，它通过 nr_running 和 load 提供瞬时负载快照，通过 cfs/rt/dl 三个子队列实现不同调度类的进程管理，并通过 rq->lock 保证并发安全。理解 runqueue 的布局和字段含义，是后续分析调度器核心流程（如进程入队、出队、负载均衡）的基础。