Memory Allocation

来自osdev
跳到导航 跳到搜索
本篇是关于内存分配(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接口 (malloccallocreallocfree 在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上运行的多线程程序。

另见

教程

外部链接