今天,我出现了面试,面试官问我这个,
- 告诉我的步骤,你将如何设计自己的
free( )功能,用于解除分配所分配的内存.- 它如何比C的默认
free()功能更有效？你能得出什么结论？
我很困惑,想不出设计的方式.
你们觉得怎么样 ？
编辑:既然我们需要知道如何malloc()工作,你能告诉我编写自己的malloc()功能的步骤
Jam*_*rty 15
这实际上是一个非常模糊的问题,这可能就是你迷茫的原因.他是否意味着,鉴于现有的malloc实现,您将如何尝试开发一种更有效的方式来释放底层内存？或者他是否期望你开始讨论不同类型的malloc实现及其好处和问题？他是否希望您了解虚拟内存在x86架构上的功能？
此外,通过提高效率,他是指更节省空间还是更节省时间？free()必须是确定性的吗？是否必须尽可能多地将内存返回给操作系统,因为它处于低内存,多任务环境中？我们的标准是什么？
除了开始提出自己的问题以澄清之外,很难说从哪个模糊的问题开始.毕竟,为了设计自己的自由函数,首先必须知道如何实现malloc.所以很有可能,问题在于你是否知道如何实现malloc.
如果您不熟悉内存管理的内部,开始理解malloc如何实现的最简单方法是首先编写自己的内存管理.
查看这篇名为"Inside Memory Management"的IBM DeveloperWorks文章.
但在你编写自己的malloc/free之前,首先需要内存来分配/释放.不幸的是,在受保护模式的操作系统中,您无法直接寻址机器上的内存.那你怎么得到它？
你问操作系统.借助x86的虚拟内存功能,操作系统可以将任何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()实现.
因此,一个unswerable问题可能是你会怎么设计的malloc()和free() ,而不是它是不是一个简单的问题,但你可以通过提出一些非常简单的实现内存池的,不会等同于部分回答这个问题,例如malloc()课程但是会表明你的知识存在.