前言

首先要明白為何需要動態(tài)內(nèi)存分配，熟悉C語言的讀者應(yīng)該對這個比較熟悉，需要一段內(nèi)存時會使用malloc函數(shù)來申請所需要大小的內(nèi)存，函數(shù)返回一段內(nèi)存的首地址。簡單來說，動態(tài)內(nèi)存分配的好處在于需要內(nèi)存的時候可以按需分配，當(dāng)不需要內(nèi)存的時候可以將其釋放掉，這樣可以高效的利用內(nèi)存。下面本文從零開始實現(xiàn)一個完整的動態(tài)內(nèi)存分配。

簡單動態(tài)內(nèi)存分配實現(xiàn)

內(nèi)存分配是將沒有使用的內(nèi)存塊給需要的變量（普通變量、指針變量、結(jié)構(gòu)體變量等等）使用，由于其使用后需要進(jìn)行釋放，這就會導(dǎo)致空閑的內(nèi)存是分散在內(nèi)存池中的。因此，必須要對內(nèi)存進(jìn)行管理，也就是對內(nèi)存的使用情況做標(biāo)記。

上圖是一個內(nèi)存池使用后的某一時刻，可以看到，使用的塊和沒有使用的塊并不是連續(xù)的，這樣就需要用一個表對其進(jìn)行標(biāo)記，這個表稱為BitMap。假設(shè)現(xiàn)在將內(nèi)存按照每個Byte進(jìn)行劃分，然后用一個bit對塊進(jìn)行標(biāo)記，1表示已使用，0表示沒有使用，這樣一個塊需要一個bit。

下面來用C語言來實現(xiàn)這個簡單的動態(tài)內(nèi)存分配。 

#include <stdio.h>  
#define MEM_POOL_SIZE  64  
unsigned char MemPool[MEM_POOL_SIZE];  
unsigned char BitMap[MEM_POOL_SIZE/8]={0};  
//BitMap[0] MSB->LSB  MemPool[0 ~ 8]  
//BitMap[1] MSB->LSB  MemPool[9 ~15]  
//BitMap[2] MSB->LSB  MemPool[16~23]  
// ...  
void InitMemAlloc(void)  
{  
    int i=MEM_POOL_SIZE;  
    while(i--)  
    {  
        MemPool[i]=0;  
    }  
    i=MEM_POOL_SIZE/8;  
    while(i--)  
    {  
        BitMap[i]=0;  
    }  
}  
void *MemAlloc(unsigned int m_size)  
{  
    unsigned int i=0,j=0,k=0,index=0,count=0,mapv=0,cache;  
    if(m_size>MEM_POOL_SIZE)  
    {  
        return NULL;  
    }  
    else  
    {  
        for(;i<MEM_POOL_SIZE/8;i++)  
        {  
            mapv=BitMap[i];   //取出高位  
            for(j=0;j<8;j++)  
            {  
                cache=(mapv&0x80);  
                if(cache==0)  
                {  
                    count++;  
                    if(count==m_size) 
                    {  
                        for(;k<m_size;k++)  
                        {  
                            BitMap[(index+k)/8]|=(1<<(7-((index+k)%8)));  
                        }  
                        return &MemPool[index];  
                    }  
                }  
                else  
                {  
                    count=0;  
                    iindex=i*8+j+1;  
                }  
                mapv<<=1;  
            }  
        }  
        return NULL;  
    }  
}   
void MemFree(void *p,unsigned int m_size)  
{  
    unsigned int k=0,index=(((unsigned int)p)-(unsigned int)MemPool);  
    for(;k<m_size;k++)  
    {  
        BitMap[(index+k)/8]&=~(1<<(7-((index+k)%8)));  
    }  
}  
void MemPrintBitMap(void)  
{  
    unsigned int i,j,value;   
     for(i=0;i<MEM_POOL_SIZE/8;i++)  
    {  
        value=BitMap[i];  
        for(j=0;j<8;j++)  
        {  
            if(value&0x80)  
                printf("1 ");  
            else  
                printf("0 ");  
            value<<=1;  
        }  
        printf("\n");  
    }  
}  
double MemGetUsedPercent(void)  
{  
    unsigned int i,j,value;  
    double ret=0.0;  
    for(i=0;i<MEM_POOL_SIZE/8;i++)  
    {  
        value=BitMap[i];  
        for(j=0;j<8;j++)  
        {  
            if(value&0x80)  
                ret++;  
            value<<=1;  
        }  
    }  
    return (ret*100)/MEM_POOL_SIZE; 
}  
int main(int argc, char **argv)  
{  
    int *p=MemAlloc(10);  
    printf("The pool is used=%f\n",MemGetUsedPercent());  
    MemPrintBitMap();  
    int *q=MemAlloc(5);  
    printf("The pool is used=%f\n",MemGetUsedPercent());  
    MemPrintBitMap(); 
    MemFree(p,5);  
    printf("The pool is used=%f\n",MemGetUsedPercent());  
    MemPrintBitMap();  
    return 0;  
} 

最終終端輸出結(jié)果如下：

上面已經(jīng)實現(xiàn)了一個簡單的動態(tài)內(nèi)存分配，可以完成內(nèi)存的分配和釋放以及輸出使用率和查看位圖。這種方式實現(xiàn)的動態(tài)內(nèi)存分配不會產(chǎn)生內(nèi)部碎片，這也是其優(yōu)勢所在，但其缺點很明顯就是利用率太低。

實用的動態(tài)內(nèi)存分配

細(xì)心的讀者可能已經(jīng)發(fā)現(xiàn)上面的簡單動態(tài)內(nèi)存分配有一個缺點，就是一個bit只能表示一個字節(jié)，也就是說表示8個字節(jié)就需要一個字節(jié)的位圖，這種映射導(dǎo)致其內(nèi)存的

這對于很多情況是比較浪費的。為了提高利用率，就必須將映射塊的粒度增大，也就是一個Bit的映射范圍對應(yīng)多個字節(jié)。

上圖給出了一個bit映射到64Byte，這樣：

雖然利用率變高了，但是其會產(chǎn)生內(nèi)部碎片，所謂內(nèi)部碎片就是在最小粒度內(nèi)無法使用的內(nèi)存空間，為何這個空間無法使用了，原因在于當(dāng)在申請內(nèi)存塊的時候，其內(nèi)存只能以64B對齊的，即使小于64B，也得按64B來看作，因為這個粒度已經(jīng)被bitmap標(biāo)記使用了，當(dāng)下次使用時，其無法被分配。因此，可以看到，粒度越大，其可能產(chǎn)生的內(nèi)部內(nèi)存碎片越大，內(nèi)存利用率和碎片是需要權(quán)衡了，好的算法只能解決外部碎片問題，無法解決內(nèi)部碎片問題，因此在實現(xiàn)動態(tài)內(nèi)存分配時必須權(quán)衡考慮，以達(dá)到最優(yōu)結(jié)果。