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

引言

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

1 μC/OS任務(wù)調(diào)度算法

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

1.1 使任務(wù)進(jìn)入就緒態(tài)

μC/OS通過(guò)OSRdyTbl[]和OSRdyGrp某位置“1”，使相應(yīng)任務(wù)進(jìn)入就緒態(tài)，如圖1所示。

圖1 任務(wù)就緒表

假設(shè)優(yōu)先級(jí)為12的任務(wù)進(jìn)入就緒狀態(tài)，12 = 1100b,則OSRdyTbl[1]的第4位置1，且OSRdyGrp的第1位置1（代表第1組有任務(wù)處于就緒態(tài)），相應(yīng)的數(shù)學(xué)表達(dá)式為：

　　OSRdyGrp|=0x02；

　　OSRdyTbl[1]|=0x10；

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

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

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

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

　　……

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

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

　　OSRdyGrp|=OSMapTbl[prio 》 3];

　　OSRdyTbl[prio》3]|=OSMapTbl[prio 0x07];

1.2 使任務(wù)進(jìn)入空閑態(tài)

μC/OS通過(guò)任務(wù)就緒表OSRdyTbl[prio》3]（prio代表任務(wù)優(yōu)先級(jí)）中相應(yīng)位清零使相應(yīng)任務(wù)進(jìn)入空閑態(tài)，當(dāng)OSRdyTbl[prio》3]中的所有位都為零時(shí)，還需將OSRdyGrp的相應(yīng)位清零，代表全組任務(wù)中沒(méi)有一個(gè)任務(wù)進(jìn)入就緒態(tài)。

1.3 查找當(dāng)前處于就緒態(tài)的最高優(yōu)先級(jí)任務(wù)

μC/OS采用查表法查找當(dāng)前處于就緒態(tài)的最高優(yōu)先級(jí)任務(wù)，它預(yù)先定義了數(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

　　}；

相應(yīng)的查找程序如下：

　　High3=OSUnMapTbl[OSRdyGrp];//優(yōu)先級(jí)高3位，即當(dāng)前處于就緒態(tài)的最高優(yōu)先級(jí)的任務(wù)的組號(hào)

　　Low3=OSUnMapTbl[OSRdyTbl[High3]];//優(yōu)先級(jí)低3位

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

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

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

2 利用μC/OS任務(wù)調(diào)度算法實(shí)現(xiàn)嵌入式

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

2.1 基本思想

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

2.2 算法的改進(jìn)

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

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

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

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

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

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

　　High3=OSUnMapTbl[OSRdyPageGrp];//高3位

　　Low3=OSUnMapTbl[OSRdyPageTbl][High3]];//低3位

　　PrioPage=（High3《3）+Low3;//先找到含空記錄的頁(yè)號(hào)

　　High3=OSUnMapTbl[OSRdyGrp[PrioPage]];

　　Low3=OSUnMapTbl[OSRdyTbl[PrioPage][High3]];

　　prio=（High3《3）+Low3;//獲得頁(yè)中的空記錄號(hào)

　　RecordNo=PrioPage*64+prio;//獲得空記錄在整個(gè)存儲(chǔ)空間中的序號(hào)

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

　　PrioPage=RecordNo / 64;//頁(yè)號(hào)

　　prio=RecordNo % 64;//記錄號(hào)

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

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

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

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

　　OSRdyPage = ~OSMapTbl[PrioPage》3];

　　}

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

數(shù)據(jù)刪除即將存儲(chǔ)序號(hào)RecordNo對(duì)應(yīng)的頁(yè)號(hào)和記錄號(hào)的存儲(chǔ)狀態(tài)設(shè)置為“空”（則該記錄可用于后續(xù)的存儲(chǔ)），具體流程為：先設(shè)置頁(yè)號(hào)為“空”（因?yàn)橹灰擁?yè)中任意一個(gè)記錄為“空”，則頁(yè)的狀態(tài)即為“空”），然后設(shè)置記錄號(hào)的狀態(tài)為“空”，詳細(xì)程序如下：

　　PrioPage=RecordNo / 64;//頁(yè)號(hào)

　　prio=RecordNo % 64;//記錄號(hào)

　　OSRdyPage |=OSMapTbl[PrioPage》3];

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

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

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

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

3 結(jié)語(yǔ)

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