一般情況下，在嵌入式系統(tǒng)中實現(xiàn)數(shù)據管理我們常采用嵌入式數(shù)據庫。但是目前常用的嵌入式數(shù)據庫（如SQLite、Berkeley DB等）均需嵌入式操作系統(tǒng)的支持，且對嵌入式系統(tǒng)的內存、CPU處理速度等有較高要求，只能應用在比較高端的嵌入式系統(tǒng)中。在低端的嵌入式系統(tǒng)中，傳統(tǒng)的數(shù)據管理方法是對數(shù)據存儲空間按順序編號，數(shù)據存儲與刪除均根據編號順序操作。這種方法在多次刪除后會出現(xiàn)很多存儲空間碎片，一方面加大了程序查找空閑存儲空間的難度，數(shù)據管理操作時間長（類似微機系統(tǒng)中硬盤長時間不做磁盤碎片整理會造成程序運行變慢的情況），另一方面可能造成存儲空間利用率降低。本文提出了一種利用μC/OS任務調度算法實現(xiàn)的數(shù)據管理方法，該方法無需嵌入式操作系統(tǒng)的支持，可應用于低端的嵌入式系統(tǒng)中，而且可以有效克服低端嵌入式應用中傳統(tǒng)數(shù)據管理方法的缺陷。

1μC/OS任務調度算法

μC/OS是一種占先式的多任務嵌入式操作系統(tǒng)，它可以管理多達64個任務。μC/OS中，每個任務的優(yōu)先級不一樣且是唯一的，優(yōu)先級最高的任務一旦準備就緒，則擁有CPU所有權并開始投入運行。所以，μC/OS的任務調度算法的基本思想就是，查找當前準備就緒的最高優(yōu)先級的任務，并進行任務切換。實現(xiàn)上述任務調度算法主要包含兩個步驟：確定目前哪幾個任務處于就緒態(tài)，確定目前處于就緒態(tài)的任務中哪個優(yōu)先級最高。為此，μC/OS提供了兩個全局變量OSRdyTbl［］和OSRdyGrp。OSRdyTbl［］數(shù)組是任務就緒表，包含 8個字節(jié)（共64位），相當于把64個任務分為8組，每組8個任務，這64位數(shù)據的0、1狀態(tài)分別代表64個任務是否處于就緒態(tài)（0代表空閑，1代表就緒）；OSRdyGrp為1個字節(jié)數(shù)據（8位），每一位的0、1狀態(tài)分別代表OSRdyTbl［］數(shù)組的相應字節(jié)是否非零（即該組中是否有任務處于就緒態(tài)）。通過這兩個全局變量的賦值就可實現(xiàn)任務就緒態(tài)與空閑態(tài)的切換，這是μC/OS實現(xiàn)任務調度的基礎。

1.1使任務進入就緒態(tài)

μC/OS通過OSRdyTbl［］和OSRdyGrp某位置“1”，使相應任務進入就緒態(tài)，如圖1所示。

圖1任務就緒表

假設優(yōu)先級為12的任務進入就緒狀態(tài)，12 = 1100b，則OSRdyTbl［1］的第4位置1，且OSRdyGrp的第1位置1（代表第1組有任務處于就緒態(tài)），相應的數(shù)學表達式為：

OSRdyGrp|=0x02；

OSRdyTbl［1］|=0x10；

則μC/OS在執(zhí)行任務調度時，通過OSRdyGrp的值即可判斷出第1組任務中有任務處于就緒態(tài)，然后再通過OSRdyTbl［］數(shù)組的第1個字節(jié)即可判斷出此時優(yōu)先級為12的任務處于就緒態(tài)，則可做任務切換。

從上面的計算可以得到：若OSRdyGrp及OSRdyTbl［］的第n位置1，則應該把OSRdyGrp及OSRdyTbl［］的值與2n相或。為了計算方便，μC/OS中把2n的8個值（n=0~7）先計算好，存在數(shù)組OSMapTbl［］中，即：

OSMapTbl［0］=20=0x01（0000 0001）

