处理内存池中的碎片？

Question

假设我有一个带有构造函数的内存池对象,该构造函数获取指向大块内存ptr和大小为N的指针.如果我做了许多随机分配和各种大小的解除分配,我可以获得内存,使得我无法分配M字节对象在内存中连续存在,即使可能有很多空闲!与此同时,我无法压缩内存,因为这会导致消费者的悬空指针.在这种情况下如何解决碎片问题？

Answer 1

我想加上我的2美分只是因为没有人指出你的描述听起来好像你正在实现一个标准的堆分配器(即我们所有人在每次调用malloc()或operator new时都已经使用过).

堆就是这样一个对象,进入虚拟内存管理器并请求大块内存(你称之为"池").然后它有各种不同的算法来处理分配各种大小的块并释放它们的最有效方法.此外,许多人多年来一直在修改和优化这些算法.很长一段时间,Windows都提供了一个称为低碎片堆(LFH)的选项,您以前必须手动启用它.从Vista开始LFH默认用于所有堆.

堆不完美,如果使用不当,它们肯定会使性能陷入困境.由于操作系统供应商无法预测您将使用堆的每个场景,因此他们的堆管理器必须针对"平均"使用进行优化.但是如果你的需求类似于常规堆的需求(即许多对象,不同大小......),你应该考虑只使用堆而不是重新发明它,因为你的实现可能性不如操作系统已经为你提供了.

通过内存分配,您可以通过不仅仅使用堆来获得性能的唯一时间是放弃一些其他方面(分配开销,分配生命周期......),这对您的特定应用程序并不重要.

例如,在我们的应用程序中,我们要求许多分配小于1KB,但这些分配仅用于非常短的时间段(毫秒).为了优化应用程序,我使用了Boost Pool库但扩展了它,以便我的"allocator"实际上包含一组boost池对象,每个对象负责分配一个特定大小,从16个字节到1024个(步长为4).这提供了几乎免费(O(1)复杂性)分配/免除这些对象,但问题是:a)内存使用总是很大,即使我们没有分配单个对象也不会失败,b)Boost Pool never释放它使用的内存(至少在我们使用它的模式中),所以我们只将它用于不会长时间停留的对象.

那么您愿意在应用程序中放弃正常内存分配的哪个方面？

Answer 2

根据系统的不同,有几种方法可以做到这一点.

首先尝试避免碎片,如果你以2的幂分配块,你就不太可能造成这种碎片.还有其他几种方法,但是如果你达到这种状态,那么你就是OOM,因为除了杀死要求内存的进程,阻塞直到你可以分配内存之外,没有其他处理它的方法,或者返回NULL作为您的分配区域.

另一种方法是将指针传递给数据指针(例如:int**).然后你可以重新安排程序下面的内存(我希望线程安全)并压缩分配,这样你就可以分配新的块并仍然保留旧块的数据(一旦系统达到这种状态,虽然这会成为一个沉重的开销,但很少应该很少完成).

还有一些"分箱"内存的方法,以便你有连续的页面,例如专用1页只分配512或更少,另一个1024和更少,等...这使得更容易决定使用哪个bin并且在最坏的情况下,您从下一个最高分档中拆分或从较低分档合并,这样可以减少跨多个页面分段的可能性.