摘要：為了解決嵌入式設(shè)備中內(nèi)存頻繁分配和釋放所引起的內(nèi)存碎片以及瀏覽器正常運(yùn)行難問題，提出具有垃圾回收機(jī)制的可動態(tài)增長池式分配數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和具有Compaction機(jī)制的Vector分配方法；在嵌入式環(huán)境系統(tǒng)設(shè)計(jì)時(shí)，采用可回收動態(tài)增長池式分配策略，系統(tǒng)無需預(yù)潮內(nèi)存大小，而且可以循環(huán)使用池內(nèi)空間；Compaction機(jī)制的Vector分配方法可以移動“在用”對象和“廢棄”對象調(diào)整內(nèi)存占用，減少碎片。實(shí)驗(yàn)設(shè)計(jì)中應(yīng)用上述策略，驗(yàn)證了該內(nèi)存管理效率比系統(tǒng)級效率要高，嵌入式設(shè)備中打開網(wǎng)頁文件越大，體現(xiàn)出來的效率更高。
關(guān)鍵詞：嵌入式設(shè)備；瀏覽器；池式分配；位圖；對象表

0 引言
    在嵌入式系統(tǒng)中，由于設(shè)備性能限制系統(tǒng)總的可分配內(nèi)存相對較小，而在嵌入式平臺上瀏覽器正常運(yùn)行所需內(nèi)存一般都比較大，并且內(nèi)存分配和釋放操作也比較頻繁，例如，IPTV EPG界面上顯示各類菜單按鈕、鏈接以及為用戶提供動態(tài)和靜態(tài)的多媒體內(nèi)容時(shí)，往往EPG頁面中存在著各種長短不一節(jié)目導(dǎo)航提示信息、各種表單、導(dǎo)航按鈕以及圖片等，對于這些要顯示的對象需要通過數(shù)個矩形數(shù)據(jù)結(jié)構(gòu)來表示它們。在界面排版過程中，隨著上、下文的改變，會進(jìn)行頻繁的分配釋放，例如把圖片插入到網(wǎng)頁的時(shí)候，網(wǎng)頁會把一個局部區(qū)域內(nèi)的顯示對象釋放然后重新生成，從內(nèi)存管理角度來看，這導(dǎo)致了頻繁的內(nèi)存分配和釋放。為了保證瀏覽器Browser的正常運(yùn)行和減小內(nèi)部碎片，本文在分析和研究μCLinux嵌入式操作系統(tǒng)內(nèi)存管理基礎(chǔ)之上，提出運(yùn)行在嵌入式設(shè)備上瀏覽器的內(nèi)存管理策略，該策略主要針對瀏覽器中固定大小結(jié)構(gòu)的頻繁分配和釋放，比如各種box，采用池式分配的方式(Pooled Allocation)來管理固定大小結(jié)構(gòu)的分配和釋放；對于可變大小結(jié)構(gòu)的分配和釋放，比如字符串，采用Vector進(jìn)行分配和釋放。

1 μCLinux內(nèi)存管理分析
    μCLinux是主流嵌入式Linux系統(tǒng)之一，其設(shè)計(jì)的目標(biāo)平臺是那些不具有內(nèi)存管理單元(MMU)的微處理芯片。μCLinux對標(biāo)準(zhǔn)Linux修改最大的部分在于內(nèi)存管理部分，而瀏覽器內(nèi)存管理是在一塊已分配的內(nèi)存上進(jìn)行苒組織內(nèi)存的使用方式，把這塊已分配的內(nèi)存當(dāng)作物理內(nèi)存來使用。因此μCLinux的內(nèi)存管理思想對于本文設(shè)計(jì)嵌入式設(shè)備瀏覽器內(nèi)存管理有較好參考意義。
