UCGUI几种动态内存分配策略的比较分析.doc

几种动态内存分配策略的比较分析 作者: ucgui mail: ucgui@163.com 日期: 2007-01-22 来源: 文档版本: v 版本 说明 时间 v 讲解三种内存分配算法的优缺点比较，其中包括UCGUI中使用的算法。 2007-01-22 摘要: 主要分析了C语言程序设计/UCGUI图形系统/虚拟机的设计与实现c/c++三处地方所讲解的动态内存分配管理，从管理成本/管理结构/分配效率三个方面进行分析和比较，阐明具体如何根据具体的使用情况分析采用合适的算法。  算法一: 采自C语言程序设计一书中示例. 算法下载: /ucgui/g-mem.c 分配原理图： 分配块结构图： 这种内配策略的特点总结如下: 一. 用于内存分配的管理单元-----动态分配管理单元 优点: 用于分配的管理单元与分配内存一起分配, 动态分配管理单元避免了静态的用数组来做管理单元的缺点,用数组的话:一是无论有无分配内存,管理单元的成本已经负出, 而且管理单元个数限制, 能够最多进行分配的内存块数受此限制. 缺点: 因为管理单元的动态分配, 而且与分配的内存块相邻, 所以如果出现内存块使用时的越界操作, 整个内存分配管理结构则被破坏,后果严重. 二. 内存分配时的匹配方案-----最快匹配 优点: 在分配时从空闲中遍历查找有无能够满足此次分配要求的空闲块, 一旦找到够分配的则结束查找开始分配,这样处理可以很快的响应内存分配,速度比较快. 分配内存块时仅须遍历空闲块，链表中没有管理已分配块，分配时找到正好匹配或者是够分配的内存块，则将此空闲块一分为二，低地址部分继续插入空闲块，将高地址部分管理单元后的内存地址返回给用户. 缺点: 与最快内存匹配相应的是最佳内存匹配, 它是查找最合适的一块来满足当前的内存分配,相比之下比较用时, 但是最快匹配方式的缺点就是会因此产生很多的空闲块,增加了空闲块链表管理的空间,相比更加容易产生碎片,空闲链表成员越少则碎片越少. 由此在此种算法中避免产生过多的空闲块(碎片)则是一大任务,也是算法优劣的一大关键点,这主要体现在空闲块的链表组织方面, 此种算法的空闲块是按照空闲块地址从低到高链接的, 分配内存的时候是从可用内存的最高地址开始分配; 因为匹配是最快匹配方案, 因此要特别的注意空闲块的头指针所指向的最好不要是最大的空闲块,否则每次都匹配它了,这样肯定会导致内存用完释放后空闲块大量增加.因此你可以看到在算法中空闲块头指针是动态变化的,这点看似一句代码,但重要之极... 三. 内存释放时碎片整理----相邻空闲块合并 内存释放后,必须要加入到空闲块链表管理起来以备下次分配,因此必须按照空闲块的链接顺序找到合适的插入位置, 在空闲块中查找插入位置时,应该注意到空闲块的头指针freep一直是变化的,因此在遍历查找插入位置时有两个条件: [1]. 要释放块的内存块地址是位于两个空闲块之间，则插入位置已经找到,结束查找, 这种情况插入链表中间 [2]. 遍历的时候如果遇到空闲块的地址大于它的下一个空闲块时,表明此时链表已经到了最后一个空闲块(表尾), 最后一个空闲块的下一块就是第一块空闲块(链表环形),此时只有插入表头或者表尾两种情况(根据释放块地址决定). 当以上两个条件有一个成立的时候, 则表明正确找到了可供插入的位置, 才能保证空闲块是按照地址从低到高链接起来的. 找到内存块可供插入的位置后, 还要相当重要的就是碎片的整理, 即将相邻内存块合并, 因为链表是按照空闲块地址从低到高组织起来的,所以只须判断插入位置的前一块与后一块与要释放的内存是否地址连续, 如是连续的则表明可以合并成一个空闲块, 如不是则插入链表(有四种情况，相邻两块都空闲或只有一块空闲或都不空闲, 算法中代码有两次指针调整，如果换四种情况分别处理则只须一次指针调整，效率提高). 释放内存块正确插入空闲链表后,还有相当重要的一点是, 调整空闲链表头指针, 即 freep = p;虽然只有一句代码,但是对于减少碎片的产生至关重要, 上面已经提到内存分配时是最快匹配, 那么空闲链表指针就显得特别重要了, 如果老是最大的空闲块排在表头, 则每次分配内存都能得到满足, 而不会利用到空闲链表中的其它块,尽管有正好匹配大小的空闲块.调整后的空闲链表头指针是指向刚刚插入到空闲链表的内存块的上一块. 尽管这样调整还是有可能把最大的空闲块调到表头,但这是没有办法的事，因为这个算法的特点就是最大空闲块在表头，已经分配内存在高地址，所以表头必须动态调整. 四. 这个内存分配策略的几个局限之处. 内存越界操作会使整个内存管理破坏. 因为分配的时候以管理单元的整数倍分配空间,导致比较严重的浪费. 无论是分配或是释放内存块都必须遍历查