鄢 濤, 于 曦, 劉永紅, 趙衛(wèi)東, 余 悅, 曾 誼

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都 610106;2.成都大學(xué) 模式識別與智能信息處理四川省高校重點實驗室, 四川 成都 610106)

基于C++的高效內(nèi)存池的設(shè)計與實現(xiàn)

鄢 濤1,2, 于 曦1,2, 劉永紅1,2, 趙衛(wèi)東1,2, 余 悅1, 曾 誼1

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都 610106;2.成都大學(xué) 模式識別與智能信息處理四川省高校重點實驗室, 四川 成都 610106)

為了高效、安全地利用計算機內(nèi)存資源，在大型的軟件設(shè)計中，往往要進行大量的內(nèi)存分配與回收操作，為此，C++專門提供了malloc等相關(guān)函數(shù)進行操作，這些函數(shù)能夠滿足一般的使用，但由于它們調(diào)用了操作系統(tǒng)API，所以實際使用時會在操作系統(tǒng)中產(chǎn)生大量的內(nèi)存碎片，讓內(nèi)存分配成為效率瓶頸，從而降低系統(tǒng)性能.基于此，通過對循環(huán)首次適應(yīng)算法進行改進，設(shè)計并實現(xiàn)了基于C++的高效內(nèi)存池，大幅提升了內(nèi)存分配與回收的效率.同時,還為內(nèi)存池編寫了相關(guān)的分配子，使其能與C++標(biāo)準(zhǔn)庫無縫對接，提供了若干具有垃圾回收功能的智能指針，提高了內(nèi)存管理與程序運行的效率.

內(nèi)存池；內(nèi)存分配；循環(huán)首次適應(yīng)算法；高效策略

0 引 言

大型的計算機軟件應(yīng)用中，往往需要進行大量的內(nèi)存分配與回收工作，這些工作可以通過各種內(nèi)存分配函數(shù)來完成，比如C語言的malloc.但由于操作系統(tǒng)在分配內(nèi)存時，需要進行大量的查找工作，所以使用如malloc來分配內(nèi)存實際上是比較低效的.不僅如此，由于分配算法本身的問題，多次的內(nèi)存分配/回收還會產(chǎn)生大量系統(tǒng)級別的內(nèi)存碎片，進而降低內(nèi)存的利用率.針對這些問題，內(nèi)存池將會是一個很好的解決方案，內(nèi)存池實際上是一種緩沖的機制，它一次性申請大量內(nèi)存，以后每當(dāng)有內(nèi)存分配請求時，不再調(diào)用malloc這樣的函數(shù)，而是在內(nèi)存池中尋找一片合適的區(qū)域來使用.

目前，基于C++的內(nèi)存池設(shè)計與實現(xiàn)有不少方案，其中最為優(yōu)秀的當(dāng)屬準(zhǔn)標(biāo)準(zhǔn)庫Boost提供的boost::pool和boost::object-pool，前者用于儲存各種基本數(shù)據(jù)，后者用來儲存各種類的實例對象.Boost是一個重量級的庫，安裝和配置非常繁瑣，雖然boost::pool在分配指定大小的內(nèi)存時很高效，但是在分配任意大小的內(nèi)存時，卻顯得比較笨拙.在某些應(yīng)用場景下，boost中的內(nèi)存池不能完美滿足開發(fā)的需求.基于此，本研究設(shè)計并實現(xiàn)了一款高性能且輕量級的內(nèi)存池.比起已有的研究成果，本研究的最終方案不僅擁有讓使用者滿意的分配效率，而且還能提供很多方便開發(fā)者利用的內(nèi)存池輔助工具.

1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

1.1 內(nèi)存池對象設(shè)計

內(nèi)存池對象的設(shè)計要解決的首要問題就是內(nèi)存池類的維護和管理，具體為：首先需要提供至少2個接口：allocate和deallocate，分別負(fù)責(zé)內(nèi)存分配與回收工作；然后是內(nèi)存資源的維護，大多數(shù)內(nèi)存池的實現(xiàn)都會采用鏈表，有所不同的是本研究所維護的鏈表的基本結(jié)點并不是內(nèi)存，而是“內(nèi)存池結(jié)點對象"，這些結(jié)點又各自維護著自己的內(nèi)存塊.采用這種模式，能最大限度地減小內(nèi)存池各個組件之間的耦合性.

