wiki.osdev.org 系列之 - Page Frame Allocation

type

Post

status

Published

slug

2022/12/07/wiki-os-dev-org-page-frame-allocation

summary

这些算法将在您需要时为您提供新的页帧。该算法的客户端通常对返回哪个帧无所谓，尤其是对 n 帧的请求不需要返回连续的帧（除非您正在为 DMA 操作分配内存，例如网络数据包缓冲区）。

1 物理内存分配器

N 将是以下文本中页的内存的大小。

1.1 Bitmap（位图）

N/8 字节的大数组用作内存使用情况的大位图（即字节 #n 中的位 #i 定义页 #n*8+i 的状态）。设置给定页面的状态很快 (时间复杂度为O(1))，分配页面可能需要时间 (需要逐个查找空间空间 O(N))。

uint32_t 可以最多可以一次性测试 32 位，从而能够加快分配速度。

保留指向最后分配位的指针可能会提高下一次搜索的性能（保留有关所有先前字节都未成功搜索的事实的信息）

1.2 Stack/List of pages

每个可用的物理帧的地址都存储在一个类似堆栈的动态结构中。分配一个页面很快 (O(1))，释放一个页面也是如此，但是检查页面的状态是不切实际的，除非额外的元数据按物理地址排序。

1.3 Sized Portion Scheme

您将每个区域（例如 16kb）分成（例如）1 个 8kb 和 2 个 4kb 的块。然后你分发每个块。通过这样做，您可以找到更接近确切尺寸的尺码。这意味着更少的浪费。所以假设你有一个 32kb 的区域

每个部分甚至可以有 1 种、2 种、甚至 3 种或 4 种（或更多！）类型的布局。这样您就有更多尺寸可供选择。

1.4 Buddy Allocation System

这是 Linux 内核的物理内存分配器。请注意，Linux 有几个伙伴，具体取决于内存是否适合 ISA DMA，或者来自“高物理内存”还是“正常”。每个伙伴包含 k 个位图，每个位图指示 2^i 大小和 2^i 对齐的空闲页面块的可用性。通常，linux 使用从 4K 到 512K 的块。


                 0   4   8   12  16  20  24  28  32  36
                 ###.#....#........#...###...########.... real memory pattern

   buddy[0]--->  ###.#.xx.#xxxxxxxx#.xx###.xx########xxxx 5  free 4K , 5-byte bitmap
   buddy[1]--->  # # # . # . x x . # . # # . # # # # x x  5  free 8K , 20-bits map
   buddy[2]--->  #   #   #   .   #   #   #   #   #   .    2  free 16K, 10-bits map
   buddy[3]--->  #       #       #       #       #        0  free 32K, 5-bits map

N 页的伙伴大约是相同区域位图大小的两倍，但它允许更快地定位页面集合。上图显示了一个 4-buddy，其空闲页面/块表示为 . 用过的页面/块表示为 # 。当一个块至少包含一个已用子块时，它本身被标记为已用，并且作为较大块的一部分的子块也被标记为已用（图中的 x）。假设我们想在这个伙伴上分配一个 12-K 的区域，我们将查找空闲 16K 块的位图（它说我们有一个这样的从第 #12 页开始，另一个从第 #36 页开始）。 buddy[2]->bit[4] 然后被设置为 'used'。现在我们只需要我们得到的 4 页中的 3 页，所以剩余的页面将返回到适当的伙伴位图（例如单页映射）。结果伙伴是


                 0   4   8   12  16  20  24  28  32  36
                 ###.#....#..###...#...###...########.... real memory pattern

   buddy[0]--->  ###.#.xx.#xx###.xx#.xx###.xx########xxxx 6  free 4K , 5-byte bitmap
   buddy[1]--->  # # # . # . # # . # . # # . # # # # x x  5  free 8K , 20-bits map
   buddy[2]--->  #   #   #   #   #   #   #   #   #   .    1  free 16K, 10-bits map
   buddy[3]--->  #       #       #       #       #        0  free 32K, 5-bits map

请注意，最初只有最大的区域可用，因此如果 buddy[0] 显然是空的，我们需要检查 buddy[1]，然后 buddy[2] 等以找到用于拆分的空闲块。

1.5 Hybrid scheme（混合方案）

分配器可以被链接起来，这样（例如）一个堆栈只覆盖最后的操作，并且堆栈的“底部”被提交给一个位图（用于紧凑存储）。如果堆栈缺少页面，它可以扫描位图以找到一些（可能在后台作业中）。

1.6 Hybrid scheme #2

不要只跟踪表示页面的位，或者只跟踪堆栈上的页码，而是使用一个大的结构数组来表示内存。在这些页帧结构中，存储指向下一页（指针大小）的单个链接和指示其状态的 8-16 位信息块。还要包括虚拟页指针和页号所属的TCB。保留指向每种类型页面的指针，指向它们列表的开头和结尾。通过这种方式，您可以轻松地显示有关其内容的信息、每种可用类型的页面数量、混合类型、允许动态清理线程、相当轻松地进行写时复制并保持页面清晰简洁的概览。它作为一个反向页面映射表，也列出了页面类型。

有关示例实现，请参阅 AtlantisOS 0.0.2 或更高版本。

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

2.1 Flat List（平面链表）

管理大面积地址空间的一种直接方法是链表（如下所示）。每个“空闲”区域都与一个描述符相关联，描述符给出了它的大小和基地址。当需要分配一些空间时，将使用“首次匹配”或“最佳匹配”（或其他）算法扫描列表以查找足够大的区域。这是 MS-DOS 管理内存的方式。分配内存时，合适的条目将被删除（整个区域都被分配了）或调整大小（仅分配该区域的一部分）。

请注意，对于平面链表，“地址 XXX 处的内存是否可用” 或 “我在哪里可以得到大小为 YYY 的块” 这类的问题可能需要将列表进行完整遍历才能得到答案。如果虚拟内存变得碎片化并且链表变长，那么就可能会引发问题。 “地址 XXX 处的内存是否空闲？” 主要用于在释放块时将两个空闲区域合并为一个新的（更大的）区域，如果链表保持地址增长的顺序进行增长，则比较容易处理。

2.2 Tree-based approach（基于树的方法）

由于经常在链表中搜索给定的地址或给定的大小，因此使用更高效的数据结构可能会很有趣。其中一个仍然保持遍历整个链表的能力的是 AVL 树。 AVL 树中的每个“节点”都将描述一个内存区域，并具有指向较低节点子树和较高节点子树的指针。

虽然在这样的平衡树中进行 插入/删除 操作比链表更复杂，但搜索树的时间复杂度通常是 O(log2(N)) 而不是链表的 O(N) ——也就是说，如果你有 1000 个条目，使用链表它需要 1000 次迭代来进行扫描，而树只需要 10 次迭代即可找到给定的间隔。

Linux 使用 AVL 树进行虚拟地址管理已经有一段时间了。但是请注意，它将它用于区域（就像您在 /proc/xxxx/maps 中找到的那样），而不是用于类似 malloc 的接口。

3 See Also