1、引言

嵌入式系統(tǒng)的內(nèi)存資源相當(dāng)有限，所以需對(duì)其進(jìn)行合理的規(guī)劃和管理，即需要滿足其管理特點(diǎn)：【1】快速性、可靠性和高效性。

隨著嵌入式應(yīng)用軟件規(guī)模的增長(zhǎng)，人們希望DSA在滿足以上特性的同時(shí)，更能夠被方便而充分地使用。而UC/OS-II的DSA功能較弱，所以對(duì)其進(jìn)行改進(jìn)是很有必要的。

2、RTOS的DSA概覽【2】【3】【4】【5】

按照記錄以及合并空閑內(nèi)存塊的方法，可將RTOS的DSA分成順序搜索、索引搜索、分類搜索、位圖搜索以及伙伴算法等。這些DSA算法都具有分配真實(shí)內(nèi)存，立即合并空閑內(nèi)存等特點(diǎn)。

2．1 順序搜索算法

順序搜索算法采用單向或雙向鏈表維護(hù)空閑內(nèi)存。該算法的時(shí)間花費(fèi)與空閑內(nèi)存鏈表長(zhǎng)度成正比，時(shí)間花費(fèi)是有界的，但會(huì)隨著空閑內(nèi)存塊增多而增加，在嵌入式實(shí)時(shí)系統(tǒng)中并不宜使用。

2．2 索引搜索算法

索引搜索算法用一種比鏈表復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄空閑內(nèi)存。常見的如排序二叉樹，樹中每一個(gè)節(jié)點(diǎn)代表某一個(gè)尺寸的空閑內(nèi)存，存儲(chǔ)該尺寸的空閑內(nèi)存鏈表指針。索引搜索算法的數(shù)據(jù)結(jié)構(gòu)和分配、合并內(nèi)存較為復(fù)雜。

2．3 分類搜索算法

分類算法把所有空閑內(nèi)存按其尺寸范圍劃歸不同的類，同一類內(nèi)的內(nèi)存塊鏈接成一個(gè)空閑自由內(nèi)存鏈表。所有的空閑內(nèi)存頭指針統(tǒng)一由另一個(gè)數(shù)組鏈表維護(hù)，每個(gè)空閑內(nèi)存頭指針對(duì)應(yīng)該數(shù)組一個(gè)元素。值得注意的是，屬同一類的自由內(nèi)存，并不要求其物理上是相鄰的。

分類搜索算法中的鏈表可以是按空閑內(nèi)存尺寸排序的，也可以是不排序的。分類算法較為復(fù)雜，但不必搜索即可查找合適空閑內(nèi)存，時(shí)間花費(fèi)不隨空閑內(nèi)存的數(shù)量而變化，適合于嵌入式系統(tǒng)采用。

2．4 位圖搜索算法

位圖搜索算法用一個(gè)位圖來(lái)查找空閑內(nèi)存，該算法查找空閑內(nèi)存所需的信息全部存儲(chǔ)在一小塊內(nèi)存中，查找響應(yīng)速度很快。

3、UC/OS-II的DSA不足之處

UC/OS-II中的內(nèi)存管理模塊把動(dòng)態(tài)管理的內(nèi)存分成多個(gè)內(nèi)存區(qū)，每一個(gè)內(nèi)存區(qū)又分成一定數(shù)量相同尺寸的內(nèi)存塊。具體的UC/OS-II 中，DSA由OS_MEM.c實(shí)現(xiàn)，總共只包含5個(gè)函數(shù)OSMenInit,，OSMemCreate，OSMemGet，OSMemPut 與OSMemQuery，約100行代碼，十分精煉。正是由于其精煉，UC/OS-II的DSA提供的功能十分有限，存在以下不足：

1）動(dòng)態(tài)管理的內(nèi)存塊尺寸須在編譯時(shí)指定，運(yùn)行時(shí)不能更改，限制了系統(tǒng)以后擴(kuò)展應(yīng)用程序的靈活性，也造成內(nèi)存浪費(fèi)。

2）由于同一分區(qū)只能提供唯一尺寸的內(nèi)存塊，而應(yīng)用中一般需使用到不同尺寸的內(nèi)存塊。為了減少資源浪費(fèi)，此時(shí)則需建立兩個(gè)以上的內(nèi)存區(qū)，加大了維護(hù)開銷。

3）不可能提供確定不同內(nèi)存區(qū)的內(nèi)存塊之間尺寸差距的方案，使內(nèi)存的浪費(fèi)不可避免。這是由于系統(tǒng)中可能的應(yīng)用千變?nèi)f化，而他們申請(qǐng)的內(nèi)存塊尺寸也不盡相同。

4）UC/OS-II的DSA可以歸類為2.3中的分類搜索算法，但其并未提供如何搜索到合適分類的方法，也未提供向某一分類申請(qǐng)內(nèi)存失敗后如何向下一分類申請(qǐng)內(nèi)存的方法，而需要程序員自己提供，加重了程序員負(fù)擔(dān)的同時(shí)更是降低了程序的可靠性與穩(wěn)定性。