红联Linux门户
Linux帮助

Linux Mini CRT堆栈管理的实现解析

发布时间:2016-07-21 15:22:18来源:linux网站作者:caoyan_12727
程序在运行过程中,对于堆内存的申请和释放主要是靠malloc()和free()两个函数实现,当然堆内存的管理方式有很多,在不同的操作系统平台上有不同的实现,在遵循MiniCRT(c运行时库)的原则下,我们将Mini CRT堆的实现归纳为以下几条:
 
1.实现一个以空闲链表算法为基础的堆空间分配算法。
 
2.堆的大小在程序运行时,根据需要会自动向后拓展,使用brk()函数将堆的结束地址向后调整,调整之后的空间作为堆空间;
 
下面是程序员的自我修养一书中算法的源码部分:
Linux Mini CRT堆栈管理的实现解析
Linux Mini CRT堆栈管理的实现解析
Linux Mini CRT堆栈管理的实现解析
Linux Mini CRT堆栈管理的实现解析
Linux Mini CRT堆栈管理的实现解析
 
从上面的代码我们可以看出:
 
1.对于每一个堆空闲块都有16字节大小的heap_header的结构体来记录,这个结构体中含有三个成员:type(用来记录该块空间是否被利用),next(下一个空闲块的地址),prev(上一个空闲块的地址),以及当前空闲块的大小;
 
2.(void *)brk(0)的调用 是为了获取program break的地址(关于这一点还有待探讨),目前暂时将它理解为向操作系统获取可分配空间的起始地址,将从起始地址开始的30M空间划分成程序的堆;
 
3.在malloc函数中,分配过程分以下几个步骤:
A.首先找到第一个空闲块
B.将这个空闲块的大小在区间(size+16,size+32)之间,则说明这块空闲块是最佳匹配的,否则继续查找;
C.如果在步骤B中没有找到最佳匹配,而堆中有一块足够的空间来分配就要将它进行切割,然后return ADDR_ADD(header,HEADER_SIZE)返回除了头部的空间的地址;然后我们看到next-size大小始终是初始整个对空间的大小减去每次malloc(unsiged size)中size的大小,也就是说(剩下的空间包括所有heap_header的大小)(个人觉得不大好),对于已分配的区块,其大小为header->size=size+HEADER_SIZE;
 
个人觉得这个算法太简陋!
 
本文永久更新地址:http://www.linuxdiyf.com/linux/22589.html