動態內存管理的基本任務就是有效地對動態內存進行分配、回收，并同時保證系統的快速性、可靠性和穩定性。當系統請求分配內存時，系統需要從所有空閑塊中找到一個合適的空閑塊進行分配；當用戶不再使用而將某塊內存釋放時，系統需要回收這一內存塊，以備在新的請求產生時重新進行分配。為此，系統需要建立一個與內存當前使用情況相對應的內存描述，用來記錄所有與內存分配、回收相關的信息。而如何記錄這些信息并進行分配與回收，便成為各種算法的最根本區別。

　　1 嵌入式系統中內存管理技術的特點

實時系統分為硬實時系統和軟實時系統。硬實時系統是指系統中各任務不僅要執行無誤而且要做到準時；軟實時系統是指系統中各任務運行的越快越好，并不要求限定某一任務必須在多長時間內完成。可以看出動態內存分配是絕對不能用于硬實時系統的，因為動態分配具有時間不確定性（分配時間與內存塊數量有關），而且動態分配可能產生分配不成功的情況。所以對于硬實時系統，只能采用靜態內存分配方式。靜態分配是指在編譯或鏈接時將程序所需的內存空間分配好，這樣不會出現分配失敗的情況。

1.1 靜態分配與動態分配

靜態分配為系統提供了最好的可靠性與實時性。對于那些對實時性和可靠性要求極高的需求，就只能采用靜態分配方式。但采用靜態分配就必然會使系統失去靈活性。因此必須在設計階段考慮所有可能的情況，并對所有的需求做出相應的空間分配。一旦出現沒有考慮到的情況，系統就無法處理。此外靜態分配方式也必然導致很大的浪費，因為必須按照最壞情況進行最大的配置，而在實際運行中可能只用到其中的一小部分。

動態分配為系統提供了很大的靈活性，而且在內存的利用率和系統功能擴展等方面也都明顯地優于靜態分配。
大多數系統采用靜態分配和動態分配相結合的方式。由于嵌入式系統本身各個任務的可靠性、實時性要求不盡相同，通常會有一部分任務對可靠性與實時性沒有特別嚴格的要求。這些任務對一定的延時與失敗是可以接受的。因此對于這樣的一部分任務，就可以采用動態分配方式來滿足它們部分或全部的內存需求。而對于那些有嚴格時限要求的任務，為了保證任務的可靠性和實時性，就應采用靜態分配方式。

1.2 動態分配的技術要求

（1）快速性：由于嵌入式系統對實時性要求較高，所以內存分配過程要盡可能地快。在嵌入式系統中，由于還不能采用通用操作系統中復雜而完善的內存分配策略，所以一般都采用簡單、快速的內存分配方案。

（2）可靠性：由于嵌入式系統對可靠性的要求較高，所以內存分配過程也要具備高可靠性。但由于各個嵌入式系統之間對可靠性的要求不盡相同，對內存分配的可靠性要求也就各不相同。通常，可靠性要求極高的系統不采用動態分配。

（3）高效性：由于在嵌入式系統中內存資源都相對有限，所以為了保證程序的正常運行，內存管理系統要盡可能高效地使用內存，減少不必要的浪費。

　　2 伙伴系統

2.1 伙伴系統原理

伙伴（buddy）系統的基本原理就是按照2的冪次方大小對內存進行分配，以此得到很高的分配速度和回收速度。例如：對于10KB的空間請求，伙伴系統會分配16KB的空間來滿足。因為內存空閑塊大小均為2的冪次方，所以需要16KB,這是滿足10KB的最小空間；同樣對于70KB的空間請求，伙伴系統會分配128KB的空間來滿足。

2.2 伙伴系統存在的問題

伙伴系統比那些按大小而不按塊的整數倍地址分配的算法有更多的優點。其優點為當一個大小為2的K次冪的塊被釋放后，存儲管理只需要搜索2的K次冪字節大小的塊以判定是否需要合并。那些允許內存塊以任意形式分割的策略需要搜索所有的空閑塊表。相比之下，伙伴系統更快。

但是對于內存利用率來說，伙伴系統是極其低效的。問題出自所有的內存請求都必須以2的冪次方大小的空間來滿足，一個35KB的請求需要分配64KB的空間，其余的29KB被浪費了。在極端情況下內存資源有近50%被浪費。

　　3 連續的內存分配

3.1 問題提出

伙伴系統的內存管理方式對空間的使用存在極大的浪費。在某些情況下還會由于資源的浪費，導致后繼的內存請求得不到滿足，進而嚴重地影響程序的正常功能。

試考慮：系統共有1MB內存空間可用，采用伙伴系統進行管理。有如下請求：請求A,300KB;請求B,300KB;請求C,50KB.結果如表1所示。

由表1中可以看出：伙伴系統對空間的浪費是極其嚴重的，即使在物理內存充足（1MB）的情況下，也會產生請求（650KB）無法滿足的情況。

由于在嵌入式系統中，一般都沒有虛擬內存的支持，所以當內存請求無法得到滿足時，將嚴重影響程序的正常功能。因此為了保證程序的正常功能，就要提高內存的利用率，盡可能地滿足程序的內存請求。所以在對伙伴系統進行分析的基礎上，提出了連續的內存分配方式。

      3.2 連續的內存分配原理

從上例不難看出，只要采用連續的內存分配方式（即分配與請求大小相等的空間來滿足請求），便不難使請求C得到滿足，而且還會有很大的剩余空間繼續用來滿足其他的內存請求。結果如表2所示。

