摘要：为了解决嵌入式设备中内存频繁分配和释放所引起的内存碎片以及浏览器正常运行难问题，提出具有垃圾回收机制的可动态增长池式分配数据结构设计和具有ComPACtion机制的Vector分配方法；在嵌入式环境系统设计时，采用可回收动态增长池式分配策略，系统无需预潮内存大小，而且可以循环使用池内空间；Compaction机制的Vector分配方法可以移动“在用”对象和“废弃”对象调整内存占用，减少碎片。实验设计中应用上述策略，验证了该内存管理效率比系统级效率要高，嵌入式设备中打开网页文件越大，体现出来的效率更高。
关键词：嵌入式设备；浏览器；池式分配；位图；对象表
引言
在嵌入式系统中，由于设备性能限制系统总的可分配内存相对较小，而在嵌入式平台上浏览器正常运行所需内存一般都比较大，并且内存分配和释放操作也比较频繁，例如，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的分配从下到上。
(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所示，从而达到了废弃内存区域的循环使用。
上一篇：一种实时机场集成行李处理系统
