一種基于μC/OS-Ⅱ的多任務優(yōu)先級調(diào)度新算法

梁建明，金京林

(華南師范大學計算機學院， 廣東廣州 510631)

嵌入式實時操作系統(tǒng)，一方面需要具有低資源和低功耗的嵌入式系統(tǒng)特點，另一方面還需要滿足實時性，以保證任務在可確定的相對短的時間內(nèi)得到響應[1]. 在實時系統(tǒng)的任務調(diào)度中，調(diào)度策略最多的是采用優(yōu)先級搶占式調(diào)度法[2]. μC/OS-Ⅱ是一種“硬實時”的嵌入式操作系統(tǒng)[3]，是由Jean J Labrosse編寫的一個源代碼公開的搶占式實時內(nèi)核[4]，在嵌入式領域有著廣泛的應用[5]. 它采用查表法的算法實現(xiàn)了最高優(yōu)先級任務的快速查找，其查找的時間復雜度和任務數(shù)無關，但其空間復雜度會隨著任務數(shù)的增加而呈幾何級數(shù)的增長. 正因為這個關鍵因素，目前μC/OS-Ⅱ最大只能支持64個任務，而隨著嵌入式應用的發(fā)展，會成為一個瓶頸.

本文在保持現(xiàn)有其它算法和數(shù)據(jù)結(jié)構(gòu)不變的基礎上，提出了一種查找最高優(yōu)先級的新算法. 首先，為便于理解和比較新舊算法的區(qū)別，對現(xiàn)有的查找最高優(yōu)先級的算法和主要數(shù)據(jù)結(jié)構(gòu)進行了分析；然后，詳細闡述了新算法的推導和實現(xiàn)過程；最后，對新舊算法在性能上作一些分析和比較.

1 現(xiàn)有的查找最高優(yōu)先級的算法分析

μC/OS-Ⅱ目前能支持的最大任務數(shù)為64個，任務標識號同時也是任務優(yōu)先級號，且唯一，與高優(yōu)先級任務相比有較小的優(yōu)先級號. 現(xiàn)有的算法是將這64個任務分為8組，每組包括8個任務. 圖1為相關的數(shù)據(jù)結(jié)構(gòu)示意圖.

圖1 現(xiàn)有算法的數(shù)據(jù)結(jié)構(gòu)Figure 1 The data structure of existing algorithm

圖1表明：任務優(yōu)先級號Prio[6]是1個8比特的無符號整數(shù)，其中用YYY(第4位到第6位)這3位來確定該任務屬于哪一組，即對應OSRdyGrp[6]中的第幾位，用XXX(第1位到第3位)這3位來確定該任務屬于該組中的第幾個任務，即對應OSRdyTbl[][6]中的第幾位，高2位(第7位和第8位)目前是備用狀態(tài)；任務就緒組OSRdyGrp是一個8比特的無符號整數(shù)，每個比特位代表一組任務，該位為1表示該組任務中至少有一個任務處于就緒態(tài)，為0表示該組中8個任務都處于非就緒態(tài)；任務就緒表OSRdyTbl[]是一個含8個元素的數(shù)組，數(shù)組下標與OSRdyGrp中的比特位一一對應，每個元素是一個8比特的無符號整數(shù)，每個比特位代表一個任務，該位為1表示該任務處于就緒態(tài)，為0表示該任務處于非就緒態(tài)，只要這8比特位不全為0，則該組任務在OSRdyGrp中對應的位就為1. 當某個任務進入或退出就緒態(tài)時，根據(jù)該任務優(yōu)先級號Prio中的YYY和XXX的值分別對OSRdyGrp和OSRdyTbl[]的相應位進行置1或清0，這部分的算法比較精簡，文中對此不作進一步分析和優(yōu)化. 當需要調(diào)度最高優(yōu)先級的任務進入運行態(tài)時，μC/OS-Ⅱ目前是采用查表法的算法來實現(xiàn)，即根據(jù)當前任務就緒組OSRdyGrp和任務就緒表OSRdyTbl[]的值，在優(yōu)先級判定表OSUnMapTbl[][6]中找到最高優(yōu)先級的YYY和XXX值，再組合成當前最高優(yōu)先級號Prio. 該部分現(xiàn)有的關鍵算法如下：

//數(shù)據(jù)結(jié)構(gòu)聲明

INT8U Prio; //任務優(yōu)先級

INT8U OSRdyGrp; //任務就緒組