由于內(nèi)存池的創(chuàng)建和銷毀都需要消耗大量的資源，所以不妨在這個設(shè)計中利用單例模式來防止用戶創(chuàng)建過多的內(nèi)存池對象.單例模式是一種最簡單的設(shè)計模式，只需要把構(gòu)造/析構(gòu)函數(shù)設(shè)置為私有，然后提供一個靜態(tài)函數(shù)作為接口即可.此外，還需要若干個成員變量，分別表示鏈表頭、鏈表尾、當(dāng)前結(jié)點等.內(nèi)存池類的簽名如下，

class memPool final

{

public:

void *allocate(size-t);

bool deallocate(void *);

static memPool& memPool();

private:

memPool();

～memPool();

memNode *currentNode;

memNode *lastNode;

memNode *firstNode;

};

這個類禁止被繼承，所以需使用final修飾，同時，為了保證最多只有1個實例，還需要禁用拷貝構(gòu)造函數(shù)和賦值運算符.

這樣的設(shè)計非常簡潔，在不影響內(nèi)存池功能的情況下，最大程度地簡化了對外接口，用戶能很輕松使用這個內(nèi)存池.

1.2 內(nèi)存池結(jié)點設(shè)計

內(nèi)存池維護一個“內(nèi)存池結(jié)點”的鏈表，每到分配內(nèi)存時，便通過某種算法，找到1個合適的結(jié)點，然后讓結(jié)點來執(zhí)行分配操作，所以結(jié)點類依然要有allocate和deallocate 2個接口.內(nèi)存池結(jié)點的簽名為，

struct memPool::memNode

{

explicit memNode(size-t);

～memNode();

void* allocate(size-t s);

void deallocate(void *);

memNode *next;

void *block;

};

內(nèi)存池結(jié)點類是內(nèi)存池類的內(nèi)部結(jié)構(gòu)體，不能被外部所實例化.

這樣設(shè)計內(nèi)存池結(jié)點的好處在于，把實際的內(nèi)存分配工作下發(fā)給各個結(jié)點，而不由內(nèi)存池親自完成，降低了內(nèi)存池和結(jié)點之間的耦合度，同時提高了代碼的可讀性.

2 分配算法的實現(xiàn)

2.1 結(jié)點的分配與回收算法

2.1.1 結(jié)點的分配與回收.

內(nèi)存池結(jié)點并不直接與外界打交道，只負(fù)責(zé)處理來自內(nèi)存池對象的分配/回收請求，即：當(dāng)1個結(jié)點被請求分配內(nèi)存時，它被內(nèi)存池認(rèn)為是當(dāng)前最合適的選擇，接著它會嘗試從自己維護的內(nèi)存區(qū)段中尋找一片合適的內(nèi)存分區(qū)并將其分割，然后返回結(jié)果，如果不能找到合適的，則返回NULL.

結(jié)點所維護的內(nèi)存區(qū)段被分為若干個不同的塊，每個塊由塊頭、塊尾及中間區(qū)域3部分組成.塊頭和塊尾標(biāo)記這塊內(nèi)存是否可以被分配，以及這塊內(nèi)存的大小，而中間的區(qū)域則是可以被外界所使用的.

2.1.2 結(jié)點的分配算法.

內(nèi)存分配算法中，目前比較通用的是循環(huán)首次適應(yīng)算法，該算法在分配內(nèi)存空間時，從上次找到空閑區(qū)的下1個空閑分區(qū)開始查找，直到找到第1個能滿足要求的空閑區(qū)為止，并從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè).該算法能使內(nèi)存中的空閑區(qū)分布得較均勻，但這樣會缺少大的空閑分區(qū).

本研究內(nèi)存分配算法是對循環(huán)首次適應(yīng)算法的改進，主要改進的地方為把內(nèi)存分區(qū)的連接方式從鏈表改為了線性表.比起傳統(tǒng)的算法，雖然改進后的算法失去了一些優(yōu)點，但以下的優(yōu)點卻讓它更適合內(nèi)存池：回收內(nèi)存時只需修改標(biāo)記即可，不需要查找任何表，只消耗常量時間；回收內(nèi)存后可以很容易地合并空閑分區(qū)，這在一定程度上克服了原算法缺少較大的空閑分區(qū)的問題；比起鏈表，線性表需要更少的布局成本，能讓更多的內(nèi)存被用戶使用，而不是用作系統(tǒng)保留.

本算法的思路為：從第1個結(jié)點開始，依次檢索結(jié)點中的空閑分區(qū)，直到找到1個合適大小的分區(qū)為止；若在某個結(jié)點中，無法找到合適的結(jié)點，則嘗試下1個結(jié)點，若所有結(jié)點都已經(jīng)試過，則增加1個新的結(jié)點，或者直接返回錯誤信息；若能找到合適的區(qū)域，則檢查該區(qū)域是否“足夠大”.本分配算法的代碼為，

