一种高效动态存储管理方案

摘　要：动态存储管理是许多软件系统统重要组成部分。在理论研究和实际应用中，按地址有序首次匹配线性表结构的DMM由于其有利于增强程序局部性，显著地减少内存碎片，因而得到广泛的关注。给出了适用于按地址有序首次匹配DMM的一种基于CACHE的动态存储管理方案，该方案通过缓存最近释放的内存块，可以显著提高DMM，尤其是内存释放的效率。理论分析和实际评估结果证明了方案的有效性。

关键词：动态存储管理；CACHE；地址有序；首次匹配

1 引　言

动态存储管理(DMM)是许多软件系统重要组成部分。有研究表明在内存操作频繁的C程序中DMM占了近30%的运行时间。在面向对象的程序设计语言C++中，频繁的对象创建和删除使得内存操作更加频繁。为提高软件运行效率，高效率DMM设计受到广泛关注。目前，许多大型的应用系统中采用了专门的DMM算法，一方面是为了提供DMM效率(时间和空间)，另一方面是为了回收垃圾内存。方案考虑DMM执行时间效率。

由于应用程序申请的内存大小，到达时间和内存对象生存期长短的随机性，整个DMM维护的存储空间会出现许多使用中的内存块和空闲内存块相互交替。因此DMM需要按照某种方式表示DMM的可用内存块、邻接块等信息，以便于对内存块的申请和释放。

在过去40多年的理论研究和实际应用中，DMM较多的采用了线性表结构，将可用内存块以某种形式的双向链表形式连接在一起。链表的形式有FIFO、FILO和按地址有序。对FIFO的链表，DMM将每次释放的内存块放在链表头部；对FILO链表，DMM将每次释放的内存块放在链表尾部；对按地址有序的链表，DMM释放内存块到链表时查找合适的插入位置以保持链表顺序。DMM分配内存块的算法有最佳匹配法、首次匹配法、下次匹配法和最差匹配法。直接的线性表实现将所有可用内存块(任意大小)组织在一个线性列表上，其优点是允许任意大小的内存块。相邻块合并简单高效，有利于减少内存碎片，但是伸缩性差，当线性表很长时，查找需要很长的时间。一个改进是使用区分空闲列表，将某个或某大小范围内内存使用请求在单独的线性表实现。该方案会对相邻块合并和分裂块产生一定影响，在某些情况下可伸缩性仍然很差。另外一个衍生是有着独特的分裂和合并方式的伙伴系统。伙伴系统得到了较广泛的应用，但是存在较严重的内部碎片问题，并且合并相邻块有一定限制，合并时可能引起级连操作。延迟合并技术能改进采用伙伴系统的DMM效率。

有些DMM采用了其他更复杂的数据结构，如有序二进树和笛卡儿树，位图映射也得到了一些应用。

笔者提出基于CACHE的动态存储管理方案，适用于按地址有序首次匹配的DMM。按地址有序的线性表首次匹配DMM有利于增强程序局部性，显著地减少了内存碎片，得到了最广泛的研究和应用。但是，按地址有序首次匹配DMM存在可伸缩性差的问题。研究发现，通过缓存最近释放的内存块，可以显著提高DMM，尤其是内存释放的效率。最后给出基于CACHE的DMM数据结构与算法、评估结果和分析。

2 基于CACHE的动态存储管理

已经提到按地址有序线性表首次匹配的DMM得到了最广泛的研究和最广泛的使用，但是它存在可伸缩性差的问题。如果DMM管理的堆非常大，内存使用非常频繁时，线性表变得很长，导致每次分配和释放内存块时在线性表上次查找相当费时。当内存释放时，为了保持线性表地址有序，需要查找线性表来定位内存块插入的位置；当内存申请时，同样要查找整个线性表来寻找合适的内存块。

