从零写OS内核 | 物理内存管理——Buddy System 伙伴系统

一个 64KB 的内存请求，你手上最小的空闲块是 128KB——你是把它切成两半用一半留一半，还是直接分出去？

这就是 Buddy System 要解决的核心问题。

物理内存管理是内核最核心的基础设施之一。当你的程序需要内存时，内核要在物理内存中找到一块合适的空间分配出去，同时还要能把它回收回来、合并回去、再次利用。Buddy System 是 Linux 原生使用的物理页分配算法，也是 wandos 正在努力实现的核心模块。

今天，我们来把它彻底搞清楚。

1. 为什么需要Buddy System

直接用”最佳匹配”（Best Fit）可以吗？可以，但你很快会遇到一个问题：内存碎片化。

假设你有一个 1MB 的空闲内存块，程序依次请求：64KB、64KB、64KB、64KB。你分配了 4 个 64KB 块。现在程序释放了第 2 和第 4 块，你还有 128KB 空闲，但它们不连续——中间夹着第 1 和第 3 块。

Bash

内存碎片化示意图：

[64KB][64KB][64KB][64KB]  初始分配
[ALLOC][64KB][ALLOC][64KB]  释放了第2、4块
      ↑
      这两个64KB不连续，无法合并成128KB给大请求用

这就是外部碎片（External Fragmentation）：空闲内存的总和足够，但物理上不连续，无法满足大块请求。

Buddy System 用一种简单但有效的策略解决这个问题：按2的幂次方分配，每次分裂都是”对半劈”，每次合并都是”遇到好邻居就合并”。

2. Buddy System 工作原理

2.1 核心规则：分裂与合并

分配时：

从请求的大小出发，找到最接近的 2ⁿ 页（比如请求 7页 → 找 8页）
在对应大小的空闲链表中查找
如果没有，向上找更大的块（2ⁿ⁺¹），分裂成两个”伙伴”
递归，直到找到合适的块

释放时：

释放这个块
检查它的”伙伴块”（同一父块分裂出来的两个块之一）是否也空闲
如果伙伴也空闲，合并成更大的块
递归向上，直到无法合并

Bash

Buddy System 分裂与合并示意：

层级     块大小      空闲链表
2⁽⁵⁾   32页 (128KB)
          ↓ 分裂
2⁽⁴⁾   16页        [A][B]        ← A和B是伙伴
          ↓ B被分配
2⁽⁴⁾   16页        [A]           ← 只剩A
          ↓ A被释放，检查伙伴B
          ↑ B还在空闲，合并
2⁽⁵⁾   32页                      ← 合并回层级5

2.2 伙伴块的定义

两个块是”伙伴”，必须满足：

大小相同（都是 2ⁿ 页）
物理地址连续
起始地址是 2^(n+1) 页的倍数

第 3 条是关键——给定一个块的起始地址，你可以通过公式算出它伙伴的地址：

Bash

假设块起始地址 = A，大小 = 2ⁿ 页（每页 4KB）

伙伴地址 = A + 2ⁿ × 4096  （如果A是较低地址块）
         = A - 2ⁿ × 4096  （如果A是较高地址块）

或者用位运算（假设起始地址对齐）：
伙伴 = A ^ (2ⁿ × 4096)   ← 用异或切换对应的位

这就是为什么 Buddy System 要求分配大小必须是 2 的幂次——只有这样，伙伴地址才能通过简单的位运算得到。

2.3 空闲链表结构

Buddy System 用一组空闲链表（free_list）来管理每个大小级别的空闲块：

Bash

┌─────────────────────────────────────────────────────────────┐
│  free_area[0]  →  单页块链表（4KB）                           │
│  free_area[1]  →  两页块链表（8KB）                           │
│  free_area[2]  →  四页块链表（16KB）                          │
│  free_area[3]  →  八页块链表（32KB）                          │
│  free_area[4]  →  十六页块链表（64KB）                        │
│  ...                                                         │
│  free_area[MAX_ORDER-1]  →  最大阶（通常 10 或 11）           │
└─────────────────────────────────────────────────────────────┘

每个 free_area 节点：
struct free_area {
    struct list_head free_list;  // 空闲块链表头
    unsigned long nr_free;       // 该级别空闲块数量
}

Linux 的 MAX_ORDER 默认是 11，意味着最大分配单元是 2^10 = 1024 个连续页（4MB）。

3. 分配算法详细流程

以分配 17 页为例，走一遍完整流程：

Bash

请求：17页 → 最接近的 2ⁿ = 32页（2⁵）

Step 1: 检查 free_area[5]（32页链表）
        → 链表为空，没有现成的 32页块

