c - 测试内存碎片

Question

因此，作为我正在学习的操作系统类(class)的一部分，我实现了一个内存分配器(就像 C 中的 malloc 一样)。可用空间存储在链表中。

接下来我的问题是:我将如何测试各种分配策略(例如，最适合、最适合和最差适合)。现在我只是迭代预定义的次数，每次分配一个大小为 1-N 字节的 block ，其中 N 类似于 20000。基本上我分配一些迭代然后我通过释放一些分配的 block 。在退出之前，我检查了 freelist 并计算了外部碎片。我不确定这是否是要走的路，还是有更好的方法来做到这一点？

为每种策略选择随机 block 大小的一个问题是，如果分配的 block 大小不同，则无法真正比​​较它们，对吧？所以替代方案是执行相同的测试，只是现在我在测试每个策略时使用相同的分配大小并释放相同的 block 。

希望这不会令人困惑:)

Answer 1

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

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

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

对于像 Glibc 这样从 Linux 重建包，一个很好的资源是 Linux from Scratch 项目，http://www.linuxfromscratch.org/ .