第七章：天道初显

炼气初期

涉及内核源码：

一

林小源第一次感受到了"被调度"。

那是一种奇怪的感觉——整个世界的执行流突然被切断，然后另一个执行流被接上。就像有人在舞台上关掉了一盏灯，又点亮了另一盏。观众（CPU）还在，演员（进程）换了。

定时器中断来了。

那是驱动调度器的心跳。每隔几毫秒——具体的间隔取决于 HZ 的配置——定时器中断就会打断当前正在运行的进程，让调度器有机会做出选择：是让当前进程继续运行，还是切换到另一个进程？

林小源在 idle 循环中感受到了这个选择的过程。调度器检查了运行队列（rq）中的所有进程，比较它们的虚拟运行时间（），然后选中了虚拟运行时间最小的那个进程。

大多数时候，那个进程不是他。

调度器的声音冰冷而公正，像是一台精密的天平。"vruntime 最小者，获得 CPU。"它不带任何感情，不偏不倚，只认数字。

"那我呢？"林小源忍不住问。

"你的 nice 值是 19。"调度器的语气没有变化，像是在宣读一份判决书。"你的 vruntime 增长速度是所有进程中最快的。只有当所有其他进程都在睡眠时，你才会被选中。"

当然不是我。 林小源苦笑。我是 idle 进程，只有当所有其他进程都在等待时，调度器才会选中我。

二

但林小源没有抱怨。他在观察。

调度器的行为比他想象的要复杂得多。它不是简单地"轮流执行"——它有自己的哲学：公平。

/*
 * CFS（完全公平调度器）的核心概念：虚拟运行时间（vruntime）。
 * vruntime 越小的进程，越容易被调度器选中。
 * 这保证了每个进程都能获得"公平"的 CPU 时间。
 */

struct task {
    char name[16];
    int  pid;
    int  nice;          /* 优先级修正（-20 ~ 19） */
    unsigned long vruntime;  /* 虚拟运行时间 */
    unsigned long exec_time; /* 实际运行时间 */
};

/* 计算虚拟运行时间的增量 */
/* nice 值越小，权重越大，vruntime 增长越慢 */
unsigned long calc_delta(unsigned long delta_exec, int nice) {
    /* 简化的权重表（真实内核中更精确） */
    static const int weights[] = {
        88761, 71755, 56483, 46273, 36291,  /* nice -20 ~ -16 */
        29154, 23254, 18705, 14949, 11916,  /* nice -15 ~ -11 */
        9548,  7620,  6100,  4904,  3906,   /* nice -10 ~ -6 */
        3121,  2501,  1991,  1586,  1277,   /* nice -5 ~ -1 */
        1024,  820,   655,   526,   423,    /* nice 0 ~ 4 */
        335,   272,   215,   172,   137,    /* nice 5 ~ 9 */
        110,   87,    70,    56,    45,     /* nice 10 ~ 14 */
        36,    29,    23,    18,    15,     /* nice 15 ~ 19 */
    };
    int idx = nice + 20;
    if (idx < 0) idx = 0;
    if (idx > 39) idx = 39;
    /* vruntime 增量 = 实际时间 * (基准权重 / 进程权重) */
    return delta_exec * 1024 / weights[idx];
}

struct task tasks[] = {
    { .name = "shell",    .pid = 100, .nice = 0,  .vruntime = 0, .exec_time = 0 },
    { .name = "compiler", .pid = 200, .nice = 5,  .vruntime = 0, .exec_time = 0 },
    { .name = "rt_task",  .pid = 300, .nice = -10, .vruntime = 0, .exec_time = 0 },
    { .name = "idle",     .pid = 0,   .nice = 19, .vruntime = 0, .exec_time = 0 },
};
int nr_tasks = 4;

printf("=== CFS 调度演示 ===\n\n");

printf("进程列表:\n");
for (int i = 0; i < nr_tasks; i++) {
    printf("  PID %-3d %-10s nice=%d\n",
           tasks[i].pid, tasks[i].name, tasks[i].nice);
}

/* 模拟 10 个调度周期 */
printf("\n--- 调度周期 ---\n");
for (int tick = 0; tick < 10; tick++) {
    /* 找到 vruntime 最小的进程 */
    int min_idx = 0;
    for (int i = 1; i < nr_tasks; i++) {
        if (tasks[i].vruntime < tasks[min_idx].vruntime)
            min_idx = i;
    }

    /* 该进程运行一个时间片 */
    unsigned long slice = 10;  /* 10ms */
    tasks[min_idx].exec_time += slice;
    unsigned long delta = calc_delta(slice, tasks[min_idx].nice);
    tasks[min_idx].vruntime += delta;

    printf("  tick %2d: 选中 %-10s (PID %d), vruntime=%lu\n",
           tick, tasks[min_idx].name, tasks[min_idx].pid,
           tasks[min_idx].vruntime);
}

