对于一个面试问题：我将如何编写新的“malloc”和“free”函数？我不认为“使用 new 和 delete”是一个可以接受的答案或使用类似 LocalAlloc/HeapAlloc 的东西
问问题
9493 次
7 回答
12
由于这是一个面试问题，它可能不会有一个“正确”的答案，而且他们对你的思维过程以及你对该主题的一般知识更感兴趣。
您应该要求澄清要求，或根据情况给出一系列答案。以下是一些需要考虑的问题：
- 避免内存碎片重要吗？固定的分配大小可能会有所帮助。
- 您需要分配速度保证吗？使用/空闲块的使用索引。
- 您是否需要轻松跟踪执行的分配？将日志结构添加到 malloc/free 库。
- 您是否需要防止或检测内存不足/溢出？额外的填充和定期填充检查。
于 2013-02-06T09:03:13.980 回答
4
简单的说，
您的malloc函数应该能够从操作系统获取内存并将其提供给请求动态分配内存的客户端（例如，您的 C 程序）。为了实现这一点，malloc 库通常具有许多数据结构（取决于实现） - 例如，malloc实现可以选择使用链表跟踪空闲内存块。一种更有效的方法是拥有一个链表列表，每个链表都包含特定大小范围的块。
我碰巧在TCMalloc库上工作，这可能会帮助您更清楚地理解这一点
通过freelists分配内存
可以说，0 类是大小为 4k 的空闲块的链表，1 类是大小为 8k 的空闲块的链表，依此类推。
当调用 malloc 时（例如，大小为 10k），您的 malloc 实现将遍历freelist以找出满足请求的最小空闲块（在这种情况下，4k 块是不够的，所以它将获取一个 8k 块，将其从freelist中删除，然后将其返回给您的程序）。
同样，当调用到时free，您的实现（除其他外）应该从程序中回收块并将其添加到freelists之一的适当位置。
于 2013-02-06T09:04:44.373 回答
3
这个网站回答了你的问题。
http://www.codeproject.com/Questions/177316/Write-your-own-malloc - 同样的问题 http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf
于 2013-02-06T09:03:11.730 回答
3
如果面试官问你
我将如何编写新的“malloc”和“free”函数？
你开始谈论你要做什么，你已经失败了。在手之前，您需要问几个问题才能更精确地使用 malloc 函数。在我的头上，一些第一个问题是：
- 适用于哪个操作系统？
- 对于哪个内存？用户 malloc 还是内核 malloc？
- 最常见的使用场景是什么？通用malloc？大块还是小块更好？
在开始讨论代码之前，需要进行第一轮的需求获取。
于 2013-02-06T09:06:15.483 回答
1
这取决于要求，例如，假设您想创建嵌入式软件，有时在运行时或由于性能原因不允许执行 malloc/free。然后，您可以创建自己的 malloc/free 版本，它不分配/释放内存，而只是从预分配的堆中获取/重新运行块。
于 2013-02-06T08:56:28.873 回答
1
如果您正在谈论挂钩malloc()和free()呼叫，您可以使用以下方式进行操作：
#define malloc(x) your_malloc(x)
#define free(x) your_free(x)
但是，如果您正在谈论创建自己的内存分配器，那么您可能想要查看 Kernighan 和 Ritchie 在他们的“The C Programming Language 2nd Edition”一书中的堆分配器实现之一。它基本上依赖于使用sbrk()系统函数来增加进程的数据段的大小。
于 2013-02-06T09:02:40.820 回答
0
我想他们可以/应该用另一种方式表达这个问题：“堆内存如何由 malloc 和 free 管理？”。
然后你可以用一种稍微不同的方式来思考这个问题——给定一个线性的值列表，你如何划分列表的块并跟踪它们，你如何把那个列表的块还给你，你如何管理碎片清单等
简而言之，尽管下一个空闲块的地址存储在分配出的块旁边的堆中，但下一个空闲内存块存储位置的信息对用户是不可见的，但仍然是同一个堆的一部分。这就是为什么超出分配的内存会完全破坏堆并导致 malloc 和 free 之类的崩溃。
通常，面试官会用这个问题让你自由地展示你的知识。你可以从基本功能开始，然后如果你知道你的洋葱如何管理它，不同的算法是什么等等。毕竟，无论你描述什么都不太可能涵盖过去二十年的研发学科！
于 2013-02-06T08:59:49.860 回答