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

而相比于個人計算機，嵌入式系統(tǒng)的內(nèi)存資源更是稀缺。作為嵌入式C的開發(fā)人員，了解其內(nèi)存管理的原理能使其更加正確地使用內(nèi)存資源以及定位程序的bug。本文將以C語言為例介紹動態(tài)內(nèi)存管理的原理。

一、動態(tài)內(nèi)存的原理

1. 棧空間與堆空間

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

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

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

在task執(zhí)行s = calculate_sum(a,b);之前，task的棧內(nèi)保存如下數(shù)據(jù)：

程序接下來執(zhí)行calculate_sum函數(shù)，其棧向下增長。在返回task之前，其棧結(jié)構(gòu)如下：

執(zhí)行完calculate_sum之后，根據(jù)返回地址返回task之后，棧恢復(fù)調(diào)用之前的結(jié)構(gòu)：

所以棧空間存儲著代碼塊內(nèi)的局部變量，動態(tài)地增減著內(nèi)部的數(shù)據(jù)。這也就是為什么當(dāng)接口調(diào)用結(jié)束后變量就不再“生存”的原因。

堆空間是由OS管理的一片區(qū)域，開發(fā)者可向OS動態(tài)申請一片區(qū)域用于操作數(shù)據(jù)。

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

堆空間由編譯器決定，如果開發(fā)者想嘗試實現(xiàn)一片動態(tài)內(nèi)存，可向堆申請一片對齊的內(nèi)存空間。

2. 內(nèi)存資源的申請與釋放

我們這里以常用的內(nèi)存操作接口——malloc與free為例，介紹操作動態(tài)內(nèi)存的細(xì)節(jié)。

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

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

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

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

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

3. 內(nèi)存泄漏

對于動態(tài)申請的內(nèi)存，使用完畢之后應(yīng)該還給堆，才能在后續(xù)繼續(xù)分配出去。

而如果申請的內(nèi)存如果沒有還回去，就造成了內(nèi)存泄漏。

參考如下一段代碼：

現(xiàn)在我們設(shè)flag=1，執(zhí)行這個函數(shù)會發(fā)生什么？

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

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

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

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

對于動態(tài)內(nèi)存的操作，需要時刻記住：當(dāng)一塊申請的內(nèi)存不再使用的時候，必須及時釋放。一個malloc操作需要對應(yīng)一個free操作。

4. 內(nèi)存對齊

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

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

二、內(nèi)存管理算法

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

1. 鏈表法

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

現(xiàn)在我們以最先匹配算法為例介紹算法的細(xì)節(jié)。最先匹配算法是從空閑鏈表的表頭出發(fā)，依次尋找空閑的內(nèi)存，一旦找到足夠大的連續(xù)區(qū)域則將其返回給用戶。

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

程序運行一段時間之后，假設(shè)堆內(nèi)的空間分布如下：

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

現(xiàn)在用戶需要申請一片大小為3k的內(nèi)存，系統(tǒng)會從free link出發(fā)，先是找到2k的空閑區(qū)，由于2k的空間不夠用，接下來再繼續(xù)尋找，找到了4k的區(qū)域，發(fā)現(xiàn)4k的區(qū)域夠大了，就會將4k的空間取走3k的空間并將其鏈入used link。

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

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

現(xiàn)在考慮這樣的一種情況：假設(shè)用戶要申請5k的內(nèi)存塊，系統(tǒng)能夠提供嗎？并不能。

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

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

2. 位圖法

使用位圖法，系統(tǒng)的內(nèi)存會被劃分成固定的內(nèi)存塊。再用變量的其中一位指示其中的一塊內(nèi)存：

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

下圖的第1，2個內(nèi)存塊和第7，8，9個內(nèi)存塊都被使用了，而相應(yīng)的位都被置1說明被占用了。

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

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

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

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