内存管理：页帧分配（Page Frame Allocation）译文

本文译自 OSDev Wiki 上的一篇文章，原文链接为 Page Frame Allocation。

物理内存分配器（Physical Memory Allocators）

这些算法用于在需要时向你提供新的页帧（page frame）。该算法的调用者通常并不关心返回的是哪一帧，特别是当请求 n 个页时，也不需要返回连续的页帧（除非你要为网络包缓冲等 DMA 操作分配内存）。

在下文中，N 表示以页为单位的内存大小。

位图（Bitmap）

使用一个大小为 N/8 的字节数组作为内存使用情况的大型位图（即：第 n 个字节的第 i 位表示第 n*8+i 个页的状态）。 设置某个页的状态非常快（O(1)），但分配一个页可能需要较长时间（O(N)）。

优化方式：

• 使用 uint32_t 一次比较 32 位，可以加速搜索空闲页。
• 记录上次成功分配的位置，下次从该位置继续搜索，可避免重复扫描先前已确认没有空闲页的区域。

页栈 / 页链表（Stack/List of pages）

将每个可用物理页帧的地址存入类似栈的动态结构中。 分配和释放页都很快（O(1)），但查询某个页的状态不太实用，除非你额外维护按物理地址排序的元数据。

固定大小分段方案（Sized Portion Scheme）

将每个区域（例如 16 KB）拆分为若干块，例如：一个 8 KB 块和两个 4 KB 块，然后按块进行分配。 通过这种方式，你可以找到更接近实际需求大小的内存块，从而减少浪费。

例如，一个 32 KB 区域可以这样拆分：

你甚至可以为每个区域设计 1、2、3 或 4（甚至更多）种布局，这样就能提供更多可选的块大小。

伙伴分配系统（Buddy Allocation System）

这是 Linux 内核使用的物理内存分配器。需要注意的是，Linux 维护了多个 buddy 分配器，分别用于适合 ISA DMA 的内存、“高端物理内存”（high memory）以及“普通内存”（normal memory）。 每个 buddy 维护 k 个位图，每个位图表示大小为 2ⁱ、并且地址按 2ⁱ 对齐的空闲页块（block）的可用性。通常来说，Linux 会使用从 4 KB 到 512 KB 范围大小的块。

                 0   4   8   12  16  20  24  28  32  36
                 ###.#....#........#...###...########....  实际内存使用情况

   buddy[0]--->  ###.#.xx.#xxxxxxxx#.xx###.xx########xxxx  5 个空闲 4K，位图 5 字节
   buddy[1]--->  # # # . # . x x . # . # # . # # # # x x   5 个空闲 8K，20 位位图
   buddy[2]--->  #   #   #   .   #   #   #   #   #   .     2 个空闲 16K，10 位位图
   buddy[3]--->  #       #       #       #       #         0 个空闲 32K，5 位位图

对于 N 个页，buddy 结构的大小大约是对应位图方案的两倍，但它能更快定位连续的页块。

上图展示了一个 4 级 buddy：空闲页块用 “.” 表示，已使用页块用 “#” 表示。 如果一个块中至少有一个子块被使用，那么该块就会视为“已使用”；而属于更大块的子块也会被标记为“已使用”（图中的 x）。

例如，我们要在此 buddy 中分配一个 12 KB 区域：

1. 在 16 KB 块位图中查找可用块 根据 buddy[2]，在页 12 和页 36 处各有一个空闲 16 KB 块。

2. 将 buddy[2] 的第 4 位标记为“已使用”。

3. 但我们只需要 3 页（12 KB），剩下的 1 页要被分拆并返回到更小块的 buddy（例如 4 KB 级的位图）。

更新后的 buddy 如下：

                 0   4   8   12  16  20  24  28  32  36
                 ###.#....#..###...#...###...########....  实际内存使用情况

   buddy[0]--->  ###.#.xx.#xx###.xx#.xx###.xx########xxxx  6 个空闲 4K
   buddy[1]--->  # # # . # . # # . # . # # . # # # # x x   5 个空闲 8K
   buddy[2]--->  #   #   #   #   #   #   #   #   #   .     1 个空闲 16K
   buddy[3]--->  #       #       #       #       #         0 个空闲 32K

需要注意的是：系统初始化时，只有最大块是可用的。 如果 buddy[0]（最小块大小）看上去空的，就必须依次检查 buddy[1]、buddy[2] 等更高层级，以分裂更大的块来满足请求。

混合方案（Hybrid scheme）

可将多个分配器串联使用。例如：