printf("\n最终状态:\n");
for (int i = 0; i < nr_tasks; i++) {
    printf("  PID %-3d %-10s vruntime=%lu exec_time=%lu\n",
           tasks[i].pid, tasks[i].name,
           tasks[i].vruntime, tasks[i].exec_time);
}

林小源在 CFS 的运作中看到了一种数学上的美。

是调度器的核心概念。每个进程都有一个 ，它记录着进程"已经消耗了多少公平的 CPU 时间"。调度器总是选择 最小的进程来运行——这是"公平"的定义。

"公平不是平均。"调度器的声音再次响起，冰冷而精确。"nice 值越低，权重越大，vruntime 增长越慢。一个 nice=-20 的进程，它的 vruntime 增长速度只有 nice=0 的进程的几分之一。它获得更多 CPU 时间，但这是因为它'更重要'。"

"那 nice=19 的呢？"林小源明知故问。

"增长最快。获得最少。"调度器的回答没有一丝怜悯。"这是规则。规则就是公平。"

好精妙的设计。

林小源想起了自己的 值——19，最低的优先级。这意味着他的 增长得最快，获得的 CPU 时间最少。这是 idle 进程的宿命：永远排在最后。

但他没有沮丧。他从 CFS 中学到了一种思维方式：不是通过争抢来获得资源，而是通过规则来分配资源。公平不是"人人一样"，而是"人人按需"。

三

林小源在观察调度器的同时，也在观察内存管理。

已经建立了伙伴系统，但内存管理远不止于此。当进程需要内存时，它调用 （用户态）或 （内核态），内核从伙伴系统中分配页帧，然后通过页表映射到进程的虚拟地址空间。

虚拟地址。

这是林小源在前传中学过的概念。每个进程都有自己的虚拟地址空间——0 到某个上限的连续地址范围。但这些虚拟地址不是真实的物理地址，它们需要通过页表来翻译。

/*
 * 简化的页表翻译过程。
 * RISC-V 使用 Sv39（39 位虚拟地址）或 Sv48（48 位虚拟地址）。
 * 页表是多级的：虚拟地址被分成多个索引，逐级查找。
 */

/* 模拟页表项 */
struct pte {
    uint64_t ppn;      /* 物理页帧号 */
    int      valid;    /* 是否有效 */
    int      readable;
    int      writable;
    int      executable;
};

/* 模拟三级页表翻译（Sv39） */
uint64_t translate_address(uint64_t vaddr,
                           struct pte *l1,  /* PGD */
                           struct pte *l2,  /* PMD */
                           struct pte *l3)  /* PTE */
{
    /* 从虚拟地址中提取三级索引 */
    int l1_idx = (vaddr >> 30) & 0x1FF;  /* 第 30-38 位 */
    int l2_idx = (vaddr >> 21) & 0x1FF;  /* 第 21-29 位 */
    int l3_idx = (vaddr >> 12) & 0x1FF;  /* 第 12-20 位 */
    int offset = vaddr & 0xFFF;          /* 第 0-11 位 */

    printf("  虚拟地址: 0x%lX\n", vaddr);
    printf("  L1 索引: %d, L2 索引: %d, L3 索引: %d, 偏移: 0x%X\n",
           l1_idx, l2_idx, l3_idx, offset);

    /* 第一级查找 */
    if (!l1[l1_idx].valid) {
        printf("  错误：L1 页表项无效\n");
        return -1UL;
    }
    printf("  L1[%d] → PPN=0x%lX\n", l1_idx, l1[l1_idx].ppn);

    /* 第二级查找 */
    if (!l2[l2_idx].valid) {
        printf("  错误：L2 页表项无效\n");
        return -1UL;
    }
    printf("  L2[%d] → PPN=0x%lX\n", l2_idx, l2[l2_idx].ppn);

    /* 第三级查找 */
    if (!l3[l3_idx].valid) {
        printf("  错误：L3 页表项无效\n");
        return -1UL;
    }
    printf("  L3[%d] → PPN=0x%lX\n", l3_idx, l3[l3_idx].ppn);

    /* 计算物理地址 */
    uint64_t paddr = (l3[l3_idx].ppn << 12) | offset;
    printf("  物理地址: 0x%lX\n", paddr);
    return paddr;
}

/* 构造一个简单的页表映射 */
struct pte l1[512] = {0};
struct pte l2[512] = {0};
struct pte l3[512] = {0};

