第四十一章：运行队列
结丹中期涉及内核源码：
一
林小源在竞技场中走了很远，直到他看到了一排并列的石台。
每座石台都有一人高，表面光滑如镜，上面刻着密密麻麻的符文。石台的数量与系统的 CPU 核数相同——四座石台一字排开，每座石台的顶端都嵌着一颗发光的晶石，晶石中不断闪烁着进程的 PID。
"运行队列。"一个声音从石台后面传来。
林小源绕过石台，看到一个穿着蓝色长袍的中年人正在擦拭其中一座石台的表面。他的动作很轻，像在擦拭一件珍贵的器物。
"我是 struct rq，"中年人说，"每座石台代表一个 CPU 的运行队列。我是 CPU 0 的运行队列。"
林小源看着石台上的符文："这些是什么？"
"nr_running——可运行进程数。cfs——CFS 运行队列，里面是一棵红黑树。rt——RT 运行队列。dl——Deadline 运行队列。curr——当前运行的进程。idle——idle 进程。clock——队列时钟。"
"每个 CPU 都有自己的运行队列？"
"对。"中年人说，"这是 per-CPU 设计。如果所有 CPU 共享一个运行队列，锁竞争会成为性能瓶颈——每次调度都需要加锁，多个 CPU 同时争抢同一把锁，效率极低。"
他拍了拍石台："有了 per-CPU 运行队列，每个 CPU 只需要访问自己的石台，不需要加锁。除非是特殊情况下的负载均衡。"
林小源看着四座石台，它们的表面刻着不同的数字——有的石台上的 nr_running 很大，有的很小。
二
"per-CPU 设计还有另一个好处，"中年人继续说，"缓存亲和性。"
他指向 CPU 0 的石台："当一个进程在 CPU 0 上运行时，它的数据会被缓存在 CPU 0 的缓存中。如果进程被迁移到 CPU 1，缓存就失效了——CPU 1 需要重新从内存中加载数据。"
"所以进程倾向于在同一个 CPU 上运行？"
"对。"中年人说，"调度器会尽量让进程在同一个 CPU 上运行，利用缓存中的数据。这就是'缓存亲和性'。"
林小源想起了自己在内核中看到的 NUMA 架构："NUMA 节点呢？"
"NUMA 是另一个层次。"中年人说，"在 NUMA 系统中，每个 CPU 有自己的本地内存。访问本地内存快，访问远程内存慢——可能差 2-3 倍。所以调度器还会考虑 NUMA 亲和性，尽量让进程在本地 NUMA 节点上运行。"
"分而治之。"林小源喃喃道。
"对。"中年人点头，"多核调度的核心思想就是分而治之——每个 CPU 管理自己的运行队列，减少锁竞争，提高缓存亲和性，支持 NUMA 感知。"
三
林小源在四座石台之间走动，观察着它们的运作。
他注意到每座石台的表面都有三层结构——最上面是 RT 运行队列，中间是 CFS 运行队列（红黑树），最下面是 Deadline 运行队列。
"运行队列是分层的？"林小源问。
中年人走过来："对。调度器按优先级依次检查：先检查 RT 运行队列，如果有可运行的 RT 进程，就选它。如果没有，再检查 CFS 运行队列。最后才是 Deadline 运行队列。"
"那 idle 进程呢？"
"idle 进程是最后的兜底。"中年人说，"如果所有运行队列都是空的，就运行 idle 进程。它不消耗任何资源，只是让 CPU 等待新的进程到来。"
林小源看着四座石台，突然意识到运行队列不仅仅是"工作台"——它是每个 CPU 的"领地"。每个 CPU 在自己的领地上调度进程，管理资源，做出决策。而负载均衡则是在这些领地之间进行"资源再分配"。
"你有没有想过，"林小源问，"如果某些 CPU 的运行队列很'重'，而另一些很'轻'，系统整体的利用率就不高？"
中年人看了他一眼，目光中带着一丝赞许："你已经看到了问题的核心。这就是负载均衡需要解决的问题——但那是另一个故事了。"
/*
* 运行队列 (struct rq) 是 per-CPU 的：
* 每个 CPU 都有自己的运行队列
* 避免了多核之间的锁竞争
*
* struct rq 的关键字段：
* nr_running — 可运行进程数
* cfs — CFS 运行队列（红黑树）
* rt — RT 运行队列
* dl — Deadline 运行队列
* curr — 当前运行的进程
* idle — idle 进程
* clock — 队列时钟
*
* per-CPU 设计的好处：
* - 减少锁竞争
* - 缓存亲和性
* - NUMA 感知
*/
struct cfs_rq {
int nr_running;
unsigned long min_vruntime;
};
struct rq {
int cpu;
int nr_running;
struct cfs_rq cfs;
int curr_pid;
int idle_pid;
unsigned long clock;
};
printf("=== 运行队列 — per-CPU 调度器 ===\n\n");
/* 模拟 4 个 CPU 的运行队列 */
struct rq rqs[4];
for (int i = 0; i < 4; i++) {
rqs[i].cpu = i;
rqs[i].nr_running = 0;
rqs[i].cfs.nr_running = 0;
rqs[i].curr_pid = 0;
rqs[i].idle_pid = i; /* 每个 CPU 有自己的 idle */
rqs[i].clock = 0;
}
/* 分配进程到不同的运行队列 */
rqs[0].nr_running = 5;
rqs[0].cfs.nr_running = 4;
rqs[0].curr_pid = 100;
rqs[1].nr_running = 3;
rqs[1].cfs.nr_running = 2;
rqs[1].curr_pid = 200;
rqs[2].nr_running = 8;
rqs[2].cfs.nr_running = 7;
rqs[2].curr_pid = 300;
rqs[3].nr_running = 1;
rqs[3].cfs.nr_running = 0;
rqs[3].curr_pid = 0; /* idle */
printf("各 CPU 的运行队列状态：\n");
printf("%-6s %-12s %-10s %-10s\n", "CPU", "nr_running", "cfs_running", "curr");
printf("%-6s %-12s %-10s %-10s\n", "---", "---", "---", "---");
for (int i = 0; i < 4; i++) {
printf("%-6d %-12d %-10d %-10s\n",
rqs[i].cpu, rqs[i].nr_running,
rqs[i].cfs.nr_running,
rqs[i].curr_pid == 0 ? "idle" : "PID...");
}
printf("\n--- per-CPU 设计的优势 ---\n");
printf("1. 减少锁竞争：每个 CPU 只访问自己的运行队列\n");
printf("2. 缓存亲和性：进程倾向于在同一个 CPU 上运行\n");
printf("3. NUMA 感知：进程倾向于在本地 NUMA 节点上运行\n\n");
printf("--- 运行队列的操作 ---\n");
printf("enqueue_task(): 把进程加入运行队列\n");
printf("dequeue_task(): 把进程从运行队列移除\n");
printf("pick_next_task(): 选择下一个运行的进程\n");
printf("scheduler_tick(): 时钟中断时更新运行队列\n");#include <stdio.h>
#include <string.h>
/*
* 运行队列 (struct rq) 是 per-CPU 的：
* 每个 CPU 都有自己的运行队列
* 避免了多核之间的锁竞争
*
* struct rq 的关键字段：
* nr_running — 可运行进程数
* cfs — CFS 运行队列（红黑树）
* rt — RT 运行队列
* dl — Deadline 运行队列
* curr — 当前运行的进程
* idle — idle 进程
* clock — 队列时钟
*
* per-CPU 设计的好处：
* - 减少锁竞争
* - 缓存亲和性
* - NUMA 感知
*/
struct cfs_rq {
int nr_running;
unsigned long min_vruntime;
};
struct rq {
int cpu;
int nr_running;
struct cfs_rq cfs;
int curr_pid;
int idle_pid;
unsigned long clock;
};
int main() {
printf("=== 运行队列 — per-CPU 调度器 ===\n\n");
/* 模拟 4 个 CPU 的运行队列 */
struct rq rqs[4];
for (int i = 0; i < 4; i++) {
rqs[i].cpu = i;
rqs[i].nr_running = 0;
rqs[i].cfs.nr_running = 0;
rqs[i].curr_pid = 0;
rqs[i].idle_pid = i; /* 每个 CPU 有自己的 idle */
rqs[i].clock = 0;
}
/* 分配进程到不同的运行队列 */
rqs[0].nr_running = 5;
rqs[0].cfs.nr_running = 4;
rqs[0].curr_pid = 100;
rqs[1].nr_running = 3;
rqs[1].cfs.nr_running = 2;
rqs[1].curr_pid = 200;
rqs[2].nr_running = 8;
rqs[2].cfs.nr_running = 7;
rqs[2].curr_pid = 300;
rqs[3].nr_running = 1;
rqs[3].cfs.nr_running = 0;
rqs[3].curr_pid = 0; /* idle */
printf("各 CPU 的运行队列状态：\n");
printf("%-6s %-12s %-10s %-10s\n", "CPU", "nr_running", "cfs_running", "curr");
printf("%-6s %-12s %-10s %-10s\n", "---", "---", "---", "---");
for (int i = 0; i < 4; i++) {
printf("%-6d %-12d %-10d %-10s\n",
rqs[i].cpu, rqs[i].nr_running,
rqs[i].cfs.nr_running,
rqs[i].curr_pid == 0 ? "idle" : "PID...");
}
printf("\n--- per-CPU 设计的优势 ---\n");
printf("1. 减少锁竞争：每个 CPU 只访问自己的运行队列\n");
printf("2. 缓存亲和性：进程倾向于在同一个 CPU 上运行\n");
printf("3. NUMA 感知：进程倾向于在本地 NUMA 节点上运行\n\n");
printf("--- 运行队列的操作 ---\n");
printf("enqueue_task(): 把进程加入运行队列\n");
printf("dequeue_task(): 把进程从运行队列移除\n");
printf("pick_next_task(): 选择下一个运行的进程\n");
printf("scheduler_tick(): 时钟中断时更新运行队列\n");
return 0;
}道藏笔记
内核启示
运行队列（struct rq）是 per-CPU 的调度器核心数据结构。
运行队列的关键字段：
- — 可运行进程数
- — CFS 运行队列（包含红黑树）
rt— RT 运行队列dl— Deadline 运行队列- — 当前运行的进程
- — idle 进程
- — 队列时钟
per-CPU 设计的优势：
- 减少锁竞争
- 缓存亲和性
- NUMA 感知
运行队列的操作：
- — 把进程加入运行队列
- — 把进程从运行队列移除
- — 选择下一个运行的进程
scheduler_tick()— 时钟中断时更新运行队列
运行队列是调度器的"工作台"——每个 CPU 有自己的工作台。
运行队列之试
每个 CPU 都维护自己的调度现场，本章称这座保存可运行任务的地方是什么？