c++ - 内存池/内存分配器的正确布局？ (哪个算法)

Question

你好，我正在考虑通过尝试一些我以前从未做过的事情来扩展我的技能。一直让我有点困惑的一件事是内存分配器和内存池。我想要做的是拿一 block 内存，只从系统分配一次内存。我目前已经设置好了，内存是一个字节(或字符)数组，用于测试目的是 65535。

我考虑使用两种算法。

首先是一种算法，其中整个数据 block 附加了剩余的内存量，以及指向第一个分配 block (或 block 头)的指针(或更确切地说是偏移量)，然后每次分配都是前面是分配的大小，以及上一个和下一个分配，所以我可以轻松释放分配。然后，我可以通过查看当前分配后的空间来生成最大和最小的 block 。

我的另一个选择是在分配的内存之前添加第二个偏移量，并将其指向第一个未分配的 block ，然后每个未分配的 block 也有上一个和下一个分配，以及一个大小，以便我可以轻松找到可以放置我的下一个分配的地方。

问题是我不知道哪个是“正确的”。假设我们将有可变大小的分配(但大多数分配的大小不会有那么大的开销。)第一个分配会比较慢，以获得最大和最小的可能 block ，但我可以存储它们并在必要时对其进行操作以避免重新生成它们。然而，第二个将花费更长的时间来释放(由于必须找到哪个释放器紧挨着哪个分配器)并且不一定会给分配带来任何好处。事实上，对于剩余少于 6 个字节的情况(2 个字节用于大小，2 个用于上一个偏移量，2 个用于下一个偏移量)，它需要更专门的代码。

我的直觉告诉我第一个要好得多，但第二个的某些方面很诱人。有什么意见吗？或者有更简单的解决方案吗？

Answer 1

这种方法的问题是处理碎片(以及如何合并相邻的空闲内存块)。看这道题:Designing and coding a non-fragmentizing static memory pool , 讨论了一种不同的方法...