基于嵌入式设备浏览器内存管理策略研究

摘要：为了解决嵌入式设备中内存频繁分配和释放所引起的内存碎片以及浏览器正常运行难问题，提出具有垃圾回收机制的可动态增长池式分配数据结构设计和具有Compaction机制的Vector分配方法；在嵌入式环境系统设计时，采用可回收动态增长池式分配策略，系统无需预潮内存大小，而且可以循环使用池内空间；Compaction机制的Vector分配方法可以移动“在用”对象和“废弃”对象调整内存占用，减少碎片。实验设计中应用上述策略，验证了该内存管理效率比系统级效率要高，嵌入式设备中打开网页文件越大，体现出来的效率更高。
关键词：嵌入式设备；浏览器；池式分配；位图；对象表

0 引言
    在嵌入式系统中，由于设备性能限制系统总的可分配内存相对较小，而在嵌入式平台上浏览器正常运行所需内存一般都比较大，并且内存分配和释放操作也比较频繁，例如，IPTV EPG界面上显示各类菜单按钮、链接以及为用户提供动态和静态的多媒体内容时，往往EPG页面中存在着各种长短不一节目导航提示信息、各种表单、导航按钮以及图片等，对于这些要显示的对象需要通过数个矩形数据结构来表示它们。在界面排版过程中，随着上、下文的改变，会进行频繁的分配释放，例如把图片插入到网页的时候，网页会把一个局部区域内的显示对象释放然后重新生成，从内存管理角度来看，这导致了频繁的内存分配和释放。为了保证浏览器Browser的正常运行和减小内部碎片，本文在分析和研究μCLinux嵌入式操作系统内存管理基础之上，提出运行在嵌入式设备上浏览器的内存管理策略，该策略主要针对浏览器中固定大小结构的频繁分配和释放，比如各种box，采用池式分配的方式(Pooled Allocation)来管理固定大小结构的分配和释放；对于可变大小结构的分配和释放，比如字符串，采用Vector进行分配和释放。

1 μCLinux内存管理分析
    μCLinux是主流嵌入式Linux系统之一，其设计的目标平台是那些不具有内存管理单元(MMU)的微处理芯片。μCLinux对标准Linux修改最大的部分在于内存管理部分，而浏览器内存管理是在一块已分配的内存上进行苒组织内存的使用方式，把这块已分配的内存当作物理内存来使用。因此μCLinux的内存管理思想对于本文设计嵌入式设备浏览器内存管理有较好参考意义。
1．1 μCLinux内存管理数据结构
    μCLinux取消了标准Linux的VMA结构(该结构建立在虚拟内存之上)，每个进程维护自己的内存地址空间的方法是在它的mm_DataStruet中维护了一个此进程所使用的内存块的链表。一个进程可以拥有任意多个内存块，每个内存块用mm_Rblock_DataStruct类型的数据结构描述其起始地址、长度以及当前被使用的次数。每个内存块由mMap()的调用来建立。
    每个进程维护了一个mm_DataStruct结构(如图1所示)用来管理它所拥有的内存空间。tblock是管理所有这个进程所用到的内存区域块的链表表头。mm_Tbloek_DataStruet是管理mm_Rblock_DataStruct的链表结构，rblock指向当前位置的链表项，next是指向下一个位置的链表项。mm_Rblock_DataStruct结构是用来管理内存块的数据结构，size指明kblock所指向的内存区域的大小，ref_count记录了这个内存空间的用户个数，kbloek是指向这个内存块空间起始位置的指针。

1．2 μCLinux物理空间管理
    虽然μCLinux中对内存地址的操作都是直接对物理内存进行的，但是仍然需要使用Linux中对物理页帧的管理数据结构，μCLinux对物理空间管理主要有以下几个方面：
    (1)物理内存以页帧为单位，页帧的长度固定为4 KB，在内核中使用page结构来表示每个物理页帧；
    (2)所有的page结构形成一个mem_map表，mem_map表在系统初始化时由free_area_init()函数创建；
    (3)在物理内存低端的bitmap表以位图方式记录了所有物理内存的空闲状况，它也是在系统初始化时由free_area_init()函数创建，bitmap表分割NR_MEM_LISTS组，对第i组初始化时设定长度为(end_mem_start_mem)／PAGE_SIZE／2(i+3)，每位表示连续2i个页帧的空状况，置位为1表示其中一页或几页已被占用；
    (4)用free_area数组记录空闲的物理页帧，free_area数组由NR_MEM_LISTS个free_area_struct结构类型的数组元素构成，每个元素均作为一条空闲块链表的表头，连续2i个空闲页帧则挂到free_area数组的第i项后面，free_area当前空闲页面个数要大于系统中硬性规定的必须保留的空闲页面的个数(5或者低于5的某个数值)，如果不足规定的空闲页面，则调用try_to_free_page()函数尝试增加系统中的空闲页面的数量；
    (5)Linux采用buddy算法分配空闲块。

