摘  要： 為降低嵌入式系統(tǒng)的內(nèi)存管理開銷,，提升內(nèi)存分配效率，詳細分析了slab分配器機制并指出其不足,，給出相應(yīng)的改進措施,，提出了基于e_slab算法的內(nèi)存分配器。實驗表明,，e_slab算法不僅簡化了內(nèi)存管理結(jié)構(gòu),，而且提高了內(nèi)存分配效率。
關(guān)鍵詞： slab,；e_slab,；嵌入式系統(tǒng)；cache

    隨著硬件技術(shù)的發(fā)展和內(nèi)存容量的擴大,，操作系統(tǒng)中內(nèi)存管理技術(shù)日趨完善,。但是在嵌入式領(lǐng)域中，硬件性能和內(nèi)存容量遠遠落后于PC機,，其內(nèi)存管理受到多種因素制約,，若直接采用操作系統(tǒng)中的內(nèi)存管理技術(shù)，不僅難以達到預(yù)期效果,，而且會影響嵌入式系統(tǒng)的性能,。
    在嵌入式系統(tǒng)內(nèi)存管理設(shè)計過程中,，發(fā)現(xiàn)操作系統(tǒng)中的slab分配器雖然在PC機上有良好的性能,，但是在嵌入式系統(tǒng)中不但不能發(fā)揮其優(yōu)勢，還降低了系統(tǒng)的整體性能,。本文通過分析,，指出了slab分配器的不足，并給出相應(yīng)的解決方案,。實驗結(jié)果表明,，slab分配器經(jīng)過改進可適用于嵌入式系統(tǒng)。
1 slab分配器分析
    操作系統(tǒng)內(nèi)核運行時會頻繁地為某些對象分配內(nèi)存空間,，而這些對象往往只需要幾十或幾百KB的空間,，如果直接采用頁面管理器進行內(nèi)存分配，將產(chǎn)生很多內(nèi)存碎片,，造成嚴(yán)重的內(nèi)存浪費,。slab分配器支持細粒度的內(nèi)存分配，較好地解決了此問題,。由于性能優(yōu)越,，slab被Linux,、FreeBSD等操作系統(tǒng)采用，是目前應(yīng)用最廣的內(nèi)核內(nèi)存管理器之一[1],。
1.1 slab分配器設(shè)計思想
    基于頁面分配器[2],，將一頁或幾頁的內(nèi)存組織起來，劃分成一定數(shù)量的小塊內(nèi)存,，這種連續(xù)的頁面稱之為slab,。它為內(nèi)核中使用頻繁的對象建立專門的緩沖區(qū)(cache)，每種類型的對象都有自己專用的cache[2],。一個cache管理著多個slab,，每個slab又管理著多個對象。slab的大小與所管理對象的大小有關(guān),。根據(jù)slab管理對象的分配情況,，可將每個cache中的slab分為3類[3-4]：(1)slab管理的對象已經(jīng)完全分配，沒有空閑的對象,；(2)slab管理的對象部分分配,，還有部分空閑對象；(3)slab中的對象都未分配,，都是空閑對象,。
    不同的slab分別放入不同的隊列中，即每個cache管理3個slab隊列,，cache與cache之間的關(guān)系如圖1虛框①內(nèi)所示,，cache與slab的關(guān)系如圖1虛框②內(nèi)所示。

    當(dāng)slab分配器接收到內(nèi)存申請時,，根據(jù)所申請內(nèi)存的大小找到合適的cache,，從cache管理的第二類slab中分配對象，若失敗則從第三類slab中分配對象,，若還不成功則說明cache中沒有空閑對象,，須為cache創(chuàng)建一個新的slab，從新的slab中分配空閑對象,。
    對象釋放過程中,，不僅要清空對象占用的空間，而且還要調(diào)整對象所屬slab的狀態(tài),，判斷是否改變此slab在cache中的位置,。
    slab分配器采用著色機制將不同slab中的對象放入不同的偏移處，利用硬件高速緩存的映射機制,，將頁的不同偏移映射到硬件緩存的不同地址,。而每個slab的開始部分訪問頻率最高，只要slab中起始對象的偏移不同則映射到硬件高速緩存的位置就不同，從而降低了頻繁換入換出的性能損失[4-5],。
