1 前言

首先要明白為何需要?jiǎng)討B(tài)內(nèi)存分配，熟悉C語(yǔ)言的讀者應(yīng)該對(duì)這個(gè)比較熟悉，需要一段內(nèi)存時(shí)會(huì)使用malloc函數(shù)來(lái)申請(qǐng)所需要大小的內(nèi)存，函數(shù)返回一段內(nèi)存的首地址。

簡(jiǎn)單來(lái)說(shuō)，動(dòng)態(tài)內(nèi)存分配的好處在于需要內(nèi)存的時(shí)候可以按需分配，當(dāng)不需要內(nèi)存的時(shí)候可以將其釋放掉，這樣可以高效的利用內(nèi)存。下面本文從零開(kāi)始實(shí)現(xiàn)一個(gè)完整的動(dòng)態(tài)內(nèi)存分配。

2 簡(jiǎn)單動(dòng)態(tài)內(nèi)存分配實(shí)現(xiàn)

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

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

下面來(lái)用C語(yǔ)言來(lái)實(shí)現(xiàn)這個(gè)簡(jiǎn)單的動(dòng)態(tài)內(nèi)存分配。

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

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

3 實(shí)用的動(dòng)態(tài)內(nèi)存分配

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

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

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

雖然利用率變高了，但是其會(huì)產(chǎn)生內(nèi)部碎片，所謂內(nèi)部碎片就是在最小粒度內(nèi)無(wú)法使用的內(nèi)存空間，為何這個(gè)空間無(wú)法使用了，原因在于當(dāng)在申請(qǐng)內(nèi)存塊的時(shí)候，其內(nèi)存只能以64B對(duì)齊的，即使小于64B，也得按64B來(lái)看作，因?yàn)檫@個(gè)粒度已經(jīng)被bitmap標(biāo)記使用了，當(dāng)下次使用時(shí)，其無(wú)法被分配。

因此，可以看到，粒度越大，其可能產(chǎn)生的內(nèi)部?jī)?nèi)存碎片越大，內(nèi)存利用率和碎片是需要權(quán)衡了，好的算法只能解決外部碎片問(wèn)題，無(wú)法解決內(nèi)部碎片問(wèn)題，因此在實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存分配時(shí)必須權(quán)衡考慮，以達(dá)到最優(yōu)結(jié)果。

　　審核編輯：湯梓紅