INT8U OSRdyTbl[8]; //任務就緒表

INT8U OSUnMapTbl[256]; //優(yōu)先級判定表

//查找最高優(yōu)先級號

YYY=OSUnMapTbl[OSRdyGrp];

XXX=OSUnMapTbl[OSRdyTbl[YYY]];

Prio=(YYY<<3)+XXX;

可以看出，實現(xiàn)這個算法，需要一直在內(nèi)存中保存優(yōu)先級判定表OSUnMapTbl[]，而且這個優(yōu)先級判定表的元素個數(shù)會隨任務數(shù)的增加而呈幾何級數(shù)的增加，占用的內(nèi)存資源也隨之迅速增加. 假設μC/OS-Ⅱ支持的任務數(shù)是n2個，則OSUnMapTbl[]中就有2n個元素. 現(xiàn)在如果讓μC/OS-Ⅱ支持的任務數(shù)增加到256個，即n=16，按每個整數(shù)占2個字節(jié)計算，保存OSUnMapTbl[]就需要128 KB的內(nèi)存空間，這顯然不符合嵌入式系統(tǒng)的低資源的特點.

2 新算法的推導和實現(xiàn)

將μC/OS-Ⅱ支持的任務數(shù)增加到256個為例來討論. 首先將這256個任務分為16組，每組包括16個任務. 只需將目前任務優(yōu)先級號Prio中的2個備用位用上，用其中的高4位YYYY來確定該任務屬于哪一組，用低4位XXXX來確定該任務屬于該組中的第幾個任務，這樣很容易就可以將支持的任務數(shù)增加到256個. 圖2為相關的數(shù)據(jù)結(jié)構(gòu)示意圖.

圖2 新算法的數(shù)據(jù)結(jié)構(gòu)Figure 2 The data structure of new algorithm

若采用現(xiàn)有的查表法的算法思想，其內(nèi)存空間的耗用對嵌入式系統(tǒng)來說是無法接受的. 跳出查表法的算法思想，其實查找最高優(yōu)先級號的關鍵在于：在OSRdyGrp中，由右向左按位掃描，找出第一個“1”并將其位序號賦給YYYY；同理，在OSRdyTbl[]中，由右向左按位掃描，找出第一個“1”并將其位序號賦給XXXX；找出的2個數(shù)組合起來就是當前最高優(yōu)先級號. 這樣，算法關鍵要解決的問題就是：對任意一個二進制表示的無符號整數(shù)k，由右向左按位掃描，找出第一個“1”所在數(shù)位的位序號n(序號從0開始). 針對這個問題模型，經(jīng)數(shù)學推導可得：

結(jié)論1n=log2((k?(k-1))+1)-1,其中k為任意一個二進制表示的無符號整數(shù)，n為k中由右向左按位掃描的第一個“1”所在數(shù)位的位序號(序號從0開始).

證明不失一般性，設k為m位無符號二進制整數(shù)，表示為：

其中，ki(i=m-1,m-2,…,n+2,n+1)的取值為0或1,則k-1可表示為：

其中，ki(i=m-1,m-2,…,n+2,n+1)的取值為0或1.將k和k-1作異或運算有：

結(jié)果轉(zhuǎn)換為十進制表示為：k?(k-1)=2n+1-1，進而可得：.

n=log2((k?(k-1))+1)-1.

證畢.

根據(jù)結(jié)論1中的這個等式，就很容易實現(xiàn)查找最高優(yōu)先級號的新算法，關鍵程序如下：

//數(shù)據(jù)結(jié)構(gòu)聲明

INT8U Prio; //任務優(yōu)先級

INT16U OSRdyGrp; //任務就緒組

INT16U OSRdyTbl[16]; //任務就緒表

//查找最高優(yōu)先級號

YYYY= log10((OSRdyGrp^(OSRdyGrp-1))+1)/log10(2)-1;

XXXX=log10((OSRdyTbl[YYYY]^(OSRdyTbl[YYYY]-1))+1)/log10(2)-1;

Prio=(YYYY<<4)+XXXX.

以上算法表明，它沒有使用到優(yōu)先級判定表OSUnMapTbl[]，而是用簡單的數(shù)學運算來代替，從而完全克服了現(xiàn)有查表法的局限性，保證了響應時間的確定性和實時性，其空間復雜度和時間復雜度都為O(1)，與支持的任務數(shù)完全無關，而且如果要增加支持的任務數(shù)的話，關鍵算法不需要作修改，只是在數(shù)據(jù)結(jié)構(gòu)定義部分改變一下相關變量的位數(shù)，這點可以通過宏定義的方式來做，這樣會更方便快捷.