1．1 μCLinux內(nèi)存管理數(shù)據(jù)結(jié)構(gòu)
    μCLinux取消了標(biāo)準(zhǔn)Linux的VMA結(jié)構(gòu)(該結(jié)構(gòu)建立在虛擬內(nèi)存之上)，每個進(jìn)程維護(hù)自己的內(nèi)存地址空間的方法是在它的mm_DataStruet中維護(hù)了一個此進(jìn)程所使用的內(nèi)存塊的鏈表。一個進(jìn)程可以擁有任意多個內(nèi)存塊，每個內(nèi)存塊用mm_Rblock_DataStruct類型的數(shù)據(jù)結(jié)構(gòu)描述其起始地址、長度以及當(dāng)前被使用的次數(shù)。每個內(nèi)存塊由mMap()的調(diào)用來建立。
    每個進(jìn)程維護(hù)了一個mm_DataStruct結(jié)構(gòu)(如圖1所示)用來管理它所擁有的內(nèi)存空間。tblock是管理所有這個進(jìn)程所用到的內(nèi)存區(qū)域塊的鏈表表頭。mm_Tbloek_DataStruet是管理mm_Rblock_DataStruct的鏈表結(jié)構(gòu)，rblock指向當(dāng)前位置的鏈表項(xiàng)，next是指向下一個位置的鏈表項(xiàng)。mm_Rblock_DataStruct結(jié)構(gòu)是用來管理內(nèi)存塊的數(shù)據(jù)結(jié)構(gòu)，size指明kblock所指向的內(nèi)存區(qū)域的大小，ref_count記錄了這個內(nèi)存空間的用戶個數(shù)，kbloek是指向這個內(nèi)存塊空間起始位置的指針。

1．2 μCLinux物理空間管理
    雖然μCLinux中對內(nèi)存地址的操作都是直接對物理內(nèi)存進(jìn)行的，但是仍然需要使用Linux中對物理頁幀的管理數(shù)據(jù)結(jié)構(gòu)，μCLinux對物理空間管理主要有以下幾個方面：
    (1)物理內(nèi)存以頁幀為單位，頁幀的長度固定為4 KB，在內(nèi)核中使用page結(jié)構(gòu)來表示每個物理頁幀；
    (2)所有的page結(jié)構(gòu)形成一個mem_map表，mem_map表在系統(tǒng)初始化時(shí)由free_area_init()函數(shù)創(chuàng)建；
    (3)在物理內(nèi)存低端的bitmap表以位圖方式記錄了所有物理內(nèi)存的空閑狀況，它也是在系統(tǒng)初始化時(shí)由free_area_init()函數(shù)創(chuàng)建，bitmap表分割NR_MEM_LISTS組，對第i組初始化時(shí)設(shè)定長度為(end_mem_start_mem)／PAGE_SIZE／2(i+3)，每位表示連續(xù)2i個頁幀的空狀況，置位為1表示其中一頁或幾頁已被占用；
    (4)用free_area數(shù)組記錄空閑的物理頁幀，free_area數(shù)組由NR_MEM_LISTS個free_area_struct結(jié)構(gòu)類型的數(shù)組元素構(gòu)成，每個元素均作為一條空閑塊鏈表的表頭，連續(xù)2i個空閑頁幀則掛到free_area數(shù)組的第i項(xiàng)后面，free_area當(dāng)前空閑頁面?zhèn)€數(shù)要大于系統(tǒng)中硬性規(guī)定的必須保留的空閑頁面的個數(shù)(5或者低于5的某個數(shù)值)，如果不足規(guī)定的空閑頁面，則調(diào)用try_to_free_page()函數(shù)嘗試增加系統(tǒng)中的空閑頁面的數(shù)量；
    (5)Linux采用buddy算法分配空閑塊。

