C – 设计你自己的free（）函数
今天，我出现在面试中，面试官问我这个，
- 告诉我你将如何设计自己的
free( )函数来解除分配内存的步骤。- 它如何比C的默认
free()函数更有效？ 你能得出什么结论？
我很困惑，想不出设计的方式。
你们觉得怎么样 ？
编辑：因为我们需要知道malloc()如何工作，你能告诉我编写自己的malloc()函数的步骤
这实际上是一个非常模糊的问题，这可能就是你迷茫的原因。 他是否意味着，鉴于现有的malloc实现，您将如何尝试开发一种更有效的方式来释放底层内存？ 或者他期待你开始讨论不同类型的malloc实现及其好处和问题？ 他是否希望您了解虚拟内存在x86架构上的function？
此外，通过提高效率，他是指更节省空间还是更节省时间？ free（）必须是确定性的吗？ 它是否必须尽可能多地向操作系统返回内存，因为它处于低内存，多任务环境中？ 我们的标准是什么？
除了开始提出自己的问题以澄清之外，很难说从哪里开始这样一个模糊的问题。 毕竟，为了设计自己的自由函数，首先必须知道如何实现malloc。 所以很有可能，问题在于你是否知道如何实现malloc。
如果您不熟悉内存管理的内部，那么开始了解如何实现malloc的最简单方法是首先编写自己的内存管理。
查看这篇名为“Inside Memory Management”的IBM DeveloperWorks文章 。
但在你编写自己的malloc / free之前，首先需要内存来分配/释放。 不幸的是，在受保护模式的操作系统中，您无法直接寻址机器上的内存。 那你怎么得到它？
你问操作系统。 借助x86的虚拟内存function，操作系统可以将任何RAM或交换内存映射到内存地址。 您的程序看到的内存在整个系统中可能是物理碎片，但是由于内核的虚拟内存管理器，它看起来都是一样的。
内核通常提供系统调用，允许您为进程映射额外的内存。 在较旧的UNIX操作系统上，通常是brk / sbrk将堆内存增加到进程的边缘或将其缩小，但是很多系统还提供mmap / munmap来简单地映射大块的堆内存。只有你一次可以访问一个大型，连续的内存块，您需要malloc / free来管理它。
一旦你的进程有一些可用的堆内存，它就是把它分成块，每个块都包含它自己的关于它的大小和位置的元信息，以及它是否被分配，然后管理这些块。 一个简单的结构列表，每个结构包含元信息和大量字节的一些字段，可以工作，在这种情况下，malloc必须运行列表，直到找到足够大的未分配块（或它可以组合的块），并且如果找不到足够大的块，则映射到更多内存。 找到块后，只需返回指向数据的指针即可。 然后，free（）可以使用该指针将几个字节反向回到结构中存在的成员字段，然后可以修改它（即标记chunk.allocated = false;）。 如果列表末尾有足够的未分配块，您甚至可以从列表中删除它们，并取消映射或缩小进程堆中的内存。
这是实现malloc的一种非常简单的方法。 可以想象，有很多可能的方法可以将内存分成块然后管理这些块。 数据结构和算法的方法有很多种。 它们都是为不同的目的而设计的，例如限制由于小的，分配的块与小的，未分配的块混合的碎片，或者确保malloc和自由运行快速（或者有时甚至更慢，但可预测地缓慢）。 有dlmalloc ， ptmalloc ， jemalloc ， Hoard的malloc等等，其中很多都非常小巧简洁，所以不要害怕阅读它们。 如果我没记错的话，Kernighan和Ritchie的“C编程语言”甚至使用一个简单的malloc实现作为他们的例子之一。
你不能盲目地设计free()而不知道malloc()是如何工作的，因为free()实现需要知道如何操作簿记数据，而且如果不知道malloc()是如何实现的话，这是不可能的。
所以一个不可回答的问题可能是你如何设计malloc（）和free（）而不是一个简单的问题但是你可以部分地回答它，例如通过提出一些非常简单的内存池实现，它不等同于malloc()当然会表明你的知识存在。
当您只能访问用户空间（通常称为内存池）时，一种常见方法是在应用程序启动时从操作系统中获取大量内存。 您的malloc需要检查该池的正确大小的哪些区域仍然是免费的（通过一些数据结构）并分发指向该内存的指针。 您的free需要在数据结构中将内存标记为空闲，并可能需要检查池的碎片。
好处是您可以在几乎恒定的时间内进行分配，缺点是您的应用程序消耗的内存比实际需要的内存多。
内存使用模式可能是一个因素。 free的默认实现不能假设你分配/解除分配的频率和你分配的大小。
例如，如果经常分配和释放大小相似的对象，则可以通过使用内存池来提高速度，内存效率和减少碎片。
编辑：正如尖锐的指出，只有将free和malloc设计在一起才有意义。 所以首先要弄清楚malloc是如何实现的。
告诉我你将如何设计自己的free（）函数来解除分配内存的步骤。
#include #undef free #define free(X) my_free(X) inline void my_free(void *ptr) { }
它如何比C的默认free（）函数更有效？
它非常快，需要零机器周期。 它还会使免费使用后的漏洞消失。 它是一个非常有用的free函数，可用于实例化为短期批处理的程序; 它可以在某些生产环境中有效地部署。
你能得出什么结论？
我真的很想要这份工作，但在另一家公司工作。
如果您的应用程序要在操作系统之上工作， malloc和free只有意义。 如果您想编写自己的内存管理函数，您必须知道如何从该特定操作系统请求内存，或者您可以使用现有的malloc立即保留堆内存，然后使用您自己的函数来分发/重新分配已分配的内存通过你的应用程序
有一个malloc和free应该遵循的架构 – 本质上是允许不同策略共存的类架构。 然后执行的free版本对应于所使用的malloc版本。
但是，我不确定这种架构的观察频率。
有关malloc()的工作知识是实现free()必要条件。 您可以使用K＆R中的sbrk()系统调用找到malloc()和free()实现.C编程语言第8章，第8.7节“示例 – 存储分配器”第185-189页。