Memory Allocation

本篇是关于内存分配（allocation of memory）功能的内容，该功能让进程可以分配到可用的内存空间 (如通过malloc() 和new())。 有关页面帧的分配，请参见 页面帧分配。

内核 的最基本功能之一是 内存管理，即内存的分配和释放。

系统刚刚启动时，内核是系统中唯一的进程。 但它并不孤单: BIOS 数据结构、内存映射的硬件寄存器等填充了地址空间。 内核必须做的第一件事是开始登记内存使用，确定哪些物理内存区域可供使用（available），哪些被视为 “占用（occupied）”。

随后，可用空间将用于内核数据结构，应用程序二进制文件，它们的堆（heap）和 栈（stack） 等等。 - 内核需要实现一个将内存区域标记为“已保留”的函数，并使该区域内存可用于需要它的进程。 在C标准库中，这由malloc() 和free()函数处理的; 在C++中由new() 和delete() 处理。

整体概观

一个操作系统有许多 内存管理 层。 每一层都建在上一层之上。 逐层透视如下:

• RAM在物理内存管理器（Physical Memory Manager PMM）中分配，通常是 页面帧分配器 (另一个流行的选择是 SLAB 和 buddy allocator)。
• 页面由虚拟内存管理器（Virtual Memory Manager VMM）分配到地址空间 (通常通过sbrk() 或mmap() 系统调用)。
• 然后，可用地址空间由用户空间分配器 (user-space allocator-通常称为malloc()) 管理，到这里才是这是本文讨论的主题。

内核堆管理和虚拟内存管理器非常相似（译者注：一个是内核空间，一个是用户空间），具有相同的抽象，但使用不同的操作实现:

• 在底层，使用相同的PMM（物理内存管理器）。
• 内存通常通过特殊函数映射到内核地址空间，并且不需要系统调用来提高权限级别。
• 分配内核堆是通过kmalloc() 完成的，它与malloc() 非常相似，但在libc中没有定义，而是在内核库中定义。

如你所见，VMM（虚拟内存管理）仅在一件事上有所不同: 分页 表用于映射PMM分配的页面 (用户空间vs.内核空间)。 某些保护位 (例如supervisor page上的位) 也有所不同，其它一些步骤是相同的。

顶层内存管理也非常相似，唯一的区别是，当管理器用完空闲虚拟内存时，在VMM中要使用哪个回调。 也可以说，如果你在它们中替换回调，你也可以使用任何现有的内存分配器作为kmalloc()。

总之内存分配要经过这些步骤:

1. 我们有足够的空闲虚拟内存吗？
2. 如果有，请使用某种结构来记录内存分配状态 (取决于分配器)
3. 如果没有，请要求VMM扩大可用地址空间 (sbrk/mmap/mapkernelheap 等)
4. VMM转而调用PMM分配RAM
5. 新分配的RAM由VMM记录在相应的分页表中
6. 转到步骤2。

步骤3-5很慢 (主要是因为所需的权限级别更改)，因此内存分配器倾向于减少这些调用，并尽可能地在其已经映射的地址空间中重用内存。

一个非常非常简单的内存管理器

你能做的最简单的就是水印分配器（WaterMark allocator）。 只需跟踪你分配了多少内存，而不考虑 “释放” 的要求即可。

           before ...
                                                          <-N-->
   +----+-----+--+--------//--+             +----+-----+--+----+---//--+
   |##A#|##B##|C#|  free      |             |##A#|##B##|C#|##D#|free   |
   +----+-----+--+---------//-+             +----+-----+--+----+---//--+
                 ^freebase    ^freetop                    ^d   ^fbase  ^ftop

为D分配N个字节时，只需检查 (freetop-freebase > N)，然后将freebase递增N个字节。 这是一个非常简单的内存管理器

现在，如果你需要释放空间，最简单的解决方案之一是在释放区域的开头放置一个描述符，然后你再将该描述符放入空闲区域列表中。 保持该列表按地址排序有助于你识别连续的空闲区域，并帮你将它们合并到较大的空闲区域中。

      first free                        Structure of a   +--.--.--.--+    +---> +-- ...
        \/                              free zone        |F  R  E  E |    |     | FREE
   +----+-----+--+----+---+-----//--+                    |nextfreeptr|----+
   |##A#|free |C#|free|#E#|   free  |               <----|prevfreeptr|
   +----+-|---+--+-|--+---+-----//--+                    | zone size |
          +-next>--+                                     +///////////+

