首页 文章

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

提问于
浏览 次
25

我总是假设heap (data structure)用于实现一个heap (dynamic memory allocation)，但我've been told I'错了 .

通常情况下，如何实现堆（例如，典型的 malloc 例程或Windows的 HeapCreate 等实现的堆）？他们使用什么数据结构？

我不是要问：

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

  • 从未将内存释放回操作系统的堆（！）

  • 只能在类似大小的小块上提供合理的性能

  • 仅为大型连续块提供合理性能的堆

  • 等

这很有趣，他们都避免了更难的问题：
"normal"，通用堆（如 malloc ， HeapCreate 背后的那个）是如何实现的？

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

memory-management data-structures heap

2 回答

  • 14

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

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

    • 内存以大块的形式从系统中获取 - 一次通常为兆字节 .

    • 然后在执行分配时将这些块拆分为各种较小的块 . 与您分配的大小不完全相同，但通常在某些范围内（200-250字节，251-500字节等） . 有时这是多层次的，你有一个额外的"medium chunks"层，它在你的实际请求之前 .

    • 控制哪一个"large chunk"打破一块是非常困难和重要的事情 - 这极大地影响了内存碎片 .

    • 为这些范围中的每一个维护一个或多个空闲池（也称为"free list"，"memory pool"，"lookaside list"） . 有时甚至是线程本地池 . 这可以大大加快分配/解除分配大小相似的许多对象的模式 .

    • 大量分配的处理方式略有不同，以免浪费大量内存，如果有的话，不要汇集太多内存 .

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

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

    这导致* nix兼容的分配器通常直接为您提供 malloc / free 实现，其中它只为一切使用一个分配器（否则它们会相互踩踏），而Windows特定的分配器提供额外的功能，留下 malloc /单独使用 free 并且可以和谐使用（例如，您可以使用HeapCreate创建可以与其他人一起工作的私有堆） .

    实际上，这种灵活性的交易使得* nix分配器在性能方面略有提升 . 它是偶然的，因为不同的DLL使用不同的运行时，每个运行时都有自己的 malloc / free ，如果你没有勤奋地跟踪哪些堆来自哪个堆，可能会引起很多麻烦 .

    回复于
  • 6

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

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

    • 是的，这在Unix机器上很常见;由于* nix的底层API和内存模型的运行方式 . 基本上，标准API将内存返回给操作系统系统只允许在分配用户内存和用户内存与系统工具（如堆栈）之间的"hole"之间返回内存 . （有问题的API是brk or sbrk） . 许多堆只是尝试重用程序本身不再使用的内存，而不是尝试将内存返回给系统，而不是将内存返回给操作系统 . 这在Windows上不常见，因为它等同于 sbrk （ VirtualAlloc ）没有此限制 . （但是像 sbrk 一样，它非常昂贵并且有一些注意事项，例如只分配页面大小和页面对齐的块 . 所以堆尽量尝试尽可能少）

    • 这听起来像"block allocator"，它将内存分成固定大小的块，然后只返回一个空闲块 . 对于我（尽管有限）的理解，Windows' RtlHeap 为不同的已知块大小维护了许多这样的数据结构 . （例如，对于大小为16的块，它会有一个）RtlHeap称这些为"lookaside lists" .

    • 我真的不知道处理这种情况的具体结构 . 对于大多数分配系统来说，大块是有问题的，因为它们会导致地址空间碎片化 .

    我发现讨论主要平台上采用的通用分配策略的最佳参考是书Secure Coding in C and C++, by Robert Seacord . 第4章的所有内容都专门用于堆数据结构（以及当用户错误地使用所述堆系统时引起的问题） .

    回复于

相关问题