進(jìn)入20世紀(jì)90年代，嵌入式技術(shù)全面展開(kāi)，目前已成為通信和消費(fèi)類(lèi)產(chǎn)品的共同發(fā)展方向。在通信領(lǐng)域，數(shù)字技術(shù)正在全面取代模擬技術(shù)。在廣播電視領(lǐng)域，美國(guó)已開(kāi)始由模擬電視向數(shù)字電視轉(zhuǎn)變，歐洲的DVB（數(shù)字電視廣播）技術(shù)已在全球大多數(shù)國(guó)家推廣。數(shù)字音頻廣播（DAB）也已進(jìn)入商品化試播階段。而軟件、集成電路和新型元器件在產(chǎn)業(yè)發(fā)展中的作用日益重要。

動(dòng)態(tài)內(nèi)存管理的基本任務(wù)就是有效地對(duì)動(dòng)態(tài)內(nèi)存進(jìn)行分配、回收，并同時(shí)保證系統(tǒng)的快速性、可靠性和穩(wěn)定性。當(dāng)系統(tǒng)請(qǐng)求分配內(nèi)存時(shí)，系統(tǒng)需要從所有空閑塊中找到一個(gè)合適的空閑塊進(jìn)行分配；當(dāng)用戶(hù)不再使用而將某塊內(nèi)存釋放時(shí)，系統(tǒng)需要回收這一內(nèi)存塊，以備在新的請(qǐng)求產(chǎn)生時(shí)重新進(jìn)行分配。為此，系統(tǒng)需要建立一個(gè)與內(nèi)存當(dāng)前使用情況相對(duì)應(yīng)的內(nèi)存描述，用來(lái)記錄所有與內(nèi)存分配、回收相關(guān)的信息。而如何記錄這些信息并進(jìn)行分配與回收，便成為各種算法的最根本區(qū)別。

1 嵌入式系統(tǒng)中內(nèi)存管理技術(shù)的特點(diǎn)

實(shí)時(shí)系統(tǒng)分為硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)。硬實(shí)時(shí)系統(tǒng)是指系統(tǒng)中各任務(wù)不僅要執(zhí)行無(wú)誤而且要做到準(zhǔn)時(shí)；軟實(shí)時(shí)系統(tǒng)是指系統(tǒng)中各任務(wù)運(yùn)行的越快越好，并不要求限定某一任務(wù)必須在多長(zhǎng)時(shí)間內(nèi)完成?？梢钥闯鰟?dòng)態(tài)內(nèi)存分配是絕對(duì)不能用于硬實(shí)時(shí)系統(tǒng)的，因?yàn)閯?dòng)態(tài)分配具有時(shí)間不確定性（分配時(shí)間與內(nèi)存塊數(shù)量有關(guān)），而且動(dòng)態(tài)分配可能產(chǎn)生分配不成功的情況。所以對(duì)于硬實(shí)時(shí)系統(tǒng)，只能采用靜態(tài)內(nèi)存分配方式。靜態(tài)分配是指在編譯或鏈接時(shí)將程序所需的內(nèi)存空間分配好，這樣不會(huì)出現(xiàn)分配失敗的情況。

1.1 靜態(tài)分配與動(dòng)態(tài)分配

靜態(tài)分配為系統(tǒng)提供了最好的可靠性與實(shí)時(shí)性。對(duì)于那些對(duì)實(shí)時(shí)性和可靠性要求極高的需求，就只能采用靜態(tài)分配方式。但采用靜態(tài)分配就必然會(huì)使系統(tǒng)失去靈活性。因此必須在設(shè)計(jì)階段考慮所有可能的情況，并對(duì)所有的需求做出相應(yīng)的空間分配。一旦出現(xiàn)沒(méi)有考慮到的情況，系統(tǒng)就無(wú)法處理。此外靜態(tài)分配方式也必然導(dǎo)致很大的浪費(fèi)，因?yàn)楸仨毎凑兆顗那闆r進(jìn)行最大的配置，而在實(shí)際運(yùn)行中可能只用到其中的一小部分。

動(dòng)態(tài)分配為系統(tǒng)提供了很大的靈活性，而且在內(nèi)存的利用率和系統(tǒng)功能擴(kuò)展等方面也都明顯地優(yōu)于靜態(tài)分配。

大多數(shù)系統(tǒng)采用靜態(tài)分配和動(dòng)態(tài)分配相結(jié)合的方式。由于嵌入式系統(tǒng)本身各個(gè)任務(wù)的可靠性、實(shí)時(shí)性要求不盡相同，通常會(huì)有一部分任務(wù)對(duì)可靠性與實(shí)時(shí)性沒(méi)有特別嚴(yán)格的要求。這些任務(wù)對(duì)一定的延時(shí)與失敗是可以接受的。因此對(duì)于這樣的一部分任務(wù)，就可以采用動(dòng)態(tài)分配方式來(lái)滿(mǎn)足它們部分或全部的內(nèi)存需求。而對(duì)于那些有嚴(yán)格時(shí)限要求的任務(wù)，為了保證任務(wù)的可靠性和實(shí)時(shí)性，就應(yīng)采用靜態(tài)分配方式。