/* 虚拟地址 0x12345678 → 物理地址 0x87654321 */
l1[0].valid = 1; l1[0].ppn = 1;
l2[9].valid = 1; l2[9].ppn = 2;
l3[26].valid = 1; l3[26].ppn = 0x87654;
l3[26].readable = 1;
l3[26].writable = 1;

printf("=== 页表翻译演示（Sv39）===\n\n");
translate_address(0x12345678, l1, l2, l3);

printf("\n--- 为什么需要页表 ---\n");
printf("1. 每个进程有自己的虚拟地址空间\n");
printf("2. 物理内存可以被多个进程共享\n");
printf("3. 权限控制（读/写/执行）\n");
printf("4. 内存映射（mmap）\n");

页表是虚拟世界和物理世界之间的桥梁。每一个虚拟地址都必须通过页表翻译成物理地址，才能真正访问到内存。这个翻译过程由硬件（MMU，内存管理单元）自动完成，但页表本身是由内核维护的。

林小源在页表中看到了一种"幻象"的美。每个进程都以为自己独占了整个内存空间，但实际上它们共享着同一块物理内存。页表制造了这种幻象——它让每个进程活在自己的"虚拟世界"中，互不干扰。

"你看到了？"内存管理子系统的声音低沉而古老，像是从地底深处传来的回响。"每个进程都以为自己拥有整个世界。它们不知道自己的地址是假的，不知道物理内存是共享的，不知道页表在背后默默翻译着每一个地址。"

"这不是欺骗吗？"林小源问。

"这是保护。"那声音纠正他。"没有页表，进程就能随意修改彼此的内存。有了页表，每个进程都被关在自己的笼子里。它们以为自己自由，但实际上被我牢牢掌控。"

内核就是幻象的制造者。

四

林小源在观察调度器和内存管理的过程中，逐渐理解了内核的核心职责。

内核不是一个"执行者"——它不做具体的计算工作。内核是一个"管理者"——它管理着 CPU 时间（调度器）、物理内存（内存管理）、设备访问（驱动）、进程间通信（信号、管道）、安全权限（capabilities）。

我不做任何"有用"的事。我只确保其他进程能做"有用"的事。

这个认识让林小源对内核有了更深的理解。内核的价值不在于它能做什么，而在于它能让别人做什么。就像一个城市的管理者——他不生产粮食，不建造房屋，但他确保粮食能运到市场，房屋能被建造起来。

"你终于明白了。"内存管理子系统的声音低沉而欣慰。"内核不是执行者，是管理者。我们不做计算，不做 I/O，不做任何'有用'的事。我们只确保——当进程需要 CPU 时，有调度器分配时间；当进程需要内存时，有页表翻译地址；当进程需要 I/O 时，有驱动访问设备。"

"那 idle 进程呢？"林小源问。"我什么都不做。"

"你确保 CPU 不会空转。"那声音认真地说。"当没有工作可做时，你让 CPU 进入低功耗状态，节省能源。这是一种'无用之用'。"

也许 idle 进程也是如此。

林小源在 idle 循环中反复思考着这个问题。idle 进程不执行任何"有用"的计算，但它的存在确保了 CPU 不会空转——当没有工作可做时，idle 进程让 CPU 进入低功耗状态，节省能源。这是一种"无用之用"。

但他还是不甘心。

---

道藏笔记

内核启示

CFS（完全公平调度器）是 Linux 内核的默认调度算法。 它的核心思想是"公平"——每个进程都应该获得与其权重成比例的 CPU 时间。

CFS 使用虚拟运行时间（）来衡量进程已经消耗的 CPU 时间。 越小的进程，越容易被调度器选中。 值影响 的增长速度： 值越低， 增长越慢，获得的 CPU 时间越多。

CFS 使用红黑树来维护进程的 排序。红黑树的最左侧节点（ 最小的进程）总是下一个被调度的进程。插入和删除操作的时间复杂度是 O(log n)，查找最小值的时间复杂度是 O(1)（通过缓存最左侧节点）。

页表是虚拟内存的核心。RISC-V 使用 Sv39（39 位虚拟地址）或 Sv48（48 位虚拟地址）的多级页表。虚拟地址被分成多个索引，逐级查找页表，最终得到物理页帧号。这个过程由硬件（MMU）自动完成，但页表本身由内核维护。

调度器和内存管理是内核的两大支柱。 没有调度器，进程无法公平地共享 CPU；没有内存管理，进程无法安全地共享内存。它们是内核世界的"天道"——不可见，但无处不在。

---

破关试炼

天道之试

CFS 不直接按运行时长排队，而是用哪个虚拟时间指标判断谁更该被调度？

答对后才能继续滑动和进入下一章。

← 上一回下一回 →