基于基于malloc与与free函数的实现代码及分析函数的实现代码及分析
用于内存管理的malloc与free这对函数,对于使用C语言的程序员应该很熟悉。前段时间听说有的IT公司以“实现一个简单
功能的malloc”作为面试题,正好最近在复习K&R,上面有所介绍,因此花了些时间仔细研究了一下。毕竟把题目做出来是次
要的,了解实现思想、提升技术才是主要的。本文主要是对malloc与free实现思路的介绍,蓝色部分文字是在个人思考中觉得
比较核心的东西;另外对于代码的说明,有一些K&R上的解释,使用绿色加亮。
在研究K&R第八章第五节的实现之前,不妨先看看其第五章第四节的alloc/afree实现,虽然这段代码主要目的是展示地址
运算。
代码如下:
alloc实现
#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE]; /*storage for alloc*/
static char *allocp = allocbuf; /*next free position*/
char *alloc(int n)
{
if(allocbuf+ALLOCSIZE – allocp >= n) {
allocp += n;
return alloc – n;
} else
return 0;
}
void afree(char *p)
{
if (p >= allocbuf && p<allocbuf + ALLOCSIZE)
allocp = p;
}
这种简单实现的缺点:
1.作为代表内存资源的allocbuf,其实是预先分配好的,可能存在浪费。
2.分配和释放的顺序类似于栈,即“后进先出”,释放时如果不按顺序会造成异常。
这个实现虽然比较简陋,但是依然提供了一个思路。如果能把这两个缺点消除,就能够实现比较理想的malloc/free。
仅仅依靠地址运算来进行定位,是限制分配回收灵活性的原因,它要求已使用部分和未使用部分必须通过某个地址分开成
两个相邻区域。为了能让这两个区域能够互相交错,甚至其中还包括一些没有分配的地址空间,需要使用指针把同类的内存空
间连接起来形成链表,这样就可以处理地址不连续的一系列内存空间。但是为什么只连接了空闲空间而不连接使用中的空间?
这么问可能出于在对图中二者类比时的直觉而没有经过思考,这很简单,因为没有必要。前者相互链接是为了能够在内存分配
时遍历所有空闲空间,并且在使用free()回收已使用空间时进行重新插入。而对于使用中的空间,由于我们在分配空间时已经
知道它们的地址了,回收时可以直接告诉free(),并不用像malloc()时进行遍历。