使用什么数据结构来实现动态内存分配堆？

Question

我总是假设堆(数据结构)用于实现堆(动态内存分配),但我被告知我错了.

通常情况下,如何实现堆(例如,通过典型malloc例程或Windows 实现的堆HeapCreate)？他们使用什么数据结构？

我不是要问:

在线搜索时,我已经看到了大量关于如何实施严格限制的堆的描述.
仅举几例,我已经看到了很多关于如何实现的描述:

• 永远不会将内存释放回操作系统的堆(!)
• 堆只能在小型,类似大小的块上提供合理的性能
• 堆只能为大型连续块提供合理的性能
• 等等

而这很有趣,他们都避开更难的问题:
如何是"正常"的,通用的堆(如一个在后面malloc,HeapCreate)来实现？

他们使用什么数据结构(可能还有算法)？

Answer 1

分配器往往非常复杂,并且在实施方式上往往存在很大差异.

您无法用一种常见的数据结构或算法来描述它们,但有一些共同的主题:

1. 内存以大块的形式从系统中获取 - 通常一次以兆字节为单位.
2. 然后在执行分配时将这些块拆分为各种较小的块.与您分配的大小不完全相同,但通常在某些范围内(200-250字节,251-500字节等).有时候这是多层次的,你会在实际请求之前有一层额外的"中等块".
3. 控制哪个"大块"打破一块是非常困难和重要的事情 - 这极大地影响了内存碎片.
4. 为这些范围中的每一个维护一个或多个空闲池(也称为"空闲列表","存储池","后备列表").有时甚至是线程本地池.这可以大大加快分配/解除分配大小相似的许多对象的模式.
5. 大量分配的处理方式略有不同,以免浪费大量内存,如果有的话,不要汇集太多内存.

如果你想查看一些源代码,jemalloc是一个现代的高性能分配器,应该代表其他常见的复杂性.TCMalloc是另一种常见的通用分配器,它们的网站涉及所有血腥实现细节.英特尔的线程构建模块具有专为高并发性而构建的分配器.

Windows和*nix之间可以看到一个有趣的区别.在*nix中,分配器对应用程序使用的地址空间具有非常低级别的控制.在Windows中,你基本上有一个粗粒度的慢速分配器,VirtualAlloc可以将你自己的分配器作为基础.

这导致*nix兼容的分配器通常直接给你一个malloc/ free实现,假设你只使用一个分配器来代替所有东西(否则它们会相互踩踏),而Windows特定的分配器提供额外的功能,离开malloc/ free单独,并且可以和谐地使用(例如,您可以使用HeapCreate来创建可以与其他人一起工作的私有堆).

实际上,这种灵活性的交易使得*nix分配器在性能方面略有提升.很少见到一个应用程序故意在Windows上使用多个堆 - 大多数是偶然的,因为不同的DLL使用不同的运行时,每个运行时都有自己的malloc/ free,如果你不勤于跟踪哪个堆,会引起很多麻烦一些记忆来自.

Answer 2

注意:以下答案假设您使用的是具有虚拟内存的典型现代系统.C和C++标准不需要虚拟内存; 因此,当然,如果没有此功能,您不能依赖硬件上的这些假设(例如,GPU通常没有此功能;也不会像PIC这样的极小型硬件).

这取决于您使用的平台.堆可以是非常复杂的野兽; 他们不只使用单一的数据结构; 并且没有"标准"数据结构.即使堆代码所在的位置也不同,具体取决于平台.例如,堆代码通常由Unix上的C Runtime框提供; 但通常由Windows上的操作系统提供.

1. 是的,这在Unix机器上很常见; 由于*nix的底层API和内存模型的运行方式.基本上,在这些系统上将内存返回给操作系统的标准API仅允许在分配用户内存的"前沿"和用户内存与堆栈等系统设施之间的"漏洞"之间返回内存.(有问题的API是brk或sbrk).许多堆只是尝试重用程序本身不再使用的内存,而不是尝试将内存返回给系统,而不是将内存返回给操作系统.这在Windows上不太常见,因为它等效于sbrk(VirtualAlloc)没有此限制.(但是sbrk,它非常昂贵并且有一些警告,例如只分配页面大小和页面对齐的块.所以堆尽量尝试尽可能少)
2. 这听起来像一个"块分配器",它将内存划分为固定大小的块,然后只返回一个空闲块.对于我(虽然有限)的理解,Windows' RtlHeap为不同的已知块大小维护了许多这样的数据结构.(例如,对于大小为16的块,它会有一个)RtlHeap称这些为"后备列表".
3. 我真的不知道处理这种情况的具体结构.对于大多数分配系统来说,大块是有问题的,因为它们会导致地址空间碎片化.

我发现讨论主要平台上常用分配策略的最佳参考是Robert Seacord撰写的" C和C++中的安全编码 "一书.第4章的所有内容都专门用于堆数据结构(以及当用户错误地使用所述堆系统时引起的问题).