詳解內(nèi)存池技術(shù)的原理與實(shí)現(xiàn)

序言

最近在網(wǎng)上看到了幾篇篇講述內(nèi)存池技術(shù)的文章，有一篇是有IBM中國研發(fā)中心的人寫的，寫的不錯(cuò)~~文章地址在本篇blog最后。原文的講述比我的要清晰很多，我在這只是把我的一些理解和遇到的一些問題和大家分享一下~~

一、為什么要使用內(nèi)存池技術(shù)呢

主要有兩個(gè)原因：1、減少new、delete次數(shù)，減少運(yùn)行時(shí)間；2、避免內(nèi)存碎片。

1、效率

c語言中使用malloc/free來分配內(nèi)存，c++中使用new/delete來分配內(nèi)存，他們的內(nèi)存申請(qǐng)與釋放都是與操作系統(tǒng)進(jìn)行交互的。具體的內(nèi)容在嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)的第八章有相關(guān)講述，主要就是系統(tǒng)要維護(hù)一個(gè)內(nèi)存鏈表，當(dāng)有一個(gè)內(nèi)存申請(qǐng)過來時(shí)，根據(jù)相應(yīng)的分配算法在鏈表中找個(gè)一個(gè)合適的內(nèi)存分配給它。這些算法有的是分配最先找到的不小于申請(qǐng)內(nèi)存的內(nèi)存塊，有的是分配最大的內(nèi)存塊，有的是分配最接近申請(qǐng)內(nèi)存大小的內(nèi)存塊。分配的內(nèi)存塊可能會(huì)大于所申請(qǐng)的內(nèi)存大小，這樣還有進(jìn)行切割，將剩余的內(nèi)存插入到空閑鏈表中。當(dāng)釋放的時(shí)候，系統(tǒng)可能要對(duì)內(nèi)存進(jìn)行整理，判斷free的內(nèi)存塊的前后是否有空閑，若有的話還要進(jìn)行合并。此外，new/delete還要考慮多線程的情況。總之一句話，調(diào)用庫中的內(nèi)存分配函數(shù)，十分的耗時(shí)~~

2、內(nèi)存碎片

什么是內(nèi)存碎片內(nèi)，從字面意思就很好理解了，就是內(nèi)存不再是一整塊的了，而是碎了。因?yàn)檫B續(xù)的這種new/delete操作，一大塊內(nèi)存肯能就被分割成小的內(nèi)存分配出去了，這些小的內(nèi)存都是不連續(xù)的。當(dāng)你再去分配大的連續(xù)內(nèi)存的時(shí)候，盡管剩余內(nèi)存的總和可能大于所要分配的內(nèi)存大小，但系統(tǒng)就找不到連續(xù)的內(nèi)存了，所以導(dǎo)致分配錯(cuò)誤。malloc的時(shí)候會(huì)導(dǎo)致返回NULL，而new的時(shí)候再vc6.0中返回NULL，vs2003以上則是拋出異常。

二、原理

要解決上述兩個(gè)問題，最好的方法就是內(nèi)存池技術(shù)。具體方法就是大小固定、提前申請(qǐng)、重復(fù)利用。

因?yàn)閮?nèi)存的申請(qǐng)和釋放是很低效的，所以我們只在開始時(shí)申請(qǐng)一塊大的內(nèi)存（在該塊內(nèi)存不夠用時(shí)在二次分配），然后每次需要時(shí)都從這塊內(nèi)存中取出，并標(biāo)記下這塊內(nèi)存被用了，釋放時(shí)標(biāo)記此內(nèi)存被釋放了。釋放時(shí)，并不真的把內(nèi)存釋放給操作系統(tǒng)，只要在一大塊內(nèi)存都空閑的時(shí)候，才釋放給操作系統(tǒng)。這樣，就減少了new/delete的操作次數(shù)，從而提高了效率。

在調(diào)用內(nèi)存分配函數(shù)的時(shí)候，大部分時(shí)間所分配的內(nèi)存大小都是一定的，所以可以采用每次都分配固定大小的內(nèi)存塊，這樣就避免了內(nèi)存碎片產(chǎn)生的可能。

三、具體實(shí)現(xiàn)

我所采用的內(nèi)存池的構(gòu)造方法完全是按照文章1所介紹的方法，內(nèi)存池的結(jié)構(gòu)圖如下：

