第六十八章：页分配器

元婴后期

涉及内核源码：

一

林小源在内景中继续探索，走到了一片奇特的区域。

这里的地面上刻满了整齐的线条，把大地划分成大小不一的方块。有的方块只有巴掌大，有的方块延伸到视野尽头。所有方块都排列得整整齐齐，像某种精密的棋盘。

"这是什么地方？"

"伙伴系统的领地。"mm_struct 说，"物理页面的分配器。"

林小源蹲下来，用手指沿着一条刻线划过。刻线很深，像是用刀刻出来的。他注意到每条刻线旁边都刻着一个数字——0、1、2、3……一直排到 10。

"那些数字是什么？"

"阶。"一个声音从旁边传来。

林小源转头，看到一个穿着白色长袍的修行者站在不远处。他的袍子上绣满了二进制的数字，双手各持一块方木，像积木一样在手里翻转。他的眼睛很锐利，像在丈量什么东西。

"我是伙伴系统。"白袍修行者说，"负责分配物理页面。你看到的这些方块，每一个都是一个空闲块。"

他把右手的方木放在地上。方木落地的瞬间，地面上出现了一个方块——2 阶，4 页大小。

"阶是什么意思？"林小源问。

"2 的幂次。"伙伴系统说，"0 阶是 1 页，1 阶是 2 页，2 阶是 4 页，3 阶是 8 页……以此类推。我只分配 2 的幂次大小的块。"

"那如果我只需要 2 页呢？"

"1 阶。"伙伴系统说，"但如果我手上没有 1 阶的块——只有 10 阶的，也就是 1024 页——那我就得把它拆开。"

他拿起左手的方木，用力一掰。方木裂成两半，一半大一半小——不，两半一样大，都是 9 阶。他把其中一半放在地上，另一半继续掰。9 阶变成两个 8 阶。8 阶变成两个 7 阶。一路掰下去，直到掰出两个 1 阶的块。

"把一个给你。"他把其中一块递给林小源，"另一个放回空闲列表。"

林小源接过那块方木。它很轻，只有 2 页大小，但拿在手里有一种奇怪的"完整感"——它是一个不可再分的最小单位。

"这就是分配？"

"这就是分配。"伙伴系统说，"从大块拆出小块。简单，但有效。"

二

林小源把玩着手里那块 1 阶方木，忽然想到了一个问题。

"如果我把这块还给你呢？"

"释放。"伙伴系统说，"释放的时候，我会检查你的'伙伴'是不是也空闲。如果是——我就把你们合并成更大的块。"

"伙伴？"

伙伴系统蹲下来，在地面上画了两块相邻的方块。它们一样大，紧挨在一起。

"这两个就是伙伴。"他说，"它们的大小相同，地址相邻。判断两个块是不是伙伴，只需要一个公式——"他在地面上写下一串符号：

buddy = page ^ (1 << order)

"异或运算。"他说，"把页帧号和 1 左移 order 位做异或，得到的就是伙伴的页帧号。如果伙伴也在空闲列表里，就合并。"

林小源看着那个公式。异或——相同为 0，不同为 1。两个相邻的块，它们的页帧号只在某一位上不同，异或那一位就能找到对方。

"如果合并之后，更大的块也有空闲的伙伴呢？"

"继续合并。"伙伴系统说，"递归地合并，直到不能合并为止。两个 1 阶合并成 2 阶，两个 2 阶合并成 3 阶，一直合并上去。"

他拿起地上那两块方木，合在一起。两块 1 阶变成了一块 2 阶。他又拿起旁边另一块 2 阶，合在一起——变成了一块 3 阶。

"合并是释放的灵魂。"他说，"如果不合并，内存会碎片化——到处都是零散的小块，没有连续的大块。合并能把碎片重新拼成整体。"

林小源看着他手里的方木越合越大，从 3 阶变成 4 阶，从 4 阶变成 5 阶。每合并一次，方木就变大一倍，颜色也变深一些。

"但不是所有碎片都能合并。"伙伴系统突然停了手，"如果两个伙伴中有一个正在被使用——就合并不了。碎片就永远留在那里了。"

他把手里那块没合并成功的方木放在地上。它孤零零的，旁边没有伙伴。

"这是外部碎片。"他说，"伙伴系统能减少它，但不能消灭它。"

三

林小源在棋盘般的地面上走了一圈，心里渐渐有了一个画面。

伙伴系统就像一个精密的工匠。它手里的材料是物理页面——整个系统的物理内存。它把这些页面组织成大小不等的块，像搭积木一样拆分和合并。

"你一共管理多少页面？"他问。

"看系统有多少物理内存。"伙伴系统说，"如果你有 4GB 内存，那就是 1048576 页。我把它们组织成 0 到 10 阶的块，放在 11 个空闲列表里。"

他伸出手，指向远方。林小源顺着他的手指望去——远处有 11 个发光的柱子，从左到右排列，高度递增。最左边的柱子最矮，上面放着密密麻麻的小方块——0 阶的，1 页大小。最右边的柱子最高，上面只放着几个大方块——10 阶的，1024 页大小。

"分配的时候，我从最小的能满足需求的柱子上取。"伙伴系统说，"如果那个柱子是空的，就从更大的柱子上拆。"

"如果所有柱子都是空的呢？"

伙伴系统看了他一眼。眼神很平静，但林小源在里面看到了一丝无奈。