3 性能分析

上面詳細分析了μC/OS-Ⅱ中查找最高優(yōu)先級任務的現(xiàn)有算法和新算法，現(xiàn)從以下幾個方面對這2種算法作性能上的分析和比較.

(1) 直觀地從代碼量和程序結(jié)構(gòu)上看，新算法和現(xiàn)有算法基本是一樣的，沒有任何條件分支語句，這點可以保證在任何情況下，系統(tǒng)的響應時間都是確定的，不會因極端情況的出現(xiàn)導致響應時間時快時慢.

(2) 從算法的時間復雜度上看，新算法保留了現(xiàn)有算法的優(yōu)點，都是O(1).

(3) 從算法的空間復雜度上看，對于系統(tǒng)支持最大任務數(shù)為n2個的情況，現(xiàn)有算法的空間復雜度是O(2n)，而新算法是O(1). 換句話說，現(xiàn)有算法的空間復雜度會隨支持的任務數(shù)的增加而呈幾何級數(shù)的增長，這點對嵌入式系統(tǒng)而言是無法接受的. 而新算法與支持的任務數(shù)完全無關，可以輕松地將支持的任務數(shù)從現(xiàn)有的64個增加到256個，根據(jù)實際需要還可以更多，而且不會對時間和空間復雜度有任何影響. 從圖3可以更形象地看出現(xiàn)有算法和新算法在空間復雜度變化趨勢上的不同，其中橫坐標為μC/OS-Ⅱ中支持的最大任務數(shù)的開方，縱坐標是所需優(yōu)先級判定表OSUnMapTbl[]數(shù)組的元素個數(shù)，實心星號表示的連線為現(xiàn)有算法的變化趨勢，空心圓點表示的連線為新算法的變化趨勢.

圖3 空間復雜度變化趨勢比較Figure 3 Trends comparison of space complexity

4 結(jié)束語

實驗結(jié)果表明，新算法保持了與現(xiàn)有的μC/OS-Ⅱ系統(tǒng)兼容，保留了現(xiàn)有算法的優(yōu)點，而且在算法的空間復雜度和系統(tǒng)可擴展性上還更具優(yōu)勢，并且該算法同樣還可以用于優(yōu)化μC/OS-Ⅱ的事件控制塊中的等待任務調(diào)度算法，有助于μC/OS-Ⅱ在更多更復雜的嵌入式應用場合中推廣.

參考文獻：

[1] KRISHNA C M, SHIN K G. 實時系統(tǒng)[M].戴瓊海，譯.北京:清華大學出版社,2004.

[2] 金宏,王宏安,王強,等.一種任務優(yōu)先級的綜合設計方法[J].軟件學報,2003,14(3):376-382.

JIN Hong, WANG Hongan, WANG Qiang, et al. An integrated design method of task priority[J].Journal of Software, 2003,14(3):376-382.

[3] 郭勐,黃江洪,王貞松.實時操作系統(tǒng)μC/OS-Ⅱ的多任務改進方法[J].計算機工程與應用,2005(12):5-7.

GUO Meng, HUANG Jianghong, WANG Zhensong. A novel method for multitask support on real-time operating system μC/OS-Ⅱ[J].Computer Engineering and Applications,2005(12):5-7.

[4] 熊玉梅,陳一民.μC/OS-Ⅱ任務調(diào)度算法的改進[J].計算機應用與軟件,2008,25(6):84-86.

XIONG Yumei, CHEN Yiming. An improved scheduling algorithm of μC/OS-Ⅱ[J].Computer Applications and Software,2008,25(6):84-86.

[5] 季虹,付少鋒,車向泉,等.實時嵌入式操作系統(tǒng)μC/OS-Ⅱ內(nèi)核的分析與改進[J].計算機工程,2007,33(16):246-250.

JI Hong, FU Shaofeng, CHE Xiangquan, et al. Analysis and improvement of real-time embedded operating system μC/OS-Ⅱ kernel[J].Computer Engineering,2007,33(16):246-250.

[6] LABROSSE J J. 嵌入式實時操作系統(tǒng)μC/OS-Ⅱ [M]. 2版.邵貝貝，譯.北京:北京航空航天大學出版社,2003.