c++ - C++中malloc的自定义实现

Question

我遇到了一个面试问题，他们要求在 C++ 中实现 malloc() 和 free 函数。

一开始声明了一个大小为 50000 的 char 数组（50000 字节）。假设这是堆内存，编写 malloc 和 free 函数来分配内存块并释放内存。

任何人都可以为我提供 C++ 工作/伪代码或只是解释机制？（显然代码会使它更容易理解）。

谢谢，罗希特

Answer 1

虽然编写生产级动态内存分配器是一项非常艰巨的任务，但编写玩具分配器却很简单。这个问题显然是为了测试你的技能，但从别人的作品中寻找灵感仍然是公平的。

Kernighan & Ritchie 的“The C Programming Language”包含一个简单的malloc. 研究它并考虑其设计和实施的影响。考虑如何改进它以更好地执行、减少碎片或处理多个线程。之后，编写自己的玩具分配器并回答出现的任何问题应该不再困难。

Answer 2

有几种不同的算法可以使用。对于这么小的内存，我只需在每个块前面加上一个指向下一个块的指针，以及一个指示它是分配还是释放的标志。分配包括找到足够大的空闲块，必要时将其拆分，并将返回的块标记为已分配。免费包括将块标记为空闲。在某些时候，您还必须合并块：如果两个空闲块相互跟随，它们将合并为一个。（我在实现的分配过程中这样做了。）

上述算法本身并不难。真正的诀窍是让所有不同的演员阵容都正确。这是非常低级编程的一个很好的练习。

Answer 3

我之前没有测试过，但我认为可以通过使用 new 关键字和模板来支持通用状态来创建所需类型的数组，但我会按照这个问题来找出 C++ 英雄的回应。