1、UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛1几种动态内存分配策略的比较分析作者: ucgui mail: 日期: 2007-01-22来源: http:/文档版本: v1.0.0.0版本 说明 时间v1.0.0.0 讲解三种内存分配算法的优缺点比较，其中包括 UCGUI 中使用的算法。 2007-01-22摘要: 主要分析了 C 语言程序设计/UCGUI 图形系统/ 虚拟机的设计与实现 c/c+三处地方所讲解的动态内存分配管理，从管理成本/管理结构/ 分配效率三个方面进行分析和比较，阐明具体如何根据具体的使用情况分析采用合适的算法。UCGUI 技术文集 UCGUI 专业网站:U
2、CGUI论坛2算法一: 采自 C 语言程序设计一书中示例.算法下载:http:/ 用于内存分配的管理单元-动态分配管理单元优点:1. 用于分配的管理单元与分配内存一起分配, 动态分配管理单元避免了静态的用数组来做管理单元的缺点,用数组的话:一是无论有无分配内存 ,管理单元的成本已经负出, 而且管理单元个数限制, 能够最多进行分配的内存块数受此限制.缺点:2. 因为管理单元的动态分配, 而且与分配的内存块相邻, 所以如果出现内存块使用时的越界操作, 整个内存分配管理结构则被破坏,后果严重.二. 内存分配时的匹配方案-最快匹配优点:UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛31.
3、在分配时从空闲中遍历查找有无能够满足此次分配要求的空闲块, 一旦找到够分配的则结束查找开始分配,这样处理可以很快的响应内存分配,速度比较快.2. 分配内存块时仅须遍历空闲块，链表中没有管理已分配块，分配时找到正好匹配或者是够分配的内存块，则将此空闲块一分为二，低地址部分继续插入空闲块，将高地址部分管理单元后的内存地址返回给用户.缺点:3. 与最快内存匹配相应的是最佳内存匹配, 它是查找最合适的一块来满足当前的内存分配,相比之下比较用时, 但是最快匹配方式的缺点就是会因此产生很多的空闲块,增加了空闲块链表管理的空间,相比更加容易产生碎片,空闲链表成员越少则碎片越少.4. 由此在此种算法中避免产生
4、过多的空闲块(碎片) 则是一大任务 ,也是算法优劣的一大关键点,这主要体现在空闲块的链表组织方面, 此种算法的空闲块是按照空闲块地址从低到高链接的, 分配内存的时候是从可用内存的最高地址开始分配; 因为匹配是最快匹配方案 , 因此要特别的注意空闲块的头指针所指向的最好不要是最大的空闲块,否则每次都匹配它了,这样肯定会导致内存用完释放后空闲块大量增加.因此你可以看到在算法中空闲块头指针是动态变化的,这点看似一句代码,但重要之极.三. 内存释放时碎片整理-相邻空闲块合并1. 内存释放后,必须要加入到空闲块链表管理起来以备下次分配,因此必须按照空闲块的链接顺序找到合适的插入位置, 在空闲块中查找插入
5、位置时,应该注意到空闲块的头指针 freep 一直是变化的,因此在遍历查找插入位置时有两个条件:1. 要释放块的内存块地址是位于两个空闲块之间，则插入位置已经找到 ,结束查找, 这种情况插入链表中间2. 遍历的时候如果遇到空闲块的地址大于它的下一个空闲块时,表明此时链表已经到了最后一个空闲块(表尾), 最后一个空闲块的下一块就是第一块空闲块(链表环形), 此时只有插入表头或者表尾两种情况(根据释放块地址决定 ).当以上两个条件有一个成立的时候, 则表明正确找到了可供插入的位置, 才能保证空闲块是按照地址从低到高链接起来的.2. 找到内存块可供插入的位置后, 还要相当重要的就是碎片的整理 , 即
6、将相邻内存块合并, 因为链表是按照空闲块地址从低到高组织起来的,所以只须判断插入位置的前一块与后一块与要释放的内存是否地址连续, 如是连续的则表明可以合并成一个空闲块, 如不是则插入链表(有四种情况，相邻两块都空闲或只有一块空闲或都不空闲, 算法中代码有两次指针调整，如果换四种情况分别处理则只须一次指针调整，效率提高).3. 释放内存块正确插入空闲链表后,还有相当重要的一点是, 调整空闲链表头指针, 即 freep = p;虽然只有一句代码,但是对于减少碎片的产生至关重要, 上面已经提到内存分配时是最快匹配, 那么空闲链表指针就显得特别重要了, 如果老是最大的空闲块排在表头, 则每次分配内存都
7、能得到满足, 而不会利用到空闲链表中的其它块,尽管有正好匹配大小的空闲块.调整后的空闲链表UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛4头指针是指向刚刚插入到空闲链表的内存块的上一块.4. 尽管这样调整还是有可能把最大的空闲块调到表头,但这是没有办法的事，因为这个算法的特点就是最大空闲块在表头，已经分配内存在高地址，所以表头必须动态调整.四. 这个内存分配策略的几个局限之处.1. 内存越界操作会使整个内存管理破坏.2. 因为分配的时候以管理单元的整数倍分配空间,导致比较严重的浪费.3. 无论是分配或是释放内存块都必须遍历查找空闲块，多数内存分配算法都无须在释放时做查找工作，简单快
8、速.改善:对于第一点,是此种内存分配方案最基本的地方, 所以改了这点似乎已经背离了这种算法了 ; 对于第二点则可以改善,可以改成不必以管理单元的整数倍来分配内存, 而用 2 或者是 4 的对齐粒度, 这样在分配与释放时都有不同的处理了, 空闲块的大小以及在分配时的判断上都有不同.在上述提供的算法源文件当中,我已经进行改进,使得分配时不再必须是管理单元的整数倍,改进的时候要特别注意的几点是:1. 主要是指针的运算操作,改进后指针的运算操作是字节型的,不再是管理单元型的指针运算.2. 分配时要注意如果选中进行分配的空闲块的大小满足分配后的剩余大小不大于管理单元,则表明无法再形成一个新的空闲块,因此
9、必须全部将此空闲块分配出去.3. 分配后虽然节约了内存,但是要注意由此空闲块数量会增多, 因为先前多种大小的请求都会整理成管理单元倍数, 空闲块的数量会直接影响到查找或是释放时的效率.UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛5算法二: 采自“虚拟机的设计与实现 c c+”算法下载:http:/ 分配原理图：内存块结构图:此种分配方案最典型的地方是，双链表结构但无记载分配位置及大小的信息，因为管理单元小，而且其双链表结构的指针均为数组之索引，因此大小可变，根据要管理的内存可适当变化，以节约管理开销。一. 与上面那种内存分配算法相比较,有几个方面都是完全相同的:1. 管理单元动态
10、分配,而且与要分配的内存块相邻, 管理单元在前面, 紧接其后就是分配的内存块.2. 内存分配时也是最快匹配查找.3. 释放内存时进行碎片整理,合并相邻的空闲内存块，但不能进行整体碎片整理的处理,因为这种处理显然是非常费时的,要把小碎片合并就必须移动已经分配的内存块，如果已经返回给用户实际的内存地址就不能再动这些块的位置.4. 同样存在内存写越界会破坏管理链表的缺陷.UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛6二. 也有显著不现的地方:1. 可以分配任意大小的内存块,无须以管理单元整数倍来管理整个分配内存;可以设定最小粒度对齐,如 2 字节或是四字.2. 已经分配与未分配内存块均
11、存在于同一个管理链表中,通过状态字来区别,因为没有记载分配块大小, 而是通过前后块之间的指针运算来计算内存块大小的，所以已分配与未分配的必须都加入链表.3. 因为已分配与未分配的都在同一个链表中管理着,所以对于分配内存则加大了查找链表的时间(因为链表成员相对多).4. 释放内存时不必要再查找空闲块内存的插入位置,仅须做状态改变以及相邻空闲块合并操作,没有了释放所须的查找链表工作,因此这种方法相比起来就在释放内存时有优势.三. 下面具体讲讲这种算法在分配与释放时的具体细节工作:注意以下所说的位置及索引等,均指在可供分配内存数组中的位置,必须依赖数组才有意义.1. 初始化.首先初始化时,初始可供分
12、配的起始位置与终止位置, 并初始化链表的链表头的上下指针均为 0,链表头位于可供分配的起始地址.2. 分配.首先从链表头开始,遍历查找符合分配要求的空闲块:1. 如果遍历到链表尾时(最开始没有任何分配时链表只有一个成员), 下指针所指为 0,此时即表明此空闲块之后的全部都为空闲,分配的内存块在插在链表尾; 2. 如果找到中间的空闲块,则将空闲块一分为二,也即将一空闲块分成一个空闲块及一个已使用块,已使用块在前,新生成的空闲块必须插入链表中,要注意双链表操作时的指针调整.3. 分配内存时从低地址端开始分配，起始阶段高地址端都是空闲区域；拆分空闲块时也是从低地址开始分配，如果拆分时剩余空闲块大小不
13、够管理单元大，此不会进行拆分，全部分配出去.4. 此算法分配时的代码不够简炼,代码有些重复,精简如下可节约代码空间 :U8 alloc(U8 nbytes)int ret;U8 i;i=first;for(i = first; i=next(i) /houhh 20070126.if(status(i)=FREE)ret = currentNodeAlloc(i,nbytes);if(ret=TRUE)return(i+SIZE_HEADER);if(next(i) =0) break;UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛7return(0);/*end alloc*/3
14、. 释放.释放内存块,除了改变内存块的使用状态标志,还须进一步做相邻空闲块合并,合并时有四种情况:1.上下两块均为空闲,此时要调整上块的 Next 指针以及下块之再一下一块的 Prev 指针.2.上块为空闲块,此时要调整上块的 Next 指针以及下块 Prev 指针.3.下块为空闲块.此时须调整要释放块的 Next 指针以及下块之再下一块的 Prev 指针.4.上下均无空闲块,仅改变释放块为未使用状态.说来说去,其实就是一个简单的双链表中删除链表成员的问题,这里的相邻碎片整理情形与算法一是完全一样的，但是此种算法的较好高效,将须要调整赋值的指针数降到了最少，如果按照算法一的思路相邻两边分开调整
15、，则要调整的指针赋值增加一倍.讨论：有的人可能想此算法中的同时管理着空闲块与已分配块，是否可以将已分配块从链表中去掉，如算法 1 中一样呢？仔细去想就知道是不行的，首先当然释放已分配块时根据就无从知道这个已分配块的大小，因为它不在链表当中.UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛8算法三: 采自 UCGUI 中内存分配的算法分析算法源码文件参见 UCGUI 源码算法原理图:管理单元结构图：有关 UCGUI 的动态内配分配算法,我在“UCGUI 的动态内存分配的原理深入分析“一文中进行了深入的分析, 虽然 UCGUI 的版本现在已经到了 404,但是内存分配这一块基本没有怎么变
16、化,可以参考此文一. 与上两种比较相同与不同的地方.UCGUI 中采用的方法与上两种算法比较起来,有比较大的不同点:1. UCGUI 中可分配的内存以及管理单元数组都是通过数组在编译时静态分配.UCGUI 技术文集 UCGUI 专业网站:UCGUI论坛92. 在释放时无须进行碎片整理,因为相邻内存本来就是连在一起的,它们之间不会夹杂有管理单元;而且释放时无须进行空闲块的插入管理,只是进行从链表中删除相应管理单元操作,释放的空闲块无须加入链表管理起来.3. 在分配时,因为只管理已分配块链表,链表的分配块地址也是从低到高有序的,且每一个链表节点记录了分配块起址以及大小,因此可以找出相邻两个分配块之
17、间的空闲区域进行内存分配,相比算法 2 链表中少了空闲块的信息,分配查找起来较快.4. 分配时与前两种算法一样都是最快匹配方案.5. 因为 UCGUI 是独立的静态固定大小的管理单元数组,因此管理单元的个数固定,而且其占用空间也固定,可最大管理的分配块数目有限.6. 因为管理单元与分配内存单元分别位于不同的数组当中,因此不会因为越界内存写操作而可能造成整个管理链表的破坏.7. 与算法 2 相比,本算法管理单元所占成本偏高,主要多出了记录分配块大小以及位置的信息,在算法 2 中则可以通过链表指针运算就得出分配的大小以及位置信息.8. 本算法可以进行整体的碎片整理工作,将空闲区域整体合并到高位地址
18、以提高分配效率,但是前两种算法均不能进行这种碎片整理,因为它们分配出去的地址是已经固定的,而不象这种算法,它是相对的,外界引用时都是通过管理数组索引来转换得到真实的地址的,就因为这一层隔离处理才有了这层优越性.讨论：有的人可能想此算法中的有上下块两个指针，可否将双链表结构变成单链表结构呢？仔细去想其实是可行，在此算法当中关于前一块指针仅仅是在释放内存时使用，用于从双链表中删除结点，如果去掉了前指针，首先可以减少管理单元空间的占用；再次可以减少分配时有关指针的赋值操作等；但是带来的问题是：降低了释放内存的效率，它使得在删除链表结点时必须从头至尾遍历.因此只有根据实际的情形就进行分析，看空间还是时间重要，取其一.