if (*blockSize- need - 2 * infoSize

{

*i = false;/*i指向“塊頭"*/

*(i + * blockSize - infoSize) = false;/*塊尾*/

this->available -= * blockSize - 2 * infoSize;/*可

用部分減少*/

return i+infoSize;/*infoSize是“塊頭”相對可用區(qū)域的偏

移*/

}

else

{

size-t oldSize = *temp;

*i = false;

*(i + 1) = need + 2 * infoSize;/*由于有分割，所以

要重設(shè)大小*/

j += need + infoSize;

*j= false;

*(j + 1) = need + 2 * infoSize;/*設(shè)置塊尾*/

j += infoSize;

*j = true;/*分割出的新塊的塊頭*/

*(j + 1) = oldSize - (need + 2 * infoSize);

*(i + oldSize - infoSize) = true;/*分割出的新塊的塊

尾*/

*(i + oldSize - infoSize + 1) = oldSize - (need + 2 *

infoSize);

available -= need + 2 * infoSize;

return i+infoSize;

}

2.1.3 結(jié)點的回收算法.

比起分配算法，結(jié)點的回收算法則要簡單得多，只需要把塊頭塊尾的標(biāo)記從false改為true即可.

需要注意的是，在分配算法中，可能會導(dǎo)致一個內(nèi)存區(qū)段中有越來越多的內(nèi)存塊，太多內(nèi)存塊顯然是不利于分配的，所以在內(nèi)存回收時應(yīng)該嘗試合并這些內(nèi)存塊.在回收的時候，首先檢查塊頭的標(biāo)記是否為false，如果不是，說明這塊內(nèi)存已經(jīng)遭到破壞，屬于嚴(yán)重錯誤，此時應(yīng)該調(diào)用abort函數(shù)立即終止程序.

合并內(nèi)存塊分為2步：向前檢索和向后檢索，即分別檢查前面與后面緊鄰的內(nèi)存塊是否空閑，如果是則將它們合并，其代碼為，

size-t prevSize=0,nextSize=0;

if (flag != start&&*(flag - infoSize)) /*如果前方有內(nèi)存塊

并且可用*/

prevSize = *(flag - sizeof(size-t));

if ((flag + tempSize)!= end&&*(flag + tempSize))

nextSize = *(flag + tempSize + sizeof(bool));

*(flag - prevSize)=true;

*(flag - prevSize + sizeof(bool)) = blockSize+ prevSize +

nextSize;/*合并后的大小*/

*(flag + tempSize + nextSize - infoSize) = true;

*(flag + nextSize + tempSize - sizeof(size-t)) = tempSize +

prevSize + nextSize;

2.2 內(nèi)存池的分配與回收算法

2.2.1 內(nèi)存池的分配算法.

內(nèi)存池需要完成的工作是尋找一個合適的結(jié)點，并調(diào)用結(jié)點的分配算法.如果找不到合適的結(jié)點還需要額外申請空間以滿足需求；如果請求的分配大小大于單個結(jié)點所能提供的最大值，則直接返回NULL以表示分配失敗.

和結(jié)點類似，內(nèi)存池對象也采用循環(huán)首次適應(yīng)算法，它保存著下一次分配內(nèi)存的最佳起始位置，然后依次搜索，直到分配成功或者決定新增一片內(nèi)存為止，代碼為，

memNode *temp = currentNode;

for (;;)

{

temp = getNext(temp);

if (temp->available >=need+ 2 * (currentNode->

infoSize))

{

currentNode = getNext(currentNode);

result = temp->allocate(need);

if (result != nullptr)

break;

}

if (temp == currentNode)

{

lastNode->next = new memNode(nodeSize);

lastNode = lastNode->next;

result = lastNode->allocate(need);

currentNode = lastNode;

currentNodeNum++;

break;

}

}

其中，getNext函數(shù)的作用是尋找下一個結(jié)點.

2.2.2 內(nèi)存池的回收算法.

而內(nèi)存池的回收算法更加簡單，只需要遍歷鏈表，判斷需要回收的指針屬于哪個結(jié)點即可，由于鏈表通常不會有太多結(jié)點，因此回收算法甚至可以認(rèn)為是一個O(1)的操作，代碼為，

memNode *temp=firstNode;

if (ptr == NULL)/*處理NULL的情況*/

return;

for (;temp!=NULL;temp=temp->next)

if(ptr>=temp->block&&ptrblock+temp->

size)

temp->deallocate(ptr);

3 分配子的實現(xiàn)

C++標(biāo)準(zhǔn)庫中，最重要的一部分是STL，STL提供了大量的高性能的容器.這些容器通常擁有自動管理內(nèi)存的功能.默認(rèn)情況下，它們使用new和delete來分配內(nèi)存.然而，STL是一款設(shè)計精良的產(chǎn)品，組件之間耦合度極低，甚至低到可以由用戶單獨定制內(nèi)存分配的方式，而用戶指定內(nèi)存分配規(guī)則的關(guān)鍵，就在于分配子.

實際上，C++標(biāo)準(zhǔn)明確規(guī)定了一個合格的分配子應(yīng)該有哪些成員，編寫一個分配子也并不復(fù)雜，而需要關(guān)心的只有負(fù)責(zé)內(nèi)存分配/釋放的allocate和deallocate.allocate的全部代碼為，

pointer allocate(size-type n, const-pointer = 0)

{

void* p = pool.allocate(n*sizeof(value-type));/*從內(nèi)

存池獲取內(nèi)存*/

if (!p)

throw std::bad-alloc();

return (pointer)p;

}

其中，pool是一個memPool的引用，在分配子的構(gòu)造函數(shù)中被初始化.

deallocate的編寫十分簡單，調(diào)用pool的相關(guān)函數(shù)即可，

void deallocate(pointer p, size-type)

{

pool.deallocate(p);

}

當(dāng)然，一個分配子不止這么簡單，只是剩余部分都可以參考默認(rèn)的分配子的實現(xiàn)，直接拷貝，而不需要額外編寫.

4 智能指針的實現(xiàn)

事實上，從內(nèi)存池中獲取內(nèi)存都需要遵循“有借有還”的原則，即分配內(nèi)存后必須顯式釋放它，這需要用戶手動編寫釋放內(nèi)存的代碼，這顯然是很麻煩的.

C++標(biāo)準(zhǔn)庫中有一種名叫智能指針的類，它擁有和普通指針類似的行為，但是卻能在離開作用域時自動釋放內(nèi)存.受此啟發(fā)，本研究專門為內(nèi)存池打造了相關(guān)的智能指針.

首先是指向緩沖區(qū)的智能指針，這類智能指針可以當(dāng)成動態(tài)數(shù)組來使用，其類的簽名如下，

class poolPtr

{

public:

explicit poolPtr(size-t);

virtual ～poolPtr();

void reset(size-t);

void *get();

protected:

void *ptr;

AMemPool &pool;

};

通過get函數(shù)可以獲得原始指針，通過reset可以重設(shè)緩沖區(qū)的大小.相關(guān)函數(shù)的實現(xiàn)比較容易，所以這里不再贅述.

為了能讓智能指針指向各種類的對象，還需要設(shè)計一款objectPtr，它派生自poolPtr：

template

class objectPtr :protected poolPtr

{

public:

objectPtr()

virtual ～objectPtr();

T *get();

T *operator->();

T &operator*();

};

該實現(xiàn)是在poolPtr的基礎(chǔ)上增加了一些操作符而已，這些操作符底層調(diào)用父類的相關(guān)操作.需要注意的是，繼承方式是protected而不是public，這么做是為了禁用reset函數(shù).

5 性能測試與改進

為了測試本內(nèi)存池算法的性能，本研究編寫了相關(guān)代碼用于測試，其代碼為，

const int loopCount = 10000000;

const int blockSize = 10;

memPool::iniPool(1, 1000 * 1024 * 1024);/*結(jié)點數(shù)量應(yīng)盡

量少*/

memPool &pool = memPool::getMemPool();

std::vector> s(loopCount);

/*使用內(nèi)存池的分配子*/

for (int i = 0; i < loopCount; i++)

s[i] = pool.allocate(blockSize);

for (int i = 0; i < loopCount; i++)

pool.deallocate(s[i]);

for (int i = 0; i < loopCount; i++)

s[i] = malloc(blockSize);

for (int i = 0; i < loopCount; i++)

free(s[i]);

上述程序用于對自定義函數(shù)庫和系統(tǒng)函數(shù)庫進行1 000萬次內(nèi)存分配和回收運算進行比較測試.利用Visual Studio提供的性能分析工具，可以看出效率差距，測試結(jié)果如圖1所示.

圖1 1 000萬次內(nèi)存分配與回收性能報告

在整個程序的運行時間中，內(nèi)存池的所有相關(guān)操作僅僅占了10.97%，剩下的時間用于malloc/free以及其他的一些占用時間不長的函數(shù).

事實上，Visual Studio所提供的性能分析工具非常專業(yè)和精準(zhǔn)，根據(jù)這個測試結(jié)果可見，本研究設(shè)計的內(nèi)存池?fù)碛邢喈?dāng)好的性能表現(xiàn).

