很多工程師都知道，C/C++語言與其他語言不同，它需要開發者自己管理內存資源，動態內存使用不當，容易造成段錯誤或者內存泄漏，因此內存管理至關重要。本文將以C語言為例介紹動態內存管理的原理。

C/C++語言與其他語言不同，它需要開發者自己管理內存資源。對于動態內存的使用不當容易造成段錯誤或者內存泄漏。尤其是內存泄漏，內存泄漏往往是在程序運行一段時間才會被發現，使得開發人員無法第一時間定位錯誤。

而相比于個人計算機，嵌入式系統的內存資源更是稀缺。作為嵌入式C的開發人員，了解其內存管理的原理能使其更加正確地使用內存資源以及定位程序的bug。

動態內存的原理

1、棧空間與堆空間

在介紹內存管理之前，我們先解釋一下棧空間與堆空間：棧空間是由編譯器自動分配釋放，對于AWorks等操作系統，在用戶創建一個任務的時候可以由自己決定任務棧空間的大小。

棧空間里面一般存放著如下數據：在函數內的局部變量（不包括static定義的變量），在調用另一個函數時保存的通用寄存器信息等。

參考如下例程（為了便于理解，省略通用寄存器等信息）：

在task執行s = calculate_sum(a,b)；之前，task的棧內保存如下數據：

程序接下來執行calculate_sum函數，其棧向下增長。在返回task之前，其棧結構如下：

執行完calculate_sum之后，根據返回地址返回task之后，棧恢復調用之前的結構：

所以棧空間存儲著代碼塊內的局部變量，動態地增減著內部的數據。這也就是為什么當接口調用結束后變量就不再“生存”的原因。

堆空間是由OS管理的一片區域，開發者可向OS動態申請一片區域用于操作數據。

堆空間在程序運行時一直有效，相當于定義了一個大型的全局數組。需要時向堆空間申請內存，使用完畢再還回去。這樣可以使得開發者能夠動態地控制空間的大小，而不需要在寫代碼的時候就考慮最糟的情況（定義一個數組必須在編譯之前就確定其大小，使用過程中無法增加或減少，所以必須考慮最多需要的數據大小）。

堆空間由編譯器決定，如果開發者想嘗試實現一片動態內存，可向堆申請一片對齊的內存空間。

2、內存資源的申請與釋放

我們這里以常用的內存操作接口——malloc與free為例，介紹操作動態內存的細節。

void* malloc(size)——申請一片大小為size字節的內存。

參考下圖，灰色部分是已經被使用的內存，空白部分則是可以被申請使用的內存。在申請內存的時候，系統會首先判斷有沒有足夠大的未被使用的區域，如果有，則將其分配給申請者，再將此區域標記為“已使用”；否則分配失敗。

（為方便讀圖，從這里開始我們假定內存的地址從上往下增長）

void free(void *)——釋放已申請的內存。與malloc相反，free的作用是把“已使用”的區域標記為“未使用”，那么釋放的內存下一次就可以再分配出去復用。free釋放的內存必須是malloc申請的內存。

由于需要對內存進行狀態標記和位置記錄（以便釋放）。在申請/釋放內存的時候需要額外的空間進行信息的記錄。有的系統會將記錄的信息集中管理，有的則是申請內存的時候額外地多申請一小片區域用于記錄。

3、內存泄漏

對于動態申請的內存，使用完畢之后應該還給堆，才能在后續繼續分配出去。而如果申請的內存如果沒有還回去，就造成了內存泄漏。參考如下一段代碼：

現在我們設flag=1，執行這個函數會發生什么？

首先ptr會指向申請的128字節的內存（圖b）,然后判斷flag==1之后再申請256字節的內存（圖c）。假設我們現在使用完畢將ptr釋放：

現在我們釋放了256字節的內存塊了，但是我們開始的時候還申請過128字節的內存塊，這128字節的內存塊最終會怎樣呢？由當時唯一指向這塊內存的指針ptr后面指向了256字節的內存塊，現在沒有任何指針指向這塊內存，因此這一塊內存再也無法被釋放，這時候我們就說內存泄漏了。

在程序最開始運行的一段時間內，系統是沒有異常的。即使一小片內存不被釋放也不會造成錯誤，因為內存堆還有足夠的空間可以使用。但是如果運行的時間足夠長，多次調用這個函數（參數flag==1）之后，堆空間會逐漸被泄漏的內存塊占滿，直到程序無法再從堆里申請到內存，程序才會報錯。