2 嵌入式设备浏览器内存管理策略
    应用程序浏览器内存管理是在一块已分配的内存上进行再组织内存的使用方式，它不会涉及操作系统的内存管理，但是可以借鉴操作系统的各种内存管理方法，使对应用程序级的内存管理更高效。首先系统获得一块固定大小的内存，然后把这块内存按照功能进行固定分区，图2是Brow ser内存管理各分区的布局。把从系统获得的内存分为4个区：第一个区是Static Section，大小为20 KB，这个区主要用于保存全局性数据结构GlobalCtlVar，50 Word大小的索引缓存(Indi-ces Buffer)和Pool Linked List。第二个区是String Map Section是一个对象表，大小为20 KB，用于存入数组结构StrMap的数组，预定义数组大小为1 000，String Map功能之一类似于bitmap，用于管理空闲的数据块。第三个区是Reserve Section(保留区)，大小是20 KB。第四个区是Available Section，真正分配给用户的内存从这个区取出，有关pool的分配从上到下，有关Vector的分配从下到上。[!--empirenews.page--]

    (1)管理策略一：具有垃圾回收机制的可动态增长的池式分配。与传统固定大小的内存池技术相比，在此引入了具有垃圾回收机制的可动态增长的池式分配，其数据结构如图3所示。由于会根据需要而动态增长，因此不用预测内存池的大小；由于具有垃圾回收机制，因此可以循环使用池内空间。浏览器使用多种box对象，并经常对它们进行分配和归还，但典型的内存管理器会为每一个对象存储一个header(表头)，对小对象而言这些headers可能会使程序的内存需求加倍，此外，在一个共享的heap中分配和归还小对象会带来碎片风险，并因大量动态对象而增加管理时间。因此，对每种分配和归还频繁的box对象分别建立一个对象池，各种对象池形成一个poollinkedlist。一个对象池首先预先分配一个固定大小的arena并按对象大小对arena进行格式化，当用完arena的最后一个对象时，对当前的pool进行垃圾回收，把回收的空间放入这个pool的freelist当中，用户可以重用freelist上的空间，如果垃圾回收后发现在这个pool中已经没有可用空间，则动态分配一个arena。从这种池式分配的过程来看，对arena的分配采用了动态分区方式，对arena中结构对象的分配采用了固定分区方式。

   从理论上分析，由于内存管理器减少了存储每一个对象需要的一个header(表头)大小(在这里这个表头是GCThing，GCThing由next指针、flagp指针组成)，并且减少了碎片，池式分配能够在较少内存中存储更多对象，减少系统的整体内存需求。同时，通过一个具有垃圾回收机制的可动态增长的内存池来容纳一类小型结构对象，使这些小型结构对象在内存中紧密排列，因而降低分页系统中的paging频率及其带来的额外开销。由于本方案实现的分配和归还函数性能较好，因而提高了时间效率和实时响应能力。但是，对于每个arena，由于在最后剩余空间不能容纳一个结构对象的大小，那么这块剩余空间就会成内部碎片。当然，求出arena的合理大小会使内部碎片减少到几个字节，甚至是没有内部碎片；特别是每个pool的最后一个arena，由于这个arena最有可能没有放满结构对象，因此可能会有比较多的空间浪费。
    用户从arena中分配走内存空间，图3中标有allocated space的区域(这块区域由其上面的GCThing数据结构进行管理，GCThing由next指针、flagp指针组成)，当用户用完这块内存空间，应用程序级的内存管理应该如何重用它，以及在什么时候重用它。采用位图与垃圾回收机制结合来重用在arena中已被用户废弃的内存空间。在图3中的FLAG SECTION其本质上是一个bitmap，在FLAG SECTION中最小的单位是一个字节而不是一个位，在FLAG SECTION中每一个flag都与一个按存放结构大小进行格式化后的内存区域相对应，在图3中用GCThing数据结构中的flagp指针处理flag与其相对应的内存区域之间相互挂钩，用flag字节来表示其相对应的内存区域是正在使用，还是用户已经废弃，或是已经被的内存管理器回收。用户通过的内存管理器获得一块内存区域，内存管理器把相对应的flag置为正在使用；用户通过内存管理器释放分配给它的内存区域，内存管理器把相对应的flag置为已经废弃；内存管理器回收flag标志为已经废弃的内存区域，把回收的内存区域通过GCTh-ing数据结构挂到以freeListHead为头指针的空闲块链表中，如图3所示，从而达到了废弃内存区域的循环使用。[!--empirenews.page--]
    (2)管理策略二：具有Compaction机制的Vector分配策略。在Browser中，除了结构大小固定的对象频繁分配和归还外，经常有大量大小不同的对象分配和归还，目前，这种现象主要出现在处理TextBox这一块内容上，这些大小不向的对象具有如下特点：其一是对象的分配和归还是随机发生的；其二是对象可以在其生命过程中改变自身大小。如果直接利用系统函数进行分配和释放，在总内存比较小的嵌入式系统中会造成过多的碎片，从而浪费了大量内存空间。具有Compaction机制的Vector通过移动“继续在用对象”来移除“继续在用对象”之间的“已经废弃不用的对象”，从而把“继续在用对象”移成连续排列，而“已经废弃不用的所有对象”所占用的空间解放出来放到地址空间的某一端，对它们进行循环使用，移动对象，最富有挑战的问题在于保证原来对内存空间的引用都被正确更新。当某个对象移往一个新位置，所有指向原地址的指针都将失效。虽然技术上有可能找出每一个移动对象的原有指针并更新之，但通常引入一个额外的间接层会使问题更简单：用户引用的是指向对象表中一个项目栏内对象的“handle”，而不再直接指向对象地址，“handle”是指向某对象真实地址的“惟一”指针，对象表中一个项目栏内有代表handle的addr、有表示对象所占空间的大小size和用于标志对象所占空间是否为“继续在用对象”还是“已经废弃不用的对象”的标志位mark。图4表示了对象引用、对象表和实际对象的三者关系。当内存中移动“继续在用对象”的时候，只需要更新对象表中相对应项目栏中代表handle的addr，使它指向对象的新地址，其他所有引用都可以继续正确地访问该对象。这里返回给用户的引用是对象表的索引，用户再通过索引获得相对应的handle指针addr，为了使用户快速获取可用索引，建立了50个可用索引的buffer。

    如果对许多对象执行Compaction，那么整个Compaction过程是比较费时的，因此，什么时候执行Compaction将对一个应用程序的执行效率有着重大影响。原则是：在内存空间和可用索引能够满足分配的情况下，能不要Compaction就不要执行Compaction。因此建立了两个执行Compaction的触发点，一个触发点是当用完了预分配1 000个索引值时；另一个触发点是当没有可用内存空间用于分配时触发。结果，在许多情况下避开了Compaction过程。对于管理索引值问题，采用了如下简单算法：先取前50个索引值放到Index Buffer中，用完50个索引值以后，再取50个索引值放入Buffer中，直到预分配的1 000个索引值用完为止，这时执行Compaction，然后按顺序搜索对象表，如果对象表表项标志为可以重复利用，则把这个对象表表项的索引加入到Index Buffer之中，直到填满Index Buffer为止；如果1 000个索引值已经全部用完，则按100为单位动态增加索引值。在Vector中，存放对象表需要一些额外的空间，大量对象的Compaction会占用比较多的时间，从而降低时间效率。

