1 前言

首先要明白為何需要動態(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)存分配。

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

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

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

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

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

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

3 實用的動態(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é)果。

　　審核編輯：湯梓紅