1.2 slab分配器在嵌入式系統(tǒng)中的缺陷
    slab分配器雖然能解決系統(tǒng)對小塊內(nèi)存的頻繁需求,，但是管理結(jié)構(gòu)復(fù)雜，內(nèi)存分配策略開銷較大,。在內(nèi)存受限的嵌入式系統(tǒng)中,，slab的缺陷大大影響了系統(tǒng)的整體性能?？傊?，slab分配器存在以下三方面的缺陷：
    (1)slab管理結(jié)構(gòu)和存儲開銷較大
    每個slab由slab描述結(jié)構(gòu)、管理空閑對象的整型數(shù)組和對象三部分組成,，整型數(shù)組把slab中空閑對象組成一個順序隊列,，數(shù)組大小與對象數(shù)有關(guān)，每個對象對應(yīng)一個整數(shù),，如圖2所示,。當(dāng)對象較小時，整型數(shù)組將造成較大的內(nèi)存開銷,。

    (2)cache結(jié)構(gòu)復(fù)雜而且數(shù)量較多
    系統(tǒng)中存在著專用對象和通用對象,。專用對象專門存儲特定用途的數(shù)據(jù)結(jié)構(gòu)，例如CPU,、文件系統(tǒng)等,，其數(shù)量與系統(tǒng)密切相關(guān)；通用對象用來存儲一般的數(shù)據(jù)結(jié)構(gòu),，大小在幾十KB到幾千KB之間（一般為2的整次冪字節(jié)）,，有十多種。不管是專用對象還是通用對象,，slab分配器都為其建立了一個cache結(jié)構(gòu),，眾多cache組織和管理的較大開銷是嵌入式系統(tǒng)難以承受的。
    (3)復(fù)雜的隊列管理
    如圖1所示,，slab分配器中存在較多的隊列,，每個cache管理著3個slab隊列,，每個slab隊列與cache組成循環(huán)隊列,。所有的cache組成雙向循環(huán)隊列。面對眾多的隊列,，如何有效地管理是很困難的,。
1.3 slab在嵌入式系統(tǒng)中的改進
    針對上節(jié)中slab分配器的三點缺陷，給出相應(yīng)的改進方案,。
    (1)改進slab結(jié)構(gòu)
    針對slab中對象管理數(shù)組開銷過大的問題,，可以將多個不同的slab合并成一個slab，從而減少slab的數(shù)量，即一個slab管理對象的大小可在一個小范圍內(nèi)浮動,。由于slab中對象大小不同,，無法確定slab中對象的大小、數(shù)量和位置,，所以必須重新設(shè)置slab結(jié)構(gòu),。
    (2)限制slab分配器管理的內(nèi)存粒度范圍
    由于內(nèi)核內(nèi)存管理器主要負(fù)責(zé)細粒度的內(nèi)存管理，所以限制所管理對象的大小,。對于大塊內(nèi)存的申請,，直接由頁面分配器處理。
    (3)精簡隊列管理
    簡化cache中繁雜的隊列,，將cache中的前兩個slab隊列合并成一個隊列,。