固定大小分配

分配和释放固定大小的内存区域非常简单。 你基本上可以将所有空闲内存视为节点的链表（译者注：包含前后指针的链表）。 要分配内存，就从链接列表中删除前节点。 要释放内存，就将前节点返回到链表。 该算法在提供了固定大小的分配/释放同时不会产生碎片。

在现实世界中，程序喜欢分配不同大小的内存块，因此你不太可能仅依赖此方法。

但是，从理论上讲，可以设计一个微内核，使所有内存结构的大小完全相同 (进程结构，线程结构，消息结构等)。 这将是非常快速和有效的。

在此说明，大多数Lisp实现都具有单个 “box-and-pointer” 基本数据类型。 box-and-pointer类型是一对值，通常是pointer/pointer或atom/pointer (atom表示数值)。在32位系统上，这种结构有8个字节。 所有其他数据结构 (列表，树，对象等) 都在此类型之上构建。 因此，Lisp系统上的内存分配非常快。

进一步的提示

• 有时，尤其是在使用对象时，你必须分配许多始终具有一定大小的对象。 为此类对象创建预先划分的大块内存池是明智的做法。
• 将分配的对象的大小保持在对请求者隐藏的标头中会更容易，这样对 free 的调用就不需要对象的大小。 通常，此隐藏标头仅保留在 malloc 返回的块之前。
• 在主机OS中设计内存分配器比在内核中更容易。 另外，如果你实现了完整的malloc接口 (malloc，calloc，realloc 和 free 在Linux上就足够了) 一个好的健全性测试是将你的 malloc 编译到一个共享库中，然后配合LD_PRELOAD使用你的malloc编译一些东西 (例如你的整个主机操作系统树)。
• 像 “F R E E” 和 “U S E D” 这样的日志中的醒目单词将使你在调试时更加轻松。 TimRobinson甚至提供32位来存储请求者的地址，这样你就可以看到日志：“好的，这是一个由 MySillyFunction() 请求的N字节块，第3405行”...

内存和微内核

在微内核环境中，出现了一个问题: 该把内存管理放在哪里？ 在堆管理的意义上存在两个过程: 给内核一个专用的分配器和一个获得专用的内存区域来使用 - 你的微内核可能同时需要这两个: 一个用于消息接受发送，另一个用于所有其他内容。（译者注：微内核获得内存申请消息，标记内存后，返回可用空间地址消息）

内存管理的另一项任务: 进程地址空间管理，跟踪使用的页面 (是的，我们也要关注带来程序整洁的分页，让你觉得脚下暖暖的)，并根据需要将内存分配给进程，已在需要时将其再拆分。 更准确地说，你必须将内存使用任务拆分-或者将内存管理的各个方面保留在内核中，以使其变得容易。 一种推荐的管理进程地址空间的方法是: 每个进程用自己的方式处理它。 当实际进程需要内存: 就分配一块内存并将其分发给进程，让进程在外部处理它。 因此，你可以使页面分配过程变得简单明了。 对于分配/释放内存的任务，你应该考虑到，执行此类操作的任务应该能够在需要时细分地址空间 (它只是加载所需的页面目录，并做它必须做的事情-你会发现你脚下其实是踩了一个黄鼠狼。) 充分考虑这些因素，并投入大量的脑力劳动。在这里做好工程是值得的。

移植现有内存分配器

编写自己的内存分配器并不总是可取或实用的。 编写一个高效的内存分配器本身可以是一个完整的项目，幸运的是，将现有的内存分配器移植到你的操作系统 (在内核或用户空间中运行) 非常容易。 使用现有内存分配器的优点是; 移植一个比编写自己的要快得多，尤其是当你想专注于操作系统的其他领域时，它可能会经过良好的测试，因此你不必调试内存分配器，移植它需要最少的工作，最后，其他人付出了艰苦的努力才能使其快速，可扩展，稳定等。