6 結(jié) 論

本研究對循環(huán)首次適應(yīng)算法進行了改進，設(shè)計并實現(xiàn)了基于C++的高效內(nèi)存池及一系列的輔助工具,封裝成了可分發(fā)重用的類庫，能夠進行分發(fā)和復(fù)用.實際測試表明，通過該內(nèi)存池使用策略來做內(nèi)存分配/回收的工作，其效率遠高于直接調(diào)用內(nèi)存分配/回收的函數(shù).該內(nèi)存池最大的優(yōu)點在于它可以和標(biāo)準(zhǔn)庫相配合，保證了它的實用性.不僅如此，與內(nèi)存池配套的智能指針也大大減少了手動管理內(nèi)存的工作量，大幅度提升了使用者的工作效率和程序的運行效率.

[1]劉磊.Linux內(nèi)核內(nèi)存池實現(xiàn)研究[J].科學(xué)技術(shù)與工程,2007,7(12):2849-2851.

[2]吳捷,陶志榮.一種自適應(yīng)變長塊內(nèi)存池SVBSMP[J].計算機應(yīng)用,2008,28(S1):280-283.

[3]余俊良,楊正益.基于虛擬單元可智能增長的內(nèi)存池研究[J].計算機工程與應(yīng)用,2014,50(16):127-130.