OSMapTbl［1］=21=0x02（0000 0010）

……

OSMapTbl［7］ = 27=0x80（1000 0000）

μC/OS中，優(yōu)先級數(shù)分解為高3位和低3位，高3位代表任務組號，低3位代表任務在所在組中的位置。則任意優(yōu)先級為prio的任務進入就緒態(tài)只需執(zhí)行以下程序：

OSRdyGrp|=OSMapTbl［prio 》 3］;

OSRdyTbl［prio》3］|=OSMapTbl［prio & 0x07］;

1.2使任務進入空閑態(tài)

μC/OS通過任務就緒表OSRdyTbl［prio》3］（prio代表任務優(yōu)先級）中相應位清零使相應任務進入空閑態(tài)，當OSRdyTbl［prio》3］中的所有位都為零時，還需將OSRdyGrp的相應位清零，代表全組任務中沒有一個任務進入就緒態(tài)。

1.3查找當前處于就緒態(tài)的最高優(yōu)先級任務

μC/OS采用查表法查找當前處于就緒態(tài)的最高優(yōu)先級任務，它預先定義了數(shù)組OSUnMapTbl［］作為查找表，如下：

INT8U cONST OSUnMapTbl［］={

0， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

5， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

6， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

5， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

7， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

5， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

6， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

5， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0，

4， 0， 1， 0， 2， 0， 1， 0， 3， 0， 1， 0， 2， 0， 1， 0

}；

相應的查找程序如下：

High3=OSUnMapTbl［OSRdyGrp］;//優(yōu)先級高3位，即當前處于就緒態(tài)的最高優(yōu)先級的任務的組號

Low3=OSUnMapTbl［OSRdyTbl［High3］］;//優(yōu)先級低3位

prio=（Hign3《3）+Low3;//獲得當前處于就緒態(tài)的最高優(yōu)先級的任務

例如：若OSRdyGrp的值為01101000b，則查得OSUnMapTbl［OSRdyGrp］的值是3，它對應于OSRdyGrp中的第3位置1（即當前處于就緒態(tài)的最高優(yōu)先級任務處于第1組任務中）；若OSRdyTbl［3］的值是11100100b，則查OSUnMapTbl［OSRdyTbl［3］］的值是2，則進入就緒態(tài)的最高任務的優(yōu)先級prio=3×8+2=26。

從上文的計算可看出μC/OS查找當前最高優(yōu)先級任務所*的時間為常數(shù)，與應用程序中建立的任務數(shù)無關，這個特性是本文實現(xiàn)新型嵌入式數(shù)據管理的關鍵。

2利用μC/OS任務調度算法實現(xiàn)嵌入式

數(shù)據管理在低端的嵌入式應用中，數(shù)據管理的主要功能就是數(shù)據存儲與數(shù)據刪除。傳統(tǒng)的做法是對數(shù)據存儲空間按地址順序編號，數(shù)據存儲與刪除均根據編號操作，每個編號的存儲空間還提供了標志位，用于判斷該空間是否已被占用。這種方法有一個很大的弊端：多次刪除后會出現(xiàn)存儲空間碎片，這造成后續(xù)操作中查找空閑空間耗時較長，且存儲量越大，這個現(xiàn)象越嚴重，大大降低了數(shù)據管理操作的效率。有些程序員為了解決這個弊端對刪除操作只提供刪除所有記錄的功能，不提供單獨刪除某個記錄的功能，但這顯然犧牲了產品的易用性。本文利用μC/OS任務調度算法實現(xiàn)嵌入式數(shù)據管理，可有效解決以上問題。

2.1基本思想