1.2 動(dòng)態(tài)分配的技術(shù)要求

（1）快速性：由于嵌入式系統(tǒng)對(duì)實(shí)時(shí)性要求較高，所以?xún)?nèi)存分配過(guò)程要盡可能地快。在嵌入式系統(tǒng)中，由于還不能采用通用操作系統(tǒng)中復(fù)雜而完善的內(nèi)存分配策略，所以一般都采用簡(jiǎn)單、快速的內(nèi)存分配方案。

（2）可靠性：由于嵌入式系統(tǒng)對(duì)可靠性的要求較高，所以?xún)?nèi)存分配過(guò)程也要具備高可靠性。但由于各個(gè)嵌入式系統(tǒng)之間對(duì)可靠性的要求不盡相同，對(duì)內(nèi)存分配的可靠性要求也就各不相同。通常，可靠性要求極高的系統(tǒng)不采用動(dòng)態(tài)分配。

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

2 伙伴系統(tǒng)

2.1 伙伴系統(tǒng)原理

伙伴（buddy）系統(tǒng)的基本原理就是按照2的冪次方大小對(duì)內(nèi)存進(jìn)行分配，以此得到很高的分配速度和回收速度。例如：對(duì)于10KB的空間請(qǐng)求，伙伴系統(tǒng)會(huì)分配16KB的空間來(lái)滿(mǎn)足。因?yàn)閮?nèi)存空閑塊大小均為2的冪次方，所以需要16KB,這是滿(mǎn)足10KB的最小空間；同樣對(duì)于70KB的空間請(qǐng)求，伙伴系統(tǒng)會(huì)分配128KB的空間來(lái)滿(mǎn)足。

2.2 伙伴系統(tǒng)存在的問(wèn)題

伙伴系統(tǒng)比那些按大小而不按塊的整數(shù)倍地址分配的算法有更多的優(yōu)點(diǎn)。其優(yōu)點(diǎn)為當(dāng)一個(gè)大小為2的K次冪的塊被釋放后，存儲(chǔ)管理只需要搜索2的K次冪字節(jié)大小的塊以判定是否需要合并。那些允許內(nèi)存塊以任意形式分割的策略需要搜索所有的空閑塊表。相比之下，伙伴系統(tǒng)更快。

但是對(duì)于內(nèi)存利用率來(lái)說(shuō)，伙伴系統(tǒng)是極其低效的。問(wèn)題出自所有的內(nèi)存請(qǐng)求都必須以2的冪次方大小的空間來(lái)滿(mǎn)足，一個(gè)35KB的請(qǐng)求需要分配64KB的空間，其余的29KB被浪費(fèi)了。在極端情況下內(nèi)存資源有近50%被浪費(fèi)。

3 連續(xù)的內(nèi)存分配

3.1 問(wèn)題提出

伙伴系統(tǒng)的內(nèi)存管理方式對(duì)空間的使用存在極大的浪費(fèi)。在某些情況下還會(huì)由于資源的浪費(fèi)，導(dǎo)致后繼的內(nèi)存請(qǐng)求得不到滿(mǎn)足，進(jìn)而嚴(yán)重地影響程序的正常功能。

試考慮：系統(tǒng)共有1MB內(nèi)存空間可用，采用伙伴系統(tǒng)進(jìn)行管理。有如下請(qǐng)求：請(qǐng)求A,300KB;請(qǐng)求B,300KB;請(qǐng)求C,50KB.結(jié)果如表1所示。

由表1中可以看出：伙伴系統(tǒng)對(duì)空間的浪費(fèi)是極其嚴(yán)重的，即使在物理內(nèi)存充足（1MB）的情況下，也會(huì)產(chǎn)生請(qǐng)求（650KB）無(wú)法滿(mǎn)足的情況。

由于在嵌入式系統(tǒng)中，一般都沒(méi)有虛擬內(nèi)存的支持，所以當(dāng)內(nèi)存請(qǐng)求無(wú)法得到滿(mǎn)足時(shí)，將嚴(yán)重影響程序的正常功能。因此為了保證程序的正常功能，就要提高內(nèi)存的利用率，盡可能地滿(mǎn)足程序的內(nèi)存請(qǐng)求。所以在對(duì)伙伴系統(tǒng)進(jìn)行分析的基礎(chǔ)上，提出了連續(xù)的內(nèi)存分配方式。