?

如圖所示MemoryPool是一個(gè)內(nèi)存池類，其中pBlock是一個(gè)指向了一個(gè)內(nèi)存塊的指針，nUintSzie是分配單元的大小，nInitSize是第一次分配時(shí)向系統(tǒng)申請(qǐng)的內(nèi)存的大小，nGrouSize是后面每次向系統(tǒng)申請(qǐng)的內(nèi)存的大小。

MemoryBloc代表一個(gè)內(nèi)存塊單元，它有兩部分構(gòu)成，一部分時(shí)MemoryBlock類的大小，另一部分則是實(shí)際的內(nèi)存部分。一個(gè)MemoryBlock的內(nèi)存是在重載的new操作符中分配的，如下所示：

void* MemoryBlock::operator new(size_t, int nUnitSize,int nUnitAmount )
{
    return ::operator new( sizeof(MemoryBlock) + nUnitSize * nUnitAmount );
}

MemoryBlock內(nèi)中，nSize代碼該內(nèi)存塊的大小（系統(tǒng)分配內(nèi)存大小-MemoryBlock類的大?。?，nFree是空閑內(nèi)存單元的個(gè)數(shù)，nFirst代表的是下一個(gè)要分配的內(nèi)存單元的序號(hào)。aData是用來記錄待分配內(nèi)存的位置的。因?yàn)橐峙涞膬?nèi)存是在new中一起向系統(tǒng)申請(qǐng)的，并沒有一個(gè)指針指向這塊內(nèi)存的位置，但它的位置就在MemoryBlock這個(gè)類的地址開始的，所以可以用MemoryBlock的最后一個(gè)成員的位置來表示待分配內(nèi)存的位置。

帶分配內(nèi)存中，是以nUnitSize為單位的，一個(gè)內(nèi)存單元的頭兩個(gè)字節(jié)都記錄了下一個(gè)要分配的內(nèi)存單元的序號(hào)，序號(hào)從0開始。這樣實(shí)際也就構(gòu)成了一個(gè)數(shù)組鏈表。由MemoryBlock的構(gòu)造函數(shù)來完成這個(gè)鏈表的初始化工作：

MemoryBlock::MemoryBlock( int nUnitSize,int nUnitAmount )
    :   nSize   (nUnitAmount * nUnitSize),
        nFree   (nUnitAmount - 1),  //構(gòu)造的時(shí)候，就已將第一個(gè)單元分配出去了，所以減一
        nFirst  (1),                //同上
        pNext   (NULL)
{
    //初始化數(shù)組鏈表，將每個(gè)分配單元的下一個(gè)分配單元的序號(hào)寫在當(dāng)前單元的前兩個(gè)字節(jié)中
    char* pData = aData;
    //最后一個(gè)位置不用寫入
    for( int i = 1; i < nSize - 1; i++)
    {
        (*(USHORT*)pData) = i;
        pData += nUnitSize;
    }
}

在MemoryPool的Alloc（）中，遍歷block鏈表，找到nFree大于0的block，從其上分配內(nèi)存單元。然后將nFree減一，修改nFirst的值。

在MemoryPool的Free（pFree）函數(shù)中，根據(jù)pFree的值，找到它所在的內(nèi)存塊，然后將它的序號(hào)作為nFirst的值（因?yàn)樗^對(duì)是空閑的），在pFree的頭兩個(gè)字節(jié)中寫入原來nFirst的值。然后要判斷，該block是否全部為free，方法是檢測(cè)nFree * nUnitSize == nSize。若是，則向系統(tǒng)釋放內(nèi)存，若不是，則將該block放到鏈表的頭部，因?yàn)樵揵lock上一定含有空隙的內(nèi)存單元，這樣可以減少分配時(shí)遍歷鏈表所消耗的時(shí)間。

四、使用

內(nèi)存池一般都是作為一個(gè)類的靜態(tài)成員，或者全局變量。使用時(shí)，重載new操作符，使其到MemoryPool中去分配內(nèi)存，而不是向系統(tǒng)申請(qǐng)。這樣，一個(gè)類的所以對(duì)象都在一個(gè)內(nèi)存池中開辟空間。

void CTest::operator delete( void* pTest )
{   
    Pool.Free(pTest);   
}
 
 
void* CTest::operator new(size_t)
{
    return (CTest*)Pool.Alloc();
}