連續的內存分配方式明顯不同于其他以塊為單位進行分配的內存管理方法。它采用連續分配的方式，按照請求空間的實際大小來進行空間分配。

      3.3 連續的內存分配實現方法

為了提高內存空間的利用率，采用按請求的實際大小來分配空間，而不是按塊的整數倍大小來分配空間。

基本方法就是將所有獨立塊（空閑塊和使用塊）按物理地址的先后順序組織成一個雙鏈表，每個塊中存放塊本身的一些獨立信息。分配空間時，需要查找整個鏈表以找到最優適配的空閑塊，之后再將此空閑塊分裂成二塊，一塊用來滿足請求，另一塊則作為空閑塊插入鏈表。空間釋放時，只需根據鏈表便可以方便地找到與其相鄰的物理塊，在空間合并處理完成之后再將新的塊插入鏈表。

但事實上，由于在分配過程中只需要在空閑塊中查找最優適配塊，所以可以采用一個單獨的鏈表將所有的空閑塊鏈接起來，這樣可以極大地加快空間分配時空閑塊的查找速度。

另外，從對伙伴系統的分析可知，將所有的內存空閑區保留在一個或多個按空閑區大小排序的鏈表中將使內存分配很快。所以借鑒伙伴系統的實現方式，可以將單個的空閑分區鏈組織成多個鏈表間有序的空閑分區鏈。在動態內存操作頻繁的情況下，這將會提高系統內存分配的效率。

由于以上的方式容易產生許多小的不能繼續使用的空閑區，所以在進行空間分配時，如果分配所得的空閑區小于某一特定值，則不再進行空間分配，而是將整個空間作為請求結果返回。

綜上所述，可以將內存塊組織成二個雙鏈表，即空閑塊鏈表和物理塊鏈表。

（1）空閑塊鏈表：將所有的空閑塊按鏈表間有序的方式組織成多個獨立的空閑鏈表。空間分配時，根據空間的大小選擇相應的鏈表進行查找。若查找成功，則在空間分配處理完成之后，將已分配空間返回給請求；若查找失敗，則在更大空間的鏈表中繼續查找；若直到全部鏈表查找完成仍未找到合適的空閑塊，則認為此次分配操作失敗。

（2）物理塊鏈表：將所有獨立塊（空閑塊和使用塊）組織成一個雙鏈表，鏈表中各節點之間是按照物理地址的先后順序鏈接的，每個塊中存放塊本身的一些獨立信息。空間釋放時，可以不需查找，而直接根據這一鏈表找到與釋放塊相鄰的塊。再根據相鄰塊中的相關信息就可以方便地進行內存塊的合并操作。

具體實現時，可以將這二個鏈表的控制信息與用戶空間獨立存放，避免控制信息被意外地破壞。也可以利用物理塊本身來存放這些控制信息，得到更好的空間利用率和更好的靈活性。

3.4 連續的內存分配工作方式

首先假定空間不再進行分配的最小值為1KB,即當空間分裂時所得的空閑區小于1KB時，將不再進行空間分配。
分別保留大小為1KB、2KB、4KB、8KB字節等直到大于內存總容量大小的鏈表。例如對于容量為1 024KB的內存，有從1KB字節到2 048KB字節的12個鏈表。初始時，所有內存都是空閑的，2 048KB的鏈表包含一個1 024KB的空閑區（每個鏈表存放所有小于鏈表本身字節數、大于等于前一鏈表的字節數的內存塊，2 048KB的鏈表存放所有小于2 048KB大于等于1 024KB的內存塊）。其他的鏈表均為空，內存最初的情況如圖1所示。為表示方便，圖中使用單鏈表來表示鏈接關系。實線表示物理塊鏈表指針，短劃線表示空閑塊鏈表指針，虛線表示空指針。對于物理塊鏈表，灰色塊表示已分配塊，白色塊表示空閑塊。

當有一個300KB的內存請求（用A表示）產生時，系統找到512KB鏈表的表頭。因為這個鏈表中可能包含滿足請求所需的最小空間。之后按照最佳適配（best fit）算法，在鏈表中搜尋是否有夠用的最小空閑區。此時512KB的鏈表為空，1 024KB的鏈表也為空，所以最終在2 048KB的鏈表中找到1 024KB可用空間。將此空間分割成大小分別為300KB和700KB的塊，700KB的塊（大于最小塊1KB）插入到1 024KB的鏈表中，300KB的塊則返回給請求A.
接著，又有一個300KB（用B表示）和一個50KB（用C表示）的內存請求。結果如圖2所示。

現在塊B被釋放。此時，根據物理塊鏈表，可以方便地找到與B鄰接的物理塊A和物理塊C.由于塊A和塊C都未被釋放，所以不需要進行合并操作。因為塊B的大小介于256KB和512KB之間，所以將塊B插入到512KB的空閑鏈表中，結果如圖3所示。

接著，塊C被釋放。此時根據物理塊鏈表可知與塊C鄰接的為塊B和塊F,并且二塊都為空閑狀態。將塊B和塊F從512KB空閑塊鏈表中刪除，再將三塊合并成一個700KB的塊（用F表示）插入到1 024KB的空閑鏈表中，結果如圖4所示。

最后當塊A被釋放時，塊A與塊F合并成1 024KB的塊，回到最初只有1 024KB空閑區的情況。

　　4 結 論

動態內存管理一直是計算機領域的一項重要技術。動態內存管理給用戶提供了比較大的自由度，用戶可以從系統分區中申請內存塊，也可以從用戶內存區申請內存塊。這樣增加了系統的靈活性，同時也限制了大量碎片產生的可能（在不頻繁刪除建立系統內存分區的前提下）。也增加了部分c 代碼的可移植性。