• 栈结构只负责处理最近的分配与释放操作；
• 栈的底层存储在一个紧凑的位图中；
• 当栈中没有可用页时，可以扫描位图找空闲页（甚至可以在后台线程中进行）。

混合方案 #2（Hybrid scheme #2）

与其只维护页位（bit）或只维护页号栈，不如使用一大块结构体数组来表示内存。

每个 页帧结构体（page frame struct） 中可包含：

• 指向下一个页的指针（形成链表）
• 一个 8~16 位的信息字段表示此页的状态
• 虚拟页指针
• 属于哪个 TCB（线程控制块）的信息

并对不同类型的页分别维护其链表的 头指针 和 尾指针。

这种设计的优势包括：

• 容易展示每类页面的数量和状态
• 可以混合管理不同类型的页
• 支持动态清理线程
• 实现写时复制（COW）更加简单
• 提供清晰、紧凑的页面管理概览

它相当于一个带页类型信息的“反向页映射表”（reverse page map）。

示例实现参考：AtlantisOS 0.0.2 或更高版本。

虚拟地址分配器（Virtual Addresses Allocator）

平面链表（Flat List）

管理大型虚拟地址空间的一种直接方法是使用链表（如下图所示）。 每个“空闲”区域都对应一个描述符，记录其基地址和大小。 当需要分配空间时，通过“首次适配（first fit）”“最佳适配（best fit）”或其他策略扫描链表，寻找足够大的区域。

（例如，MS-DOS 就采用类似的管理方式。）

当区域被分配时：

• 如果整个区域被使用，则将链表项删除；
• 如果只使用一部分，则调整链表项的大小与起始地址。

需要注意： 使用平面链表时，无论是查询 “地址 XXX 是否空闲”，还是查找 “大小 YYY 的连续空闲区域”，都可能需要遍历整个链表。 当虚拟内存碎片化、链表变长时，这会变得低效。

特别是，“地址 XXX 是否空闲？” 的查询主要用于在释放内存后合并相邻的空闲区域。如果链表按地址升序排列，那么合并空闲区会更容易实现。

Flat list.png

基于树的方案（Tree-based approach）

由于常见操作包括按地址查找或按大小查找，因此使用更高效的数据结构可能更有意义。 其中一个既能保持整体可遍历性、又能提供高效搜索的数据结构是 AVL 平衡树。

AVL 树中的每个节点描述一个内存区域，并有指向：

• 较小地址区域的子树；
• 较大地址区域的子树。

Tree based.png

在这种结构中，插入和删除的复杂度比链表更高，但搜索效率要显著更好：

• 链表：O(N)
• 平衡树（例如 AVL）：O(log₂N)

举例来说： 如果有 1000 个空闲区域，链表需要扫描 1000 次，而 AVL 树大约只需 10 次比较即可定位到目标区域。

Linux 在虚拟地址管理上长期使用 AVL 树。 但需要注意：Linux 使用它来管理“区域”（如 /proc/xxxx/maps 中显示的 VMA 区域），而不是用来实现类似 malloc() 的小块动态分配。

参见

文章（Articles）

• 编写页帧分配器（Writing A Page Frame Allocator）
• 内存分配（Memory Allocation）
• 内存管理（Memory management）
• 编写内存管理器——教程（Writing a memory manager - a tutorial）

线程（Threads）

• 为分配器分配内存而没有分配器（Allocating memory for an allocator without an allocator）
• 一种基于位图的分配技术（A bitmap based allocation technique）
• 跟踪已分配 RAM 的方法（Ways to keep track of allocated RAM）
• 关于内存分配的问题（Questions about Memory Allocation）
• 内存管理（Memory Management）
• 更高级的内存管理（Memory Management to the X’th）
• 内存管理相关问题（MM Questions）
• （关于）Tim Robinson 的内存管理教程 #1（(about) Tim Robinson Memory Management Tutorial #1）
• 管理已使用/空闲的页（Managing used/free pages）
• Malloc 等（curufir 的教程）（Malloc, etc. (tute by curufir)）
• 物理内存管理（Freanan 编写）（Physical MM (by Freanan)）
• 各种替代内存管理方案的概念与要点（Concepts and key points on alternative memory management schemes）

外部链接（External Links）

• mystran 的《傻瓜版基础虚拟内存管理》（Basic VMM for Dummies，缓存版）
• 维基百科：页面置换算法（Page replacement algorithm on Wikipedia）

如果你需要，我也可以把整篇文档整理成 PDF、Markdown 或总结成知识要点，随时告诉我即可。