基于预测原理的嵌入式内存分配算法设计

程小辉，何军权，梁启亮，黄佳欢，顾俊杰

（桂林理工大学 信息科学与工程学院，广西 桂林541006）

0 引 言

内存作为嵌入式系统中十分有限的资源之一，其管理效率的高低制约着系统的整体性能。本文从内存分配速率和内存碎片率方面出发，设计一种可预测的、合并算法的动态内存管理机制。此机制一方面利用预测线程预测即将需要的内存块大小进行预分配，减少任务等待内存分配的时间开销［1］；另一方面，采用了合并原理，在内存分配时将当前需要的内存空间与预测的内存空间整体分配，以减少内存碎片。

1 嵌入式内存分配算法

嵌入式系统中，内存分配算法有多种多样，也有各自的特点，其中比较经典的有：首先适应算法、TLSF分配算法和伙伴系统。

首先适应算法，该算法主要是从系统的空闲内存链表头部开始查询，一旦寻找到不小于所需求的内存空间长度的内存块，则停止搜索，再按照作业的实际需求，从该内存块中分配出所需要的内存空间给请求者，剩下的空闲空间留在空闲分区链表中。首次适应算法主要使用空闲分区中的低地址内存空间，在系统一开始该算法效率较高，但随着系统运行时间的增长，空闲链表中前部的分区已被分割成多小块，难以满足后来的大块需求，算法查找开销也会随之越来越大。

TLSF （two level segregated fit）算法是一种二级隔离适应算法，使用位图与链表相结合的方法对内存池进行管理［2］。TLSF算法使用隔离适应机制实现一个最佳适应策略，使用位图实现了快速、定时的映射和搜索功能［3］。隔离适应机制采用了空闲链表数组，每一个空闲数组都拥有一个特定大小的空闲内存块。为了尽可能的提高获得空闲块的速度和方便管理大量的隔离链表，这些空链表分成两级。第1级将数据空间划分为2n个部分 （n＝4，5，…），第2级将第1级链表进行线型划分，每一个组都有一个与之相关的位图，用于标志链表是否为空和哪些数组有空闲块，为了保证内存空间不越界与连贯性，第2级在划分第1级链表时，往往只能划分成8个隔离链表，分别是0到7。TLSF算法在实时嵌入式系统中有很高的应用，它的优势在于用2个位图优化合适的内存查找，实现了查询时间复杂度为常数。

伙伴系统主要解决的是内存外碎片问题以及提高系统的可靠性［4］，它是把系统中所有的内存空间按照2n进行划分，在linux系统中，伙伴算法将系统的所有空闲页面分为10个块链表，每个块链表的每个块元素分别包含1，2，4，…，1024个连续的页框，每个块的第1个页框的物理地址是该块大小的整数倍，如果任务需要内存则从块链表中选择对应的块元素进行分配。例如，大小为8个页框的块，它的起始地址为8＊4K 的倍数。算法在分配内存块时是寻找合适的i，使得需要分配k大小的内存空间满足，2i－1＜k＜＝2i。伙伴系统中，要想成为伙伴必须满足3个条件：①块大小相等；②块来自同一个大块分割而成；③2 个块地址连续［5］。伙伴算法在解决外部碎片问题上相当出色，但是由于它的3个条件使得该算法存在一些不足，往往一个很小的块就会阻碍2个很大的块的合并，算法也会导致大量的内部碎片，使得本身可以申请空闲块，由于分割过小而无法继续分配。

以上几种算法都是嵌入式系统中常用到的内存分配算法，虽然这些算法有很多的有点，但也存在着一定的不足，无法同时在系统空闲时提前预知接下来要的内存块。本文设计了一种带有提前预测内存块大小的分配算法，该算法一方面使用了文献 ［1］中的马尔科夫预测算法的改进版，另一方面采用了类伙伴算法，从时间和碎片率方面提高系统的效率。

2 预测－合并内存分配机制

在嵌入式系统中，内存资源十分有限，如何高效利用有限的内存资源，是保证系统实时性、可靠性、高效性的关键之一。提高内存管理效率要从时间和空间2个方面考虑，既要考虑系统的实时性，又要考虑资源利用率。

2.1 内存块预测

嵌入式系统中，对内存资源的使用有一定规律性，申请内存块的大小一般比较集中在某一区域，这为内存预测创造了良好的条件。本文设计了一种马尔科夫预测内存预测分配算法，该算法相对于先前学者的研究，在预测内存块方面做了一定的改进，以达到提高预测的命中率的效果。预测分配原理如图1示。

图1 内存预测原理

