引言

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

1  μC/OS任務調度算法

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

1.1  使任務進入就緒態

μC/OS通過OSRdyTbl[]和OSRdyGrp某位置“1”，使相應任務進入就緒態，如圖1所示。

μC/OS任務調度算法的嵌入式數據管理" height="195" src="http://files.chinaaet.com/images/20110607/9cdf5ad1-b417-426e-a937-a2e2a5726401.jpg" width="392" />

圖1  任務就緒表

假設優先級為12的任務進入就緒狀態，12 = 1100b,則OSRdyTbl[1]的第4位置1，且OSRdyGrp的第1位置1（代表第1組有任務處于就緒態），相應的數學表達式為：

OSRdyGrp|=0x02；

OSRdyTbl[1]|=0x10；

則μC/OS在執行任務調度時，通過OSRdyGrp的值即可判斷出第1組任務中有任務處于就緒態，然后再通過OSRdyTbl[]數組的第1個字節即可判斷出此時優先級為12的任務處于就緒態，則可做任務切換。

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

OSMapTbl[0]=20=0x01（0000 0001）

OSMapTbl[1]=21=0x02（0000 0010）

……

OSMapTbl[7] = 27=0x80（1000 0000）

μC/OS中，優先級數分解為高3位和低3位，高3位代表任務組號，低3位代表任務在所在組中的位置。則任意優先級為prio的任務進入就緒態只需執行以下程序：

OSRdyGrp|=OSMapTbl[prio 》 3]；

OSRdyTbl[prio》3]|=OSMapTbl[prio & 0x07]；

1.2  使任務進入空閑態

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

1.3  查找當前處于就緒態的最高優先級任務

μC/OS采用查表法查找當前處于就緒態的最高優先級任務，它預先定義了數組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]；//優先級高3位，即當前處于就緒態的最高優先級的任務的組號

Low3=OSUnMapTbl[OSRdyTbl[High3]]；//優先級低3位

prio=（Hign3《3）+Low3；//獲得當前處于就緒態的最高優先級的任務
例如：若OSRdyGrp的值為01101000b，則查得OSUnMapTbl[OSRdyGrp]的值是3，它對應于OSRdyGrp中的第3位置1（即當前處于就緒態的最高優先級任務處于第1組任務中）；若OSRdyTbl[3]的值是11100100b，則查OSUnMapTbl[OSRdyTbl[3]]的值是2，則進入就緒態的最高任務的優先級prio=3×8+2=26。

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

2  利用μC/OS任務調度算法實現嵌入式

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

2.1  基本思想

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

2.2  算法的改進

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

2.3  嵌入式數據管理主要步驟的實現

2.3.1  數據初始化

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

2.3.2  數據存儲

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

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；//獲得空記錄在整個存儲空間中的序號

根據以上程序得到序號后，就可以將數據存儲到相應存儲空間了，存儲完成后需將該序號的存儲空間設置為“滿”狀態，具體流程為：先將該頁中的記錄號置為“滿”狀態（即清零相應位），然后判斷本頁中是否所有記錄均為“滿”，若是則置該頁的狀態為“滿”。詳細程序如下：

PrioPage=RecordNo / 64；//頁號

prio=RecordNo % 64；//記錄號

if （（OSRdyTbl[PrioPage][prio》3] &=~OSMapTbl[prio & 0x07]）==0）

OSRdyGrp[PrioPage] &=~OSMapTbl[prio》3]； //置頁中的記錄號為“滿”狀態

if（OSRdyGrp[PrioPage]==0）{//若該頁中的所有記錄均為“滿”則置該頁為“滿”狀態

if （（OSRdyPageTbl[PrioPage》3] &=~OSMapTbl[PrioPage & 0x07]）==0）

OSRdyPage &= ~OSMapTbl[PrioPage》3]；

}

2.3.3  數據刪除

數據刪除即將存儲序號RecordNo對應的頁號和記錄號的存儲狀態設置為“空”（則該記錄可用于后續的存儲），具體流程為：先設置頁號為“空”（因為只要該頁中任意一個記錄為“空”，則頁的狀態即為“空”），然后設置記錄號的狀態為“空”，詳細程序如下：

PrioPage=RecordNo / 64；//頁號

prio=RecordNo % 64；//記錄號

OSRdyPage |=OSMapTbl[PrioPage》3]；

OSRdyPageTbl[PrioPage》3] |=OSMapTbl[PrioPage & 0x07]；//設置該頁的存儲狀態為“空”

OSRdyGrp[PrioPage] |=OSMapTbl[prio》3]；

OSRdyTbl[PrioPage][prio》3] |=OSMapTbl[prio & 0x07]；）//設置頁中的記錄為“空”狀態

按以上方法將相應序號的存儲空間設置為空狀態，則在后續操作中該存儲空間可用于存儲。

3 結語

本文利用μC/OS嵌入式操作系統的任務調度 算法并加以改進，巧妙地實現了簡易的嵌入式數據管理，與傳統方法比較，該方法具備不出現存儲空間碎片、數據管理操作效率高等優點，可廣泛應用于低端嵌入式應用中的數據管理。該方法已在筆者所開發的SF6電氣設備分解產物檢測儀及智能抄表終端中應用，運行穩定可靠。