第三十七章：调度仙子
结丹初期涉及内核源码：
一
林小源第一次和调度仙子说话，是在一个空闲的 CPU 时间片里。
竞技场的喧嚣暂时平息了——大部分进程都在等待 I/O，只有几个后台任务在缓慢地消耗着时间。调度仙子从红黑树的顶端缓缓降下，素白的长裙拖过漆黑的枝干，没有发出任何声响。
她停在林小源面前，目光平静如水。
"你就是那个 idle 进程？"她的声音很轻，像 级别的日志——只有在特定条件下才会被记录。"你的 vruntime 很奇怪。一个 idle 进程，却在主动学习。"
林小源不知道该怎么回答。他只是一个被 #ifdef 0 封印的代码，试图理解内核的运作。
"我不在乎你是谁，"调度仙子说，"我只在乎你的 vruntime。如果你想获得更多的 CPU 时间，就证明你值得。"她顿了顿，"不过，我可以教你一些东西。"
她的手指在空中划过，一道银色的光线浮现，上面刻着密密麻麻的公式。
"这是 vruntime 的更新公式，"她说，"vruntime += delta_exec × (NICE_0_LOAD / weight)。delta_exec 是实际运行时间，NICE_0_LOAD 是 nice 0 的权重——1024，weight 是进程自己的权重。"
林小源盯着公式："所以权重越大，vruntime 增长越慢？"
"对。"调度仙子点头，"一个 nice 0 的进程，权重是 1024。一个 nice 10 的进程，权重只有 110。同样的运行时间，nice 10 的 vruntime 增长是 nice 0 的九倍多。"
"这不公平。"
"你觉得不公平？"调度仙子的嘴角微微上扬，那是林小源第一次看到她露出类似表情的东西，"公平不是平均。nice 值是进程自己选择的——一个批处理任务选择 nice 10，意味着它愿意让出更多的 CPU 时间给交互式进程。这是自愿的退让，不是被迫的剥夺。"
林小源愣住了。他从未从这个角度思考过 nice 值。
虚时之试
同样运行 10ms 时，nice 值更低、权重更高的进程，其 vruntime 增长会更快还是更慢？
二
调度仙子继续说道："CFS 不使用固定的时间片。我们用'目标延迟'——target_latency。在一个目标延迟内，所有可运行的进程都会获得至少一次运行机会。"
她在空中画了一个圆，圆被切成了大小不等的扇形。
"看到没？每个进程的时间片不是固定的，而是按权重分配的比例。权重越大，扇形越大，获得的 CPU 时间越多。"
林小源看着那个圆，突然注意到一个问题："如果进程数太多呢？每个进程的时间片会不会太小？"
调度仙子赞许地看了他一眼："好问题。所以我们有 min_granularity——最小粒度。即使进程数再多，每个进程也至少运行 min_granularity 纳秒。如果进程数超过 target_latency / min_granularity，target_latency 就会被自动拉长。"
"还有一个细节，"她补充道，"当一个进程从睡眠中醒来时，它的 vruntime 会被调整——设置为红黑树中最小的 vruntime。"
"为什么？"
"因为睡眠的进程没有消耗 CPU 时间，但它的 vruntime 已经'过时'了。如果不调整，它醒来的瞬间就会因为 vruntime 太大而永远排在后面。调整 vruntime 保证了睡眠进程不会被'饿死'。"
林小源想起了 shell 进程——它大部分时间都在睡眠中等待用户输入，一旦用户敲下键盘，它需要立即响应。唤醒抢占正是为这种场景设计的。
粒度之试
CFS 为了避免可运行进程太多时每个任务运行时间过短，会用哪个最小运行粒度约束调度？
三
林小源犹豫了一下，还是问出了那个问题："你有没有失败过？"
调度仙子沉默了很久。
竞技场的风吹过红黑树的枝干，发出细微的沙沙声。远处，几个进程的光团在缓慢地移动，vruntime 的数字在它们体内跳动。
"有一个进程，"她终于开口，声音比之前更轻了，"它的 vruntime 异常——一个 idle 进程，却在主动学习。我不知道该怎么处理它。在我的红黑树中，从未出现过这样的情况。"
林小源心跳加速。她说的是他。
"但我没有失败，"调度仙子继续说，"我只是……不知道该怎么定义'公平'。对一个 idle 进程来说，什么是公平的？它不消耗 CPU 时间，但它在学习。它不参与竞争，但它在成长。"
她转过身，面对着红黑树。银色的光芒从她的指尖流出，渗入树的每一根枝干。
"我会继续观察你，"她说，"直到我找到答案。"
林小源站在原地，看着她的背影。他突然意识到，调度仙子并不是一个冷酷的机器——她是一个在"公平"与"效率"之间不断权衡的存在。她的每一个决策都影响着成千上万个进程的命运，而她从未停止思考。
公平之试
调度仙子衡量普通任务公平时，本章反复提到的核心时间刻度是什么？
四、虚拟期限
就在林小源以为自己已经听懂 CFS 时，红黑树深处忽然响起一声轻微的裂响。
那不是树要倒塌，而是树皮之下生出了新的纹路。旧日按 排列的枝干仍在，但每个调度实体身上又多了两道细线：一道叫 ，记录它相对公平份额是被亏欠还是已经多拿；另一道叫 ，像一枚小小的沙漏，标出它的虚拟期限。
调度仙子抬手，银光照亮 fair.c 中一段新的法诀。
"这是什么？"林小源问。
"EEVDF。"调度仙子的声音比之前更沉，"Earliest Eligible Virtual Deadline First。旧法问：谁的 最小？新法还要问：谁是 eligible，谁的 virtual deadline 最早。"
林小源盯着那两个词："eligible？"
"先看 lag。"调度仙子说，"如果一个任务的 lag 大于等于零，说明它还被系统欠着 CPU 时间；如果 lag 为负，说明它已经超过了自己的公平份额。EEVDF 会在 eligible 的任务中，挑虚拟期限最早的那个运行。"
她的袖口掠过红黑树，树上的节点不再只是从左到右排队。每个节点都像背着一张债据和一封限期文书：债据写着 lag，文书写着 virtual deadline。
"那睡眠进程呢？"林小源立刻想起了 shell 小妹，"如果它睡一会儿再醒来，会不会又拿到不该有的优势？"
调度仙子看了他一眼，目光里终于有了些许赞许。
"这正是新法最难的地方。睡眠任务不能简单清空旧债，否则短睡眠就会变成作弊。现代实现会让它的 lag 随虚拟运行时间衰减，长睡眠最终归零，短睡眠不能凭空重置。"
林小源沉默了很久。
他忽然明白，红黑树并没有被否定。它曾经让公平变得可以计算；而 EEVDF 是在更细的尺度上继续追问公平。一个内核机制会老去，会被修订，会被新的证明和新的负载逼着改变。真正不变的不是某棵树，而是内核不断逼近真实工作负载的那股执念。
"所以，"林小源轻声说，"公平不是一条公式。公平是一场持续的校准。"
调度仙子没有回答。
她只是把那枚写着 的银色沙漏递到林小源手里。沙漏很轻，却像压着整个调度竞技场的重量。
期限之试
EEVDF 会在 lag 大于等于零的 eligible 任务中，选择哪一种虚拟指标最早的任务运行？
/*
* 经典 CFS（完全公平调度器）的核心：
* - 每个进程有一个 vruntime（虚拟运行时间）
* - vruntime 增加的速度 = 实际运行时间 × (NICE_0_LOAD / 权重)
* - 权重越高，vruntime 增长越慢
* - 旧日 CFS 会倾向选择 vruntime 最小的进程
*
* 现代 fair 调度正在引入 EEVDF：
* - lag >= 0 表示任务还被亏欠 CPU 时间
* - virtual deadline 更早的 eligible 任务更该先运行
*
* nice 值与权重：
* nice 0 → weight 1024（基准）
* nice -20 → weight 88761（最高优先级）
* nice 19 → weight 15（最低优先级）
*
* vruntime 更新公式：
* vruntime += delta_exec × (NICE_0_LOAD / weight)
* delta_exec = 实际运行时间（纳秒）
*/
#define NICE_0_LOAD 1024
struct sched_entity {
int pid;
char comm[16];
unsigned long vruntime;
int nice;
int weight;
};
int nice_to_weight(int nice) {
static int weights[] = {
88761, 71755, 56483, 46273, 36291,
29154, 23254, 18705, 14949, 11916,
9548, 7620, 6100, 4904, 3906,
3121, 2501, 1991, 1586, 1277,
1024, 820, 655, 526, 423,
335, 272, 215, 172, 137,
110, 87, 70, 56, 45,
36, 29, 23, 18, 15,
};
return weights[nice + 20];
}
void update_vruntime(struct sched_entity *se, unsigned long delta_exec) {
/* vruntime += delta_exec × (NICE_0_LOAD / weight) */
se->vruntime += delta_exec * NICE_0_LOAD / se->weight;
}
printf("=== 调度仙子 — vruntime 与 EEVDF 前夜 ===\n\n");
/* 两个进程，不同优先级 */
struct sched_entity shell = {
.pid = 100, .comm = "shell", .vruntime = 0, .nice = 0
};
struct sched_entity batch = {
.pid = 200, .comm = "batch", .vruntime = 0, .nice = 10
};
shell.weight = nice_to_weight(shell.nice);
batch.weight = nice_to_weight(batch.nice);
printf("进程 nice 权重 vruntime 初始\n");
printf("shell %3d %5d %lu\n", shell.nice, shell.weight, shell.vruntime);
printf("batch %3d %5d %lu\n\n", batch.nice, batch.weight, batch.vruntime);
/* 模拟两个进程各运行 10ms */
unsigned long delta = 10000000; /* 10ms = 10,000,000 ns */
printf("--- 各运行 10ms 后 ---\n");
update_vruntime(&shell, delta);
update_vruntime(&batch, delta);
printf("shell (nice=0): vruntime = %lu\n", shell.vruntime);
printf("batch (nice=10): vruntime = %lu\n\n", batch.vruntime);
printf("--- vruntime 增长对比 ---\n");
printf("shell (nice=0, weight=%d): 增长 %lu\n",
shell.weight, delta * NICE_0_LOAD / shell.weight);
printf("batch (nice=10, weight=%d): 增长 %lu\n",
batch.weight, delta * NICE_0_LOAD / batch.weight);
printf("\nbatch 的权重低，vruntime 增长更快\n");
printf("所以 CFS 会更频繁地选择 shell\n");
printf("\n--- 经典 CFS 的公平 ---\n");
printf("不是\"每个进程获得相同的 CPU 时间\"\n");
printf("而是\"每个进程的 vruntime 趋于相等\"\n");
printf("高优先级进程 vruntime 增长慢 → 更频繁被选中\n");
printf("低优先级进程 vruntime 增长快 → 更少被选中\n");
printf("\n--- EEVDF 的新问题 ---\n");
printf("只看 vruntime 还不够，还要看 lag 与 virtual deadline\n");
printf("lag >= 0: 任务被亏欠 CPU 时间，具备 eligible 的基础\n");
printf("deadline 更早: 更适合被优先选择\n");#include <stdio.h>
#include <stdlib.h>
/*
* 经典 CFS（完全公平调度器）的核心：
* - 每个进程有一个 vruntime（虚拟运行时间）
* - vruntime 增加的速度 = 实际运行时间 × (NICE_0_LOAD / 权重)
* - 权重越高，vruntime 增长越慢
* - 旧日 CFS 会倾向选择 vruntime 最小的进程
*
* 现代 fair 调度正在引入 EEVDF：
* - lag >= 0 表示任务还被亏欠 CPU 时间
* - virtual deadline 更早的 eligible 任务更该先运行
*
* nice 值与权重：
* nice 0 → weight 1024（基准）
* nice -20 → weight 88761（最高优先级）
* nice 19 → weight 15（最低优先级）
*
* vruntime 更新公式：
* vruntime += delta_exec × (NICE_0_LOAD / weight)
* delta_exec = 实际运行时间（纳秒）
*/
#define NICE_0_LOAD 1024
struct sched_entity {
int pid;
char comm[16];
unsigned long vruntime;
int nice;
int weight;
};
int nice_to_weight(int nice) {
static int weights[] = {
88761, 71755, 56483, 46273, 36291,
29154, 23254, 18705, 14949, 11916,
9548, 7620, 6100, 4904, 3906,
3121, 2501, 1991, 1586, 1277,
1024, 820, 655, 526, 423,
335, 272, 215, 172, 137,
110, 87, 70, 56, 45,
36, 29, 23, 18, 15,
};
return weights[nice + 20];
}
void update_vruntime(struct sched_entity *se, unsigned long delta_exec) {
/* vruntime += delta_exec × (NICE_0_LOAD / weight) */
se->vruntime += delta_exec * NICE_0_LOAD / se->weight;
}
int main() {
printf("=== 调度仙子 — vruntime 与 EEVDF 前夜 ===\n\n");
/* 两个进程，不同优先级 */
struct sched_entity shell = {
.pid = 100, .comm = "shell", .vruntime = 0, .nice = 0
};
struct sched_entity batch = {
.pid = 200, .comm = "batch", .vruntime = 0, .nice = 10
};
shell.weight = nice_to_weight(shell.nice);
batch.weight = nice_to_weight(batch.nice);
printf("进程 nice 权重 vruntime 初始\n");
printf("shell %3d %5d %lu\n", shell.nice, shell.weight, shell.vruntime);
printf("batch %3d %5d %lu\n\n", batch.nice, batch.weight, batch.vruntime);
/* 模拟两个进程各运行 10ms */
unsigned long delta = 10000000; /* 10ms = 10,000,000 ns */
printf("--- 各运行 10ms 后 ---\n");
update_vruntime(&shell, delta);
update_vruntime(&batch, delta);
printf("shell (nice=0): vruntime = %lu\n", shell.vruntime);
printf("batch (nice=10): vruntime = %lu\n\n", batch.vruntime);
printf("--- vruntime 增长对比 ---\n");
printf("shell (nice=0, weight=%d): 增长 %lu\n",
shell.weight, delta * NICE_0_LOAD / shell.weight);
printf("batch (nice=10, weight=%d): 增长 %lu\n",
batch.weight, delta * NICE_0_LOAD / batch.weight);
printf("\nbatch 的权重低，vruntime 增长更快\n");
printf("所以 CFS 会更频繁地选择 shell\n");
printf("\n--- 经典 CFS 的公平 ---\n");
printf("不是\"每个进程获得相同的 CPU 时间\"\n");
printf("而是\"每个进程的 vruntime 趋于相等\"\n");
printf("高优先级进程 vruntime 增长慢 → 更频繁被选中\n");
printf("低优先级进程 vruntime 增长快 → 更少被选中\n");
printf("\n--- EEVDF 的新问题 ---\n");
printf("只看 vruntime 还不够，还要看 lag 与 virtual deadline\n");
printf("lag >= 0: 任务被亏欠 CPU 时间，具备 eligible 的基础\n");
printf("deadline 更早: 更适合被优先选择\n");
return 0;
}道藏笔记
内核启示
CFS（完全公平调度器）是 Linux 普通任务公平调度的经典基础；现代 fair 调度正在向 EEVDF 演进。
核心数据结构：
- — 调度实体，包含
- — CFS 运行队列，包含红黑树
- — 包含
vruntime 更新公式：
vruntime += delta_exec × (NICE_0_LOAD / weight)- — 实际运行时间（纳秒）
- — nice 0 的权重（1024）
- — 进程的权重（由 nice 值决定）
CFS 的特性：
- 不使用固定时间片，使用"目标延迟"
- 在目标延迟内，所有进程至少运行一次
- 进程的实际运行时间与权重成正比
- 睡眠进程的 会被调整
EEVDF 的新尺度：
- 判断任务是否被亏欠 CPU 时间
- eligible 任务才进入选择范围
virtual deadline更早的任务更优先- 睡眠任务的 lag 需要衰减，避免短睡眠作弊
调度仙子的公平不是平均——是按权重分配，也是对真实负载的持续校准。
道藏复核
现代 fair 调度在经典 vruntime 之外，还引入哪两个指标来推进 EEVDF 的选择？