Step 2: 向上找 free_area[6]（64页链表）
        → 链表为空

Step 3: 继续向上 free_area[7]（128页链表）
        → 找到一个块，把它分裂成两个 64页块
        → 两个 64页块互为伙伴，分别加入 free_area[6]
        → 重新检查 free_area[6]

Step 4: free_area[6] 现在有两个 64页块
        → 取其中一个（假设地址较低的），分裂成两个 32页块
        → 两个 32页块互为伙伴，加入 free_area[5]
        → 重新检查 free_area[5]

Step 5: free_area[5] 现在有两个 32页块
        → 取其中一个，分配出去
        → 返回起始地址

结果：分配了 32页（因为 17页最近接 32页）

向上分裂的代价是可能浪费内存（Internal Fragmentation）——请求 17页实际给了 32页，多给了 15页。但换来的是分配和回收的 O(1) 复杂度，以及合并的简单性。

4. 合并的逆向过程

释放 32页块（起始地址 A）：

Bash

Step 1: 加入 free_area[5]（32页链表）

Step 2: 计算伙伴地址
        伙伴 = A ^ (32 × 4096) = A ^ 0x20000

Step 3: 检查伙伴块是否也在 free_area[5] 里且空闲
        → 如果是，合并成 64页块，从 free_area[5] 删除两个块

Step 4: 把合并后的 64页块加入 free_area[6]

Step 5: 重复：计算 64页块的伙伴，是否也在 free_area[6]
        → 如果是，合并成 128页块，加入 free_area[7]
        → 继续向上，直到层顶

合并的最大收益：不会产生无法使用的小碎片。只要两个伙伴都空闲，就一定合并；合并后的块如果和它的新伙伴也空闲，继续合并。

5. Linux 实践：查看 Buddy System 状态

在 Linux 系统上，你可以直接看到 Buddy System 的状态：

Bash

# 查看每个阶的空闲页数量（/proc/buddyinfo）
cat /proc/buddyinfo

Node 0, zone      DMA      1      0      1      1      2      1      1      0      1      3
Node 0, zone    DMA32    412   1023    890    445    123     89     34     15      7      3
Node 0, zone   Normal   8901   3421    567    234    112     45     12      5      2      1

解读：每列从左到右是 2⁰, 2¹, 2², ... 2⁹ 页（即1页、2页、4页...512页）
     DMA 区域 Node 0 有 1 个单页、0 个两页、1 个四页、1 个八页...

Bash

# 观察内存分配时 Buddy 的变化（vmstat 1）
vmstat 1

procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 0  0      0 655360  12340 234567    0    0     0     0   34   12  5  2 93  0  0

# free 列下降 → Buddy System 在分配
# 每秒刷新看变化趋势

Bash

# 触发内存分配，观察阶的变化
# 分配 100MB 内存然后释放，看阶如何恢复
python3 -c &quot;
import os
a = []
for i in range(25600):  # 分配约100MB (25600 * 4KB)
    a.append(bytearray(4096))
&quot; &amp;
sleep 2
cat /proc/buddyinfo
# 观察 Normal 区域的各阶数字变化

Bash

# 手动查看具体页分配情况
cat /proc/pagetypeinfo

Node 0, zone    DMA32  全忙页数  空闲页数  ...
Node 0, zone   Normal 全忙页数  空闲页数  ...

6. 从零实现：wandos 的 Buddy System

⚠️ wandos 当前状态：wandos 的 kernel/memory/ 目录下有 slab_allocator.cpp 和 paging.cpp，但没有独立的 Buddy System 实现。以下展示的是基于 wandos 内存管理架构的分析，以及如果要实现 Buddy 需要怎么写。

6.1 核心数据结构

Cpp

// wandos 风格的 Buddy 实现（需要新建 kernel/memory/buddy.cpp）

#define PAGE_SIZE       4096
#define MAX_ORDER       10          // 最大 2^10 = 1024 页 = 4MB
#define NR_ZONES        1

struct page {
    unsigned long flags;             // 页面状态标志
    unsigned int order;              // 如果在空闲链表，记录阶数
    struct page *next;              // 链表 next 指针
    struct page **prev;             // 链表 prev 指针（用于 O(1) 删除）
};

struct free_area {
    struct list_head free_list;
    unsigned long nr_free;
};

// 全局管理结构
struct zone {
    unsigned long start_pfn;        // 起始页帧号
    unsigned long end_pfn;          // 结束页帧号
    unsigned long managed_pages;    // 可管理的页数
    struct free_area free_area[MAX_ORDER + 1];
};

// 全局变量
static struct zone memory_zones[NR_ZONES];

6.2 分配函数

Cpp