为了实现预测功能，需要在系统中额外增加2 个块：信息统计表struct stat＿table和预测表struct pred＿list，其中pred＿list结构如下所示：

其中，total是指该fl中对应sl链表中内存块数量，task＿size则是申请fl中对应内存块大小的任务数量，head＿sl＿list指向二级链表的第1个元素。

信息统计表是一个局部二维数组用P 表示，用于统计每个任务内存块转移信息，假如系统中可分配的内存块大小为8B，16B，32B，64B，128B，256B，512B，1024 B的8 种状态，分别用｛s0，s1，s2，s3，s4，s5，s6，s7｝表示，则Pij＝Count（Si→Sj）（i，j＝0，1，…，7），Pij表示为内存块由状态Si转移到状态Sj的频数。在文献 ［1］中采用了传统的频数作为马尔科夫预测值

敲减Fascin后的CaSki细胞裸鼠移植瘤在7、12、17、22、27 d肿瘤体积和肿瘤质量均明显降低，而阴性对照慢病毒对CaSki细胞裸鼠移植瘤肿瘤体积和肿瘤质量均没有影响（表3）。敲减Fascin可以明显抑制CaSki细胞裸鼠移植瘤生长（P＜0.05）。

改进后的预测值是根据所有状态的期望值得到的，预测值为

预测链表数组：是pred＿list类型的数组，是面向整个系统的、两级隔离的，第1级 （fl）用于区分内存块大小，系统中每一个基本分配单元 （大小为size）可以通过索引log2（size）对应一个struct Pred＿list fl＿list［］数组中的元素。第2级 （sl）是用于存放内存块的单向链表，并且同在一个fl中的sl级内存块大小是相同的，为2 的幂次方。假设系统中最大的分配单位为Max，最小为Min，则fl＿list的 索引号为i ＝log2（size／Min），最大索引号：n ＝log2（Max／Min），为了减少查找时间，定义系统级位图unsigned int PL＿bitmap用于说明系统中fl＿list［i］所对应的链表中是否存在 “多余”的内存块，初始值为0，PL＿bitmap计算方式为：PL＿bitmap＝fl＿list［i］.total＞fl＿list［i］.task＿size？PL＿bitmap｜ （1＜＜i）：0。

内存预测分配需要大量的原始数据，数据越多预测结果越准确。模型首先通过预测算法预测将要分配的内存块大小，如图1所示。

当内存大小预测后，接着开始向系统申请内存空间，申请内存块前，首先需要查看PL＿bitmap的状态，查看预测链表中是否已存在所申请的内存块，如果命中则直接使用，并将对应位置0，如果没有命中，则向系统内存空闲链表中申请；其次，完成申请后，对信息统计表的对应位信息进行更新。因此，任务在申请内存块时，总是先查询PL＿bitmap，根据PL＿bitmap查看预测链表中是否有需要的内存块，如果没有再从系统内存空闲表中申请，并加入到预测链表中例如，系统假设只有8个基本块，在A、B、C、D时刻，预测线程predict（stat＿table）预测到的待分配内存块大小分别为17B，56B，237B，148B，320B。分配内存时，首先需要根据PL＿bitmap｜ （Sj＞＞4）来确认链表中是否已存在所分配的内存块，如果存在则不分配，不存在则分配，已使用则对应位置0，预测链表状态变化如图2所示。

图2 预测链表状态变化

2.2 内存块 “合并”分配

预测算法可以很好地节约系统分配内存消耗的时间，但是却无法改变内存外碎片问题，内存空间利用率没有得到很好地改善。内存空间利用率是评价系统效率的一个重要因素，系统在内存分配过程中，由于分配算法以及系统固有设计等原因不可能分配恰好与需要的内存块大小一致的空间，而导致分配出去的内存块中有部分未被使用的空闲空间而使得对内存空间不能达到100%的利用。本文设计的“预测合并算法”是从内存分配块着手，力图在内存申请时，将当前需要的内存块与预测出的即将需要的内存块作为整体进行申请，这样可以有效的减少分配块的内部碎片，提高内存的有效利用率，同时带有预测功能可以降低时间消耗。为了便于处理，需要定义一个数据结构BLK＿INFO，用于记录每个合并后的新块的划分，结构如下：

2个 “小块”地址分别为BlkAddr和 （BlkAddr＋First－Size）。内存利用率定义为

式中：S——任务实际需求的内存空间大小，P——系统malloc（）函数分配给任务的内存块大小。

当申请内存块大小满足以上2个条件，算法会将2个待分配请求进行合并，统一向系统申请内存块，并在对应BLK＿INFO 变量中写入相关信息。

