最适合vs隔离适合vs伙伴系统,以减少碎片

Question

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

对于伙伴系统,我读过它有很高的内部碎片,因为大多数要求的大小都不是2的幂.

为了最合适,我听到的唯一消极是它是顺序的,所以搜索需要很长时间(在我的情况下不是问题).在任何情况下,我都可以使用我理解的二叉树来搜索.我还可以将固定大小的数组拆分为两个,其中左侧大小用于较小的块,正确的大小用于较大的块.我不知道其他任何负面消息.

对于隔离拟合,它类似于伙伴系统,但我不确定它是否具有相同的碎片问题,因为它不会被2的幂分割.

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

Answer 1

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

当您开始考虑减少通用内存管理器中的碎片时，您提到的这些简单算法将没有任何作用。有一些复杂的内存管理算法可以处理此类问题，例如jemalloc、tcmalloc和Poul-Henning Kamp malloc 。围绕此发布了许多白皮书。ACM 和 IEEE 有大量与此相关的文献。