编写自己的malloc [英] Write your own malloc

问题描述

大家好，

有谁能帮助我使用C为自己的malloc函数编写代码或算法.
请注意，我不想使用任何库函数.

在此先谢谢您.

Hi Everyone,

Can any one help me in writing a code or an algorithm for my own malloc function using C.
Please make a note that i don''t want to use any library functions.

Thanks in Advance.

推荐答案

我知道避免库函数的唯一方法是将内存预分配到堆栈上，然后将此类内存用于您自己的malloc版本.

可能更好的方法是实际上使用库malloc来预分配大内存块，然后使用自己的函数进行管理.
:-)

The only way I know to avoid library functions is preallocationg memory onto the stack and then using such memory for your own version of malloc.

Possibly a better way would be actually using library malloc to pre-allocate large blocks of memory and then manage them with you own function.
:-)

这取决于您要走多远，但这不是一件简单的任务.我已经做过几次了，但我仍然忘记了一些事情.

考虑一下malloc必须做什么:
1)分配足够大的内存来满足请求，并返回指向它的指针.
2)记住使用了哪些ram块，哪些不是.
3)将免费的块组合成更大的块.

因此，您需要做的第一件事就是分配大量内存.获得它的唯一方法是从堆中对其进行malloc分配:通常来说，对于这种事情而言，堆栈太小了. (在VS中，默认情况下堆栈只有1MB，但是我知道带有1K堆栈的基于C的系统！)这可能在您的家庭作业中是允许的，因为您必须从某个地方获取内存！

现在，您需要几个链接列表.
1)您需要一个可用内存"列表:块的开始和块的大小.
2)您需要一个正在使用"列表:块的开始和块的大小.

接下来，您需要确定将使用哪种算法进行分配:
1)First fit:符合您的请求的空闲列表中的第一个块被切掉一块，并作为新的内存块返回
2)最适合:可以容纳请求的最小的此类块.
3)最差的拟合:始终使用最大的块.
4)固定大小分配:所有块均大小相同. (因为它不会碎片化，所以在嵌入式应用程序中效果很好)
还有其他！ Wiki可能会帮助您.

现在您可以开始了:
Malloc:
1)查找要使用的块:如果不存在，则为错误！
2)从可用内存列表中删除块.
3)将块分为两部分:请求块和空闲块.
4)将空闲"块添加到空闲内存列表中
5)将请求块添加到使用中列表
6)返回块指针

您还需要一个免费的:
1)在使用列表中找到请求块指针.如果不存在，就会出错！
2)从使用中列表中将其删除.
3)将其添加到可用内存列表中.
4)如果您不使用固定大小的分配，请在空闲内存列表中进行拖曳，然后将大块合并为连续的大块.

听起来很简单?

实际上还算不错，但是最好将其分阶段进行，因为它可能会成为调试的麻烦.
请记住，您需要在某个地方存储链接列表...这可能会导致它自己的问题，因为您可能必须为列表分配m空间，并且它们可能会增长，从而导致您不得不分配一个a链.更大的空间并复制它们...

大量潜在的陷阱！

我会先阅读所有我能找到的东西！

It depends on how far you want to go, but this is not a trivial task. I''ve done it a few times, and I still forget some things.

Think about what a malloc has to do:
1) Allocate a chunk of memory big enough to satisfy the request, and return a pointer to it.
2) Remember which chunks of ram are in use and which aren''t.
3) Combine free chunks to make bigger ones.

So, the first thing you need is a big chunk of memory to allocate. The only way you are going to get it is to malloc it off the heap: generally speaking, stacks are far too small for this kind of thing. (In VS, the stack is only 1MB by default, but I''ve known C based systems with a 1K stack!) This is probably allowable in your homework as you have to get your memory from somewhere!

Now, you need a couple of linked lists.
1) You need a "free memory" list: Start of block, and size of block.
2) You need an "in use" list: Start of block, and size of block.

Next, you need to decide what algorithm you will use for allocation:
1) First fit: The first chunk in the free list that fits your request has a lump chopped off it, and returned as the new memory block
2) Best Fit: The smallest such chunk that will hold the request.
3) Worst Fit: The biggest chunk is always used.
4) Fixed size allocation: All chunks are the same size. (Works well in embedded applications since it doesn''t fragment)
There are others! Wiki will probably help there.

Now you are ready to go:
Malloc:
1) Find the chunk to use: If none: error!
2) Remove chunk from free memory list.
3) Break chunk into two: request chunk, and free chunk.
4) Add the Free chunk to the free memory list
5) Add the request chunk to the in use list
6) Return the chunk pointer

You also need a Free:
1) Find the request chunk pointer in the in use list. If it isn''t there, error!
2) Remove it from the in use list.
3) Add it to the free memory list.
4) If you aren''t using a fixed size allocation, trawl through the free memory list and combine chunks into bigger chunks where they are contiguous.

Sound simple?

Not too bad in fact, but it is best to take it in easy stages, because it can be a bugger to debug.
Bear in mind, that you need to have somewhere to store your linked lists... That can cause it''s own problems, as you may have to malloc space for the lists and they could grow, causing you to have to malloc a bigger space and copy them...

Loads of potential pitfalls!

I would read up on everything I could find first!

这篇关于编写自己的malloc的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！