测试内存碎片

Question

因此，作为我正在学习的OS课程的一部分，我实现了一个内存分配器(就像C中的malloc一样)。空闲空间存储在链表中。

我的问题如下:如何测试各种分配策略(例如，first-fit，best-fit和worst-fit)。现在我只是迭代预定的次数，每次分配一个大小为1-N字节的块，其中N大约是20000。基本上，我分配一些迭代，然后通过释放一些分配的块来切换它。在退出之前，我检查freelist并计算外部碎片。我不确定这是不是应该这样做，或者有没有更好的方法来这样做？

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

希望这不会让人感到困惑:)

Answer 1

这只是一个想法:您可以从实际运行的系统中采样数据，然后将其用作测试数据。然后，您的测试人员只需要读取您记录的数据的日志文件，并对您的分配器重放相同的alloc()、free()调用。要在实践中实现这一点可能很棘手，但在带有Glibc的Linux上，他们有一种官方方法可以将自定义挂钩添加到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从头开始的项目http://www.linuxfromscratch.org/。