// 分配 2^order 个连续物理页
struct page *alloc_pages(unsigned int order) {
    struct zone *zone = &amp;memory_zones[0];

    // Step 1: 在请求的阶查找
    unsigned int current_order = order;
    while (current_order &lt;= MAX_ORDER) {
        struct free_area *area = &amp;zone-&gt;free_area[current_order];
        if (!list_empty(&amp;area-&gt;free_list)) {
            // 找到空闲块，分配出去
            struct page *page = list_entry(area-&gt;free_list.next, struct page, list);
            list_del(&amp;page-&gt;list);
            area-&gt;nr_free--;
            page-&gt;order = order;
            return page;
        }
        current_order++;
    }

    // Step 2: 向上分裂
    // 从比请求更大的阶开始分裂
    // （实际实现需要从当前找到的最高阶分裂，这里是简化逻辑）
    return NULL;  // 分配失败
}

// 内部分裂逻辑
static struct page *split_buddy(struct zone *zone, unsigned int target_order) {
    // 找到第一个有空闲块的阶
    int start_order = MAX_ORDER;
    for (int i = MAX_ORDER; i &gt;= target_order; i--) {
        if (!list_empty(&amp;zone-&gt;free_area[i].free_list)) {
            start_order = i;
            break;
        }
    }
    if (start_order &lt; target_order) return NULL;

    // 从高阶向下分裂到目标阶
    struct page *page = list_entry(zone-&gt;free_area[start_order].free_list.next,
                                    struct page, list);
    list_del(&amp;page-&gt;list);
    zone-&gt;free_area[start_order].nr_free--;

    // 逐层分裂
    for (int cur = start_order; cur &gt; target_order; cur--) {
        struct page *buddy = page + (1 &lt;&lt; (cur - 1));
        buddy-&gt;order = cur - 1;
        list_add(&amp;buddy-&gt;list, &amp;zone-&gt;free_area[cur - 1].free_list);
        zone-&gt;free_area[cur - 1].nr_free++;
    }

    page-&gt;order = target_order;
    return page;
}

6.3 释放函数

Cpp

// 释放 2^order 个连续物理页（起始地址 page）
void free_pages(struct page *page, unsigned int order) {
    struct zone *zone = &memory_zones[0];
    unsigned long pfn = page - pages;  // 页帧号
    unsigned int current_order = order;

    // 把块加入对应阶的空闲链表
    list_add(&page->list, &zone->free_area[current_order].free_list);
    zone->free_area[current_order].nr_free++;
    page->order = current_order;

    // 尝试合并
    while (current_order < MAX_ORDER) {
        unsigned long buddy_pfn = pfn ^ (1 << current_order);
        struct page *buddy = &pages[buddy_pfn];

        // 检查伙伴是否也在同一阶且空闲
        if (buddy_pfn >= zone->end_pfn - zone->start_pfn)
            break;  // 超出 zone 范围
        if (buddy->order != current_order)
            break;  // 伙伴不是空闲的
        if (!page_in_free_area(buddy, current_order))
            break;  // 伙伴不在正确的链表里

        // 伙伴空闲，合并
        list_del(&buddy->list);
        zone->free_area[current_order].nr_free--;

        // 合并后的块起始地址是较小的那一个
        if (buddy_pfn < pfn)
            page = buddy;
        pfn = (pfn & ~(1 << current_order));  // 清除当前阶对应位
        current_order++;
    }
}

6.4 wandos 现有实现分析

wandos 当前的 slab_allocator.cpp 是建立在 Buddy System 之上的更细粒度分配器——Buddy System 负责分配物理页，SLAB 在这些物理页之上管理对象缓存。paging.cpp 负责虚拟地址到物理页的映射。

所以 wandos 如果要实现 Buddy System，需要：

建立物理页帧管理（page 结构体数组）
实现 free_area 数组和空闲链表
实现 alloc_pages() / free_pages()
slab_allocator.cpp 调用 Buddy 分配的页，而不是直接请求物理内存

7. 动手环节：实现一个简易Buddy分配器

今天的目标：在 os-kernel-from-scratch 里实现一个简单的 Buddy System 分配器，用 C 语言写出能在用户态运行的演示版本。

任务 1：实现空闲块分裂函数

给定一个 2^k 页的块，分裂成两个 2^(k-1) 页的块，把其中一个加入 free_area[k-1]，返回另一个用于分配。

// 提示：伙伴地址 = address ^ (PAGE_SIZE * (1 &lt;&lt; (order - 1)))

任务 2：实现合并函数

给定一个空闲块，检查它的伙伴是否也空闲，如果是则合并，递归向上。

任务 3：实现 `buddy_alloc()` 和 `buddy_free()`