2 嵌入式設(shè)備瀏覽器內(nèi)存管理策略
    應(yīng)用程序?yàn)g覽器內(nèi)存管理是在一塊已分配的內(nèi)存上進(jìn)行再組織內(nèi)存的使用方式，它不會涉及操作系統(tǒng)的內(nèi)存管理，但是可以借鑒操作系統(tǒng)的各種內(nèi)存管理方法，使對應(yīng)用程序級的內(nèi)存管理更高效。首先系統(tǒng)獲得一塊固定大小的內(nèi)存，然后把這塊內(nèi)存按照功能進(jìn)行固定分區(qū)，圖2是Brow ser內(nèi)存管理各分區(qū)的布局。把從系統(tǒng)獲得的內(nèi)存分為4個區(qū)：第一個區(qū)是Static Section，大小為20 KB，這個區(qū)主要用于保存全局性數(shù)據(jù)結(jié)構(gòu)GlobalCtlVar，50 Word大小的索引緩存(Indi-ces Buffer)和Pool Linked List。第二個區(qū)是String Map Section是一個對象表，大小為20 KB，用于存入數(shù)組結(jié)構(gòu)StrMap的數(shù)組，預(yù)定義數(shù)組大小為1 000，String Map功能之一類似于bitmap，用于管理空閑的數(shù)據(jù)塊。第三個區(qū)是Reserve Section(保留區(qū))，大小是20 KB。第四個區(qū)是Available Section，真正分配給用戶的內(nèi)存從這個區(qū)取出，有關(guān)pool的分配從上到下，有關(guān)Vector的分配從下到上。[!--empirenews.page--]

    (1)管理策略一：具有垃圾回收機(jī)制的可動態(tài)增長的池式分配。與傳統(tǒng)固定大小的內(nèi)存池技術(shù)相比，在此引入了具有垃圾回收機(jī)制的可動態(tài)增長的池式分配，其數(shù)據(jù)結(jié)構(gòu)如圖3所示。由于會根據(jù)需要而動態(tài)增長，因此不用預(yù)測內(nèi)存池的大??；由于具有垃圾回收機(jī)制，因此可以循環(huán)使用池內(nèi)空間。瀏覽器使用多種box對象，并經(jīng)常對它們進(jìn)行分配和歸還，但典型的內(nèi)存管理器會為每一個對象存儲一個header(表頭)，對小對象而言這些headers可能會使程序的內(nèi)存需求加倍，此外，在一個共享的heap中分配和歸還小對象會帶來碎片風(fēng)險(xiǎn)，并因大量動態(tài)對象而增加管理時(shí)間。因此，對每種分配和歸還頻繁的box對象分別建立一個對象池，各種對象池形成一個poollinkedlist。一個對象池首先預(yù)先分配一個固定大小的arena并按對象大小對arena進(jìn)行格式化，當(dāng)用完arena的最后一個對象時(shí)，對當(dāng)前的pool進(jìn)行垃圾回收，把回收的空間放入這個pool的freelist當(dāng)中，用戶可以重用freelist上的空間，如果垃圾回收后發(fā)現(xiàn)在這個pool中已經(jīng)沒有可用空間，則動態(tài)分配一個arena。從這種池式分配的過程來看，對arena的分配采用了動態(tài)分區(qū)方式，對arena中結(jié)構(gòu)對象的分配采用了固定分區(qū)方式。

   從理論上分析，由于內(nèi)存管理器減少了存儲每一個對象需要的一個header(表頭)大小(在這里這個表頭是GCThing，GCThing由next指針、flagp指針組成)，并且減少了碎片，池式分配能夠在較少內(nèi)存中存儲更多對象，減少系統(tǒng)的整體內(nèi)存需求。同時(shí)，通過一個具有垃圾回收機(jī)制的可動態(tài)增長的內(nèi)存池來容納一類小型結(jié)構(gòu)對象，使這些小型結(jié)構(gòu)對象在內(nèi)存中緊密排列，因而降低分頁系統(tǒng)中的paging頻率及其帶來的額外開銷。由于本方案實(shí)現(xiàn)的分配和歸還函數(shù)性能較好，因而提高了時(shí)間效率和實(shí)時(shí)響應(yīng)能力。但是，對于每個arena，由于在最后剩余空間不能容納一個結(jié)構(gòu)對象的大小，那么這塊剩余空間就會成內(nèi)部碎片。當(dāng)然，求出arena的合理大小會使內(nèi)部碎片減少到幾個字節(jié)，甚至是沒有內(nèi)部碎片；特別是每個pool的最后一個arena，由于這個arena最有可能沒有放滿結(jié)構(gòu)對象，因此可能會有比較多的空間浪費(fèi)。
    用戶從arena中分配走內(nèi)存空間，圖3中標(biāo)有allocated space的區(qū)域(這塊區(qū)域由其上面的GCThing數(shù)據(jù)結(jié)構(gòu)進(jìn)行管理，GCThing由next指針、flagp指針組成)，當(dāng)用戶用完這塊內(nèi)存空間，應(yīng)用程序級的內(nèi)存管理應(yīng)該如何重用它，以及在什么時(shí)候重用它。采用位圖與垃圾回收機(jī)制結(jié)合來重用在arena中已被用戶廢棄的內(nèi)存空間。在圖3中的FLAG SECTION其本質(zhì)上是一個bitmap，在FLAG SECTION中最小的單位是一個字節(jié)而不是一個位，在FLAG SECTION中每一個flag都與一個按存放結(jié)構(gòu)大小進(jìn)行格式化后的內(nèi)存區(qū)域相對應(yīng)，在圖3中用GCThing數(shù)據(jù)結(jié)構(gòu)中的flagp指針處理flag與其相對應(yīng)的內(nèi)存區(qū)域之間相互掛鉤，用flag字節(jié)來表示其相對應(yīng)的內(nèi)存區(qū)域是正在使用，還是用戶已經(jīng)廢棄，或是已經(jīng)被的內(nèi)存管理器回收。用戶通過的內(nèi)存管理器獲得一塊內(nèi)存區(qū)域，內(nèi)存管理器把相對應(yīng)的flag置為正在使用；用戶通過內(nèi)存管理器釋放分配給它的內(nèi)存區(qū)域，內(nèi)存管理器把相對應(yīng)的flag置為已經(jīng)廢棄；內(nèi)存管理器回收flag標(biāo)志為已經(jīng)廢棄的內(nèi)存區(qū)域，把回收的內(nèi)存區(qū)域通過GCTh-ing數(shù)據(jù)結(jié)構(gòu)掛到以freeListHead為頭指針的空閑塊鏈表中，如圖3所示，從而達(dá)到了廢棄內(nèi)存區(qū)域的循環(huán)使用。[!--empirenews.page--]
    (2)管理策略二：具有Compaction機(jī)制的Vector分配策略。在Browser中，除了結(jié)構(gòu)大小固定的對象頻繁分配和歸還外，經(jīng)常有大量大小不同的對象分配和歸還，目前，這種現(xiàn)象主要出現(xiàn)在處理TextBox這一塊內(nèi)容上，這些大小不向的對象具有如下特點(diǎn)：其一是對象的分配和歸還是隨機(jī)發(fā)生的；其二是對象可以在其生命過程中改變自身大小。如果直接利用系統(tǒng)函數(shù)進(jìn)行分配和釋放，在總內(nèi)存比較小的嵌入式系統(tǒng)中會造成過多的碎片，從而浪費(fèi)了大量內(nèi)存空間。具有Compaction機(jī)制的Vector通過移動“繼續(xù)在用對象”來移除“繼續(xù)在用對象”之間的“已經(jīng)廢棄不用的對象”，從而把“繼續(xù)在用對象”移成連續(xù)排列，而“已經(jīng)廢棄不用的所有對象”所占用的空間解放出來放到地址空間的某一端，對它們進(jìn)行循環(huán)使用，移動對象，最富有挑戰(zhàn)的問題在于保證原來對內(nèi)存空間的引用都被正確更新。當(dāng)某個對象移往一個新位置，所有指向原地址的指針都將失效。雖然技術(shù)上有可能找出每一個移動對象的原有指針并更新之，但通常引入一個額外的間接層會使問題更簡單：用戶引用的是指向?qū)ο蟊碇幸粋€項(xiàng)目欄內(nèi)對象的“handle”，而不再直接指向?qū)ο蟮刂罚?ldquo;handle”是指向某對象真實(shí)地址的“惟一”指針，對象表中一個項(xiàng)目欄內(nèi)有代表handle的addr、有表示對象所占空間的大小size和用于標(biāo)志對象所占空間是否為“繼續(xù)在用對象”還是“已經(jīng)廢棄不用的對象”的標(biāo)志位mark。圖4表示了對象引用、對象表和實(shí)際對象的三者關(guān)系。當(dāng)內(nèi)存中移動“繼續(xù)在用對象”的時(shí)候，只需要更新對象表中相對應(yīng)項(xiàng)目欄中代表handle的addr，使它指向?qū)ο蟮男碌刂?，其他所有引用都可以繼續(xù)正確地訪問該對象。這里返回給用戶的引用是對象表的索引，用戶再通過索引獲得相對應(yīng)的handle指針addr，為了使用戶快速獲取可用索引，建立了50個可用索引的buffer。

    如果對許多對象執(zhí)行Compaction，那么整個Compaction過程是比較費(fèi)時(shí)的，因此，什么時(shí)候執(zhí)行Compaction將對一個應(yīng)用程序的執(zhí)行效率有著重大影響。原則是：在內(nèi)存空間和可用索引能夠滿足分配的情況下，能不要Compaction就不要執(zhí)行Compaction。因此建立了兩個執(zhí)行Compaction的觸發(fā)點(diǎn)，一個觸發(fā)點(diǎn)是當(dāng)用完了預(yù)分配1 000個索引值時(shí)；另一個觸發(fā)點(diǎn)是當(dāng)沒有可用內(nèi)存空間用于分配時(shí)觸發(fā)。結(jié)果，在許多情況下避開了Compaction過程。對于管理索引值問題，采用了如下簡單算法：先取前50個索引值放到Index Buffer中，用完50個索引值以后，再取50個索引值放入Buffer中，直到預(yù)分配的1 000個索引值用完為止，這時(shí)執(zhí)行Compaction，然后按順序搜索對象表，如果對象表表項(xiàng)標(biāo)志為可以重復(fù)利用，則把這個對象表表項(xiàng)的索引加入到Index Buffer之中，直到填滿Index Buffer為止；如果1 000個索引值已經(jīng)全部用完，則按100為單位動態(tài)增加索引值。在Vector中，存放對象表需要一些額外的空間，大量對象的Compaction會占用比較多的時(shí)間，從而降低時(shí)間效率。