五、代碼

MemoryPool.h

#include 
#include 
 
#define  MEMPOOL_ALIGNMENT 8            //對(duì)齊長(zhǎng)度
//內(nèi)存塊，每個(gè)內(nèi)存塊管理一大塊內(nèi)存，包括許多分配單元
class MemoryBlock
{
public:
                    MemoryBlock (int nUnitSize,int nUnitAmount);
                    ~MemoryBlock(){};
    static void*    operator new    (size_t,int nUnitSize,int nUnitAmount);
    static void     operator delete (void* ,int nUnitSize,int nUnitAmount){};
    static void     operator delete (void* pBlock);
 
    int             nSize;              //該內(nèi)存塊的大小，以字節(jié)為單位
    int             nFree;              //該內(nèi)存塊還有多少可分配的單元
    int             nFirst;             //當(dāng)前可用單元的序號(hào)，從0開始
    MemoryBlock*    pNext;              //指向下一個(gè)內(nèi)存塊
    char            aData[1];           //用于標(biāo)記分配單元開始的位置，分配單元從aData的位置開始
     
};
 
class MemoryPool
{
public:
                    MemoryPool (int _nUnitSize,
                                int _nGrowSize = 1024,
                                int _nInitSzie = 256);
                    ~MemoryPool();
    void*           Alloc();
    void            Free(void* pFree);
 
private:
    int             nInitSize;          //初始大小
    int             nGrowSize;          //增長(zhǎng)大小
    int             nUnitSize;          //分配單元大小
    MemoryBlock*    pBlock;             //內(nèi)存塊鏈表
};

MemoryPool.cpp

#include "MemoryPool.h"
 
MemoryBlock::MemoryBlock( int nUnitSize,int nUnitAmount )
    :   nSize   (nUnitAmount * nUnitSize),
        nFree   (nUnitAmount - 1),  //構(gòu)造的時(shí)候，就已將第一個(gè)單元分配出去了，所以減一
        nFirst  (1),                //同上
        pNext   (NULL)
{
    //初始化數(shù)組鏈表，將每個(gè)分配單元的下一個(gè)分配單元的序號(hào)寫在當(dāng)前單元的前兩個(gè)字節(jié)中
    char* pData = aData;
    //最后一個(gè)位置不用寫入
    for( int i = 1; i < nSize - 1; i++)
    {
        (*(USHORT*)pData) = i;
        pData += nUnitSize;
    }
}
 
void* MemoryBlock::operator new(size_t, int nUnitSize,int nUnitAmount )
{
    return ::operator new( sizeof(MemoryBlock) + nUnitSize * nUnitAmount );
}
 
void MemoryBlock::operator delete( void* pBlock)
{
    ::operator delete(pBlock);
}
 
MemoryPool::MemoryPool( int _nUnitSize, int _nGrowSize /*= 1024*/, int _nInitSzie /*= 256*/ )
{
    nInitSize = _nInitSzie;
    nGrowSize = _nGrowSize;
    pBlock = NULL;
    if(_nUnitSize > 4)
        nUnitSize = (_nUnitSize + (MEMPOOL_ALIGNMENT - 1)) & ~(MEMPOOL_ALIGNMENT - 1);
    else if( _nUnitSize < 2)
        nUnitSize = 2;
    else
        nUnitSize = 4;
}
 
MemoryPool::~MemoryPool()
{
    MemoryBlock* pMyBlock = pBlock;
    while( pMyBlock != NULL)
    {
        pMyBlock = pMyBlock->pNext;
        delete(pMyBlock);
    }
}
 
