B06 —— 物理内存的管理者：Buddy System 伙伴系统

金句：把内存按”伙伴”分组，让分配和回收都变得高效。

为什么需要 Buddy System

操作系统需要管理物理内存的分配和回收。最简单的方式是位图管理（Bitmap），但这种方式在分配大块内存时效率很低。

Bash
位图管理的问题：

假设用 4KB 页框（Page Frame）管理 16GB 内存：
  - 16GB / 4KB = 4M 个页框
  - 位图大小 = 4M bits = 0.5MB（可以接受）

问题：分配 2MB（512 个连续页框）
  - 位图需要找到连续的 512 个 1（空闲位）
  - 最坏情况：扫描整个位图 → O(n)，n=4M
  - 碎片化严重时，可能找不到连续的 512 个页框

Buddy System 的解决方案：
  - 把空闲内存按 2 的幂次分成块（order）
  - 2^0 = 4KB, 2^1 = 8KB, 2^2 = 16KB, ..., 2^10 = 4MB
  - 每个 order 维护一个空闲链表
  - 分配：从小到大找可用块，拆分成"伙伴"满足请求
  - 回收：合并"伙伴"块回到更大的空闲块

优点：分配/回收 O(log n)，天然合并碎片

Buddy System 的工作原理

Bash
Buddy System 的核心思想：

1. 空闲块按大小（2^n）分类
   - Order 0：4KB
   - Order 1：8KB
   - Order 2：16KB
   - ...
   - Order 10：4MB
   - Order 11：8MB

2. 每个 Order 有自己的空闲链表（free list）

3. 分配算法：
   - 请求 size = k
   - 找到最小的 order ≥ k（假设 order i）
   - 如果 free_list[i] 不为空，分配
   - 如果为空，向上找更大块（order i+1），拆成两个"伙伴"
   - 把其中一个分配出去，另一个加入 free_list[i]

4. 回收算法：
   - 释放块 A，大小 2^i
   - 检查 A 的"伙伴"B 是否也在 free_list[i]
   - 如果 B 在，合并成 2^(i+1)，加入 free_list[i+1]
   - 如果 B 不在，把 A 加入 free_list[i]
   - 递归向上合并，直到不能合并为止

“伙伴”的定义

Bash
什么是"伙伴"：

两个内存块是"伙伴"的条件：
  1. 大小相同（都是 2^i）
  2. 地址连续
  3. 基址是 2^(i+1) 的倍数

例子：假设物理内存从 0 开始

  Order 0（4KB）的伙伴：
    块 A：0x1000 ~ 0x1FFF
    块 B：0x2000 ~ 0x2FFF
    A 和 B 合并成 order 1 的块：0x1000 ~ 0x2FFF

  A 和 C：0x3000 ~ 0x3FFF 是不是 A 的伙伴？
    → 不算！0x3000 不是 0x4000（0x1000+0x3000）的倍数
    → 伙伴要求基址是 2^(i+1)=8KB 的倍数
    → 0x3000 不是 8KB 的倍数

Order 1（8KB）的伙伴：
  块 A：0x0000 ~ 0x1FFF
  块 B：0x2000 ~ 0x3FFF
  合并后的基址 = 0x0000（8KB 的倍数）

关键性质：
  给定块地址 addr，大小 2^i
  伙伴地址 = addr XOR 2^i（异或操作）

Buddy System 的分配示例

Bash
分配 128KB（32 个 4KB 页框）的过程：

假设：
  系统内存：128MB（32768 个 4KB 页框）
  Order 0 ~ Order 10（4KB ~ 4MB）

Step 1：请求 128KB = 32 × 4KB = 2^5 × 4KB
  → 需要 Order 5（32KB）？不对
  → 128KB = 32 × 4KB = 2^5 × 4KB
  → Order = 5（因为 2^5 × 4KB = 128KB）

Step 2：检查 free_list[5]（128KB 块）
  → 如果有，直接分配！

Step 3：如果 free_list[5] 为空
  → 检查 free_list[6]（256KB）
  → 如果有：把 256KB 拆成两个 128KB
    - 第一个 128KB 分配出去
    - 第二个 128KB 加入 free_list[5]
  → 如果 free_list[6] 也为空，向上继续

Step 4：直到找到可用的更大块

实际代码（简化）：
  for (order = requested; order <= MAX_ORDER; order++) {
      if (!list_empty(&free_area[order])) {
          // 找到可用块
          page = alloc_pages(order);
          return page;
      }
  }
  // 无法分配，返回 NULL

Buddy System 的回收示例

Bash
释放 128KB（Order 5）：

Step 1：把 128KB 块标记为空闲
  → 尝试合并到更大的块