利用μC/OS任務調度算法實現(xiàn)嵌入式數(shù)據管理的基本思想是：將μC/OS中的“任務優(yōu)先級”與數(shù)據管理的“記錄號”對應，將“任務就緒態(tài)”與“存儲空間空狀態(tài)”（注意，不是存儲空間滿狀態(tài)）對應，將“任務空閑態(tài)”與“存儲空間滿狀態(tài)”對應，將“使任務進入就緒態(tài)”與“數(shù)據刪除”對應，將“使任務進入空閑態(tài)”與“數(shù)據存儲”對應，將“查找當前處于就緒態(tài)的最高優(yōu)先級任務”與“查找當前空閑存儲空間”對應。即在實際應用中，數(shù)據存儲前先根據μC/OS中的“查找當前處于就緒態(tài)的最高優(yōu)先級任務”的方法查找目前優(yōu)先級最高的空閑存儲空間，獲得相應記錄號，然后在數(shù)據存儲后根據μC/OS中的“使任務進入空閑態(tài)”的方法使相應記錄的存儲空間置為“滿”狀態(tài)；數(shù)據刪除后根據μC/OS中的“使任務進入就緒態(tài)”的方法使相應記錄的存儲空間置為“空”狀態(tài)。顯然，該方法較傳統(tǒng)方法有兩大優(yōu)點：查找空閑存儲空間的速度遠高于傳統(tǒng)方法，且查找時間為常數(shù)，即查找時間與記錄數(shù)無關（傳統(tǒng)方法的查找時間隨記錄數(shù)遞增）；不會出現(xiàn)存儲空間碎片，因為本方法按優(yōu)先級存儲數(shù)據，刪除的存儲空間的優(yōu)先級肯定高于未使用的存儲空間，則在后續(xù)存儲操作中會將其優(yōu)先用于存儲，從而也就避免了存儲空間碎片的出現(xiàn)。

2.2算法的改進

μC/OS的最大任務數(shù)為64，這意味著直接采用μC/OS任務調度算法實現(xiàn)的數(shù)據管理的最大記錄數(shù)也僅為64個，這顯然不適用于多數(shù)應用場合，因此需對算法進行改進。本方法引入“頁”的概念，即每64個記錄為1頁，數(shù)據存儲前先查找包含空記錄的頁號，然后在該頁中查找空記錄。查找包含空記錄的頁號的方法與查找空記錄的方法相同（即都根據μC/OS中的“查找當前處于就緒態(tài)的最高優(yōu)先級任務”的方法查找），因此最大記錄數(shù)為64記錄/頁×64頁=4096個記錄。依此類推，可繼續(xù)擴大存儲記錄數(shù)。為了理解方便，下文代表記錄空閑狀態(tài)和頁內記錄號的全局變量定義為OSRdyTbl［64］［8］、OSRdyGrp［64］和prio，代表頁空閑狀態(tài)和頁號的全局變量定義為OSRdyPage、OSRdyPageTbl［8］和PrioPage，代表記錄在整個存儲空間的序號定義為RecordNo（則RecordNo = PrioPage×64+prio）。

2.3嵌入式數(shù)據管理主要步驟的實現(xiàn)

2.3.1數(shù)據初始化

在嵌入式系統(tǒng)剛運行時，所有記錄應為空狀態(tài)，因此需將代表記錄空閑狀態(tài)和頁空閑狀態(tài)的全局變量OSRdyTbl［］、OSRdyGrp、OSRdyPageTbl［］和OSRdyPage的所有字節(jié)均初始化為0xff（因為“1”代表空閑）。

2.3.2數(shù)據存儲

數(shù)據存儲前先要找到優(yōu)先級最高的空記錄，其流程為先找到含空記錄的頁號，然后在該頁中查找空記錄號，最后根據頁號和空記錄號計算出當前可用于存儲且優(yōu)先級最高的存儲空間的序號。詳細程序如下：

High3=OSUnMapTbl［OSRdyPageGrp］;//高3位

Low3=OSUnMapTbl［OSRdyPageTbl］［High3］］;//低3位

PrioPage=（High3《3）+Low3;//先找到含空記錄的頁號

High3=OSUnMapTbl［OSRdyGrp［PrioPage］］;

Low3=OSUnMapTbl［OSRdyTbl［PrioPage］［High3］］;

prio=（High3《3）+Low3;//獲得頁中的空記錄號

RecordNo=PrioPage*64+prio;//獲得空記錄在整個存儲空間中的序號