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

PAGEPAGE15几种动态内存分配策略的比较分析摘要:主要分析了C语言程序设计/UCGUI图形系统/虚拟机的设计与实现c/c++三处地方所讲解的动态内存分配管理，从管理成本/管理结构/分配效率三个方面进行分析和比较，阐明具体如何根据具体的使用情况分析采用合适的算法。

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

算法二:采自“虚拟机的设计与实现cc++” 算法下载:/ucgui/mem.c分配原理图：内存块结构图:此种分配方案最典型的地方是，双链表结构但无记载分配位置及大小的信息，因为管理单元小，而且其双链表结构的指针均为数组之索引，因此大小可变，根据要管理的内存可适当变化，以节约管理开销。 一.与上面那种内存分配算法相比较,有几个方面都是完全相同的:管理单元动态分配,而且与要分配的内存块相邻,管理单元在前面,紧接其后就是分配的内存块.内存分配时也是最快匹配查找.释放内存时进行碎片整理,合并相邻的空闲内存块，但不能进行整体碎片整理的处理,因为这种处理显然是非常费时的,要把小碎片合并就必须移动已经分配的内存块，如果已经返回给用户实际的内存地址就不能再动这些块的位置.同样存在内存写越界会破坏管理链表的缺陷.二.也有显著不现的地方:可以分配任意大小的内存块,无须以管理单元整数倍来管理整个分配内存;可以设定最小粒度对齐,如2字节或是四字.已经分配与未分配内存块均存在于同一个管理链表中,通过状态字来区别,因为没有记载分配块大小,而是通过前后块之间的指针运算来计算内存块大小的，所以已分配与未分配的必须都加入链表.因为已分配与未分配的都在同一个链表中管理着,所以对于分配内存则加大了查找链表的时间(因为链表成员相对多).释放内存时不必要再查找空闲块内存的插入位置,仅须做状态改变以及相邻空闲块合并操作,没有了释放所须的查找链表工作,因此这种方法相比起来就在释放内存时有优势.三.下面具体讲讲这种算法在分配与释放时的具体细节工作:注意以下所说的位置及索引等,均指在可供分配内存数组中的位置,必须依赖数组才有意义.1.初始化.首先初始化时,初始可供分配的起始位置与终止位置,并初始化链表的链表头的上下指针均为0,链表头位于可供分配的起始地址.2.分配.首先从链表头开始,遍历查找符合分配要求的空闲块:[1].如果遍历到链表尾时(最开始没有任何分配时链表只有一个成员),下指针所指为0,此时即表明此空闲块之后的全部都为空闲,分配的内存块在插在链表尾;[2].如果找到中间的空闲块,则将空闲块一分为二,也即将一空闲块分成一个空闲块及一个已使用块,已使用块在前,新生成的空闲块必须插入链表中,要注意双链表操作时的指针调整.[3].分配内存时从低地址端开始分配，起始阶段高地址端都是空闲区域；拆分空闲块时也是从低地址开始分配，如果拆分时剩余空闲块大小不够管理单元大，此不会进行拆分，全部分配出去.[4].此算法分配时的代码不够简炼,代码有些重复,精简如下可节约代码空间:U8alloc(U8nbytes){ intret;U8i; i=first; for(i=first;;i=next(i)){//houhh20210126... if(status(i)==FREE){ ret=currentNodeAlloc(i,nbytes); if(ret==TRUE){ return(i+SIZE_HEADER); } } if(next(i)==0)break; } return(0);}/*endalloc*/3.释放.释放内存块,除了改变内存块的使用状态标志,还须进一步做相邻空闲块合并,合并时有四种情况:[1].上下两块均为空闲,此时要调整上块的Next指针以及下块之再一下一块的Prev指针.[2].上块为空闲块,此时要调整上块的Next指针以及下块Prev指针.[3].下块为空闲块.此时须调整要释放块的Next指针以及下块之再下一块的Prev指针.[4].上下均无空闲块,仅改变释放块为未使用状态.说来说去,其实就是一个简单的双链表中删除链表成员的问题,这里的相邻碎片整理情形与算法一是完全一样的，但是此种算法的较好高效,将须要调整赋值的指针数降到了最少，如果按照算法一的思路相邻两边分开调整，则要调整的指针赋值增加一倍.讨论： 有的人可能想此算法中的同时管理着空闲块与已分配块，是否可以将已分配块从链表中去掉，如算法1中一样呢？ 仔细去想就知道是不行的，首先当然释放已分配块时根据就无从知道这个已分配块的大小，因为它不在链表当中.

算法三:采自UCGUI中内存分配的算法分析算法源码文件参见UCGUI源码算法原理图:管理单元结构图：[有关UCGUI的动态内配分配算法,我在"UCGUI的动态内存分配的原理深入分析"一文中进行了深入的分析,虽然UCGUI的版本现在已经到了404,但是内存分配这一块基本没有怎么变化,可以参考此文]一.与上两种比较相同与不同的地方.UCGUI中采用的方法与上两种算法比较起来,有比较大的不同点:UCGUI中可分配的内存以及管理单元数组都是通过数组在编译时静态分配.在释放时无须进行碎片整理,因为相邻内存本来就是连在一起的,它们之间不会夹杂有管理单元;而且释放时无须进行空闲块的插入管理,只是进行从链表中删除相应管理单元操作,释放的空闲块无须加入链表管理起来.在分配时,因为只管理已分配块链表,链表的分配块地址也是从低到高有序的,且每一个链表节点记录了分配块起址以及大小,因此可以找出相邻两个分配块之间的空闲区域进行内存分配,相比算法2链表中少了空闲块的信息,分配查找起来较快.分配时与前两种算法一样都是最快匹配方案.因为UCGUI是独立的静态固定大小的管理单元数组,因此管理单元的个数固定,而且其占用空间也固定,可最大管理的分配块数目有限.因为管理单元与分配内存单元分别位于不同的数组当中,因此不会因为越界内存写操作而可能造成整个管理链表的破坏.与算法2相比,本算法管理单元所占成本偏高,主要多出了记录分配块大小以及位置的信息,在算法2中则可以通过链表指针运算就得出分配的大小以及位置信息.本算法可以进行整体的碎片整理工作,将空闲区域整体合并到高位地址以提高分配效率,但是前两种算法均不能进行这种碎片整理,因为它们分配出去的地址是已经固定的,而不象这种算法,它是相对的,外界引用时都是通过管理数组索引来转换得到真实的地址的,就因为这一层隔离处理才有了这层优越性.讨论： 有的人可能想此算法中的有上下块两个指针，可否将双链表结构变成单链表结构呢？ 仔细去想其实是可行，在此算法当中关于前一块指针仅仅是在释放内存时使用，用于从双链表中删除结点，如果去掉了前指针，首先可以减少管理单元空间的占用；再次可以减少分配时有关指针的赋值操作等；但是带来的问题是：降低了释放内存的效率，它使得在删除链表结点时必须从头至尾遍历.因此只有根据实际的情形就进行分析，看空间还是时间重要，取其一.

社会实践报告系别：班级：学号：姓名：作为祖国未来的事业的继承人，我们这些大学生应该及早树立自己的历史责任感，提高自己的社会适应能力。假期的社会实践就是很好的锻炼自己的机会。当下，挣钱早已不是打工的唯一目的，更多的人将其视为参加社会实践、提高自身能力的机会。许多学校也积极鼓励大学生多接触社会、了解社会，一方面可以把学到的理论知识应用到实践中去，提高各方面的能力；另一方面可以积累工作经验对日后的就业大有裨益。进行社会实践，最理想的就是找到与本专业对口单位进行实习，从而提高自己的实战水平，同时可以将课本知识在实践中得到运用，从而更好的指导自己今后的学习。但是作为一名尚未毕业的大学生，由于本身具备的专业知识还十分的有限，所以我选择了打散工作为第一次社会实践的方式。目的在于熟悉社会。就职业本身而言，并无高低贵贱之分，存在即为合理。通过短短几天的打工经历可以让长期处于校园的我们对社会有一种更直观的认识。实践过程：自从走进了大学，就业问题就似乎总是围绕在我们的身边，成了说不完的话题。在现今社会，招聘会上的大字报都总写着“有经验者优先”，可还在校园里面的我们这班学子社会经验又会拥有多少呢？为了拓展自身的知识面，扩大与社会的接触面，增加个人在社会竞争中的经验，锻炼和提高自己的能力，以便在以后毕业后能真正真正走入社会，能够适应国内外的经济形势的变化，并且能够在生活和工作中很好地处理各方面的问题，我开始了我这个假期的社会实践-走进天源休闲餐厅。实践，就是把我们在学校所学的理论知识，运用到客观实际中去，使自己所学的理论知识有用武之地。只学不实践，那么所学的就等于零。理论应该与实践相结合。另一方面，实践可为以后找工作打基础。通过这段时间的实习，学到一些在学校里学不到的东西。因为环境的不同，接触的人与事不同，从中所学的东西自然就不一样了。要学会从实践中学习，从学习中实践。而且在中国的经济飞速发展，又加入了世贸，国内外经济日趋变化，每天都不断有新的东西涌现，在拥有了越来越多的机会的同时，也有了更多的挑战，前天才刚学到的知识可能在今天就已经被淘汰掉了，中国的经济越和外面接轨，对于人才的要求就会越来越高，我们不只要学好学校里所学到的知识，还要不断从生活中，实践中学其他知识，不断地从各方面武装自已，才能在竞争中突出自已，表现自已。在餐厅里,别人一眼就能把我人出是一名正在读书的学生,我问他们为什么,他们总说从我的脸上就能看出来,也许没有经历过社会的人都有我这种不知名遭遇吧!我并没有因为我在他们面前没有经验而退后,我相信我也能做的像他们一样好.我的工作是在那做传菜生,每天9点钟-下午2点再从下午的4点-晚上8:30分上班,虽然时间长了点但,热情而年轻的我并没有丝毫的感到过累,我觉得这是一种激励,明白了人生,感悟了生活,接触了社会,了解了未来.在餐厅里虽然我是以传菜为主,但我不时还要做一些工作以外的事情，有时要做一些清洁的工作，在学校里也许有老师分配说今天做些什么，明天做些什么，但在这里，不一定有人会告诉你这些，你必须自觉地去做，而且要尽自已的努力做到最好，一件工作的效率就会得到别人不同的评价。在学校，只有学习的氛围，毕竟学校是学习的场所，每一个学生都在为取得更高的成绩而努力。而这里是工作的场所，每个人都会为了获得更多的报酬而努力，无论是学习还是工作，都存在着竞争，在竞争中就要不断学习别人先进的地方，也要不断学习别人怎样做人，以提高自已的能力！记得老师曾经说过大学是一个小社会，但我总觉得校园里总少不了那份纯真，那份真诚，尽管是大学高校，学生还终归保持着学生的身份。而走进企业，接触各种各样的客户、同事、上司等等，关系复杂，但我得去面对我从未面对过的一切。记得在我校举行的招聘会上所反映出来的其中一个问题是，学生的实际操作能力与在校理论学习有一定的差距。在这次实践中，这一点我感受很深。在学校，理论的学习很多，而且是多方面的，几乎是面面俱到；而在实际工作中，可能会遇到书本上没学到的，又可能是书本上的知识一点都用不上的情况。或许工作中运用到的只是很简单的问题，只要套公式似的就能完成一项任务。有时候我会埋怨，实际操作这么简单，但为什么书本上的知识让人学得这么吃力呢？这是社会与学校脱轨了吗？也许老师是正确的，虽然大学生生活不像踏入社会，但是总算是社会的一个部分，这是不可否认的事实。但是有时也要感谢老师孜孜不倦地教导，有些问题有了有课堂上地认真消化，有平时作业作补充，我比一部人具有更高的起点，有了更多的知识层面去应付各种工作上的问题，作为一名大学生，应该懂得与社会上各方面的人交往，处理社会上所发生的各方面的事情，这就意味着大学生要注意到社会实践，社会实践必不可少。毕竟，很快我就不再是一名大学生，而是社会中的一分子，要与社会交流，为社会做贡献。只懂得纸上谈兵是远远不及的，以后的人生旅途是漫长的，为了锻炼自己成为一名合格的、对社会有用的人才.很多在学校读书的人都说宁愿出去工作，不愿在校读书；而已在社会的人都宁愿回校读书。我们上学，学习先进的科学知识，为的都是将来走进社会，献出自己的一份力量，我们应该在今天努力掌握专业知识，明天才能更好地为社会服务。实践心得：虽然这次的实践只有短短的几天，而且从事的是比较简单的服务工作，但是通过与各种各样的人接触，还是让我学会了很多道理。首先是明白了守时的重要性。工作和上学是两种完全不同的概念，上学是不迟到很多时候是因为惧怕老师的责怪，而当你走上了工作岗位，这里更多的是由于自己内心的一种责任。这种责任是我学会客服自己的惰性，准时走上自己的岗位。这对我以后的学习生活也是一种鞭策，时刻牢记自己的责任，并努力加强自己的时间观念。其次让我真实的体会到了合作的重要性。虽然我工作的只是小小的一家餐厅，但是从点单到制作到递送到结帐这一环环的工作都是有分工的，只有这样才能使整家店的工作效率都大大的提高。以前虽然在书上看见过很多的团队合作的例子，但这一次是深刻的体会到了，正所谓“众人拾柴火焰高”，“团结就是力量”。在以后的学习和工作中，一定会要牢记这一点，