基于μC/OS任務調度算法的嵌入式數(shù)據(jù)管理

引言

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

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ù)據(jù)的0、1狀態(tài)分別代表64個任務是否處于就緒態(tài)（0代表空閑，1代表就緒）；OSRdyGrp為1個字節(jié)數(shù)據(jù)（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ù)據(jù)管理的關鍵。

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

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

2.1 基本思想

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

2.2 算法的改進

μC/OS的最大任務數(shù)為64，這意味著直接采用μC/OS任務調度算法實現(xiàn)的數(shù)據(jù)管理的最大記錄數(shù)也僅為64個，這顯然不適用于多數(shù)應用場合，因此需對算法進行改進。本方法引入“頁”的概念，即每64個記錄為1頁，數(shù)據(jù)存儲前先查找包含空記錄的頁號，然后在該頁中查找空記錄。查找包含空記錄的頁號的方法與查找空記錄的方法相同（即都根據(jù)μ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ù)據(jù)管理主要步驟的實現(xiàn)

2.3.1 數(shù)據(jù)初始化

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

2.3.2 數(shù)據(jù)存儲

數(shù)據(jù)存儲前先要找到優(yōu)先級最高的空記錄，其流程為先找到含空記錄的頁號，然后在該頁中查找空記錄號，最后根據(jù)頁號和空記錄號計算出當前可用于存儲且優(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;//獲得空記錄在整個存儲空間中的序號

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

　　PrioPage=RecordNo / 64;//頁號

　　prio=RecordNo % 64;//記錄號

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

　　OSRdyGrp[PrioPage] =~OSMapTbl[prio》3]; //置頁中的記錄號為“滿”狀態(tài)

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

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

　　OSRdyPage = ~OSMapTbl[PrioPage》3];

　　}

2.3.3 數(shù)據(jù)刪除

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

　　PrioPage=RecordNo / 64;//頁號

　　prio=RecordNo % 64;//記錄號

　　OSRdyPage |=OSMapTbl[PrioPage》3];

　　OSRdyPageTbl[PrioPage》3] |=OSMapTbl[PrioPage 0x07];//設置該頁的存儲狀態(tài)為“空”

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

　　OSRdyTbl[PrioPage][prio》3] |=OSMapTbl[prio 0x07];）//設置頁中的記錄為“空”狀態(tài)

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

3 結語

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