例如，任务在某一时刻向系统申请大小为U1，U2（U1＜U2）的内存块，并且满足合并算法的2个条件，则内存整个申请过程如图3所示。其中图3 （a）表示为传统的内存分配方式，图3 （b）表示本文采用的合并后再分配的方式。

图3 合并内存分配模型

2.3 预测合并算法机制

合并算法可以在一定程度上提高系统内存的利用率，但是没有考虑时间上的消耗；预测算法考虑了时间消耗指标，但是对内存利用率却没有考虑。因此，本文综合预测算法与合并算法各自的优点，设计了一种预测合并分配算法。为了降低再次申请同样大小内存的时间消耗，任务结束后，内存块不会立即释放，而是存入一个Pred＿List结构体系统变量wait＿release对应位置中，并设定一个阈值，只有超过阈值或系统内存不足时方进行内存回收。

本算法从时间和空间两方面考虑。时间上，采用预测算法，根据每个任务中的信息统计表预测任务即将需要的内存块大小，将预测结果传递给合并函数，该预测过程将后期内存块的分配工作提前化以减少后期内存分配的时间消耗；空间上，当任务申请内存块时，分配算法首先调用系统中的合并算法，将当前需要的内存块与预测出的即将需要的内存块进行合并并将2个块的相关信息写入BLK＿INFO 变量中，以合并后的内存块为整体向系统申请空闲内存块，这样可以有效的减少分配块的内部碎片，提高内存的有效利用率。任务申请内存块时先从wait＿release表中查找，如果存在则直接分配，不存在则从系统的空闲链表中获取，这种类似 “快表”的方法节省了任务申请内存块的等待时间，同时，合并模式又降低内存的内部碎片。原理如图4所示。

图4 pred＿merge（）算法原理

对应不满足预测合并分配算法第2 个条件 （即UM＜Um）的内存块，则无法使用该算法，对于这部分则单独使用预测算法模型予以解决。

当任务完成内存申请时，要判断预测是否成功，如果成功需要对信息统计表进行更新，调取更新后的信息统计表，进行第2次内存块预测，将当前需要的内存块与预测内存块合并，重复预测合并分配操作。

3 实 验

3.1 预测算法对比实验

评价内存预测算法的好坏，主要是通过内存块大小预测的命中率来评价，本文也是从预测的命中率高低来对文献 ［1］和本文的预测算法进行对比。为此，本文设计了一种通过以随机数生成函数生成的随机数，以每64个数为一组，分别用2种不同的预测算法得到的预测值，进行命中率比较，matlab仿真实验结果见表1。

表1 改进前后预测算法命中率

从表1可以看出，随着循环次数的增加，改进前的算法变化不大，基本持平，改进后的算法命中率有很大的提高，但是当循环次数增加到一定时，改进后的算法增加幅度不大。

3.2 预测－合并算法实验

3.2.1 μCOS－Ⅱ内存管理机制

μC／OS－Ⅱ是一款开源的、可读性强，具备实时操作系统全部功能的嵌入式多任务实时操作系统［6］。μC／OS－Ⅱ系统在内存管理上改进原有的DSA 的内存管理机制，采用内存两级管理策略，把一个大片的连续系统空间分割成多个分区，每个分区又被分割成多个内存块，并且同一分区中的内存块大小一致。在系统中，内存管理通常用到内存控制块OS＿MEM、OS＿MemInit（）、OSMemCreate （）、OSMemGet（）、OSMemPut（）、OSMemQuery （），它们分别完成内存块分区信息记录和跟踪、内存初始化、动态内存分区创建、请求获得内存块、释放内存块，以及查询动态内存分区状态。

为了分析预测合并算法的性能，本文选用μC／OS－Ⅱ系统和预测合并机制μC／OS－Ⅱ系统作为实验系统，并将它们移植到VC＋＋环境。考虑到μC／OS－Ⅱ中内存管理是使用分区管理形式，每个内存分区中内存块大小一致且不能再分割，为了便于分割和合并，需增加一个内存信息表BLK＿INFO，主要用于记录每个固定内存块的分割情况，且每个固定大小的内存块最多只有一个BLK＿INFO 表。

相应的OS＿MEM 也需要增加一个信息段void ＊BlkInfo，指向内存块分割信息表，此后，固定大小的内存块可以根据信息表被再次划分，减少了内存内部碎片的大小。修改后的os＿mem 结构如下：

为了减少额外开销、便于系统的管理，本方案只对μC／OS－Ⅱ系统内存分区中的固定大小内存块做一次分割，分割后的2个内存块不可以被再次分割，如图5所示。

3.2.2 实验结果分析

评价嵌入式系统内存分配算法的优良除时间外，另一个重要的的指标是碎片率，内存碎片率θ定义为

