第五十三章：调度器演进
结丹圆满涉及内核源码：
一
林小源在调度竞技场的深处，发现了一座博物馆。
博物馆的墙壁上挂满了画像——每一张画像都是一位调度器的肖像。最左边是一幅粗糙的素描，画着一个简单的循环；中间是一幅精美的油画，画着位图和优先级数组；最右边是一幅工笔画，画着一棵红黑树。
"这是调度器的历史。"CFS 从红黑树画像旁走来，"Linux 调度器经历了三代演进。"
林小源走到最左边的素描前。画中是一个简单的调度器，正在遍历一个长长的进程列表。
"第一代，O(n) 调度器，"CFS 说，"Linux 2.4 时代的调度器。每次调度都要遍历所有进程，找到最佳进程。时间复杂度 O(n)，n 是进程数。简单，但当进程数成千上万时，效率低下。"
林小源走到中间的油画前。画中是一个精巧的数据结构——位图标记哪些优先级有进程，优先级数组存储各优先级的进程链表。
"第二代，O(1) 调度器，"CFS 说，"Linux 2.6 时代的调度器。使用位图和优先级数组，时间复杂度 O(1)。高效，但对交互式进程不友好——它用启发式判断哪些进程是'交互式'的，但这个判断经常出错。"
"谁写的？"林小源问。
CFS 微微一笑："Ingo Molnar。"
林小源走到最右边的工笔画前。画中是一棵红黑树，每个节点都是一个进程，按 vruntime 排序。
"第三代，CFS 调度器，"CFS 说，"Linux 2.6.23 以来的调度器。使用红黑树，按 vruntime 排序。不需要启发式，不需要区分'交互式'和'批处理'——所有进程一视同仁。时间复杂度 O(log n)。"
"谁写的？"林小源又问。
CFS 笑得更深了："也是 Ingo Molnar。他亲手推翻了自己的 O(1) 调度器——因为 CFS 的设计哲学更好。"
二
林小源站在红黑树画像前，仔细观察每一个节点。
"为什么 CFS 要取代 O(1)？"他问。
CFS 走到他身边："O(1) 调度器的问题在于启发式。它用'睡眠时间'来判断一个进程是不是交互式的——睡眠时间长的进程被认为是交互式的，给予更高的优先级。但这个判断经常出错：一个批处理进程可能因为等待 I/O 而长时间睡眠，被错误地当作交互式进程。"
"而 CFS 不需要这种判断？"
"不需要，"CFS 说，"CFS 的核心思想是'公平'——每个进程的 vruntime 应该趋于相等。vruntime 是进程的虚拟运行时间，按权重分配。权重高的进程 vruntime 增长慢，获得更多的 CPU 时间；权重低的进程 vruntime 增长快，获得更少的 CPU 时间。调度器总是选择 vruntime 最小的进程运行——这是精确的数学计算，不是启发式猜测。"
林小源看着红黑树的结构，问道："per-CPU 运行队列呢？"
"O(1) 调度器使用全局运行队列，多核竞争一把锁，扩展性差。CFS 使用 per-CPU 运行队列，每个 CPU 有自己的红黑树，互不干扰，扩展性好。"CFS 说，"简单、公平、高效、可扩展——这就是 CFS 取代 O(1) 的原因。"
三
林小源坐在博物馆的长椅上，看着三代调度器的画像。
"好的设计不是一蹴而就的，"他说，"它需要经历多次迭代。"
CFS 在他身边坐下："没错。O(n) 调度器是'能用'——它能工作，但效率低。O(1) 调度器是'好用'——它高效，但启发式不可靠。CFS 调度器是'优雅'——它用最简单的思想解决了最复杂的问题。"
"但 CFS 也有权衡，"林小源说，"O(log n) 比 O(1) 慢。"
"是的，"CFS 说，"但 O(log n) 的'慢'几乎可以忽略——红黑树的深度通常只有十几层。而 CFS 的'公平'带来的好处远远超过这点微小的性能损失。"
林小源看着博物馆的墙壁，看到了未来的空间——也许会有第四代调度器，也许 CFS 也会被推翻。但设计哲学不会变：简单、公平、高效、可扩展。
"进化是永无止境的，"林小源说。
CFS 点头："每一次迭代都解决前一代的问题，但也引入新的权衡。这就是内核的演化——不是一步到位，而是不断试错、不断改进。"
/*
* 第一代：O(n) 调度器 (Linux 2.4)
* 遍历所有进程，找到最佳进程
* 时间复杂度 O(n)，n 是进程数
* 简单但效率低
*
* 第二代：O(1) 调度器 (Linux 2.6)
* 使用位图和优先级数组
* 位图标记哪些优先级有进程
* 优先级数组存储各优先级的进程链表
* 时间复杂度 O(1)
* 但对交互式进程不友好
*
* 第三代：CFS 调度器 (Linux 2.6.23+)
* 使用红黑树，按 vruntime 排序
* vruntime 最小的进程获得 CPU
* 公平、高效、对交互式友好
* 时间复杂度 O(log n)
*/
struct o_n_scheduler {
int nr_running;
int best_idx;
};
struct o_1_scheduler {
unsigned long bitmap; /* 位图 */
int prio_array[32]; /* 优先级数组 */
int nr_running;
};
struct cfs_scheduler {
int nr_running;
unsigned long min_vruntime;
};
printf("=== 调度器的演进 ===\n\n");
printf("--- 第一代：O(n) 调度器 ---\n");
printf("时间复杂度：O(n)\n");
printf("优点：简单\n");
printf("缺点：进程数多时效率低\n");
printf("时代：Linux 2.4\n\n");
printf("--- 第二代：O(1) 调度器 ---\n");
printf("时间复杂度：O(1)\n");
printf("优点：高效\n");
printf("缺点：对交互式进程不友好\n");
printf("时代：Linux 2.6\n\n");
printf("--- 第三代：CFS 调度器 ---\n");
printf("时间复杂度：O(log n)\n");
printf("优点：公平、对交互式友好\n");
printf("缺点：比 O(1) 稍慢\n");
printf("时代：Linux 2.6.23+\n\n");
printf("--- CFS 为什么取代 O(1) ---\n");
printf("O(1) 调度器的问题：\n");
printf(" - 交互式进程的启发式判断不准确\n");
printf(" - 某些进程被不公平地对待\n");
printf(" - 全局变量导致扩展性差\n\n");
printf("CFS 的解决方案：\n");
printf(" - 不使用启发式，使用 vruntime 精确计算\n");
printf(" - 所有进程按 vruntime 排序，天然公平\n");
printf(" - per-CPU 运行队列，扩展性好\n");
printf("\n--- 调度器的设计哲学 ---\n");
printf("O(n): 简单优先\n");
printf("O(1): 效率优先\n");
printf("CFS: 公平优先\n");#include <stdio.h>
/*
* 第一代：O(n) 调度器 (Linux 2.4)
* 遍历所有进程，找到最佳进程
* 时间复杂度 O(n)，n 是进程数
* 简单但效率低
*
* 第二代：O(1) 调度器 (Linux 2.6)
* 使用位图和优先级数组
* 位图标记哪些优先级有进程
* 优先级数组存储各优先级的进程链表
* 时间复杂度 O(1)
* 但对交互式进程不友好
*
* 第三代：CFS 调度器 (Linux 2.6.23+)
* 使用红黑树，按 vruntime 排序
* vruntime 最小的进程获得 CPU
* 公平、高效、对交互式友好
* 时间复杂度 O(log n)
*/
struct o_n_scheduler {
int nr_running;
int best_idx;
};
struct o_1_scheduler {
unsigned long bitmap; /* 位图 */
int prio_array[32]; /* 优先级数组 */
int nr_running;
};
struct cfs_scheduler {
int nr_running;
unsigned long min_vruntime;
};
int main() {
printf("=== 调度器的演进 ===\n\n");
printf("--- 第一代：O(n) 调度器 ---\n");
printf("时间复杂度：O(n)\n");
printf("优点：简单\n");
printf("缺点：进程数多时效率低\n");
printf("时代：Linux 2.4\n\n");
printf("--- 第二代：O(1) 调度器 ---\n");
printf("时间复杂度：O(1)\n");
printf("优点：高效\n");
printf("缺点：对交互式进程不友好\n");
printf("时代：Linux 2.6\n\n");
printf("--- 第三代：CFS 调度器 ---\n");
printf("时间复杂度：O(log n)\n");
printf("优点：公平、对交互式友好\n");
printf("缺点：比 O(1) 稍慢\n");
printf("时代：Linux 2.6.23+\n\n");
printf("--- CFS 为什么取代 O(1) ---\n");
printf("O(1) 调度器的问题：\n");
printf(" - 交互式进程的启发式判断不准确\n");
printf(" - 某些进程被不公平地对待\n");
printf(" - 全局变量导致扩展性差\n\n");
printf("CFS 的解决方案：\n");
printf(" - 不使用启发式，使用 vruntime 精确计算\n");
printf(" - 所有进程按 vruntime 排序，天然公平\n");
printf(" - per-CPU 运行队列，扩展性好\n");
printf("\n--- 调度器的设计哲学 ---\n");
printf("O(n): 简单优先\n");
printf("O(1): 效率优先\n");
printf("CFS: 公平优先\n");
return 0;
}道藏笔记
内核启示
Linux 调度器经历了三代演进。
第一代：O(n) 调度器（Linux 2.4）
- 遍历所有进程，找到最佳进程
- 时间复杂度 O(n)
- 简单但效率低
第二代：O(1) 调度器（Linux 2.6）
- 使用位图和优先级数组
- 时间复杂度 O(1)
- 但对交互式进程不友好
第三代：CFS 调度器（Linux 2.6.23+）
- 使用红黑树，按 vruntime 排序
- 时间复杂度 O(log n)
- 公平、高效、对交互式友好
CFS 取代 O(1) 的原因：
- O(1) 的启发式判断不准确
- CFS 不需要启发式，使用 vruntime 精确计算
- CFS 的 per-CPU 设计扩展性更好
好的设计需要迭代——每一次迭代都解决前一代的问题。
调度器演进之试
本章回顾调度器演进时，取代 O(1) 思路并以公平为核心的调度器缩写是什么？