C 語言動態內存分配
前言
首先要明白爲何需要動態內存分配，熟悉 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;
index=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 標記使用了，當下次使用時，其無法被分配。因此，可以看到，粒度越大，其可能產生的內部內存碎片越大，內存利用率和碎片是需要權衡了，好的算法只能解決外部碎片問題，無法解決內部碎片問題，因此在實現動態內存分配時必須權衡考慮，以達到最優結果。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/I6fpSn1YNJr9lgWaYW71OQ