Ç - 设计自己的free（）函数 [英] C - Design your own free( ) function
问题描述
今天，我出现了面试，面试官问我这个，
- 告诉我在步骤您将如何设计自己的
免费（）功能
释放分配的内存。
- 岂是比C的默认
免费（）函数更有效率？你能得出什么结论呢？
我很困惑，也想不出来设计的方式。
你觉得什么人？
编辑：因为我们需要了解如何
的malloc（）的作品，你能告诉我的步骤来写自己的的malloc（）函数解决方案这实际上是一个pretty模糊的问题，这可能是为什么你弄糊涂了。他是不是说，鉴于现有的malloc实现，你会怎么去试图发展以释放潜在的内存更有效的方法？还是他盼着你开始讨论各种不同的malloc实现和他们的利益和存在的问题？难道他指望你知道内存的x86架构如何虚函数？
此外，通过更有效的，他的意思是，空间利用率更高或更多的时间效率？是否免费（）必须是确定的？难道一定要尽可能多的内存返回操作系统越好，因为它是在低内存，多任务环境？这里有什么我们的标准？
这是很难说从哪里开始像一个模糊的问题，除了开始问自己的问题得到澄清。毕竟，为了设计自己的免费功能，你首先要知道的malloc是如何实现的。所以有机会，问题是真正关心你是否知道malloc的是如何实现的东西。
如果你不熟悉内存管理的内部，以开始了解如何malloc的实现是先写你自己的最简单的方法。
查看这个IBM developerWorks文章叫内存管理内幕对于初学者。
但在此之前，你可以编写自己的malloc /免费的，您首先需要内存来分配/释放。不幸的是，在保护模式下的操作系统，你不能直接解决计算机上的内存。那么，你如何得到它呢？
您要求它的操作系统。与x86的虚拟内存功能，任何一件的RAM或交换存储器可映射到由操作系统的存储器地址。你的程序发现内存可以在整个系统进行物理分段，但由于内核的虚拟内存管理器，这一切看起来是一样的。
内核通常提供的系统调用，让您在为您的工艺额外的内存映射。在旧版本的UNIX操作系统的，这是通常BRK / SBRK增长堆内存到你的进程的边缘或缩小它关闭，但很多系统还提供MMAP /在munmap在堆内存的一个大块只是地图，它是唯一的，一旦你有机会要大，连续找的内存，你需要的malloc /自由地管理它的块。
一旦你的进程可以给它一些堆内存，它是所有关于拆分为块，包含每个块自身的元信息关于它的大小和位置，以及是否它的分配，然后再管理这些块。结构的一个简单的列表，每个都包含了元信息和一个大型字节数组的某些领域，可以工作，在这种情况下的malloc具有在列表中运行，直到如果找到一个足够大的未分配块（或大块它可以结合），并然后映射更多的内存，如果它不能找到一个足够大的份额。一旦你找到一大块，你只返回一个指针数据。自由（）然后可以使用该指针扭转回存在于结构中的成员字段，它可以修改几个字节（即，标记chunk.allocated =假）。如果你的列表的末尾有足够的未分配块，你甚至可以从列表中取消映射删除或缩小内存关闭进程的堆。
这就是虽然实现的malloc一个真正的简单方法。你可以想象，有很多的分裂你的记忆成块，然后管理这些数据块的可能途径。还有，因为有数据结构和算法尽可能多的方式。他们都在为不同目的太像极限碎裂，由于具有体积小，未分配的块混合小，分配的块，或确保malloc和free跑得快（有时甚至更慢，但predictably慢）。有 dlmalloc ， ptmalloc ， jemalloc ，囤的malloc ，更多的人在那里，很多都是相当小，简洁的，所以不要害怕阅读。如果我没有记错，C程序设计语言由Kernighan和Ritchie甚至使用一个简单的malloc实现作为自己的一个例子。
Today, I appeared for an interview and the interviewer asked me this,
- Tell me the steps how will you design your own
free( )function for deallocate the allocated memory.- How can it be more efficient than C's default
free()function ? What can you conclude ?
I was confused, couldn't think of the way to design.
What do you think guys ?
EDIT : Since we need to know about how
malloc()works, can you tell me the steps to write our ownmalloc()function解决方案That's actually a pretty vague question, and that's probably why you got confused. Does he mean, given an existing malloc implementation, how would you go about trying to develop a more efficient way to free the underlying memory? Or was he expecting you to start discussing different kinds of malloc implementations and their benefits and problems? Did he expect you to know how virtual memory functions on the x86 architecture?
Also, by more efficient, does he mean more space efficient or more time efficient? Does free() have to be deterministic? Does it have to return as much memory to the OS as possible because it's in a low-memory, multi-tasking environment? What's our criteria here?
It's hard to say where to start with a vague question like that, other than to start asking your own questions to get clarification. After all, in order to design your own free function, you first have to know how malloc is implemented. So chances are, the question was really about whether or not you knew anything about how malloc can be implemented.
If you're not familiar with the internals of memory management, the easiest way to get started with understanding how malloc is implemented is to first write your own.
Check out this IBM DeveloperWorks article called "Inside Memory Management" for starters.
But before you can write your own malloc/free, you first need memory to allocate/free. Unfortunately, in a protected mode OS, you can't directly address the memory on the machine. So how do you get it?
You ask the OS for it. With the virtual memory features of the x86, any piece of RAM or swap memory can be mapped to a memory address by the OS. What your program sees as memory could be physically fragmented throughout the entire system, but thanks to the kernel's virtual memory manager, it all looks the same.
The kernel usually provides system calls that allow you to map in additional memory for your process. On older UNIX OS's this was usually brk/sbrk to grow heap memory onto the edge of your process or shrink it off, but a lot of systems also provide mmap/munmap to simply map a large block of heap memory in. It's only once you have access to a large, contiguous looking block of memory that you need malloc/free to manage it.
Once your process has some heap memory available to it, it's all about splitting it into chunks, with each chunk containing its own meta information about its size and position and whether or not it's allocated, and then managing those chunks. A simple list of structs, each containing some fields for meta information and a large array of bytes, could work, in which case malloc has to run through the list until if finds a large enough unallocated chunk (or chunks it can combine), and then map in more memory if it can't find a big enough chunk. Once you find a chunk, you just return a pointer to the data. free() can then use that pointer to reverse back a few bytes to the member fields that exist in the structure, which it can then modify (i.e. marking chunk.allocated = false;). If there's enough unallocated chunks at the end of your list, you can even remove them from the list and unmap or shrink that memory off your process's heap.
That's a real simple method of implementing malloc though. As you can imagine, there's a lot of possible ways of splitting your memory into chunks and then managing those chunks. There's as many ways as there are data structures and algorithms. They're all designed for different purposes too, like limiting fragmentation due to small, allocated chunks mixed with small, unallocated chunks, or ensuring that malloc and free run fast (or sometimes even more slowly, but predictably slowly). There's dlmalloc, ptmalloc, jemalloc, Hoard's malloc, and many more out there, and many of them are quite small and succinct, so don't be afraid to read them. If I remember correctly, "The C Programming Language" by Kernighan and Ritchie even uses a simple malloc implementation as one of their examples.
这篇关于Ç - 设计自己的free（）函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