"那就是 OOM 了。"他说，"Out of Memory。分配失败。内核会杀死一个进程，释放它的页面，然后重试。"

林小源沉默了。他看着那 11 个发光的柱子，想着整个系统的物理内存就在这些柱子上。每一次分配都是从柱子上取走一块，每一次释放都是往柱子上放回一块。柱子的高低起伏，就是系统内存压力的真实写照。

"你很累吧？"他问。

伙伴系统没有回答。他只是弯下腰，从 10 阶的柱子上取下一个大方块，开始拆分。4MB 变成 2MB，2MB 变成 1MB，1MB 变成 512KB——一路拆下去，直到拆出客户需要的大小。

他的动作很熟练，但林小源注意到他的手在微微发抖。

"每秒可能有上千次分配请求。"mm_struct 的声音从远处飘来，"他从不停歇。"

---

/*
 * 伙伴系统 (Buddy System) 的工作原理：
 *
 * 1. 把空闲页面组织成 2^n 大小的块
 *    0 阶: 1 页 (4KB)
 *    1 阶: 2 页 (8KB)
 *    2 阶: 4 页 (16KB)
 *    ...
 *    10 阶: 1024 页 (4MB)
 *
 * 2. 分配时:
 *    找到 >= 请求大小的最小块
 *    如果块太大，拆分成两个"伙伴"
 *    返回其中一个，另一个放回空闲列表
 *
 * 3. 释放时:
 *    检查"伙伴"是否空闲
 *    如果空闲，合并成更大的块
 *    递归检查，直到不能合并
 *
 * "伙伴"的定义：
 *   两个大小相同的块，地址满足:
 *   buddy = page ^ (1 << order)
 */

struct free_area {
    int nr_free;        /* 空闲块数量 */
    int block_size;     /* 块大小（页数） */
};

printf("=== 伙伴系统 — 页面分配器 ===\n\n");

/* 初始化空闲列表 */
struct free_area free_areas[11];  /* 0-10 阶 */
for (int i = 0; i <= 10; i++) {
    free_areas[i].nr_free = 0;
    free_areas[i].block_size = 1 << i;
}

/* 初始状态：一个 4MB 的空闲块 (10 阶) */
free_areas[10].nr_free = 1;

printf("初始空闲列表：\n");
for (int i = 0; i <= 10; i++) {
    if (free_areas[i].nr_free > 0)
        printf("  阶 %d: %d 块 × %d 页 = %d 页\n",
               i, free_areas[i].nr_free,
               free_areas[i].block_size,
               free_areas[i].nr_free * free_areas[i].block_size);
}

/* 分配 8KB (2 页, 1 阶) */
printf("\n--- 分配 8KB (2 页) ---\n");
printf("需要 1 阶的块\n");
printf("10 阶拆分: 4MB → 2×2MB\n");
printf("  9 阶: 1 块\n");
printf("9 阶拆分: 2MB → 2×1MB\n");
printf("  8 阶: 1 块\n");
printf("8 阶拆分: 1MB → 2×512KB\n");
printf("  7 阶: 1 块\n");
printf("...继续拆分...\n");
printf("1 阶: 分配 1 块\n\n");

/* 模拟拆分后的状态 */
free_areas[10].nr_free = 0;
free_areas[9].nr_free = 1;
free_areas[8].nr_free = 1;
free_areas[7].nr_free = 1;
free_areas[6].nr_free = 1;
free_areas[5].nr_free = 1;
free_areas[4].nr_free = 1;
free_areas[3].nr_free = 1;
free_areas[2].nr_free = 1;
free_areas[1].nr_free = 0;  /* 已分配 */
free_areas[0].nr_free = 2;  /* 伙伴 */

printf("分配后空闲列表：\n");
for (int i = 0; i <= 10; i++) {
    if (free_areas[i].nr_free > 0)
        printf("  阶 %d: %d 块 × %d 页\n",
               i, free_areas[i].nr_free, free_areas[i].block_size);
}

printf("\n--- 释放时合并 ---\n");
printf("释放 1 阶的块\n");
printf("检查伙伴: 1 阶的伙伴也空闲\n");
printf("合并: 2 × 1阶 → 1 × 2阶\n");
printf("继续检查 2 阶的伙伴...\n");

printf("\n--- 伙伴系统的优势 ---\n");
printf("1. 减少外部碎片\n");
printf("2. 分配/释放都是 O(log n)\n");
printf("3. 合并简单: buddy = page ^ (1 << order)\n");

---

道藏笔记

内核启示

伙伴系统是内核分配物理页面的核心算法。

伙伴系统的组织：

• 空闲页面组织成 2^n 大小的块
• 0 阶: 1 页 (4KB)
• 10 阶: 1024 页 (4MB)

分配过程：

1. 找到 >= 请求大小的最小块
2. 如果块太大，拆分成两个"伙伴"
3. 返回其中一个，另一个放回空闲列表

释放过程：

1. 检查"伙伴"是否空闲
2. 如果空闲，合并成更大的块
3. 递归检查，直到不能合并

"伙伴"的定义：

• buddy = page ^ (1 << order)
• 简单的异或运算

伙伴系统是物理页面分配的"基石"——拆分与合并的艺术。

---

破关试炼

页分配器之试

页分配器合并相邻空闲块时，本章给出的伙伴页计算公式是什么？

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

← 上一回下一回 →