第一次合适的分配算法如何减少内存碎片？

我正在阅读Real World OCaml的Chapter 21 Understanding the Garbage Collector。在部分内存分配策略，它说：第一次合适的分配算法如何减少内存碎片？

首先匹配分配

如果你的程序分配许多不同大小的值，你有时可能会发现，你的空闲列表变得支离破碎。在这种情况下，即使存在空闲块，GC也被迫执行昂贵的压缩，因为单独的块都不足以满足请求。

首先适合的分配重点在于减少内存碎片（并因此减少压缩次数），但是会以较慢的内存分配为代价。每次分配都会从一开始就扫描空闲列表以获得合适的空闲块，而不是将最新的堆块重新用作下一个合适的分配器。

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

来源

2016-09-25 little.Pig

想象一下这种情况。你一开始就有'n''免费块。您分配一个区块，然后分配一个区块，然后释放第一个区块。你重复这个'n/2'的时间，所以在这个过程结束时你将有'n/2'块分配和'n/2'空闲。随着下一个适合你会让他们交替，首先适合，堆的后半部分将是完全空的。 – biziclop

当然，硬币的另一面是，首先适合你在这个过程中不得不检查大约n^2/4个块，而下一个只适合'n'。 – biziclop

我想简短的答案是，接下来装从块分配在整个自由存储区，这意味着所有的块大小缓慢降低。第一次飞行从尽可能靠近前方分配，因此小块集中在那里。因此，大块的供应持续更长时间。由于压缩发生在没有空闲块足够大的情况下，First Fit将需要更少的压缩。

来源

2016-09-25 03:39:13

有关内存分配策略的摘要和（可能）针对实际程序的内存碎片问题的解决方案http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.5185&rep=rep1&type=pdf“内存碎片问题：求解？”由约翰斯通和威尔逊。他们指出，关于这个问题的大部分工作都是通过模拟内存分配和释放（Knuth在第1卷第2.5节中做的一点）。他们的贡献是从基于统计研究和随机数生成器的模拟研究转向基于真实程序的内存分配行为痕迹的模拟研究。在这种制度下，他们发现为实际生活行为调整最佳配置的变体，其使用针对常用块大小的专用于特定存储器块大小的自由列表，确实很好。

所以我认为你的答案是，除了模拟研究的结果之外，没有简单明确的答案，对于常见的C/C++程序，最佳拟合的变体事实上可以很好地工作 - 但如果OCaml的存储分配行为与C/C++的存储分配行为明显不同，当有人用不同的分配器使用真正的程序或实际程序的痕迹运行测试时，我们只能真正了解什么是好的和坏的。

来源

2016-09-25 04:51:13 mcdowella

在2.1节中。你提到的那篇文章的第一部分，它说：“如果这个块比所需的大，它就会被分割，其余的被放在空闲列表中。”这是发生在OCaml吗？ –

我不知道OCaml特有的任何内容，但通常只回传必要的内容，并将剩下的内容分开并将其放在空闲列表中。实际上，你通常只用一个空闲块来启动系统，它包含所有可用的内存。一个能够做出不同事情的系统的例子是Buddy系统，该系统仍然会分割块，但只能保持所有尺寸都是2的幂。这导致了所谓的内部碎片，在这里空间被浪费了，因为如果用户要求不是2的幂次，他们将被递交比他们要求的更大的块。 – mcdowella

第一次合适的分配算法如何减少内存碎片？

回答

相关问题