1、引言

嵌入式系統的內存資源相當有限，所以需對其進行合理的規劃和管理，即需要滿足其管理特點：【1】快速性、可靠性和高效性。

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

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

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

2．1 順序搜索算法

順序搜索算法采用單向或雙向鏈表維護空閑內存。該算法的時間花費與空閑內存鏈表長度成正比，時間花費是有界的，但會隨著空閑內存塊增多而增加，在嵌入式實時系統中并不宜使用。

2．2 索引搜索算法

索引搜索算法用一種比鏈表復雜的數據結構來記錄空閑內存。常見的如排序二叉樹，樹中每一個節點代表某一個尺寸的空閑內存，存儲該尺寸的空閑內存鏈表指針。索引搜索算法的數據結構和分配、合并內存較為復雜。

2．3 分類搜索算法

分類算法把所有空閑內存按其尺寸范圍劃歸不同的類，同一類內的內存塊鏈接成一個空閑自由內存鏈表。所有的空閑內存頭指針統一由另一個數組鏈表維護，每個空閑內存頭指針對應該數組一個元素。值得注意的是，屬同一類的自由內存，并不要求其物理上是相鄰的。

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

2．4 位圖搜索算法

位圖搜索算法用一個位圖來查找空閑內存，該算法查找空閑內存所需的信息全部存儲在一小塊內存中，查找響應速度很快。

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

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

1）動態管理的內存塊尺寸須在編譯時指定，運行時不能更改，限制了系統以后擴展應用程序的靈活性，也造成內存浪費。

2）由于同一分區只能提供唯一尺寸的內存塊，而應用中一般需使用到不同尺寸的內存塊。為了減少資源浪費，此時則需建立兩個以上的內存區，加大了維護開銷。

3）不可能提供確定不同內存區的內存塊之間尺寸差距的方案，使內存的浪費不可避免。這是由于系統中可能的應用千變萬化，而他們申請的內存塊尺寸也不盡相同。

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