Step 2：检查伙伴是否在 free_list[5]
  addr = 0x10000（假设）
  buddy = addr XOR (1 << (5 + PAGE_SHIFT))
       = 0x10000 XOR 0x20000
       = 0x30000

  如果 0x30000 在 free_list[5]：
    → 合并成 256KB（Order 6）
    → 加入 free_list[6]
    → 继续检查 Order 6 的伙伴是否也能合并

Step 3：如果伙伴不在 free_list[5]
  → 直接加入 free_list[5]
  → 完成

合并的递归性：
  Order 0 释放 → 找到伙伴 → 合并成 Order 1
  Order 1 释放（合并后）→ 找到伙伴 → 合并成 Order 2
  ...
  直到 Order MAX，无法再合并

这就是"Buddy"名字的由来——
每个块被拆成一对"伙伴"，回收时只有伙伴都在才能合并。

Linux 中的 Buddy System 实现

Bash
Linux 的 buddy system 数据结构：

struct free_area {
    struct list_head free_list[MIGRATE_TYPES];
    unsigned long nr_free;
};

struct zone {
    // 其他字段...
    struct free_area free_area[MAX_ORDER];
    // MAX_ORDER = 11（默认）
};

MAX_ORDER 定义：
  - Order 0：2^0 × PAGE_SIZE = 4KB
  - Order 1：2^1 × PAGE_SIZE = 8KB
  - Order 2：2^2 × PAGE_SIZE = 16KB
  - Order 3：2^3 × PAGE_SIZE = 32KB
  - Order 4：2^4 × PAGE_SIZE = 64KB
  - Order 5：2^5 × PAGE_SIZE = 128KB
  - Order 6：2^6 × PAGE_SIZE = 256KB
  - Order 7：2^7 × PAGE_SIZE = 512KB
  - Order 8：2^8 × PAGE_SIZE = 1MB
  - Order 9：2^9 × PAGE_SIZE = 2MB
  - Order 10：2^10 × PAGE_SIZE = 4MB
  - Order 11：2^11 × PAGE_SIZE = 8MB（如果支持）

分配函数：
  struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)
  → 分配 2^order 个连续的物理页
  → 返回指向第一个 page 结构的指针

Bash
查看 buddy system 状态：

$ cat /proc/buddyinfo

Node 0, zone      DMA      free pages 123/456
Node 0, zone    DMA32    free pages 23456/34567
Node 0, zone   Normal    free pages 78901/89012

$ cat /proc/pagetypeinfo

Page block order: 11
Number of blocks 8192

Free pages count by migratetype:
  Node 0, zone  Normal, type    Unmovable  1234
  Node 0, zone  Normal, type       Movable  45678
  Node 0, zone  Normal, type    Reclaimable  234
  ...

查看某个 order 的空闲块数：
  $ cat /proc/buddyinfo | awk '{print $5}'
  （各 order 的 nr_free）

Buddy System 的局限性

Bash
Buddy System 的问题：

1. 内部碎片（Internal Fragmentation）：
   - 请求 6KB，但只能分配 8KB（Order 1）
   - 浪费 2KB
   - 解决：SLAB/SLUB 分配器（在 buddy system 之上）

2. 外部碎片（External Fragmentation）：
   - 长时间运行后，空闲块可能分散
   - 明明有足够的总内存，但找不到连续的大块
   - 解决：内存规整（compaction，Kcompactd）

3. 分配粒度：
   - 最小单位是 4KB（Order 0）
   - 小于 4KB 的分配需要 SLAB，不能直接用 buddy

4. 内存碎片化：
   - 某些 migratetype 可能耗尽
   - 即使 total free pages 足够，也可能分配失败
   - 解决：Migrate types（Movable/Unmovable/Reclaimable）

总结

  • Buddy System：按 2 的幂次分配内存，Order 0（4KB）到 Order MAX
  • 空闲链表：每个 Order 维护一个 free_list
  • 分配：找最小满足的 Order，如果为空向上拆分（拆成两个伙伴）
  • 回收：加入对应 Order，检查伙伴是否也在，合并（递归）
  • 伙伴定义：地址连续 + 大小相同 + 基址是 2^(i+1) 的倍数，伙伴地址 = addr XOR 2^i
  • Linux 实现：free_area[MAX_ORDER]，alloc_pages(order) 分配
  • 局限性：内部碎片（SLAB 解决）、外部碎片（compaction 解决）

下篇预告（B07）：操作系统是怎么知道还有多少内存可用的？bootmem、memblock、memblock allocator——从 e820 表到内存管理初始化。

关注公众号「AI不着急」，回复”资料”获取内存学习路线图。

最后修改： 2024年3月8日

作者

评论

发表评论

您的邮箱地址不会被公开。