algorithm - 优先分配算法如何减少内存碎片？

Question

我正在阅读 Chapter 21 Understanding the Garbage Collector真实世界的 OCaml。 在内存分配策略部分，它说:

First-fit allocation

If your program allocates values of many varied sizes, you may sometimes find that your free list becomes fragmented. In this situation, the GC is forced to perform an expensive compaction despite there being free chunks, since none of the chunks alone are big enough to satisfy the request.

First-fit allocation focuses on reducing memory fragmentation (and hence the number of compactions), but at the expense of slower memory allocation. Every allocation scans the free list from the beginning for a suitable free chunk, instead of reusing the most recent heap chunk as the next-fit allocator does.

我无法弄清楚与下一次适合分配相比，首次适合分配如何减少内存碎片，这两种算法的唯一不同是它们从不同的地方开始搜索。

• Material Design Animation - Jobs allocation First Fit & Best Fit
• What are the first fit, next fit and best fit algorithms for memory management?

Answer 1

我认为简短的回答是 Next Fit 从整个空闲内存区域的 block 中分配，这意味着所有 block 的大小都在缓慢减小。 First Fit 从尽可能靠近前面的地方分配，所以小块集中在那里。因此，大块的供应持续时间更长。由于压缩发生在没有足够大的空闲 block 的情况下，First Fit 将需要更少的压缩。