第36卷第3期电子科技大学学报Vol.36No.32007年6月JournalofUniversityofElectronicScienceandTechnologyofChinaJun.2007一种嵌入式系统内存管理的延迟合并伙伴机制郭振宇，桑楠，杨霞(电子科技大学计算机科学与工程学院成都610054)【摘要】为提高嵌入式系统动态存储管理机制的运行效率，确定时间开销，该文在分析经典伙伴系统的基础上，提出了延迟合并的方法，并辅以碎片整理及位图机制。通过仿真试验效果分析，该机制具有更好的运行效率。关键词位图机制;伙伴系统;碎片整理;延迟合并中图分类号TP316.2文献标识码AARecombination-DelayingBuddyMechanismforEmbeddedSystemMemoryManagementGUOZhen-yu，SANGNan，YANGXia(SchoolofComputerScienceandEngineering,UniversityofElectronicScienceandTechnologyofChinaChengdu610054)AbstractInordertoimprovetheruntimeefficiencyofdynamicstoragemanagementforembeddedsystemandtoboundthetimespending,amethodofrecombination-delayispresentedbasedontheclassicbuddysystem,fragmentationcollection,andbitmapmechanism.Simulationexperimentsshowthatthisnewmechanismhasbetterruntimeefficiency.Keywordsbitmapmechanism;buddysystem;fragmentationcollection;recombination-delay随着嵌入式产品开发复杂程度的增加，如何在2i+3,")。嵌入式系统中更加有效地管理动态内存显得越发重当长度为2k个页面的内存块被释放时，首先检要。如果内存短缺或者管理不当，将导致整个系统查其伙伴块是否空闲，如果空闲则与伙伴块合并为反应迟缓，甚至崩溃。现代操作系统已经运用位图、长2k+1个页面的空闲块并链入对应队列中；若忙则直链表等多种手段来管理内存。但在嵌入式环境下，接链入长为2k个页面的空闲队列中。这个过程是递还要求内存管理机制具有运行效率高、时间开销可归的，即合并得到的2k+1的空闲块也要检查它的伙伴确定的特点。为此，本文在伙伴系统的基础上，提块状态并做相同的处理，直到得到最大的空闲块2M。出了延迟合并的方法。经典伙伴系统是一个非常强调时效的算法。最坏情况下内存分配和回收的时间开销都是1伙伴算法描述O(log2M)，M是堆的大小。实时嵌入式系统的堆大小由文献[1]提出的伙伴系统是一个快速的动态内M可以假定为固定的，这样内存的分配和回收可在存管理经典算法(下文称其为经典伙伴系统)。在该算一定时限内完成。经典伙伴系统内存管理的主要时k法中有多个空闲队列，块长为2个页面的空闲块都间消耗在分配时没有合适的内存块时，把大的内存链在同一个队列中。当要分配一个长为d的内存块块分裂成较小的内存块的过程，以及在回收时，把i−1ii时，求i使得2＜d≤2，然后从长为2个页面的空闲小的空闲块合并成较大空闲块的过程。队列中分配一块内存。如果该空闲队列耗尽，则从虽然经典伙伴系统有上述优点，但它在嵌入式i+1长为2个页面的空闲队列中分配一个块，将其分为系统中却没有得到广泛的应用，原因有两点：(1)经长度相等的两半(互为伙伴)，一半用于分配，另一半典伙伴系统使内存碎片化[1]，这意味着即使堆中有ii+1链入长为2的伙伴空闲队列中。如果长为2个页面足够内存，但其地址不连续从而不能满足某些内存i+2的空闲队列也空，就继续请求更大的内存块(2,请求。(2)若创建对象的生存周期很短，经典伙伴系收稿日期：2005−06−13基金项目：“十五”预研项目(4131504040b)作者简介：郭振宇(1981−)，男，硕士，主要从事实时操作系统防危技术方面的研究.556电子科技大学学报第36卷统的运行效率较低。在这些情况下，系统因为不断针对上述的问题，本文提出一种在内存请求不地将内存块分裂合并而产生过大的负载。能满足时使用的内存整理算法，其开销较小。该算针对上述问题，本文提出了一种采用延迟合并、法能整理请求大小的空闲块给程序使用，并不整理辅以碎片整理和