內存泄漏令開發者頭痛的地方也正是這個原因，內存泄漏的問題往往無法在第一時間被發現！而對于不熟悉內存管理的開發者更是難以定位錯誤。

對于動態內存的操作，需要時刻記住：當一塊申請的內存不再使用的時候，必須及時釋放。一個malloc操作需要對應一個free操作。

4、內存對齊

在很多的場合下，分配的內存不僅要滿足申請的大小，也需要進行對齊才能夠使分配的空間能夠被轉換成除char之外其他的結構類型。系統對內存的分配一般會以int型變量的字節數進行對齊。AWorks提供的aw_mem_align接口可以使用戶獲取自定義對齊的內存空間。

類型對齊相關的知識請讀者自行查找相關資料，這里不再展開細講。

內存管理算法

接下來我們學習一下怎么去對堆空間的內存進行管理。這里我們主要介紹嵌入式中兩種常用的內存管理算法。

1、鏈表法

鏈表法維護著兩個鏈表，兩個鏈表分別記錄著已分配的使用內存段和未分配的空閑內存段。當申請一片內存的時候，從空閑內存段中找到合適的塊分配給用戶，同時鏈入使用內存段。而釋放的時候則從已使用的內存段找到相應的表，然后釋放到空閑內存段中以供下次分配。

現在我們以最先匹配算法為例介紹算法的細節。最先匹配算法是從空閑鏈表的表頭出發，依次尋找空閑的內存，一旦找到足夠大的連續區域則將其返回給用戶。

還記得前面說的，管理內存區域需要額外的記錄信息，鏈表法一般是在操作內存空間的時候申請額外的空間記錄相應的信息。我們假定下圖紅色部分記錄著使用的內存區，青色記錄空閑的內存區，這里使用free link鏈表維護空閑內存段，used link維護使用的內存段：

程序運行一段時間之后，假設堆內的空間分布如下：

空閑區和使用區的信息都被兩個表維護著。

現在用戶需要申請一片大小為3k的內存，系統會從free link出發，先是找到2k的空閑區，由于2k的空間不夠用，接下來再繼續尋找，找到了4k的區域，發現4k的區域夠大了，就會將4k的空間取走3k的空間并將其鏈入used link。

盡管后面3k的空間更加適合分配，但是最先匹配算法一旦找到足夠大的空間便不會繼續往下尋找。

當用戶用完資源的時候，把申請的3k還回去，系統會從used link找到申請的內存，將鏈入free link以供下次分配，然后將空閑相鄰的內存塊合并成完整的一塊：

現在考慮這樣的一種情況：假設用戶要申請5k的內存塊，系統能夠提供嗎？并不能。

雖然空閑的內存塊一共有9k（2k+4k+3k），但是9k的內存并不連續，因此無法分配給用戶。這就是外部內存碎片——雖然整個空間的空閑內存足夠大，但卻因為零碎的內存塊割裂了連續內存而無法分配出去。

其他的鏈表法還有最佳匹配算法，下次匹配算法等.有興趣的讀者可以自行查找相關資料。

2、位圖法

使用位圖法，系統的內存會被劃分成固定的內存塊。再用變量的其中一位指示其中的一塊內存：

圖中的一個方格代表一塊固定大小的內存塊，這里假定1k。用一個16位的變量指代16k的內存段。如果一個塊是空閑的，則用0表示，如果是被使用的，則用1表示。

下圖的第1，2個內存塊和第7，8，9個內存塊都被使用了，而相應的位都被置1說明被占用了。

相比鏈表法，位圖法采用更少的額外空間記錄內存堆的信息，而且由于申請與釋放都是整塊的，會產生更少的外部碎片。

但是假如用戶只申請幾個字節的內存，但是卻分配了1k的內存塊，則大量的空間不會被使用，這樣導致的無法使用的內存我們稱為內部內存碎片。

減少內部內存碎片的其中一個方法是合理地選擇內存塊的大小，固定尺寸較小的內存塊導致的內存碎片會更小——當用戶申請幾字節的內存，比起固定1k的內存塊，固定16字節的內存塊產生更少的碎片。但是固定尺寸變小了也會導致需要更多的位記錄內存的信息。

現在有很多優秀的位圖算法——將內存分成不同的固定大小獲取更快的分配速度和更少的內存碎片，有興趣的讀者可自行查找相關資料。