　　本文將經(jīng)過上述三方面改進的分配器稱之為e_slab分配器。
2 e_slab分配器設(shè)計
2.1 基本管理結(jié)構(gòu)
    e_slab分配器有3個重要的基本結(jié)構(gòu),，下面分別對其作相關(guān)介紹,。
    (1)object_t結(jié)構(gòu)
    typedef  struct object {
            unsigned long size;
            unsigned long offset;
    } object_t;
    object_t是描述對象的基本結(jié)構(gòu)，每個對象對應(yīng)一個object_t結(jié)構(gòu),，它描述了對象的大小和下一個空閑對象的地址,。
    (2)e_slab_t結(jié)構(gòu)
    typedef struct e_slab _s {
            struct list_head    list;
            void                *s_mem;
            unsigned int        units;
            unsigned int        free;
    } e_slab _t;
    e_slab _t是管理對象的基本結(jié)構(gòu)，它不僅描述了本結(jié)構(gòu)的頁塊起始地址,，而且存儲了空閑對象的數(shù)量和地址等信息,。
    object_t、e_slab _t和對象結(jié)構(gòu)如圖3虛框②內(nèi)所示,。
    (3)cache結(jié)構(gòu)
    typedef struct cache_s {
            struct list_head    next;
            struct list_head    slab_list;
            unsigned int        objsize;
            unsigned int        gfporder;
            unsigned int        num;
            …
    } cache_t;
    cache的描述結(jié)構(gòu)為cache_t,，它主要描述了所管e_slab的基本信息。由于cache_t結(jié)構(gòu)大小相同,，可把cache_t看做一個專用對象,，所有的cache組織在一起。
    cache管理的所有e_slab被加入到list隊列,。把管理所有cache的結(jié)構(gòu)稱之為cache_cache,。cache_cache與cache之間有兩種關(guān)系：一種是雙向隊列關(guān)系，如圖3虛框①內(nèi)所示,，cache_cache利用雙向鏈表將系統(tǒng)中所有的cache(包括專用cache和通用cache)組成循環(huán)隊列,；一種是cache與對象之間的關(guān)系。

2.2 e_slab分配器初始化
    e_slab分配器初始化主要完成cache,、e_slab_t等結(jié)構(gòu)的創(chuàng)建,，為對象的分配做好準(zhǔn)備。
2.2.1 cache的創(chuàng)建
    cache_cache是系統(tǒng)中所有cache的管理者,，它的創(chuàng)建優(yōu)先于所有的cache,。系統(tǒng)會為每種對象創(chuàng)建一個cache,，創(chuàng)建流程如下：
    (1)申請一個cache空間。從cache_cache中分配一個專用對象,，即cache,。設(shè)置cache中的各個域，包括管理的對象大小的上限和e_slab大小,，其中e_slab大小與對象大小有關(guān),。
    (2)將此cache加入管理隊列。將cache加入cache_
cache組成的雙向隊列中,，雙向隊列采用通用鏈表鏈接所有的cache,。
    (3)將cache加入分配隊列。用一個全局的cache指針指向生成的cache,。
2.2.2 e_slab的創(chuàng)建
    在cache的創(chuàng)建過程中,，需為每個cache創(chuàng)建一個e_slab。e_slab中的對象全部空閑,，可供分配,，其流程如下：
    (1)借助頁面分配器申請連續(xù)物理頁面。根據(jù)e_slab申請的大小和是否有DMA請求,，在相應(yīng)的內(nèi)存區(qū)申請連續(xù)頁塊,。
    (2)設(shè)置頁面屬性。主要設(shè)置該頁面的e_slab標(biāo)志,，并將該頁塊與cache和e_slab關(guān)聯(lián),。
    (3)設(shè)置e_slab描述結(jié)構(gòu)，初始化對象結(jié)構(gòu),。
2.3 對象的分配與釋放
    對象的分配與釋放是內(nèi)存管理模塊提供的兩個基本接口,。
2.3.1 對象的分配
    當(dāng)系統(tǒng)需要小內(nèi)存塊或者專用對象時，系統(tǒng)會調(diào)用對象分配操作,，完成對對象的分配,，具體流程如圖4所示。

    (1)找到對應(yīng)的cache,。根據(jù)申請對象的大小定位相應(yīng)的cache,。
    (2)確定對應(yīng)的e_slab。檢查cache中的e_slab,，找到滿足本次請求的e_slab,，如果所有的e_slab均不能滿足，則創(chuàng)建一個新的e_slab并添加到cache管理的隊列中,。
    (3)從e_slab中分配一個空閑對象,。從e_slab為系統(tǒng)分配一個空閑對象和object_t結(jié)構(gòu)，將對象返還給系統(tǒng),，調(diào)整e_slab中對象,，管理數(shù)組結(jié)構(gòu)。
