c - 最佳匹配 vs 隔离匹配 vs 伙伴系统，以实现最少的碎片化

Question

我正在使用 C 中的固定大小的数组进行动态内存分配模拟(malloc() 和 free())，我想知道其中哪些会产生最少的碎片(内部和外部)？我不在乎速度，能够减少碎片是我想要解决的问题。

对于伙伴系统，我读到它具有很高的内部碎片，因为大多数请求的大小不是 2 的幂。

为了最合适，我听说的唯一负面因素是它是连续的，因此搜索需要很长时间(在我的情况下不是问题)。在任何情况下，我都可以使用我理解的二叉树来代替搜索。我还可以将固定大小的数组分成两部分，左边的尺寸用于较小的 block ，右边的尺寸用于较大的 block 。我不知道任何其他负面因素。

对于隔离匹配，它类似于伙伴系统，但我不确定它是否存在相同的碎片问题，因为它不会被 2 的幂分割。

有没有人有一些统计数据或知道我以前使用过这些数据的问题的答案？

Answer 1

控制碎片取决于用例。永远不会发生碎片的唯一情况是您的 malloc() 函数在您调用它时返回一个固定大小的内存块。这更多地涉及内存池。一些高端服务器通常这样做是为了提高性能，因为它们知道自己将要分配什么以及将保持该分配多长时间。

当您开始考虑在通用内存管理器中减少碎片时，您提到的这些简单算法将无济于事。有复杂的内存管理算法，如 jemalloc , tcmalloc和 Poul-Henning Kamp malloc处理这类问题。围绕这一点发表了许多白皮书。 ACM 和 IEEE 有大量关于这方面的文献。