動態(tài)內(nèi)存管理的基本任務(wù)就是有效地對動態(tài)內(nèi)存進行分配,、回收，并同時保證系統(tǒng)的快速性,、可靠性和穩(wěn)定性,。當系統(tǒng)請求分配內(nèi)存時,，系統(tǒng)需要從所有空閑塊中找到一個合適的空閑塊進行分配；當用戶不再使用而將某塊內(nèi)存釋放時,，系統(tǒng)需要回收這一內(nèi)存塊,，以備在新的請求產(chǎn)生時重新進行分配。為此,，系統(tǒng)需要建立一個與內(nèi)存當前使用情況相對應(yīng)的內(nèi)存描述,，用來記錄所有與內(nèi)存分配、回收相關(guān)的信息,。而如何記錄這些信息并進行分配與回收,，便成為各種算法的最根本區(qū)別。
1 嵌入式系統(tǒng)中內(nèi)存管理技術(shù)的特點
實時系統(tǒng)分為硬實時系統(tǒng)和軟實時系統(tǒng),。硬實時系統(tǒng)是指系統(tǒng)中各任務(wù)不僅要執(zhí)行無誤而且要做到準時,；軟實時系統(tǒng)是指系統(tǒng)中各任務(wù)運行的越快越好，并不要求限定某一任務(wù)必須在多長時間內(nèi)完成,?？梢钥闯鰟討B(tài)內(nèi)存分配是絕對不能用于硬實時系統(tǒng)的，因為動態(tài)分配具有時間不確定性（分配時間與內(nèi)存塊數(shù)量有關(guān)）,，而且動態(tài)分配可能產(chǎn)生分配不成功的情況,。所以對于硬實時系統(tǒng)，只能采用靜態(tài)內(nèi)存分配方式,。靜態(tài)分配是指在編譯或鏈接時將程序所需的內(nèi)存空間分配好,，這樣不會出現(xiàn)分配失敗的情況。
1.1 靜態(tài)分配與動態(tài)分配
靜態(tài)分配為系統(tǒng)提供了最好的可靠性與實時性,。對于那些對實時性和可靠性要求極高的需求,，就只能采用靜態(tài)分配方式。但采用靜態(tài)分配就必然會使系統(tǒng)失去靈活性,。因此必須在設(shè)計階段考慮所有可能的情況,，并對所有的需求做出相應(yīng)的空間分配。一旦出現(xiàn)沒有考慮到的情況,，系統(tǒng)就無法處理,。此外靜態(tài)分配方式也必然導致很大的浪費，因為必須按照最壞情況進行最大的配置,，而在實際運行中可能只用到其中的一小部分,。
動態(tài)分配為系統(tǒng)提供了很大的靈活性，而且在內(nèi)存的利用率和系統(tǒng)功能擴展等方面也都明顯地優(yōu)于靜態(tài)分配,。
大多數(shù)系統(tǒng)采用靜態(tài)分配和動態(tài)分配相結(jié)合的方式,。由于嵌入式系統(tǒng)本身各個任務(wù)的可靠性、實時性要求不盡相同,，通常會有一部分任務(wù)對可靠性與實時性沒有特別嚴格的要求,。這些任務(wù)對一定的延時與失敗是可以接受的,。因此對于這樣的一部分任務(wù)，就可以采用動態(tài)分配方式來滿足它們部分或全部的內(nèi)存需求,。而對于那些有嚴格時限要求的任務(wù),，為了保證任務(wù)的可靠性和實時性，就應(yīng)采用靜態(tài)分配方式,。
1.2 動態(tài)分配的技術(shù)要求
?。?）快速性：由于嵌入式系統(tǒng)對實時性要求較高，所以內(nèi)存分配過程要盡可能地快,。在嵌入式系統(tǒng)中,，由于還不能采用通用操作系統(tǒng)中復(fù)雜而完善的內(nèi)存分配策略，所以一般都采用簡單,、快速的內(nèi)存分配方案,。
（2）可靠性：由于嵌入式系統(tǒng)對可靠性的要求較高,，所以內(nèi)存分配過程也要具備高可靠性,。但由于各個嵌入式系統(tǒng)之間對可靠性的要求不盡相同，對內(nèi)存分配的可靠性要求也就各不相同,。通常,，可靠性要求極高的系統(tǒng)不采用動態(tài)分配。
?。?）高效性：由于在嵌入式系統(tǒng)中內(nèi)存資源都相對有限,，所以為了保證程序的正常運行，內(nèi)存管理系統(tǒng)要盡可能高效地使用內(nèi)存,，減少不必要的浪費,。
2 伙伴系統(tǒng)
2.1 伙伴系統(tǒng)原理
伙伴（buddy）系統(tǒng)的基本原理就是按照2的冪次方大小對內(nèi)存進行分配，以此得到很高的分配速度和回收速度,。例如：對于10KB的空間請求,，伙伴系統(tǒng)會分配16KB的空間來滿足。因為內(nèi)存空閑塊大小均為2的冪次方,，所以需要16KB,這是滿足10KB的最小空間,；同樣對于70KB的空間請求,，伙伴系統(tǒng)會分配128KB的空間來滿足,。
2.2 伙伴系統(tǒng)存在的問題
伙伴系統(tǒng)比那些按大小而不按塊的整數(shù)倍地址分配的算法有更多的優(yōu)點。其優(yōu)點為當一個大小為2的K次冪的塊被釋放后,，存儲管理只需要搜索2的K次冪字節(jié)大小的塊以判定是否需要合并,。那些允許內(nèi)存塊以任意形式分割的策略需要搜索所有的空閑塊表。相比之下,，伙伴系統(tǒng)更快,。
但是對于內(nèi)存利用率來說,，伙伴系統(tǒng)是極其低效的。問題出自所有的內(nèi)存請求都必須以2的冪次方大小的空間來滿足,，一個35KB的請求需要分配64KB的空間,，其余的29KB被浪費了。在極端情況下內(nèi)存資源有近50%被浪費,。
3 連續(xù)的內(nèi)存分配
3.1 問題提出
伙伴系統(tǒng)的內(nèi)存管理方式對空間的使用存在極大的浪費,。在某些情況下還會由于資源的浪費，導致后繼的內(nèi)存請求得不到滿足,，進而嚴重地影響程序的正常功能,。
試考慮：系統(tǒng)共有1MB內(nèi)存空間可用，采用伙伴系統(tǒng)進行管理,。有如下請求：請求A,300KB;請求B,300KB;請求C,50KB.結(jié)果如表1所示,。
由表1中可以看出：伙伴系統(tǒng)對空間的浪費是極其嚴重的，即使在物理內(nèi)存充足（1MB）的情況下,，也會產(chǎn)生請求（650KB）無法滿足的情況,。
由于在嵌入式系統(tǒng)中，一般都沒有虛擬內(nèi)存的支持,，所以當內(nèi)存請求無法得到滿足時,，將嚴重影響程序的正常功能。因此為了保證程序的正常功能,，就要提高內(nèi)存的利用率,，盡可能地滿足程序的內(nèi)存請求。所以在對伙伴系統(tǒng)進行分析的基礎(chǔ)上,，提出了連續(xù)的內(nèi)存分配方式,。
3.2 連續(xù)的內(nèi)存分配原理
從上例不難看出，只要采用連續(xù)的內(nèi)存分配方式（即分配與請求大小相等的空間來滿足請求）,，便不難使請求C得到滿足,，而且還會有很大的剩余空間繼續(xù)用來滿足其他的內(nèi)存請求。結(jié)果如表2所示,。
連續(xù)的內(nèi)存分配方式明顯不同于其他以塊為單位進行分配的內(nèi)存管理方法,。它采用連續(xù)分配的方式，按照請求空間的實際大小來進行空間分配,。
3.3 連續(xù)的內(nèi)存分配實現(xiàn)方法
為了提高內(nèi)存空間的利用率,，采用按請求的實際大小來分配空間，而不是按塊的整數(shù)倍大小來分配空間,。
基本方法就是將所有獨立塊（空閑塊和使用塊）按物理地址的先后順序組織成一個雙鏈表,，每個塊中存放塊本身的一些獨立信息。分配空間時,，需要查找整個鏈表以找到最優(yōu)適配的空閑塊,，之后再將此空閑塊分裂成二塊,，一塊用來滿足請求，另一塊則作為空閑塊插入鏈表,?？臻g釋放時，只需根據(jù)鏈表便可以方便地找到與其相鄰的物理塊,，在空間合并處理完成之后再將新的塊插入鏈表,。
但事實上，由于在分配過程中只需要在空閑塊中查找最優(yōu)適配塊,，所以可以采用一個單獨的鏈表將所有的空閑塊鏈接起來,，這樣可以極大地加快空間分配時空閑塊的查找速度。
另外,，從對伙伴系統(tǒng)的分析可知,，將所有的內(nèi)存空閑區(qū)保留在一個或多個按空閑區(qū)大小排序的鏈表中將使內(nèi)存分配很快。所以借鑒伙伴系統(tǒng)的實現(xiàn)方式,，可以將單個的空閑分區(qū)鏈組織成多個鏈表間有序的空閑分區(qū)鏈,。在動態(tài)內(nèi)存操作頻繁的情況下，這將會提高系統(tǒng)內(nèi)存分配的效率,。
由于以上的方式容易產(chǎn)生許多小的不能繼續(xù)使用的空閑區(qū),，所以在進行空間分配時，如果分配所得的空閑區(qū)小于某一特定值,，則不再進行空間分配,，而是將整個空間作為請求結(jié)果返回。
綜上所述,，可以將內(nèi)存塊組織成二個雙鏈表,，即空閑塊鏈表和物理塊鏈表。
?。?）空閑塊鏈表：將所有的空閑塊按鏈表間有序的方式組織成多個獨立的空閑鏈表,。空間分配時,，根據(jù)空間的大小選擇相應(yīng)的鏈表進行查找,。若查找成功，則在空間分配處理完成之后,，將已分配空間返回給請求,；若查找失敗，則在更大空間的鏈表中繼續(xù)查找,；若直到全部鏈表查找完成仍未找到合適的空閑塊,，則認為此次分配操作失敗。
?。?）物理塊鏈表：將所有獨立塊（空閑塊和使用塊）組織成一個雙鏈表,，鏈表中各節(jié)點之間是按照物理地址的先后順序鏈接的，每個塊中存放塊本身的一些獨立信息,?？臻g釋放時，可以不需查找,，而直接根據(jù)這一鏈表找到與釋放塊相鄰的塊,。再根據(jù)相鄰塊中的相關(guān)信息就可以方便地進行內(nèi)存塊的合并操作。
具體實現(xiàn)時,，可以將這二個鏈表的控制信息與用戶空間獨立存放,，避免控制信息被意外地破壞。也可以利用物理塊本身來存放這些控制信息,，得到更好的空間利用率和更好的靈活性,。
3.4 連續(xù)的內(nèi)存分配工作方式
首先假定空間不再進行分配的最小值為1KB,即當空間分裂時所得的空閑區(qū)小于1KB時，將不再進行空間分配,。
分別保留大小為1KB,、2KB、4KB,、8KB字節(jié)等直到大于內(nèi)存總?cè)萘看笮〉逆湵?。例如對于容量? 024KB的內(nèi)存，有從1KB字節(jié)到2 048KB字節(jié)的12個鏈表,。初始時,，所有內(nèi)存都是空閑的，2 048KB的鏈表包含一個1 024KB的空閑區(qū)（每個鏈表存放所有小于鏈表本身字節(jié)數(shù),、大于等于前一鏈表的字節(jié)數(shù)的內(nèi)存塊,，2 048KB的鏈表存放所有小于2 048KB大于等于1 024KB的內(nèi)存塊）。其他的鏈表均為空,，內(nèi)存最初的情況如圖1所示,。為表示方便，圖中使用單鏈表來表示鏈接關(guān)系,。實線表示物理塊鏈表指針,，短劃線表示空閑塊鏈表指針，虛線表示空指針,。對于物理塊鏈表,，灰色塊表示已分配塊，白色塊表示空閑塊,。
當有一個300KB的內(nèi)存請求（用A表示）產(chǎn)生時,，系統(tǒng)找到512KB鏈表的表頭。因為這個鏈表中可能包含滿足請求所需的最小空間。之后按照最佳適配（best fit）算法,，在鏈表中搜尋是否有夠用的最小空閑區(qū),。此時512KB的鏈表為空，1 024KB的鏈表也為空,，所以最終在2 048KB的鏈表中找到1 024KB可用空間,。將此空間分割成大小分別為300KB和700KB的塊，700KB的塊（大于最小塊1KB）插入到1 024KB的鏈表中,，300KB的塊則返回給請求A.
接著,，又有一個300KB（用B表示）和一個50KB（用C表示）的內(nèi)存請求。結(jié)果如圖2所示,。
現(xiàn)在塊B被釋放,。此時，根據(jù)物理塊鏈表,，可以方便地找到與B鄰接的物理塊A和物理塊C.由于塊A和塊C都未被釋放,，所以不需要進行合并操作。因為塊B的大小介于256KB和512KB之間,，所以將塊B插入到512KB的空閑鏈表中,，結(jié)果如圖3所示。
接著,，塊C被釋放,。此時根據(jù)物理塊鏈表可知與塊C鄰接的為塊B和塊F,并且二塊都為空閑狀態(tài)。將塊B和塊F從512KB空閑塊鏈表中刪除,，再將三塊合并成一個700KB的塊（用F表示）插入到1 024KB的空閑鏈表中,，結(jié)果如圖4所示。
最后當塊A被釋放時,，塊A與塊F合并成1 024KB的塊,，回到最初只有1 024KB空閑區(qū)的情況。
4 結(jié) 論
動態(tài)內(nèi)存管理一直是計算機領(lǐng)域的一項重要技術(shù),。動態(tài)內(nèi)存管理給用戶提供了比較大的自由度,，用戶可以從系統(tǒng)分區(qū)中申請內(nèi)存塊，也可以從用戶內(nèi)存區(qū)申請內(nèi)存塊,。這樣增加了系統(tǒng)的靈活性,，同時也限制了大量碎片產(chǎn)生的可能（在不頻繁刪除建立系統(tǒng)內(nèi)存分區(qū)的前提下）。也增加了部分c 代碼的可移植性,。