3 Browser内存管理的性能分析
    Browser分别调用自己应用程序级的内存管理的接口与系统级的内存管理的接口进行运行比较，结论是应用程序级的内存管理效率比系统级的内存管理效率要高，网页越大，体现出来的效率越高。
3．1 池式分配内存使用情况
    对于Browse中各种固定大小的结构(这种结构称谓thing)，分别用相对应的一个内存池(pool)进行管理，各个pool形成一条pool链，内存管理器在执行一段时间后会按照各个pool的调用频率高低对pool链进行排序，从而提高了查找pool的效率。用小网页、中等大小网页和大网页对pool链中的各个pool进行测试，得到如图5所示的结果。

[!--empirenews.page--]
3．2执行Compaction前后Vector中的内存使用情况
    首先我们察看在打开网页的过程中在没有执行Compaction的情况下，Vector中的内存使用情况，如图6所示，由图可知，标志为蓝颜色区域是正在使用的内存空间，白颜色表示已经废弃不用的内存空间。在没有Compaction以前，已经废弃不用的区域占用了大量的内存空间，在执行Compaction以后，所有正在使用的区域都会整齐地排列在内存的高端，从而提高了内存的使用效率。

3．3 内存总体使用情况及与调用系统内存管理接口性能的比较
    首先从系统堆中分配出4 MB的内存，然后对这4 MB的内存进行应用程序级的内存管理，为了测试应用程序级的内存管理的各项性能指标，使用小、中和大三种网页对总体内存使用情况进行了统计，并且做了与调用系统内存分配和释放接口进行性能比较。表1是实验网页文件大小以及性能占用数据表，图7是运行一个大网页的时候，所有内存池占用空间和Vec-tor所占用空间的比例图，图8是针对一段关键上下文，
调用应用程序级的内存管理接口和调用系统级的内存管理接口对三种大小不一的网页在执行这段上下文的时候所用平均时间的比较。从图8中可以看出，网页越大，内存管理的性能越优于直接运用系统的内存管理。

4 结语
    本文主要在对嵌入式操作系统μCLinux内存管理进行分析和小结的基础之上，根据Browser实际运行情况，提出了运行在嵌入式设备上浏览器的内存管理池式分批和Vector分配策略，并分析了这种策略的特点和性能。最后通过实验数据来分析并得出浏览器分别调用应用程序级的内存管理的接口与系统级的内存管理的接口进行运行比较，得出应用程序级的内存管理效率比系统级的内存管理效率要高。