void *buddy_alloc(int order);   // 分配 2^order 页
void buddy_free(void *addr, int order);  // 释放

验收标准

buddy_alloc(0) 连续调用 10 次，再 buddy_free 全部 10 次，不崩溃
buddy_alloc(3) 分配 8 页，释放后再次 buddy_alloc(3) 能拿到相同或更大的块
检查 /proc/buddyinfo 阶分布是否符合预期（分配后高阶块减少，释放后高阶块恢复）

8. 踩坑与注意事项

坑 1：页帧号（PFN）和物理地址混淆

PFN = 物理地址 / PAGE_SIZE。访问 pages[pfn].flags 时，物理地址要转成 PFN 再索引。如果直接用物理地址除以 PAGE_SIZE 得到偏移量，需要确认 pages 数组是从 0 开始的还是从 zone->start_pfn 开始的。

坑 2：合并时边界检查

合并到 zone 边缘时，伙伴可能超出 zone 范围。要在合并前检查 buddy_pfn < zone->end_pfn，否则会访问到无效的 page 结构体。

坑 3：最大阶的限制

MAX_ORDER 不是越大越好。如果设置成 20，意味着最大分配 2^20 页 = 4GB，这在单处理器上不现实。通常 10（4MB）或 11（8MB）是合理上限。

坑 4：内存对齐

Buddy System 依赖起始地址对齐来计算伙伴地址。如果内存不是从 0 开始的（比如有 BIOS 保留区），需要把所有计算基于 PFN（页帧号）而不是绝对物理地址，这样无论内存从哪个地址开始，算法都正确。

写在最后

Buddy System 的精髓就两句话：分配时对半劈，释放时遇到好邻居就合并。算法简单，但背后有深刻的考量——O(1) 的分配和回收复杂度，对碎片化的控制，以及和更细粒度分配器（SLAB）的衔接。

理解 Buddy System，你才算真正理解了 Linux 物理内存管理的地基。下篇我们讲它的上层建筑——SLAB 分配器，以及 Buddy 和 SLAB 是怎么配合工作的。

动手环节

想深入理解本文内容？动手实践是最好的方式：

今天的目标：下载 wandos 代码仓库，理解 Buddy System 的实现边界，对比 Linux 原版。

下载 wandos：

Bash

git clone https://github.com/zhangfuwen/wandos.git
cd wandos

找到对应模块：查看 kernel/memory/slab_allocator.cpp 和 kernel/memory/paging.cpp
实现作业：根据文中”动手环节”章节的要求，完成代码编写
提交作业：Fork 仓库，提交你的改动，在 GitHub 上开一个 Pull Request

仓库：https://github.com/golang12306/os-kernel-from-scratch

从零写OS内核 | 物理内存管理——Buddy System 伙伴系统

从零写OS内核 | 物理内存管理——Buddy System 伙伴系统

1. 为什么需要Buddy System

2. Buddy System 工作原理

2.1 核心规则：分裂与合并

2.2 伙伴块的定义

2.3 空闲链表结构

3. 分配算法详细流程

4. 合并的逆向过程

5. Linux 实践：查看 Buddy System 状态

6. 从零实现：wandos 的 Buddy System

6.1 核心数据结构

6.2 分配函数

6.3 释放函数

6.4 wandos 现有实现分析

7. 动手环节：实现一个简易Buddy分配器

任务 1：实现空闲块分裂函数

任务 2：实现合并函数

任务 3：实现 `buddy_alloc()` 和 `buddy_free()`

验收标准

8. 踩坑与注意事项

写在最后

相关阅读

动手环节

赞过：

作者

评论

发表评论取消回复

从零写OS内核 | 物理内存管理——Buddy System 伙伴系统

从零写OS内核 | 物理内存管理——Buddy System 伙伴系统

1. 为什么需要Buddy System

2. Buddy System 工作原理

2.1 核心规则：分裂与合并

2.2 伙伴块的定义

2.3 空闲链表结构

3. 分配算法详细流程

4. 合并的逆向过程

5. Linux 实践：查看 Buddy System 状态

6. 从零实现：wandos 的 Buddy System

6.1 核心数据结构

6.2 分配函数

6.3 释放函数

6.4 wandos 现有实现分析

7. 动手环节：实现一个简易Buddy分配器

任务 1：实现空闲块分裂函数

任务 2：实现合并函数

任务 3：实现 buddy_alloc() 和 buddy_free()

验收标准

8. 踩坑与注意事项

写在最后

相关阅读

动手环节

分享到：

赞过：

作者

评论

发表评论 取消回复

任务 3：实现 `buddy_alloc()` 和 `buddy_free()`

发表评论取消回复