void* MemoryPool::Alloc()
{
    if( NULL == pBlock)
    {
        //首次生成MemoryBlock,new帶參數(shù)，new了一個(gè)MemoryBlock類
        pBlock = (MemoryBlock*)new(nUnitSize,nInitSize) MemoryBlock(nUnitSize,nUnitSize);
        return (void*)pBlock->aData;
    }
 
    //找到符合條件的內(nèi)存塊
    MemoryBlock* pMyBlock = pBlock;
    while( pMyBlock != NULL && 0 == pMyBlock->nFree )
        pMyBlock = pMyBlock->pNext;
 
    if( pMyBlock != NULL)
    {
        //找到了，進(jìn)行分配
        char* pFree = pMyBlock->aData + pMyBlock->nFirst * nUnitSize;
        pMyBlock->nFirst = *((USHORT*)pFree);
        pMyBlock->nFree--;
 
        return (void*)pFree;
    }
    else
    {
        //沒有找到，說明原來的內(nèi)存塊都滿了，要再次分配
 
        if( 0 == nGrowSize)
            return NULL;
         
        pMyBlock = (MemoryBlock*)new(nUnitSize,nGrowSize) MemoryBlock(nUnitSize,nGrowSize);
 
        if( NULL == pMyBlock)
            return NULL;
 
        //進(jìn)行一次插入操作
        pMyBlock->pNext = pBlock;
        pBlock = pMyBlock;
 
        return (void*)pMyBlock->aData;
    }
}
 
void MemoryPool::Free( void* pFree )
{
    //找到p所在的內(nèi)存塊
    MemoryBlock* pMyBlock = pBlock;
    MemoryBlock* PreBlock = NULL;
    while ( pMyBlock != NULL && ( pBlock->aData > pFree || pMyBlock->aData + pMyBlock->nSize))
    {
        PreBlock = pMyBlock;
        pMyBlock = pMyBlock->pNext;
    }
 
    if( NULL != pMyBlock )      //該內(nèi)存在本內(nèi)存池中pMyBlock所指向的內(nèi)存塊中
    {      
        //Step1 修改數(shù)組鏈表
        *((USHORT*)pFree) = pMyBlock->nFirst;
        pMyBlock->nFirst  = (USHORT)((ULONG)pFree - (ULONG)pMyBlock->aData) / nUnitSize;
        pMyBlock->nFree++;
 
        //Step2 判斷是否需要向OS釋放內(nèi)存
        if( pMyBlock->nSize == pMyBlock->nFree * nUnitSize )
        {
            //在鏈表中刪除該block
             
            delete(pMyBlock);
        }
        else
        {
            //將該block插入到隊(duì)首
            PreBlock = pMyBlock->pNext;
            pMyBlock->pNext = pBlock;
            pBlock = pMyBlock;
        }
    }
}

CTest.cpp

#include 
#include "MemoryPool.h"
 
class CTest
{
public:
                CTest(){data1 = data2 = 0;};
                ~CTest(){};
    void*       operator new (size_t);
    void        operator delete(void* pTest);
public:
 
    static      MemoryPool Pool;
    int         data1;
    int         data2;
};
 
void CTest::operator delete( void* pTest )
{  
    Pool.Free(pTest);  
}
 
 
void* CTest::operator new(size_t)
{
    return (CTest*)Pool.Alloc();
}
 
MemoryPool CTest::Pool(sizeof(CTest));
 
int main()
{
    CTest* pTest = new CTest;
    printf("%d",pTest->data2);
}

六、問題

在編寫代碼時(shí)，遇到了一些小問題，現(xiàn)與大家分享如下：

重載new操作符時(shí)，編譯器要求是第一個(gè)參數(shù)必須是size_t，返回值必須是void*;free的第一個(gè)參數(shù)必須是void*.

一般要在類的成員中重載new操作符，而不要重載全局的new操作符。

一個(gè)類中要是重載了一個(gè)new操作符，一定要有一個(gè)相應(yīng)類型的delete操作符，可以什么都不干，但必須有，否則在構(gòu)造函數(shù)失敗時(shí)，找不到對(duì)應(yīng)的delete函數(shù)。

例如：

static void*    operator new    (size_t,int nUnitSize,int nUnitAmount);
    static void     operator delete (void* ,int nUnitSize,int nUnitAmount){};

4. 帶參數(shù)的new操作符

pBlock = (MemoryBlock*)new(nUnitSize,nInitSize) MemoryBlock(nUnitSize,nUnitSize);

第一個(gè)nUnitSize nInitSize是new操作符的參數(shù)，該new操作符是new了一個(gè)MemoryBlock對(duì)象，在new返回的地址上構(gòu)造MemoryBlock的對(duì)象。

5. 如果在類的內(nèi)部不能進(jìn)行靜態(tài)成員的定義的話，可以只在內(nèi)部進(jìn)行聲明，在外部定義：

MemoryPool CTest::Pool(sizeof(CTest));

?

審核編輯：湯梓紅