3 Browser內(nèi)存管理的性能分析
    Browser分別調(diào)用自己應(yīng)用程序級的內(nèi)存管理的接口與系統(tǒng)級的內(nèi)存管理的接口進(jìn)行運(yùn)行比較，結(jié)論是應(yīng)用程序級的內(nèi)存管理效率比系統(tǒng)級的內(nèi)存管理效率要高，網(wǎng)頁越大，體現(xiàn)出來的效率越高。
3．1 池式分配內(nèi)存使用情況
    對于Browse中各種固定大小的結(jié)構(gòu)(這種結(jié)構(gòu)稱謂thing)，分別用相對應(yīng)的一個內(nèi)存池(pool)進(jìn)行管理，各個pool形成一條pool鏈，內(nèi)存管理器在執(zhí)行一段時(shí)間后會按照各個pool的調(diào)用頻率高低對pool鏈進(jìn)行排序，從而提高了查找pool的效率。用小網(wǎng)頁、中等大小網(wǎng)頁和大網(wǎng)頁對pool鏈中的各個pool進(jìn)行測試，得到如圖5所示的結(jié)果。

[!--empirenews.page--]
3．2執(zhí)行Compaction前后Vector中的內(nèi)存使用情況
    首先我們察看在打開網(wǎng)頁的過程中在沒有執(zhí)行Compaction的情況下，Vector中的內(nèi)存使用情況，如圖6所示，由圖可知，標(biāo)志為藍(lán)顏色區(qū)域是正在使用的內(nèi)存空間，白顏色表示已經(jīng)廢棄不用的內(nèi)存空間。在沒有Compaction以前，已經(jīng)廢棄不用的區(qū)域占用了大量的內(nèi)存空間，在執(zhí)行Compaction以后，所有正在使用的區(qū)域都會整齊地排列在內(nèi)存的高端，從而提高了內(nèi)存的使用效率。

