B06 — The Manager of Physical Memory: The Buddy System

Key Insight: Grouping memory into “buddies” makes both allocation and reclamation efficient.

Why Do We Need the Buddy System

The OS needs to manage physical memory allocation and reclamation. The simplest approach is bitmap management, but it is inefficient for allocating large blocks.

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)，天然合并碎片

How the Buddy System Works

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]
   - 递归向上合并，直到不能合并为止

Definition of “Buddy”

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 Allocation Example

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 Deallocation Example

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"名字的由来——
每个块被拆成一对"伙伴"，回收时只有伙伴都在才能合并。

Buddy System Implementation in Linux

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 Limitations

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）

Summary

  • Buddy System: Allocates memory in powers of 2, Order 0 (4KB) to Order MAX
  • Free List: Each Order maintains a free_list
  • Allocation: Find smallest satisfying Order; if empty, split upward (into two buddies)
  • Deallocation: Add to corresponding Order; check if buddy is also present; merge (recursive)
  • Buddy Definition: Contiguous addresses + same size + base is multiple of 2^(i+1); buddy address = addr XOR 2^i
  • Linux Implementation: free_area[MAX_ORDER]; alloc_pages(order) for allocation
  • Limitations: Internal fragmentation (solved by SLAB); external fragmentation (solved by compaction)

Next (B07): How does the OS know how much memory is available? bootmem, memblock, memblock allocator. From e820 table to memory management initialization.

Last modified: 2024年3月8日

Author

Comments

Write a Reply or Comment

Your email address will not be published.