首次适配分配算法如何减少内存碎片？

Question

我正在阅读 Real World OCaml 的第21章 垃圾回收器的理解。在内存分配策略部分中，它说：

首次适配分配

如果程序分配了许多不同大小的值，则有时可能会发现您的空闲列表变得分散。在这种情况下，尽管存在空闲块，但GC被迫执行昂贵的压缩，因为没有单个块足够大来满足请求。

首次适配分配专注于减少内存碎片（从而减少压缩的数量），但以更慢的内存分配为代价。每次分配都会从开头扫描空闲列表以查找合适的空闲块，而不是像下一适配器那样重新使用最近的堆块。

我无法理解首次适配分配如何与下一适配分配相比减少内存碎片，这两种算法的唯一区别是它们从不同的位置开始搜索。

• 材料设计动画 - 工作分配的首次适应和最佳适应
• 内存管理中的首次适应、下一次适应和最佳适应算法是什么？

- zhumengzhu

---

想象一下这种情况。你开始有n个空闲块。你分配一个块，然后再分配另一个块，接着释放第一个块。你重复这个过程n/2次，因此在过程结束时，你将会有n/2个块已被分配和n/2个块仍然是空闲的。使用next-fit算法，你将获得交替分配的效果；而使用first-fit算法，则会使堆的后半部分完全为空。 - biziclop

当然，硬币的另一面是，在使用首次适应算法期间，您必须大约检查n ^ 2/4个块，而在使用下一次适应算法时只需检查n个块。 - biziclop

Answer 1

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

- Jeffrey Scofield

Answer 2

以下是关于内存分配策略的总结，以及解决实际程序中可能出现的内存碎片问题的方法：“The Memory Fragmentation Problem: Solved?” 一文，作者是Johnstone和Wilson。他们指出，对于这个问题的大多数研究都是通过模拟内存分配和释放来进行的（Knuth在第1卷第2.5节中也提到了这一点）。他们的贡献在于从基于统计研究和随机数生成器的模拟研究转向基于真实程序内存分配行为的跟踪数据的模拟研究。在这种情况下，他们发现一种针对实际情况调整的最佳适配变体，即为常用块大小使用专门的空闲列表，可以表现得非常好。

因此，我认为你的答案是除了模拟研究的结果外，并没有简单明确的答案。对于常见的C/C++程序，实际上可以制定一种最佳适配变体来工作 - 但如果OCaml的存储分配行为与C/C++有显著的不同，那么只有当有人使用真实程序或跟踪数据运行不同的分配器时，我们才真正了解什么是好的和坏的。

- mcdowella

---

在您提到的文章的2.1.1节中，它说：“如果块比必要的大，则会将其分割并将剩余部分放在空闲列表中。” OCaml 中也是这样发生的吗？ - zhumengzhu

我对OCaml没有特别的了解，但通常只返回必要的内容并将其余部分拆分并放在空闲列表中。实际上，您通常只使用一个自由块启动系统，其中包含所有可用内存。一个执行不同操作的系统示例是Buddy系统，它仍然会拆分块，但只是为了保持所有大小都是2的幂。这会导致所谓的内部碎片，其中会浪费空间，因为如果用户请求的大小不是2的幂，则会交付比请求的块更大的块。 - mcdowella