type
Post
status
Published
slug
2022/12/07/wiki-os-dev-org-page-frame-allocation
summary
这些算法将在您需要时为您提供新的页帧。该算法的客户端通常对返回哪个帧无所谓,尤其是对 n 帧的请求不需要返回连续的帧(除非您正在为 DMA 操作分配内存,例如网络数据包缓冲区)。
tags
osdev
category
osdev
icon
password
Property
Dec 10, 2022 01:33 AM
created days

1 物理内存分配器

这些算法将在您需要时为您提供新的页帧。该算法的客户端通常对返回哪个帧无所谓,尤其是对 n 帧的请求不需要返回连续的帧(除非您正在为 DMA 操作分配内存,例如网络数据包缓冲区)。
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 的区域
notion image
每个部分甚至可以有 1 种、2 种、甚至 3 种或 4 种(或更多!)类型的布局。这样您就有更多尺寸可供选择。

1.4 Buddy Allocation System

这是 Linux 内核的物理内存分配器。请注意,Linux 有几个伙伴,具体取决于内存是否适合 ISA DMA,或者来自“高物理内存”还是“正常”。每个伙伴包含 k 个位图,每个位图指示 2^i 大小和 2^i 对齐的空闲页面块的可用性。通常,linux 使用从 4K512K 的块。
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 处的内存是否空闲?” 主要用于在释放块时将两个空闲区域合并为一个新的(更大的)区域,如果链表保持地址增长的顺序进行增长,则比较容易处理。
Flat list.png
Flat list.png

2.2 Tree-based approach(基于树的方法)

由于经常在链表中搜索给定的地址或给定的大小,因此使用更高效的数据结构可能会很有趣。其中一个仍然保持遍历整个链表的能力的是 AVL 树AVL 树中的每个“节点”都将描述一个内存区域,并具有指向较低节点子树和较高节点子树的指针。
Tree_based
Tree_based
虽然在这样的平衡树中进行 插入/删除 操作比链表更复杂,但搜索树的时间复杂度通常是 O(log2(N)) 而不是链表的 O(N) ——也就是说,如果你有 1000 个条目,使用链表它需要 1000 次迭代来进行扫描,而树只需要 10 次迭代即可找到给定的间隔。
Linux 使用 AVL 树进行虚拟地址管理已经有一段时间了。但是请注意,它将它用于区域(就像您在 /proc/xxxx/maps 中找到的那样),而不是用于类似 malloc 的接口。

3 See Also

3.1 Articles

3.2 Threads

3.3 External Links

 
欢迎加入喵星计算机技术研究院,原创技术文章第一时间推送。
notion image
 
wiki.osdev.org 系列之 - Ditheringwiki.osdev.org 系列之 - Random Number Generator

  • Waline
  • Utterance