1 前言

首先要明白為何需要動態內存分配，熟悉C語言的讀者應該對這個比較熟悉，需要一段內存時會使用malloc函數來申請所需要大小的內存，函數返回一段內存的首地址。

【資料圖】

簡單來說，動態內存分配的好處在于需要內存的時候可以按需分配，當不需要內存的時候可以將其釋放掉，這樣可以高效的利用內存。下面本文從零開始實現一個完整的動態內存分配。

2 簡單動態內存分配實現

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

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

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

最終終端輸出結果如下：

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

3 實用的動態內存分配

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

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

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

雖然利用率變高了，但是其會產生內部碎片，所謂內部碎片就是在最小粒度內無法使用的內存空間，為何這個空間無法使用了，原因在于當在申請內存塊的時候，其內存只能以64B對齊的，即使小于64B，也得按64B來看作，因為這個粒度已經被bitmap標記使用了，當下次使用時，其無法被分配。

因此，可以看到，粒度越大，其可能產生的內部內存碎片越大，內存利用率和碎片是需要權衡了，好的算法只能解決外部碎片問題，無法解決內部碎片問題，因此在實現動態內存分配時必須權衡考慮，以達到最優結果。

審核編輯：湯梓紅