图5 内存申请

式中：C——所有申请的内存空间减去释放了的内存空间，即malloc（）的总量减去free（）的总量；S——内存实际使用的总量。由此可见，内存碎片率不仅和分配的内存块大小有关，还与释放大小有联系［7］。由式 （4）可知，内存的碎片率会随着释放总量的增加而递减。考虑到嵌入式系统运行的种种复杂性，本文采用了专用测试程序CFRAC［7］作为内存碎片的测试程序。图6显示了改进后的预测合并算法在申请不同大小内存块的内存碎片率，从图可以看出，预测合并算法的内存碎片率比原来的要低，但是内存碎片率会随着申请内存块的增加而增加。

图6 内存碎片率

4 结束语

本文在研究前人研究成果的基础上，对嵌入式系统内存管理进行深入研究，设计了一种预测合并分配机制，该内存分配机制包括2部分：一方面通过信息统计表对即将申请的内存空间进行预测；另一方面，采用合并成大块原理，将2次分配内存块合并后统一分配。通过实验结果表明，该算法不仅可以对下一次内存块大小进行预测，还能有效地降低碎片率。

［1］CHENG Xiaohui，GONG Youmin，XU Anming.Research of predictable embedded memory distribution mechanism based on Markov ［J］.Computer Engineering and Design，2013，34（8）：2727－2731 （in Chinese）.［程小辉，龚幼民，许安明.基于马尔可夫链的嵌入式内存预测分配算法 ［J］.计算机工程与设计，2013，34 （8）：2727－2731.］

［2］LI Jiang，MEI Jingjing，WANG Shenliang.Research and application of TLSF dynamic memory allocation algorithm ［J］.Microcontroller ＆ Embedded Systems，2011，11 （11）：1－4（in Chinese）.［李江，梅静静，王申良，等.TLSF 动态内存分配算法的研究与应用 ［J］.单片机与嵌入式系统应用，2011，11 （11）：1－4.］

［3］Masmano M，Ripoll I，Balbastre P，et al.A constant－time dynamic storage allocator for real－time systems［J］.Real－Time Systems，2008，40 （2）：149－179.

［4］GUO Qingbo，GUO Bing，SHEN Yan.Strategy of higher reliability memory management inμC／OS－Ⅱwith buddy algorithm［J］.Microcontroller ＆ Embedded Systems，2011，11 （7）：30－33 （in Chinese）. ［国庆波，郭兵，沈艳.Buddy 算法的μC／OS－Ⅱ高可靠性内存管理方案 ［J］.单片机与嵌入式系统应用，2011，11 （7）：30－33.］

［5］HE Jinxian.Research of memory management base on multicore systems ［D］.Chengdu：University of electronic science and technology of China，2009 （in Chinese）. ［何进仙.基于多核系统的内存管理研究 ［D］.成都：电子科技大学，2009.］

［6］YANG Lu.Research and improvement of real－time operating systemμC／OS－Ⅱtask scheduling mechanism ［D］.Nanjing：Nanjing University of Posts and Telecomunications，2011 （in Chinese）.［杨露.实时操作系统μC／OS－Ⅱ任务调度机制的分析与改进 ［D］.南京：南京邮电大学，2011.］

［7］YU Qinfeng，SUN Yong.Analysis and Improvement of memory management method inμC／OS－Ⅱ ［J］.Computer Engineering，2009，35 （11）：280－282 （in Chinese）. ［俞勤丰，孙涌.μC／OS－Ⅱ中内存管理方法的分析及改进 ［J］.计算机工程，2009，35 （11）：280－282.］

［8］GAO Chao，HAN Rui，NI Hong.Memory management solution in embedded Linux systems［J］.Journal of Chinese Computer Systems，2011，32 （4）：614－618 （in Chinese）.［高超，韩锐，倪宏.嵌入式Linux平台内存管理方案 ［J］.小型微型计算机系统，2011，32 （4）：614－618.］

［9］JIANG Libo.Analysis and research of memory management in Linux ［D］.Chengdu：University of Electronic Science and Technology of China，2011 （in Chinese）.［姜力波.Linux内存管理分析与研究 ［D］.成都：电子科技大学，2011.］

［10］TIAN Linlin，ZHANG Quan，TANG Chaojing.Analysis and comparison of memory management techinques for embedded operating ［J］.Microcontrollers ＆ Embedded Systems，2009，9 （11）：5－7 （in Chinese）.［田林林，张权，唐朝京.嵌入式操作系统内存管理技术的分析与比较 ［J］.单片基于嵌入式系统应用，2009，9 （11）：5－7.］