前言

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

簡單動態內存分配實現

內存分配是將沒有使用的內存塊給需要的變量（普通變量、指針變量、結構體變量等等）使用，由于其使用后需要進行釋放，這就會導致空閑的內存是分散在內存池中的。因此，必須要對內存進行管理，也就是對內存的使用情況做標記。

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

下面來用C語言來實現這個簡單的動態內存分配。 

#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;  
} 

最終終端輸出結果如下：

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

實用的動態內存分配

細心的讀者可能已經發現上面的簡單動態內存分配有一個缺點，就是一個bit只能表示一個字節，也就是說表示8個字節就需要一個字節的位圖，這種映射導致其內存的

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

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

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