C - 设计你自己的 free() 函数

Question

今天，我出现在面试中，面试官问我这个，

1. Tell me the steps how will you design your own free( ) function for deallocate the allocated memory.
2. How can it be more efficient than C's default free() function ? What can you conclude ?

我很困惑，想不出设计的方法。

你们觉得怎么样 ？

编辑:因为我们需要知道 malloc()工作，你能告诉我写我们自己的步骤吗 malloc()功能

Answer 1

这实际上是一个非常模糊的问题，这可能就是您感到困惑的原因。他的意思是，给定现有的 malloc 实现，您将如何尝试开发一种更有效的方法来释放底层内存？还是他希望您开始讨论不同类型的 malloc 实现以及它们的好处和问题？他是否希望您知道虚拟内存在 x86 架构上的功能？

此外，更高效是指更节省空间还是更节省时间？ free() 必须是确定性的吗？它是否必须尽可能多地将内存返回给操作系统，因为它处于低内存、多任务环境中？我们这里的标准是什么？

很难说从哪里开始像这样一个模糊的问题，除了开始问你自己的问题以获得澄清。毕竟要设计自己的free函数，首先要知道malloc是如何实现的。所以很有可能，问题实际上是关于你是否知道如何实现 malloc。

如果您不熟悉内存管理的内部结构，开始了解 malloc 是如何实现的最简单方法是首先编写自己的。

查看 this IBM DeveloperWorks article called "Inside Memory Management"对于初学者。

但在您编写自己的 malloc/free 之前，您首先需要分配/释放内存。不幸的是，在 protected 模式的操作系统中，您不能直接寻址机器上的内存。那你怎么得到它？

你问操作系统。借助 x86 的虚拟内存特性，任何一 block RAM 或交换内存都可以由操作系统映射到内存地址。您的程序所看到的内存可能在整个系统中物理上是碎片化的，但是由于内核的虚拟内存管理器，它看起来都一样。

内核通常提供允许您为进程映射额外内存的系统调用。在较旧的 UNIX 操作系统上，这通常是 brk/sbrk 将堆内存增长到进程的边缘或缩小它，但许多系统还提供 mmap/munmap 来简单地映射一大 block 堆内存。只有一次你可以访问需要 malloc/free 来管理的大的、连续的内存块。

一旦你的进程有一些可用的堆内存，它就是把它分成 block ，每个 block 都包含它自己的元信息，关于它的大小和位置以及它是否被分配，然后管理这些 block 。一个简单的结构列表，每个都包含一些元信息字段和一个大字节数组，可以工作，在这种情况下 malloc 必须遍历列表，直到找到足够大的未分配 block (或它可以组合的 block )，并且如果找不到足够大的 block ，则映射更多内存。一旦你找到一个 block ，你只需返回一个指向数据的指针。 free() 然后可以使用该指针将几个字节反转回结构中存在的成员字段，然后可以对其进行修改(即标记 chunk.allocated = false;)。如果列表末尾有足够多的未分配 block ，您甚至可以将它们从列表中删除，并从进程堆中取消映射或缩小该内存。

这是一个真正简单的实现 malloc 的方法。您可以想象，有很多可能的方法可以将您的内存分成 block 然后管理这些 block 。有多少数据结构和算法就有多少方法。它们也都是为不同的目的而设计的，比如限制由于小的、已分配的 block 与小的、未分配的 block 混合而导致的碎片，或者确保 malloc 和 free 运行得快(或者有时甚至更慢，但可以预见地慢)。有dlmalloc , ptmalloc , jemalloc , Hoard's malloc ，还有更多，其中许多非常小而简洁，所以不要害怕阅读它们。如果我没记错的话，Kernighan 和 Ritchie 的“The C Programming Language”甚至使用了一个简单的 malloc 实现作为他们的示例之一。