为了提高DMM效率，改进了传统的线性表首次匹配DMM算法，引入一种CACHE机制。通过CACHE来缓存最近释放的内存块，显著减少释放内存时DMM查找开销，提高DMM尤其是内存释放效率。

其做法如下：在DMM中维护两个空闲块线性表，空闲块列表free-list和CACHE块列表cache-list。这两个列表中的空闲块都按照地址有序。当释放内存块时，DMM将该内存块释放到cache-list；使用内存块时，DMM首先查找cache-list，如果找到，则返回CACHE中的块，否则将cache-list中的块全部合并到free-list，并在合并过程中查找。如果查找失败，则从操作系统申请更多的虚拟存储空间。

下面给出具体的基于CACHE的动态存储分配和释放算法。

算法1：分配算法

算法按照首次匹配策略在堆中查找一个大小至少为ReqSize的内存块，并根据一个阈值T决定是否对其进行分裂。假定CACHE块列表和空闲块列表都是按照地址增序排列。

Step1

/*初始化*/

pFound：=nil；pCache：=cache_list；

Step2

/*查找cache-list*/

　　While pCache≠nildo

　　　ifSIZE(pCache)≥ReqSize then begin

　　　　pFound：=pCache；

　　　　if SIZE(pFound)-ReqSize>T then

　　　　　分裂pFound

　　　　Return pFound；end；

　　　else

　　　　pCache：=NEXT(pCache)；

Step3

/*cache-list查找失败，合并cache-list和free-list，同时查找*/

　　pCache：=cache_list；pFree：=free_list；

cache_list：=nil；

　　whilepCache≠nil do begin

　　　if IS_ADJACENT(pCache，pFree)

then

　　　　合并相邻块pCache和pFree；

　　　Else ifADDRESS(pCache)>AD-

DRESS(pFree) then begin

　　　　If SIZE(pFree)>ReqSize then

pFound：=pFree；

　　　　pFree：=NEXT(pFree)；

　　　end

　　else begin

　　　将pCache插入到free_list中pFree前面；

　　　pCache：=NEXT(pCache)；

　　　if SIZE(pFree)>ReqSize then

pFound：=pFree；

　　end；

　　end；

　　if pFound=nil and pFree≠nil then

　　　按照首次匹配查找pFree后的节点；

　　Ifp Cache≠ni lthen

　　　将pCache及其后连接的节点加到pFree节点后；

　　If pFound≠ni lthen begin

　　　If SIZE(pFound)-ReqSize>T then

　　　　分裂pFound；

　　　Return pFound；end；

Step4

/*在cache-list和free-list查找都失败，

从os分配虚拟存储空间*/

　　向os申请虚拟存储空间；根据ReqSize分裂成两块；其中一块放入free_list； return其中ReqSize的块；

算法2：释放算法

将块pBlock释放到堆中去。释放时如果后邻接块空闲则进行合并，否则将pBlock释放到CACHE列表，保持地址增序排列。

Step1

/*得到邻接块地址*/

pNext：=NEXT(pBlock)；

Step2

/*合并邻接块*/

　　If pNext≠nil and BLOCK_IS_FREE

(pNext)thenbegin

　　　　合并pBlock和pNext；

　　　　用合并后的块替换pNext；

　　　　return；

end；

Step3

/*如果pBlock没有后续块或者后续块非空闲，释放到CACHE列表*/

　　pCurrent：=cache_list；

　　whilepCurrent≠nilandADDRESS(pCur2

rent)

　　pCurrent：=NEXT(pCurrent)；

　if pCurrent≠nilthen

　　将pBlock插入到pCurrent前；

　else

　　将pBlock插入到cache_list最后；

　return；

在设计算法的合并邻块时只考虑了对后续邻块进行合并。这种简化分析的做法实际上在许多通用的DMM中也被采用。

3　效率分析和评估

