处理内存池中的碎片？
假设我有一个内存池对象，其构造函数采用指向一大块内存 ptr 和大小 N 的指针。如果我进行多次随机分配和不同大小的释放，我可以获得处于无法分配内存的状态的内存。 M 字节对象在内存中连续存在，尽管可能有很多空闲！同时，我无法压缩内存，因为这会导致消费者出现悬空指针。在这种情况下如何解决碎片问题？
Suppose I have a memory pool object with a constructor that takes a pointer to a large chunk of memory ptr and size N. If I do many random allocations and deallocations of various sizes I can get the memory in such a state that I cannot allocate an M byte object contiguously in memory even though there may be a lot free! At the same time, I can't compact the memory because that would cause a dangling pointer on the consumers. How does one resolve fragmentation in this case?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我想添加我的 2 美分只是因为没有其他人指出，从你的描述来看，听起来你正在实现一个标准的堆分配器（即我们所有人每次调用 malloc() 或 new 运算符时都已经使用的分配器）。
堆正是这样一个对象，它进入虚拟内存管理器并请求大块内存（您称之为“池”）。然后它有各种不同的算法来处理分配各种大小的块并释放它们的最有效方式。此外，多年来许多人修改和优化了这些算法。长期以来，Windows 都带有一个名为低碎片堆 (LFH) 的选项，您过去必须手动启用该选项。从 Vista 开始，所有堆默认使用 LFH。
堆并不完美，如果使用不当，它们肯定会降低性能。由于操作系统供应商不可能预测您将使用堆的每种情况，因此他们的堆管理器必须针对“平均”使用进行优化。但是，如果您的要求类似于常规堆的要求（即许多对象，不同的大小......），您应该考虑只使用堆而不是重新发明它，因为您的实现很可能不如操作系统已经为你提供了。
使用内存分配时，通过不简单地使用堆来获得性能的唯一时间是放弃一些其他方面（分配开销、分配生命周期......），这对您的特定应用程序并不重要。
例如，在我们的应用程序中，我们需要许多小于 1KB 的分配，但这些分配仅使用非常短的时间（毫秒）。为了优化应用程序，我使用了 Boost Pool 库，但对其进行了扩展，以便我的“分配器”实际上包含一组 Boost Pool 对象，每个对象负责分配一个从 16 字节到 1024 字节的特定大小（步骤 4）。这提供了几乎免费（O(1) 复杂度）的分配/释放这些对象，但问题是 a) 内存使用量总是很大并且永远不会下降，即使我们没有分配单个对象，b) Boost Pool 永远不会释放它使用的内存（至少在我们使用它的模式下），所以我们只将它用于不会停留很长时间的对象。
那么您愿意在应用程序中放弃正常内存分配的哪些方面？
I wanted to add my 2 cents only because no one else pointed out that from your description it sounds like you are implementing a standard heap allocator (i.e what all of us already use every time when we call malloc() or operator new).
A heap is exactly such an object, that goes to virtual memory manager and asks for large chunk of memory (what you call "a pool"). Then it has all kinds of different algorithms for dealing with most efficient way of allocating various size chunks and freeing them. Furthermore, many people have modified and optimized these algorithms over the years. For long time Windows came with an option called low-fragmentation heap (LFH) which you used to have to enable manually. Starting with Vista LFH is used for all heaps by default.
Heaps are not perfect and they can definitely bog down performance when not used properly. Since OS vendors can't possibly anticipate every scenario in which you will use a heap, their heap managers have to be optimized for the "average" use. But if you have a requirement which is similar to the requirements for a regular heap (i.e. many objects, different size....) you should consider just using a heap and not reinventing it because chances are your implementation will be inferior to what OS already provides for you.
With memory allocation, the only time you can gain performance by not simply using the heap is by giving up some other aspect (allocation overhead, allocation lifetime....) which is not important to your specific application.
For example, in our application we had a requirement for many allocations of less than 1KB but these allocations were used only for very short periods of time (milliseconds). To optimize the app, I used Boost Pool library but extended it so that my "allocator" actually contained a collection of boost pool objects, each responsible for allocating one specific size from 16 bytes up to 1024 (in steps of 4). This provided almost free (O(1) complexity) allocation/free of these objects but the catch is that a) memory usage is always large and never goes down even if we don't have a single object allocated, b) Boost Pool never frees the memory it uses (at least in the mode we are using it in) so we only use this for objects which don't stick around very long.
So which aspect(s) of normal memory allocation are you willing to give up in your app?
根据系统的不同，有几种方法可以做到这一点。
首先尽量避免碎片，如果您分配 2 的幂的块，那么导致这种碎片的机会就会较小。还有其他几种方法可以解决这个问题，但如果你达到了这种状态，那么你就会在那时 OOM，因为除了杀死请求内存的进程、阻塞直到你可以分配内存之外，没有其他微妙的方法来处理它。返回 NULL 作为您的分配区域。
另一种方法是将指针传递给数据指针（例如：int **）。然后，您可以重新排列程序下方的内存（我希望是线程安全的）并压缩分配，以便您可以分配新块并仍然保留旧块中的数据（一旦系统达到这种状态，虽然这会成为沉重的开销，但很少会发生）完成）。
还有一些“分箱”内存的方法，以便您拥有连续的页面，例如，将 1 个页面专用于 512 及以下的分配，另一个用于 1024 及以下的分配，等等......这使得更容易决定使用哪个 bin在最坏的情况下，您从下一个最高的垃圾箱中拆分或从较低的垃圾箱中合并，这减少了跨多个页面碎片的机会。
Depending on the system there are a couple of ways to do it.
Try to avoid fragmentation in the first place, if you allocate blocks in powers of 2 you have less a chance of causing this kind of fragmentation. There are a couple of other ways around it but if you ever reach this state then you just OOM at that point because there are no delicate ways of handling it other than killing the process that asked for memory, blocking until you can allocate memory, or returning NULL as your allocation area.
Another way is to pass pointers to pointers of your data(ex: int **). Then you can rearrange memory beneath the program (thread safe I hope) and compact the allocations so that you can allocate new blocks and still keep the data from old blocks (once the system gets to this state though that becomes a heavy overhead but should seldom be done).
There are also ways of "binning" memory so that you have contiguous pages for instance dedicate 1 page only to allocations of 512 and less, another for 1024 and less, etc... This makes it easier to make decisions about which bin to use and in the worst case you split from the next highest bin or merge from a lower bin which reduces the chance of fragmenting across multiple pages.
为您经常分配的对象实现对象池将大大减少碎片，而无需更改您的内存分配器。
Implementing object pools for the objects that you frequently allocate will drive fragmentation down considerably without the need to change your memory allocator.
更准确地了解您实际想要做什么会很有帮助，因为有很多方法可以解决这个问题。
但是，第一个问题是：这是实际发生的，还是理论上的问题？
需要记住的一件事是，通常有比物理内存更多的可用虚拟内存地址空间，因此即使物理内存碎片化，仍然有大量连续的虚拟内存。 （当然，物理内存在下面是不连续的，但你的代码看不到这一点。）
我认为有时对内存碎片有毫无根据的恐惧，因此人们编写了一个自定义内存分配器（或更糟糕的是，他们编造了一个方案句柄和可移动内存和压缩）。我认为这些在实践中很少需要，有时扔掉它并重新使用 malloc 可以提高性能。
It would be helpful to know more exactly what you are actually trying to do, because there are many ways to deal with this.
But, the first question is: is this actually happening, or is it a theoretical concern?
One thing to keep in mind is you normally have a lot more virtual memory address space available than physical memory, so even when physical memory is fragmented, there is still plenty of contiguous virtual memory. (Of course, the physical memory is discontiguous underneath but your code doesn't see that.)
I think there is sometimes unwarranted fear of memory fragmentation, and as a result people write a custom memory allocator (or worse, they concoct a scheme with handles and moveable memory and compaction). I think these are rarely needed in practice, and it can sometimes improve performance to throw this out and go back to using malloc.