2.3.2 對象的釋放
    系統(tǒng)使用完對象后,，應(yīng)及時釋放對象,，否則內(nèi)存會越用越少。對象釋放流程如圖5所示,。

    (1)確定對象對應(yīng)的cache與e_slab,。根據(jù)對象的地址可以獲得所在頁面的描述符結(jié)構(gòu)，從而獲得對應(yīng)的cache和e_slab,。
    (2)釋放對象,。獲得對象在e_slab中的偏移，采用頭插法將對象加入空閑對象隊列,，并使e_slab中空閑內(nèi)存增加釋放值,。
    (3)e_slab的調(diào)整。檢查e_slab中空閑內(nèi)存大小,，若等于e_slab中所有對象都釋放,，則清除頁面的e_slab標(biāo)志，并把e_slab占用頁塊歸還給物理內(nèi)存管理器,。
2.4 e_slab分配器的回收
    在系統(tǒng)退出,、內(nèi)存回收等不再需要e_slab分配器時，需進行e_slab分配器的回收,主要完成e_slab的釋放和cache的釋放,。
2.4.1 e_slab的釋放
    在對象釋放過程中,，若發(fā)現(xiàn)某個e_slab已經(jīng)全部空閑，沒有分配的對象,，則將其釋放,，流程如下：
    (1)將e_slab從cache結(jié)構(gòu)中刪除。e_slab從cache的list隊列中摘掉,。
    (2)清除頁面標(biāo)志,。將e_slab所在物理頁面的e_slab標(biāo)志清除，并清除頁面與e_slab和cache的關(guān)聯(lián),，使頁面回到初始狀態(tài),。
2.4.2 cache的釋放
    當(dāng)系統(tǒng)不再使用某種對象時，系統(tǒng)要銷毀管理對象的cache,。cache銷毀流程如下：
    (1)將cache從管理隊列摘掉,。將cache從cache_cache組成的雙向隊列中刪除。
    (2)確定cache中沒有e_slab,。在cache銷毀前,，必須確定所管理的對象都已釋放，檢查cache的list隊列,，為空則cache中沒有e_slab,，否則進行e_slab釋放,。
    (3)釋放cache結(jié)構(gòu)占用的內(nèi)存。由于cache是cache_
cache管理的對象,，cache結(jié)構(gòu)的釋放過程就是對象的釋放過程,。
3 性能測試
    在嵌入式系統(tǒng)內(nèi)存管理設(shè)計過程中，分別采用頁面分配器與slab分配器相結(jié)合的方案和頁面分配器與e_slab分配器相結(jié)合的方案,，比較兩種方案中slab和e_slab管理結(jié)構(gòu)的內(nèi)存占用量和內(nèi)存分配釋放中的性能,。
    在管理結(jié)構(gòu)內(nèi)存占用方面，e_slab比slab節(jié)省了43%的空間,；在對象的內(nèi)存申請過程中,，e_slab的速度比slab快8%；內(nèi)存釋放過程中,，e_slab比slab快5%,。可見,，不管在時間上還是空間上,，e_slab性能都比slab優(yōu)越。
參考文獻
[1] GORMAN M．Understanding the Linux virtual memory  manager[M]．北京：北京航空航天大學(xué)出版社,，2006.
[2] 陳燕暉．頁面分配器的研究與實現(xiàn)[D].長沙：國防科技大學(xué),，2006.
[3] 李毅．Slab內(nèi)存分配策略與移植[D].成都：電子科技大學(xué)，2007.
[4] 李勇．虛擬機監(jiān)控器內(nèi)存管理機制研究與實現(xiàn)[D].鄭州：信息工程大學(xué),，2010.
[5] 史成偉.多核系統(tǒng)中的內(nèi)存管理系統(tǒng)優(yōu)化研究[D].成都：電子科技大學(xué),，2009.