基于多级缓存的内存管理方案

丁 锐，张亚君，陈 维

(杭州电子科技大学电子信息学院，浙江杭州310018)

0 引言

随着计算机技术和数字技术的不断发展，嵌入式系统在国防和社会生活中得到了广泛的应用。一套内存管理方案对嵌入式系统显得越发重要。在嵌入式平台上，首次出现的是GNU的面向单线程的dlmalloc，随着嵌入式系统对内存需求的增加，GNU在dlmalloc的基础上提出了面向多线程的PTmalloc。内存管理主要任务是实现内存分配的高效性、可靠性和实时性，保证系统的正常运行［1］，但PTmalloc并不能很好的适应大批量的内存申请，本文在PTmalloc的基础上提出了基于多级缓存的内存管理方案。

1 内存管理模型

本文所设计的内存管理方案模型如图1所示。

图1 内存管理模型

本内存管理方案通过3级缓存来实现内存的快速分配与回收:

(1)一级缓存，线程级别的缓存，每线程一缓存，管理少量的内存块;

(2)二级缓存，进程级别的缓存，每进程一缓存，管理大量的内存块;

(3)三级缓存，进程级别的缓存，每进程一缓存，管理从操作系统申请的大批量内存。

由图1可知，一级缓存与二级缓存通过批量的内存块进行交互，二级缓存与三级缓存通过对齐SPAN进行交互，三级缓存与操作系统通过非对齐SPAN进行交互。SPAN是具有一定页面数的内存，用于切割成小内存块供用户进程使用。本内存管理方案中的SPAN分为对齐SPAN(固定页面数)和非对齐SPAN，二级缓存管理对齐SPAN，三级缓存以地址排序链的形式分别管理对齐SPAN和非对齐SPAN，非对齐SPAN主要由对齐SPAN合并而成。

2 内存管理原理

2.1 内存分类

本内存管理方案将内存分为3种:

(1)Small内存，大小在［8，4K］，该种内存有一级缓存;

(2)Large内存，大小在(4K，32K］，该种内存没有一级缓存;

(3)Huge内存，大小在(32K，∞)，该种内存只有三级缓存。

根据实际应用系统的情况，本内存管理方案再将Small内存按不同的步长分为56种，每个一级缓存和二级缓存均有56个链表形式的内存池［2］与之相对应。

2.2 各级缓存的交互

一级缓存与二级缓存以批量的内存块为交互方式，在交互过程中，交互内存块个数随着该类内存使用频率而动态变化，称为慢启动。如图2所示。

图2 慢启动过程示意图

当一级缓存的内存池没有内存块供分配时，向二级缓存申请Num块内存。慢启动过程就是控制Num动态变化的过程:系统初始化时，Num为1，随着该类内存使用频率的不断增加，Num逐渐增大到N后以N为步长继续增长，当Num达到4N时停止增长;当一级缓存内存池的内存块个数大于Num时，若Num大于N，则以N为步长减少Num，否则逐渐减少到1。

二级缓存与三级缓存以对齐SPAN为交互方式。二级缓存没有SPAN供切割时，向三级缓存申请一个对齐的SPAN;二级缓存中的空闲SPAN达到一定的门限时，向三级缓存释放一定数量的对齐SPAN，三级缓存根据得到的对齐SPAN进行适当的合并。

2.3 内存块的切割与合并

应用进程使用的内存都源于SPAN的切割。内存块与SPAN的关系如图3所示。

SPAN根据用户进程的需要按照需要多少切割多少的原则被切割为多个大小相同的内存块。在本内存分配方案中，SPAN的切割一般都是批量的切割，为了保证内存分配的效率，Small内存的切割与Large内存的切割有所区别:Large内存的切割引用PTmalloc的内存头边界标记切割，Small内存的切割为完全无缝切割:无内存头切割。

图3 SPAN与内存块

SPAN除了支持内存块的切割外，还支持内存块的合并。此处的合并仅仅只是被释放的内存块与point指向的地方合并，不能合并的内存块则通过SPAN控制信息以单向链表管理。

2.4 内存申请、释放流程

本内存分配方案的申请、释放流程如图4所示。

图4 内存申请、释放流程

本内存管理方案中，Small内存和Large内存的申请、释放大致步骤如图4。由于Large内存没有一级缓存，在申请、释放Large内存时，直接在二级缓存中进行内存的边界标记切割与合并。

Huge内存引用PTmalloc的分配方法:通过mmap与munmap向操作系统申请、释放［3－5］。

3 本内存管理方案与PTmalloc的性能比较

本内存管理方案通过引入多级缓存结构和SPAN结构来实现性能的提升:

(1)在多级缓存结构中，通过慢启动过程动态控制内存池的长度，提高了大批量内存分配速度，并缓解了多级缓存导致的内存浪费问题;

(2)一个一级缓存严格对应一个线程，并且一级缓存与二级缓存通过批量内存进行交互，大大降低了锁冲突。PTmalloc存在多个线程对应一个分配区域的问题，导致大量的锁冲突;

(3)通过地址排序链管理SPAN，尽量使用使用过的、地址低的SPAN进行切割。PTmalloc只是对内存块按大小进行排序，切割时会导致过多的内存碎片;

(4)一个SPAN对应一种大小的内存，避免了PTmalloc杂乱无章的内存切割与合并，大大提高了内存分配速率，降低了内存碎片。

通过PTmalloc自带的测试用例测试(20个线程随机申请、随机释放100 000次)，本内存管理方案Small内存的处理比PTmalloc快一倍左右，Large与Huge内存的处理与PTmalloc不相上下，测试结果如表1、2所示。

表1 small内存测试结果

表2 large、huge内存测试结果

4 结束语

本文的内存管理方案结合了PTmalloc的优点，同时对PTmallo的缺陷进行了优化。实现了内存的快速、稳定分配，很好的解决了大批量内存分配导致的速度慢和内存碎片问题。本文的内存管理方案适用于路由器等反复进行大批量的内存申请的操作系统。

［1］ 王铮，李志军.一种适用嵌入式系统的自适应动态内存管理方案［J］.计算机技术与发展，2007，17(3):50－54.

［2］ Jonathan Bartlett.内存管理内幕［EB/OL］.http://www.ibm.com/developerworks/cn/linux/，2004 －1 －20.

［3］ 郝庆丰.返璞归真－UNIX技术内幕［M］.北京:电子工业出版社，2010:53－55.

［4］ Marshall Kirk McKusick，George V.Neville-Neil.The Design and Implementation of the FreeBSD Operating System［M］.北京:中国电力出版社，2008:141－143.

［5］ Mel Gorman.Understanding the Linux Virtual Memory Manger［M］.北京:北京航空航天大学出版社，2006:105 －109.