从理论上分析，算法2中释放内存块到CACHE列表比释放到空闲列表要显著的提高效率，因为CACHE保存的只是最近释放的空闲块，并且每次分配时CACHE查找失败后CACHE中的块全部归入空闲列表，因此，其节点数远远小于空闲块的节点数，这样在CACHE列表中定位插入位置要快得多。考虑最坏的情况，算法1中，当CACHE中查找可用内存块失败后，要合并CACHE和空闲列表，因为两个列表都是按照地址有序，合并操作的需要搜索个节点，加上事先将个块释放到CACHE时保持地址有序的开销，仍显著优于直接释放块到空闲列表时的排序开销。引入CACHE后，常规的合并相邻块的操作不受任何影响，不会因此而增加内存碎片；同时，该方案倾向于优先重复使用最近释放的内存块，因此可以在一定程度上增强程序的局部性。

模型化的评估在DMM效率分析中使用非常普遍。首先，建立内存使用的模型，然后基于这个模型，模拟DMM操作过程，在模拟过程中得到运行效率分析数据。内存使用模型的建立可以通过随机产生服从某种概率分布的模型得到，但是这种模型的准确性没有被仔细研究过。采用跟踪实际程序的运行过程生成内存使用模型。为此，选择实际程序，清华大学用C++语言开发的一套三维数字化设计系统GEMS。通过重载new/de2lete，记录下GEMS中所有动态的内存申请和释放操作，并以此来驱动DMM。

在第一组实验中，在GEMS中进行了打开/关闭一个水泵设计的零件图和相应的装配文件的操作，产生了151674次内存操作(76172次申请和75502次释放)，以DMM在相应申请和释放请求时在列表中查找次数为评价指标，实验结果如表1。

在另外一组测试中，在GEMS做了更多的操作，包括新建零件、装配图、工程图和打开/关闭文件等操作，产生了1659501次内存操作(862590次申请和796911次释放)。实验结果如表2。

两组实验期待得到不同特点的内存使用序列，包括申请对象大小分布、生存期和到达时间分布。第一组实验中，依次打开文件和关闭文件导致集中的存储申请和集中的存储释放，而在第二组实验中，进行的都是GEMS常规作图操作，存储申请和释放操作比较交叉，因而能够保持一个较短的CACHE列表，从而能更显著提高存储释放效率。可以看到，基于CACHE的方案在第二组实验中释放操作效率提高了76%，在第一组实验中提高了26%。

基于CACHE的DMM在存储分配方面的效率改进受内存重复使用模式的影响，以及考虑每次内存请求的大小倾向于比每个上次内存请求后所释放的内存块大的情形，在此情况下，很多内存请求通过“搜索CACHE列表—失败—合并CACHE列表和空闲列表—搜索空闲列表”的过程实现，从而使DMM存储分配开销增大。例如，在第一组实验中的结果是，加入CACHE后DMM存储分配效率下降了93%，而在在第二组实验中效率提高了37%。从存储分配时命中率看，在第一组实验中CACHE命中率为27%(20521次)，明显低于第二组实验中的CACHE命中率36%(311503次)。总效率方面，基于CACHE的DMM在2组实验中的改进分别为15%和60%。

4　结　论

由于面向对象程序设计语言的广泛使用所带来的动态存储管理在软件系统中日益重要的影响，以及人们对软件系统运行效率期望的不断提高，高效率的DMM正在越来越受到关注。过去40多年的理论研究和实际应用中，研究人员在线性表、伙伴系统、树和位图映射等数据结构上提出了许多DMM算法。其中，按地址有序首次匹配线性表结构的DMM因其能增强程序局部性，显著地减少内存碎片，因而得到最多的研究和应用。笔者给出了一种基于CACHE的动态存储管理方案，该方案适用于按地址有序首次匹配的DMM，通过缓存最近释放的内存块，来显著提高DMM，尤其是内存释放的效率。理论分析和实际评估结果证明该方案是有效的。后续的工作包括对基于CACHE的DMM的实时性能研究，以及在此基础上实现垃圾内存自动收集。