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的分配從下到上。

（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所示，從而達到了廢棄內存區域的循環使用。

（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所示的結果。

如果對許多對象執行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所示的結果。

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分配策略，并分析了這種策略的特點和性能。最后通過實驗數據來分析并得出瀏覽器分別調用應用程序級的內存管理的接口與系統級的內存管理的接口進行運行比較，得出應用程序級的內存管理效率比系統級的內存管理效率要高。