移植内存分配器相当简单。 它们中的大多数不超过一个源代码和一个头文件。 你必须为程序分配和释放页面挂载对应功能，这样内存分配器就可以使用内存。

有些内存分配器使用一对Hook钩子，这些钩子允许分配器以 “页面” 的方式从内核请求内存。 这些内存分配器将在源代码中某处存储一个常量，该常量是页面大小是多少 (例如，对于4KB页，“# define PAGE_SIZE 4096”)，因此分配器知道一次要请求多少页。 使用这些分配器，你必须挂钩/实现:

• void *alloc_page(size_t pages) - 在虚拟内存中分配 “页面” 或连续页面，并返回指向组开头的指针。
• void free_page(void *start, size_t pages) - 将虚拟内存中的 “页面”或连续页面从 “开头” 释放回内核。

此外，一些内存分配器将要求你挂载锁定功能，以确保内存分配器的关键部分不会产生多个线程同时执行的问题。 通常，这些函数将看起来像这样;

• void wait_and_lock_mutex() - 在进入关键部分之前锁定互斥锁。 最简单的 “锁定” 解决方案是禁用可能适合作为起点的中断。 为了获得最佳性能，建议实现自旋锁。
• void unlock_mutex() - 离开关键部分后解锁互斥锁。 你可以再次启用中断，也可以重置自旋锁。 这允许任何等待的线程运行进入关键部分。

选择内存分配器

有许多内存分配器可供选择。 没有完美的内存分配器，因为不同的分配器试图实现许多不同的目标。 通常这些都是相互冲突的目标，因此不同的分配者有不同的权衡。

分配器的特性如下;

• .. 快速。 它们每秒可以执行最多的分配和释放。 “快速” 是上下文敏感的，一个分配器在某些情况下 (分配大量大块) 可能快，而在其他情况下 (分配和释放大量小块) 可能不快。

• .. 空间效率。 虽然有些分配器可能会将内存与页面边界对齐，或者具有占用兆字节的巨大内部结构，但这些分配器确保所有内存都被打包到最紧密的拟合区域中，并且不会浪费任何字节。 如果你没有太多的内存，这一点尤其重要。

• .. 稳定。 有些分配器可能很快，但是也需这些分配器被设计为运行很长时间。 他们专注于最小化内存碎片，这对于连续运行数月的服务器很重要。

• .. 可扩展。 仅从单个线程分配时，还有一些分配器速度较快，但是存在其他线程必须锁定并等待轮到它们的问题。 而可扩展性好的分配器，可以同时处理来自最新四核CPU上的数百个线程的分配，而不会造成重大的性能损失和最小的锁定。

• .. 实时。 可能有的快速分配器，“平均” 需要75个周期来分配一个块，但偶尔会有更糟糕的情况，需要350个周期。 实时分配器可以保证在少于200个周期内返回内存指针。 这在媒体解码和实时系统中才是理想的实现。

有很多分配器可供选择，以下是一份不完全的列表;

• liballoc - 出色的分配器，最初是Spoon操作系统的一部分，设计为插入hobby OS。
• dlmalloc - 道格·李的内存分配器。广泛使用和移植的良好的通用内存分配器。
• TCMalloc 线程缓存Malloc。一种实验性的可扩展分配器。
• nedmalloc 一个非常快速和非常可扩展的分配器。 这两个属性使其在多线程视频游戏中较为流行，可以替代默认提供的分配器。
• ptmalloc glibc包含的一种广泛使用的内存分配器，可在节省空间的同时合理缩放。
• jemalloc 强调避免碎片和可扩展并发支持的通用malloc(3) 实现，首先在FreeBSD中使用
• Hoard 是malloc的直接替代品，可以显着提高应用程序性能，特别是对于在多处理器和多核cpu上运行的多线程程序。

另见

教程

• Writing a memory manager

外部链接

• Memory Management 1 - 蒂姆·罗宾逊 (Tim Robinson) 关于内存管理的两部分系列文章的第一部分
• Memory Management 2 - 蒂姆·罗宾逊 (Tim Robinson) 关于内存管理的两部分系列的第二部分
• Publications about 'Memory Management' - 一些好文章的列表
• TLSF: Memory Allocator for Real-Time 专为满足实时要求而设计的通用动态内存分配器