利用μC/OS任務(wù)調(diào)度算法實現(xiàn)嵌入式數(shù)據(jù)管理[圖]

摘要: 利用μC/OS嵌入式操作系統(tǒng)的任務(wù)調(diào)度算法，巧妙地實現(xiàn)了簡易的嵌入式數(shù)據(jù)管理。首先詳細(xì)描述了μC/OS任務(wù)調(diào)度算法的原理，在此基礎(chǔ)上提出了利用該算法實現(xiàn)嵌入式數(shù)據(jù)管理的基本思想，最后根據(jù)實際應(yīng)用需要，對該算法進行改進并給出數(shù)據(jù)管理關(guān)鍵流程的詳細(xì)實現(xiàn)方法。該方法有效解決了傳統(tǒng)方法存在的存儲空間碎片問題，且實現(xiàn)簡單，可廣泛應(yīng)用于低端嵌入式應(yīng)用中的數(shù)據(jù)管理。

引言

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

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

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

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

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

圖1 任務(wù)就緒表

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

OSRdyGrp|=0x02；

OSRdyTbl[1]|=0x10；

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

從上面的計算可以得到:若OSRdyGrp及OSRdyTbl[]的第n位置1，則應(yīng)該把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位代表任務(wù)組號，低3位代表任務(wù)在所在組中的位置。則任意優(yōu)先級為prio的任務(wù)進入就緒態(tài)只需執(zhí)行以下程序[3]：

OSRdyGrp|=OSMapTbl[prio >> 3];

OSRdyTbl[prio>>3]|=OSMapTbl[prio & 0x07];

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

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

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

μC/OS采用查表法查找當(dāng)前處于就緒態(tài)的最高優(yōu)先級任務(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)先級高3位，即當(dāng)前處于就緒態(tài)的最高優(yōu)先級的任務(wù)的組號

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

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

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

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

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

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

2.1 基本思想

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

2.2 算法的改進

μC/OS的最大任務(wù)數(shù)為64，這意味著直接采用μC/OS任務(wù)調(diào)度算法實現(xiàn)的數(shù)據(jù)管理的最大記錄數(shù)也僅為64個，這顯然不適用于多數(shù)應(yīng)用場合，因此需對算法進行改進。本方法引入“頁”的概念，即每64個記錄為1頁，數(shù)據(jù)存儲前先查找包含空記錄的頁號，然后在該頁中查找空記錄。查找包含空記錄的頁號的方法與查找空記錄的方法相同（即都根據(jù)μC/OS中的“查找當(dāng)前處于就緒態(tài)的最高優(yōu)先級任務(wù)”的方法查找），因此最大記錄數(shù)為64記錄/頁×64頁=4096個記錄。依此類推，可繼續(xù)擴大存儲記錄數(shù)。為了理解方便，下文代表記錄空閑狀態(tài)和頁內(nè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)剛運行時，所有記錄應(yīng)為空狀態(tài)，因此需將代表記錄空閑狀態(tài)和頁空閑狀態(tài)的全局變量OSRdyTbl[]、OSRdyGrp、OSRdyPageTbl[]和OSRdyPage的所有字節(jié)均初始化為0xff（因為“1”代表空閑）。

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

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

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ù)存儲到相應(yīng)存儲空間了，存儲完成后需將該序號的存儲空間設(shè)置為“滿”狀態(tài)，具體流程為：先將該頁中的記錄號置為“滿”狀態(tài)（即清零相應(yīng)位），然后判斷本頁中是否所有記錄均為“滿”，若是則置該頁的狀態(tài)為“滿”。詳細(xì)程序如下：

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對應(yīng)的頁號和記錄號的存儲狀態(tài)設(shè)置為“空”（則該記錄可用于后續(xù)的存儲），具體流程為：先設(shè)置頁號為“空”（因為只要該頁中任意一個記錄為“空”，則頁的狀態(tài)即為“空”），然后設(shè)置記錄號的狀態(tài)為“空”，詳細(xì)程序如下：

PrioPage=RecordNo / 64;//頁號

prio=RecordNo % 64;//記錄號

OSRdyPage |=OSMapTbl[PrioPage>>3];

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

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

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

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

結(jié)語

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

參考文獻

[1] 曹艷蕓.嵌入式數(shù)據(jù)庫發(fā)展?fàn)顩r研究[J].電子產(chǎn)品世界,2010，17(3):1618.

[2] 曹劍青,雷振中.對嵌入式數(shù)據(jù)庫的系統(tǒng)設(shè)計及實現(xiàn)[J].中國科技縱橫,2010(11).

[3] Labrosse Jean J.嵌入式實時操作系統(tǒng)μC/OSII[M].邵貝貝，等譯.北京:北京航空航天大學(xué)出版社,2003.

[4] 任哲,潘樹林,房紅征.嵌入式操作系統(tǒng)基礎(chǔ)μC/OSII和Linux[M].北京:北京航空航天大學(xué)出版社,2006.

徐藝文(博士研究生、講師)，主要研究方向為嵌入式系統(tǒng)及其應(yīng)用。

作者：徐藝文 魏云龍 來源：《單片機與嵌入式系統(tǒng)應(yīng)用》