[4]許健,于鴻洋.一種Linux多線程應(yīng)用下內(nèi)存池的設(shè)計與實現(xiàn)[J].電子技術(shù)應(yīng)用,2012,38(11):146-149.

[5]馬紅斌,張峰,付華楷,等.嵌入式系統(tǒng)高效內(nèi)存池的實現(xiàn)方法:CN 101968772 B[P].2011-02-09.

[6]Wang N,Liu X,He J,et al.Collaborativememorypoolinclustersystem[C]//InternationalConferenceonParallelProcessing，2007.Xi'an,China:IEEE Press,2007.

[7]Wang X M, Wang Z.DesignandimplementationofmemorypoolsforembeddedDSP[C]//InternationalConferenceonComputerScienceandSoftwareEngineering,CSSE2008.Wuhan,China：IEEE Press,2008:160-164.

[8]侯捷.STL源碼剖析[M].武漢:華中科技大學(xué)出版社,2002.

[9]Bryant R E.深入理解計算機系統(tǒng)[M].龔奕利,賀蓮,譯.北京:機械工業(yè)出版社,2016.

Abstract:In the development of large scale software,memory allocation and reclaiming usually occur for efficiency and safety.Therefore,C++ provides special functions for this,such as malloc,etc.These functions can meet the demands of common users.However,these functions call API,so the actual use of these functions produce massive memory fragments in OS and result in the efficiency bottleneck of memory allocation which lowers the system performance.This paper has improved next-fit algorithm and designed a memory pool with efficient strategies based on C++.The strategies could extremely upgrade the efficiency of memory allocation and reclaiming.Meanwhile,for the perfect connection of memory pool with C++ standard library,the strategies provide relevant allocators for memory pool.In addition,there are a number of smart pointers which have the function of garbage collection.They can free users from complex and fallible memory management,and improve the efficiency of the program.

Keywords:memory pool;memory allocation;next-fit algorithm;efficient strategy

DesignandImplementationofEfficientMemoryPoolBasedonC++

YANTao1,2,YUXi1,2,LIUYonghong1,2,ZHAOWeidong1,2,YUYue1,ZENGYi1

(1.School of Information Science and Engineering, Chengdu University, Chengdu 610106, China;2.Key Laboratory of Pattern Recognition and Intelligent Information Processing, Chengdu University, Chengdu 610106, China)

TP311.11

A

1004-5422(2017)03-0257-05

2017-08-12.

四川省科技廳軟件科學(xué)研究計劃(2017ZR0198)、 四川省科技廳應(yīng)用基礎(chǔ)計劃(2016JY0255)資助項目.

鄢 濤(1973 — )， 男， 碩士， 副教授， 從事計算機軟件工程研究.