3．3 內(nèi)存總體使用情況及與調(diào)用系統(tǒng)內(nèi)存管理接口性能的比較
    首先從系統(tǒng)堆中分配出4 MB的內(nèi)存，然后對這4 MB的內(nèi)存進(jìn)行應(yīng)用程序級的內(nèi)存管理，為了測試應(yīng)用程序級的內(nèi)存管理的各項(xiàng)性能指標(biāo)，使用小、中和大三種網(wǎng)頁對總體內(nèi)存使用情況進(jìn)行了統(tǒng)計(jì)，并且做了與調(diào)用系統(tǒng)內(nèi)存分配和釋放接口進(jìn)行性能比較。表1是實(shí)驗(yàn)網(wǎng)頁文件大小以及性能占用數(shù)據(jù)表，圖7是運(yùn)行一個大網(wǎng)頁的時(shí)候，所有內(nèi)存池占用空間和Vec-tor所占用空間的比例圖，圖8是針對一段關(guān)鍵上下文，
調(diào)用應(yīng)用程序級的內(nèi)存管理接口和調(diào)用系統(tǒng)級的內(nèi)存管理接口對三種大小不一的網(wǎng)頁在執(zhí)行這段上下文的時(shí)候所用平均時(shí)間的比較。從圖8中可以看出，網(wǎng)頁越大，內(nèi)存管理的性能越優(yōu)于直接運(yùn)用系統(tǒng)的內(nèi)存管理。

4 結(jié)語
    本文主要在對嵌入式操作系統(tǒng)μCLinux內(nèi)存管理進(jìn)行分析和小結(jié)的基礎(chǔ)之上，根據(jù)Browser實(shí)際運(yùn)行情況，提出了運(yùn)行在嵌入式設(shè)備上瀏覽器的內(nèi)存管理池式分批和Vector分配策略，并分析了這種策略的特點(diǎn)和性能。最后通過實(shí)驗(yàn)數(shù)據(jù)來分析并得出瀏覽器分別調(diào)用應(yīng)用程序級的內(nèi)存管理的接口與系統(tǒng)級的內(nèi)存管理的接口進(jìn)行運(yùn)行比較，得出應(yīng)用程序級的內(nèi)存管理效率比系統(tǒng)級的內(nèi)存管理效率要高。