内存碎片化的测试

Question

作为我正在学习的操作系统课程的一部分，我已经实现了一个内存分配器（就像C语言中的malloc）。空闲空间存储在链表中。

我的问题是：如何测试各种分配策略（例如首次适应、最佳适应和最坏适应）？目前，我只是预定义了一定次数的迭代，每次分配大小为1-N字节的块，其中N大约为20000。基本上，我进行了一些迭代的分配，然后通过释放一些已分配的块来改变它。在退出之前，我检查自由列表并计算外部碎片。我不确定这是否是正确的方法，还是有更好的方法？

选择每种策略的随机块大小的一个问题是，如果分配的块大小不同，就无法真正比较它们，对吗？因此，另一种选择是执行相同的测试，只是现在在测试每种策略时使用相同的分配大小并释放相同的块。

希望这不会太令人困惑 :)

- me_L_coding

---

如果您的分配器的free()函数合并相邻块，则碎片数量将等于freelist上的项目数（加或减一）。 - wildplasser

@wildplasser。感谢您的回复:)我知道这个:)实际上，我已经有一个可以计算外部碎片的工作实现了。我更想知道测试不同策略的方法是否足够...还是有更好的方法吗？ - me_L_coding

也许最有用的度量方式是计算实际使用的页面数、有效页面数以及它们的比率。另一种度量方式可能是虚拟地址的有效跨度与实际跨度之比（max(address) - min(address)），地址空间也是一种有价值的资源。 - wildplasser

@wildplasser。确实是不错的技巧 :) - me_L_coding

Answer 1

这里有一个想法：您可以从实际运行的系统中采样数据，然后将其用作测试数据。您的测试人员只需要读取记录数据的日志文件，并重放相同的alloc()、free()调用到您的分配器中即可。在实践中实现这一点可能有些棘手，但在Linux上使用Glibc，它们有一种官方方法来添加自定义钩子到malloc、realloc和free函数中。

http://www.gnu.org/software/libc/manual/html_node/Hooks-for-Malloc.html

基本上，我想你可以构建一个修改过的 glibc，并通过 malloc()、realloc() 和 free() 调用记录每个分配请求的钩子。使用启用日志的 glibc 运行一些典型程序，并对这些程序执行一些典型操作。尽量使其有所代表性，比如如果你是为了测试 Web 服务器的使用情况而做这个工作，那就运行 Apache 等。生成的日志应该是系统的“真实”分配行为的合理模拟。为了使测试更准确，你应该在其他系统或其他场景下重复记录过程等等……以使你的样本更具代表性，不易受到“异常”的影响。好的分配器应该在尽可能多的真实测试中最大化性能，而不是有时表现得非常出色，有时则表现得糟糕。

对于从类似 Glibc 的 Linux 包重新构建，一个很好的资源是 Linux from Scratch 项目，http://www.linuxfromscratch.org/。

- Brandin