29

我一直认为堆（数据结构）用于实现堆（动态内存分配），但有人告诉我我错了。

通常，堆（例如，由典型malloc例程或 WindowsHeapCreate等实现的堆）是如何实现的？他们使用什么数据结构？

我不是在问什么：

在网上搜索时，我看到了大量关于如何实现具有严格限制的堆的描述。
仅举几例，我已经看到了很多关于如何实现的描述：

  • 永远不会将内存释放回操作系统的堆（！）
  • 仅在类似大小的小块上提供合理性能的堆
  • 只为大的、连续的块提供合理性能的堆
  • 等等

有趣的是，它们都避免了更难的问题：
“正常”的通用堆（如 , 后面的堆malloc）是HeapCreate如何实现的？

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

4

2 回答 2

14

分配器往往非常复杂，并且在实现方式上往往存在显着差异。

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

  1. 内存是以大块的形式从系统中获取的——通常一次是兆字节。
  2. 然后，当您执行分配时，这些块会被分成各种更小的块。与您分配的大小不完全相同，但通常在特定范围内（200-250 字节、251-500 字节等）。有时这是多层的，在你的实际请求之前，你会有一个额外的“中等块”层。
  3. 控制从哪个“大块”中分离一块是一件非常困难且重要的事情——这会极大地影响内存碎片。
  4. 为每个这些范围维护一个或多个空闲池（又名“空闲列表”、“内存池”、“后备列表”）。有时甚至是线程本地池。这可以大大加快分配/释放许多类似大小的对象的模式。
  5. 大分配的处理方式略有不同，以免浪费大量 RAM，也不会被大量池化。

如果您想查看一些源代码，jemalloc是一种现代高性能分配器，应该在其他常见分配器的复杂性方面具有代表性。TCMalloc是另一种常见的通用分配器，他们的网站详细介绍了所有血腥的实现细节。英特尔的线程构建块有一个专门为高并发构建的分配器。

在 Windows 和 *nix 之间可以看到一个有趣的区别。在 *nix 中，分配器对应用程序使用的地址空间具有非常低级的控制。在 Windows 中，您基本上有一个粗略的、缓慢的分配器VirtualAlloc来作为您自己的分配器的基础。

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

在实践中，这种灵活性的交易使 *nix 分配器在性能方面略有提升。malloc在 Windows 上看到应用程序故意使用多个堆是非常罕见的——这主要是由于不同的 DLL 使用不同的运行时而导致的free意外一些记忆来自。

于 2012-12-09T05:34:14.767 回答
6

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

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

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

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

于 2012-12-09T05:29:18.960 回答