μC/OS的任務(wù)調(diào)度實(shí)現(xiàn)方法及PowerPC上的優(yōu)化
μC/OS是Jean J.Labrosse開(kāi)發(fā)的實(shí)時(shí)多任務(wù)內(nèi)核,最初是為Motorola 8位處理器68HC11寫(xiě)的。在后來(lái)的相關(guān)著作中,作者將代碼移植到了PC上,以便于更多的讀者學(xué)習(xí)。μC/OSII繼承了μC/OS的算法,有執(zhí)行效率高、占用空間小、實(shí)時(shí)性強(qiáng)和可擴(kuò)展性好等特點(diǎn),被移植到幾乎所有類(lèi)型的CPU上,成為在嵌入式領(lǐng)域非常有影響力的RTOS。然而,由于該實(shí)時(shí)內(nèi)核是為8位CPU設(shè)計(jì)的,對(duì)于那些具有優(yōu)先級(jí)算法硬件指令的CPU,僅做移植是很不夠的。
1 基于優(yōu)先級(jí)的任務(wù)調(diào)度
一個(gè)基于優(yōu)先級(jí)的實(shí)時(shí)多任務(wù)內(nèi)核的任務(wù)調(diào)度機(jī)制需要實(shí)現(xiàn)下面三個(gè)核心的處理功能:
◆ 將任務(wù)置于就緒態(tài);
◆ 將任務(wù)取消就緒態(tài);
◆ 找出最高優(yōu)先級(jí)的就緒態(tài)任務(wù)。
在32位機(jī)上運(yùn)行64個(gè)任務(wù),可使用兩個(gè)32位的整型變量數(shù)組OSRdyTbl [2],建立一個(gè)64位的任務(wù)就緒態(tài)向量;每一位表示對(duì)應(yīng)優(yōu)先級(jí)的任務(wù)是否處于就緒態(tài),例如OSRdyTbl [0]的第4位為1表示優(yōu)先級(jí)為4的任務(wù)處于就緒態(tài)。構(gòu)造如下的三個(gè)函數(shù),用來(lái)完成設(shè)置任務(wù)就緒、取消任務(wù)就緒和尋找當(dāng)前最高優(yōu)先級(jí)的就緒任務(wù)。
void SetTaskRdyBit(INT8U Prio){/*設(shè)置任務(wù)就緒態(tài)*/
if(Prio>32) OSRdyTbl [1] |= (1 << (63?Prio) );
else OSRdyTbl [0] |= (1 << (31?Prio) );
}
void ClrTaskRdyBit(INT8U Prio){ /*取消任務(wù)就緒態(tài)*/
if(Prio>32) OSRdyTbl[1] &= ~(1 << (63?Prio) );
else OSRdyTbl[0] &= ~(1 << (31?Prio) );
}
INT8U FindHigheSTRdyTask(void){ /*尋找最高優(yōu)先級(jí)的就緒態(tài)任務(wù)*/
INT32U temp;//中間變量
INT8Uprio=0;
if(OSRdyTbl[0] != 0){
temp = OSRdyTbl[0];//就緒態(tài)任務(wù)中優(yōu)先級(jí)最高者在OSRdyTbl[0]中
}
else{
temp = OSRdyTbl[1]; //就緒態(tài)任務(wù)中優(yōu)先級(jí)最高者在OSRdyTbl[1]中
prio +=32;
}
while(temp <0x80000000){//逐位查找就緒態(tài)任務(wù)中優(yōu)先級(jí)最高者
temp <<=1;
prio ++;
}
return(prio);
}
上述代碼可在任何處理器上實(shí)現(xiàn)所需的功能,沒(méi)有考慮任何的優(yōu)化和改進(jìn)。通過(guò)這樣的原理性函數(shù),可以更好地理解多任務(wù)內(nèi)核的任務(wù)調(diào)度。
尋找最高優(yōu)先級(jí)就緒態(tài)任務(wù)的函數(shù)調(diào)用頻率高,其執(zhí)行時(shí)間直接影響內(nèi)核的任務(wù)切換延遲時(shí)間,影響系統(tǒng)實(shí)時(shí)性。上述尋找最高優(yōu)先級(jí)的就緒態(tài)任務(wù)的代碼,隨當(dāng)前就緒任務(wù)的優(yōu)先級(jí)不同,其循環(huán)次數(shù)也不同,導(dǎo)致其運(yùn)行時(shí)間不確定。
2 μC/OS的任務(wù)調(diào)度實(shí)現(xiàn)方法
μC/OS和μC/OSII是為8位CPU寫(xiě)的,采用8位機(jī)算法,支持64個(gè)任務(wù)。使用8個(gè)字節(jié)的OSRdyTbl全局?jǐn)?shù)組,表示所有任務(wù)的就緒態(tài)信息:1為任務(wù)就緒,0為非就緒。數(shù)組第一個(gè)字節(jié)的b0位代表64個(gè)任務(wù)中優(yōu)先級(jí)最高的任務(wù),最后一個(gè)字節(jié)的b7位代表優(yōu)先級(jí)最低的空閑任務(wù),永遠(yuǎn)為1。當(dāng)OSRdyTbl 數(shù)組的數(shù)據(jù)不為0時(shí)(表示對(duì)應(yīng)的8個(gè)任務(wù)中至少有1個(gè)進(jìn)入就緒態(tài)),另一個(gè)單字節(jié)全局變量OSRdyGrp 中的相應(yīng)位要置1。當(dāng)任務(wù)狀態(tài)發(fā)生變化時(shí),需更新OSRdyGrp和OSRdyTbl中對(duì)應(yīng)的位。
尋找最高優(yōu)先級(jí)的就緒任務(wù)時(shí),μC/OS使用了預(yù)先固化的256字節(jié)的對(duì)照表OSUnMapTbl,給出特定字節(jié)值的最低位1所在位的信息。查表算法避免了逐位檢測(cè)各優(yōu)先級(jí)位引起的執(zhí)行時(shí)間的不確定性,程序簡(jiǎn)單,執(zhí)行速度快,與就緒任務(wù)多少和優(yōu)先級(jí)無(wú)關(guān)。
對(duì)于取值0~63的任務(wù)優(yōu)先級(jí),μC/OS將其劃分成高3位的Y和低3位的X,并保存在其任務(wù)控制塊TCB的OSTCBX和OSTCBY中,其對(duì)應(yīng)的OSUnMapTbl的值保存在OSTCBBitY和OSTCBBitX變量中,以提高運(yùn)算速度。為了避免函數(shù)調(diào)用所帶來(lái)的額外開(kāi)銷(xiāo),μC/OS直接用語(yǔ)句實(shí)現(xiàn)如下的三部分功能。
?、?設(shè)置任務(wù)進(jìn)入就緒態(tài)
OSRdyGrp |= ptcb?>OSTCBBitY;
OSRdyTbl[ptcb?﹥OSTCBY] |= ptcb?>OSTCBBitX;[!--empirenews.page--]
?、?設(shè)置任務(wù)退出就緒態(tài)。
y = OSTCBCur?>OSTCBY;
OSRdyTbl[y] &= ~OSTCBCur?>OSTCBBitX;
if (OSRdyTbl[y] == 0) {
OSRdyGrp &= ~OSTCBCur?>OSTCBBitY;
}
?、?尋找最高優(yōu)先級(jí)的就緒態(tài)任務(wù)。以O(shè)SRdyGrp的值做偏移量,查OSUnMapTbl表,得到1個(gè)0到7的數(shù)Y,作為優(yōu)先級(jí)高3位,再根據(jù)Y的值,找出OSRdyTbl中對(duì)應(yīng)的字節(jié),并且再次查OSUnMapTbl表,得到1個(gè)0到7的數(shù)X,作為優(yōu)先級(jí)低3位的值,通過(guò)將Y左移3位再加上X的值,得到就緒任務(wù)中優(yōu)先級(jí)最高的那個(gè)。
y = OSUnMapTbl[OSRdyGrp];
SPrioHighRdy = (INT8U)((y << 3) + OSUnMapTbl[OSRdyTbl[y]]);
μC/OS的任務(wù)調(diào)度算法采用了以空間換時(shí)間的策略,將特定字節(jié)值的最低位1所在位的信息預(yù)先計(jì)算并保存到表中,運(yùn)行時(shí)通過(guò)查表快速得到;每個(gè)任務(wù)的TCB中除了保存優(yōu)先級(jí)信息本身外,還使用額外的4個(gè)字節(jié)保存優(yōu)先級(jí)的高低3位和對(duì)應(yīng)的OSUnMapTbl值,以避免運(yùn)行時(shí)實(shí)時(shí)計(jì)算這幾個(gè)值所帶來(lái)的延遲。這些措施增加了系統(tǒng)ROM和RAM的開(kāi)銷(xiāo)。
3 利用PowerPC“數(shù)出前導(dǎo)零數(shù)目”指令實(shí)現(xiàn)任務(wù)調(diào)度
PowerPC是Motorola 、IBM和Apple三家公司于20世紀(jì)90年代初期聯(lián)合設(shè)計(jì)的32位CPU。Freescale(其前身是Motorola半導(dǎo)體部)發(fā)展了針對(duì)汽車(chē)電子的MPC5xx系列單片機(jī)及后續(xù)基于e200內(nèi)核的MPC5xxx系列單片機(jī);更高端的e500、e600內(nèi)核是用于通信領(lǐng)域的MPC6xxx、7xxx和8xxx系列。
下面對(duì)μC/OS任務(wù)優(yōu)先級(jí)調(diào)度算法的改進(jìn)和優(yōu)化是在MPC5554單片機(jī)上實(shí)現(xiàn)的。
PowerPC處理器具有一條“數(shù)出前導(dǎo)零數(shù)目” 的指令cntlzw(count leading zero word),可以以硬件指令方式實(shí)現(xiàn)優(yōu)先級(jí)的多任務(wù)調(diào)度算法。這條指令也可用于圖像處理和算法加密的場(chǎng)合。該指令數(shù)出一個(gè)32位寄存器中前置零的數(shù)目,例如,返回0表示b0不為零,即沒(méi)有前導(dǎo)零;返回3表示b3不為零,b3位的前面從b0到b2共有3個(gè)零;返回32表示RS寄存器中所有的位都為零。(在PowerPC架構(gòu)中,最高位MSB表示為b0,低位MSB根據(jù)位寬表示為b7、b15或b31。)
利用這條指令,用匯編語(yǔ)言改寫(xiě)尋找最高優(yōu)先級(jí)的就緒任務(wù)的函數(shù),則不需要進(jìn)行循環(huán)移位判斷,可以直接從64個(gè)任務(wù)中找出優(yōu)先級(jí)最高的那個(gè)任務(wù)。代碼如下:
asm INT8U FindHighestRdyTask(void){
lisr5,OSRdyTbl@ha//讓r5寄存器指向OSRdyTbl[]
orir5,r5,OSRdyTbl@l
lwzr3,0(r5)//將OSRdyTbl[0]的值載入r3寄存器
cntlzwr3,r3//計(jì)算OSRdyTbl[0]中前導(dǎo)零數(shù)目
cmpi0,0,r3,32//判斷前32個(gè)任務(wù)是否就緒
bne __FindEnd//如果前導(dǎo)零數(shù)目為32,說(shuō)明前32個(gè)任務(wù)均未就緒,需要從后32個(gè)任務(wù)中尋找
lwzr4,4(r5)//將OSRdyTbl[1]的值載入r4寄存器
cntlzwr4,r4//計(jì)算OSRdyTbl[1]的前導(dǎo)零數(shù)目
addir3,r4,32//后32個(gè)任務(wù)需要加上偏移量
__FindEnd:
blr //返回值保存在r3寄存器中
}
在這段代碼中,首先判斷前32個(gè)任務(wù)是否有處于就緒態(tài)的,如果沒(méi)有的話,再對(duì)后32個(gè)任務(wù)進(jìn)行判斷。由于優(yōu)先級(jí)最低的空閑任務(wù)總是處于就緒態(tài),所以后32個(gè)任務(wù)總能返回一個(gè)有效值。該代碼在前32個(gè)任務(wù)有就緒態(tài)時(shí)運(yùn)行7條指令,在前32個(gè)任務(wù)均沒(méi)有就緒時(shí)需要執(zhí)行10條指令;而μC/OS原有的代碼編譯出來(lái)的匯編程序,則需要運(yùn)行15條指令。
使用這個(gè)方法的另一個(gè)好處是不再需要使用256字節(jié)的OSUnMapTbl表,任務(wù)控制塊TCB也不需要使用OSTCBX、OSTCBY和OSTCBBitY、OSTCBBitX變量,每個(gè)ECB中也不再需要OSRdyGrp,這也減少了對(duì)ROM和RAM的占用。
4 改進(jìn)擴(kuò)展任務(wù)數(shù)的優(yōu)先級(jí)調(diào)度性能
當(dāng)對(duì)μC/OSII支持的任務(wù)數(shù)進(jìn)行擴(kuò)展時(shí),按照μC/OSII原有的做法,需要按照高低字節(jié)分別查找OSUnMapTbl對(duì)照表。任務(wù)數(shù)為256時(shí),尋找最高優(yōu)先級(jí)就緒任務(wù)的函數(shù)將需要運(yùn)行約35條指令。數(shù)出前導(dǎo)零數(shù)目的指令在這種情況下的作用將更加顯著,對(duì)于32位PowerPC處理器,精心設(shè)計(jì)的代碼可以做到僅需10條指令就將任務(wù)數(shù)擴(kuò)展到1024個(gè)。
此時(shí)OSRdyGrp擴(kuò)展為32位,OSrdyTbl擴(kuò)展成32個(gè)32位的數(shù)組。從OSRdyGrp得到的前導(dǎo)零數(shù)目,就是任務(wù)優(yōu)先級(jí)高5位的值,乘以4可以得到該字的相對(duì)偏移地址;在OSRdyTbl中,定義高位對(duì)應(yīng)高優(yōu)先級(jí)任務(wù),低位對(duì)應(yīng)低優(yōu)先級(jí)任務(wù),則其前導(dǎo)零數(shù)目就是任務(wù)優(yōu)先級(jí)低5位的值,和高5位的值移位相加就得到完整的任務(wù)優(yōu)先級(jí)。通過(guò)將OSRdyGrp和OSRdyTbl定義成結(jié)構(gòu)體,利用結(jié)構(gòu)體首地址的相對(duì)尋址來(lái)分別讀取其數(shù)值,可以減少一次取地址的操作。
尋找最高優(yōu)先級(jí)就緒態(tài)的最終代碼如下:
typedef struct {//定義結(jié)構(gòu)體
INT32U Tbl[32];
INT32U Grp;
} OSTaskRdyBlock;
OSTaskRdyBlock OSRdy;//定義全局變量OSRdy
asm INT16U FindHighestRdyTask(void){
lisr5,OSRdy@ha//將OSRdy結(jié)構(gòu)體指針載入r5寄存器
orir5,r5,OSRdy@l[!--empirenews.page--]
lwzr3,128(r5)//OSRdy.Grp在結(jié)構(gòu)體中具有固定偏移量
cntlzwr3,r3//數(shù)出OSRdyGrp的前導(dǎo)零數(shù)目
slwir6,r3,2//得到OSRdyTbl的地址偏移量
lwzxr4,r6,r5//通過(guò)結(jié)構(gòu)體指針,讀取OSRdy.Tbl的對(duì)應(yīng)字
cntlzwr4,r4//計(jì)算OSRdyTbl對(duì)應(yīng)字的前導(dǎo)零數(shù)目
slwir3,r3,5//任務(wù)優(yōu)先級(jí)高5位移位
addr3,r4,r3//和優(yōu)先級(jí)低5位相加,得到完整優(yōu)先級(jí)
blr//返回
}
在64位的PowerPC 更有cntlzd(Count Leading Zero Double word)指令,一次就可以找出64個(gè)任務(wù)中優(yōu)先級(jí)最高的那個(gè),就更沒(méi)有必要使用μC/OS?II中的算法了。
5 總結(jié)
RTOS實(shí)時(shí)內(nèi)核μC/OS和μC/OS?II中,任務(wù)調(diào)度算法巧妙,性能優(yōu)異,在嵌入式應(yīng)用領(lǐng)域很有影響力,被移植到各種CPU上。然而由于是為8位CPU設(shè)計(jì)的,對(duì)于那些具有優(yōu)先級(jí)硬件算法指令的16/32/64位CPU,μC/OS?II的軟件算法就完全失去了優(yōu)勢(shì)。應(yīng)該利用這類(lèi)CPU的特有指令,優(yōu)化任務(wù)調(diào)度算法,使RTOS的實(shí)時(shí)性達(dá)到最佳。對(duì)于這類(lèi)處理器,僅移植μC/OS?II軟件算法是很不夠的,應(yīng)該利用相關(guān)硬件算法指令。