设计你自己的free()函数

Question

设计你自己的free()函数

cmallocfree

17

今天，我参加了一次面试，面试官问了我这个问题，

告诉我你要如何设计自己的free()函数来释放已分配的内存。

它如何比C语言默认的free()函数更高效？你有什么结论吗？

我非常困惑，无法想出设计的方法。

你们觉得呢？

编辑：由于我们需要了解如何编写malloc()函数，你能告诉我编写自己的malloc()函数的步骤吗？

- Saurabh Gokhale

9

为了让这个有用，你需要自己的 malloc，对吗？ - pmr

3

由于标准没有指定free的实现方式，我不认为有人能够回答问题2。 - Andreas Brinck

1

你不能给出绝对的答案，但它确实可以引发良好的讨论 - 这可能就是目的！我同意如果没有自己的malloc，就没有重用内存的空间。事实上，指出这样“显而易见”的事情可能正是他/她想要的，接着是更深入的讨论如何编写高效的动态内存分配系统（速度 vs 内存等）。记住：面试官并不是在试图欺骗你，而是想看看你如何解决问题以及你所知道的东西。大声思考并请求澄清。展示给他们你所知道的东西！ - noelicus

2

除非面试官不称职，否则我怀疑他们更关注你将使用哪些算法来存储和管理空闲块列表... - R.. GitHub STOP HELPING ICE

2

从操作系统实际请求内存只是malloc/free的一部分实现......C实际上从操作系统请求'大'内存块，然后保留一个'空闲'内存位置的链接列表。当内存被释放时，它会返回到空闲列表中。还要注意，实现的步骤0是增加每年$40K的薪水，用于维护难以调试的系统相关代码。 - Barton Chittenden

显示剩余3条评论

8个回答

8

如果你不知道malloc()的底层实现方式，那么就不能盲目设计free()函数，因为实现free()需要了解如何操作管理数据，而在不了解malloc()的实现方式的情况下是不可能做到的。

因此，一个无法回答的问题可能是如何设计malloc()和free()，这不是一个简单的问题，但你可以部分回答它，例如提出一些非常简单的内存池实现方式，当然这种实现方式并不等同于malloc()，但可以表明你有相关知识。

- sharptooth

1

最好的malloc和free（基本上是dlmalloc）通用算法广为人知，即使需要更多的实现细节，也可以在几分钟内轻松表达。我只会解释这个。 - R.. GitHub STOP HELPING ICE

3

当你只能访问用户空间（通常称为内存池）时，一种常见方法是在应用程序启动时从操作系统获取大块内存。您的malloc需要通过一些数据结构检查该池中仍然空闲的正确大小的区域，并分配指向该内存的指针。您的free需要在数据结构中将内存标记为空闲，可能还需要检查池的碎片情况。

好处是您可以几乎恒定时间进行分配，缺点是您的应用程序消耗的内存比实际所需的要多。

- pmr

优点是您可以在几乎恒定的时间内进行分配，缺点是您的应用程序消耗的内存比实际需要的要多。 - Neel Basu

2

告诉我你将如何设计自己的免费（）函数来释放已分配的内存的步骤。

#include <stdlib.h>
#undef free
#define free(X) my_free(X)

inline void my_free(void *ptr) { }

它如何比C语言的默认free()函数更有效？

它非常快，不需要任何机器周期。它还可以消除使用后释放的错误。在短暂批处理进程中实例化的程序中，这是一个非常有用的free函数；它可以在某些生产情况下有用地部署。

你能得出什么结论？

我真的很想要这份工作，但在另一家公司。

- Kaz

1

内存使用模式可能是一个因素。默认的free实现不能假设你分配/释放的频率以及你分配时分配的大小。

例如，如果你经常分配和释放相似大小的对象，那么使用内存池可以提高速度、内存效率和减少碎片。

编辑：正如sharptooth所指出的，只有设计好free和malloc才有意义。所以第一件事就是弄清楚malloc的实现方式。

- orip

0

malloc和free只有在您的应用程序要在操作系统之上运行时才有意义。如果您想编写自己的内存管理函数，您需要知道如何从特定的操作系统请求内存，或者您可以直接保留堆内存使用现有的malloc，然后使用自己的函数在整个应用程序中分配/重新分配已分配的内存。

- Djole

0

有一种架构，malloc和free应该遵循--基本上是一个允许不同策略共存的类架构。然后执行的free版本对应于使用的malloc版本。

然而，我不确定这种架构有多少被遵守。

- Hot Licks

0

实现free()需要了解malloc()的工作原理。您可以在K&R The C Programming Language第8章第8.7节“示例-存储分配器”pp.185-189中找到使用sbrk()系统调用实现malloc()和free()的代码。

- vine'th

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James O'Doherty · Accepted Answer

这其实是一个相当模糊的问题，可能正因如此你感到困惑。他是指，在现有malloc实现的基础上，您将如何尝试开发更高效的内存释放方式？还是他希望您开始讨论不同种类的malloc实现及其利弊和问题？他是否期望您知道x86架构上虚拟内存是如何工作的？

另外，所谓更高效，他是指更省空间还是更省时间？free()函数必须是确定性的吗？它是否必须在低内存、多任务环境下返回尽可能多的内存给操作系统？我们的标准是什么？

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

如果您对内存管理的内部工作机制不熟悉，那么了解malloc的实现方式的最简单方法是首先编写您自己的实现。

参考这篇IBM DeveloperWorks文章“内存管理之内部揭秘”开始。

但在编写自己的malloc/free之前，您首先需要可分配/释放的内存。不幸的是，在受保护的模式操作系统中，您无法直接访问计算机上的内存。那么该怎么办呢？

您需要向操作系统请求内存。使用x86的虚拟内存特性，操作系统可以将任何一块RAM或交换内存映射到内存地址上。您的程序视为内存的内容可能物理上分散在整个系统中，但由于内核的虚拟内存管理器，它们看起来都是相同的。

内核通常提供系统调用，允许您为进程映射更多的内存。在旧的UNIX操作系统上，这通常是使用brk/sbrk来将堆内存增加到进程的边缘或将其缩小，但很多系统也提供mmap/munmap来简单地映射一个大块堆内存。只有当您能够访问一个大的、连续的内存块时，您才需要使用malloc/free来管理它。

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

这是一种非常简单的实现malloc的方法。可以想象，将内存分成块并管理这些块有很多可能的方式。就像有数据结构和算法一样多样化。它们也都是为不同的目的而设计的，比如限制由小的分配块与小的未分配块混合而导致的碎片化，或者确保malloc和free运行快速（有时甚至更慢，但可预测地缓慢）。有dlmalloc、ptmalloc、jemalloc、Hoard's malloc等等，其中许多都相当小巧简洁，因此不要害怕阅读它们。如果我没记错的话，《C程序设计语言》（Kernighan和Ritchie著）甚至使用了一个简单的malloc实现作为他们的示例之一。