μC/OS優(yōu)先級調(diào)度機制在PowerPC上的優(yōu)化

摘要: μC/OSII實時操作系統(tǒng)被移植到幾乎所有CPU上，在我國嵌入式領(lǐng)域頗具影響力。μC/OS和μC/OSII是為8位CPU設(shè)計的，對于具有優(yōu)先級算法硬件指令的32位中高端CPU，則應(yīng)該對其任務(wù)調(diào)度算法做進(jìn)一步優(yōu)化，以得到更好的系統(tǒng)實時響應(yīng)。本文以一款PowerPC系列中的中低端單片機為例，說明如何使用優(yōu)先級算法硬件指令改進(jìn)任務(wù)調(diào)度算法。

關(guān)鍵詞: μC/OS；PowerPC；優(yōu)先級調(diào)度；前導(dǎo)零計算

Optimization of μC/OS Task Switching Scheme in PowerPC Architecture
Gong Guanghua1，Che Huijun2
(1. Dept. of Engineering Physics, Tsinghua Univ.，Beijing 100084,China；2. Beijing National Railway Research&Design Institute of Signal&Communication)
Abstract： Real?time multitask kernel μC/OS and μC/OSII are ported to almost all popular processors and are widely used in China. As originally designed for 8 bit microcontroller, the kernel is not aware of nor utilizes the hardware priority calculation instruction that exists in some high?performance 32 bit microcontroller families. Based on MPC5554 from Freescale PowerPC embedded microcontroller, this article shows how the hardware priority calculation instruction is used to improve the system response latency.
Key words: μC/OS; PowerPC; task switching; count leading zero instruction

　　μC/OS是Jean J.Labrosse開發(fā)的實時多任務(wù)內(nèi)核，最初是為Motorola 8位處理器68HC11寫的。在后來的相關(guān)著作中，作者將代碼移植到了PC上，以便于更多的讀者學(xué)習(xí)。μC/OSII繼承了μC/OS的算法，有執(zhí)行效率高、占用空間小、實時性強和可擴展性好等特點，被移植到幾乎所有類型的CPU上，成為在嵌入式領(lǐng)域非常有影響力的RTOS。然而，由于該實時內(nèi)核是為8位CPU設(shè)計的，對于那些具有優(yōu)先級算法硬件指令的CPU，僅做移植是很不夠的。

1  基于優(yōu)先級的任務(wù)調(diào)度

　　一個基于優(yōu)先級的實時多任務(wù)內(nèi)核的任務(wù)調(diào)度機制需要實現(xiàn)下面三個核心的處理功能：

◆ 將任務(wù)置于就緒態(tài)；
◆ 將任務(wù)取消就緒態(tài)；
◆ 找出最高優(yōu)先級的就緒態(tài)任務(wù)。

　　在32位機上運行64個任務(wù)，可使用兩個32位的整型變量數(shù)組OSRdyTbl [2]，建立一個64位的任務(wù)就緒態(tài)向量;每一位表示對應(yīng)優(yōu)先級的任務(wù)是否處于就緒態(tài)，例如OSRdyTbl [0]的第4位為1表示優(yōu)先級為4的任務(wù)處于就緒態(tài)。構(gòu)造如下的三個函數(shù)，用來完成設(shè)置任務(wù)就緒、取消任務(wù)就緒和尋找當(dāng)前最高優(yōu)先級的就緒任務(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)先級的就緒態(tài)任務(wù)*/
　　INT32U temp;//中間變量
　　INT8Uprio=0;
　　if(OSRdyTbl[0] != 0){
　　　　temp = OSRdyTbl[0];//就緒態(tài)任務(wù)中優(yōu)先級最高者在OSRdyTbl[0]中
　　}
　　else{
　　　　temp = OSRdyTbl[1]; //就緒態(tài)任務(wù)中優(yōu)先級最高者在OSRdyTbl[1]中
　　　　prio +=32;
　　}
　　while(temp <0x80000000){//逐位查找就緒態(tài)任務(wù)中優(yōu)先級最高者
　　　　temp <<=1;
　　　　prio ++;
　　}
　　return(prio);
}

　　上述代碼可在任何處理器上實現(xiàn)所需的功能，沒有考慮任何的優(yōu)化和改進(jìn)。通過這樣的原理性函數(shù)，可以更好地理解多任務(wù)內(nèi)核的任務(wù)調(diào)度。

　　尋找最高優(yōu)先級就緒態(tài)任務(wù)的函數(shù)調(diào)用頻率高，其執(zhí)行時間直接影響內(nèi)核的任務(wù)切換延遲時間，影響系統(tǒng)實時性。上述尋找最高優(yōu)先級的就緒態(tài)任務(wù)的代碼，隨當(dāng)前就緒任務(wù)的優(yōu)先級不同，其循環(huán)次數(shù)也不同，導(dǎo)致其運行時間不確定。[!--empirenews.page--]

2  μC/OS的任務(wù)調(diào)度實現(xiàn)方法

　　μC/OS和μC/OSII是為8位CPU寫的，采用8位機算法，支持64個任務(wù)。使用8個字節(jié)的OSRdyTbl全局?jǐn)?shù)組，表示所有任務(wù)的就緒態(tài)信息：1為任務(wù)就緒，0為非就緒。數(shù)組第一個字節(jié)的b0位代表64個任務(wù)中優(yōu)先級最高的任務(wù)，最后一個字節(jié)的b7位代表優(yōu)先級最低的空閑任務(wù)，永遠(yuǎn)為1。當(dāng)OSRdyTbl 數(shù)組的數(shù)據(jù)不為0時（表示對應(yīng)的8個任務(wù)中至少有1個進(jìn)入就緒態(tài)），另一個單字節(jié)全局變量OSRdyGrp 中的相應(yīng)位要置1。當(dāng)任務(wù)狀態(tài)發(fā)生變化時，需更新OSRdyGrp和OSRdyTbl中對應(yīng)的位。

　　尋找最高優(yōu)先級的就緒任務(wù)時，μC/OS使用了預(yù)先固化的256字節(jié)的對照表OSUnMapTbl，給出特定字節(jié)值的最低位1所在位的信息。查表算法避免了逐位檢測各優(yōu)先級位引起的執(zhí)行時間的不確定性，程序簡單，執(zhí)行速度快，與就緒任務(wù)多少和優(yōu)先級無關(guān)。

　　對于取值0～63的任務(wù)優(yōu)先級，μC/OS將其劃分成高3位的Y和低3位的X，并保存在其任務(wù)控制塊TCB的OSTCBX和OSTCBY中，其對應(yīng)的OSUnMapTbl的值保存在OSTCBBitY和OSTCBBitX變量中，以提高運算速度。為了避免函數(shù)調(diào)用所帶來的額外開銷，μC/OS直接用語句實現(xiàn)如下的三部分功能。

① 設(shè)置任務(wù)進(jìn)入就緒態(tài)

OSRdyGrp |= ptcb?>OSTCBBitY;
OSRdyTbl[ptcb?﹥OSTCBY] |= ptcb?>OSTCBBitX;

② 設(shè)置任務(wù)退出就緒態(tài)。

y = OSTCBCur?>OSTCBY;
OSRdyTbl[y] &= ~OSTCBCur?>OSTCBBitX;
if (OSRdyTbl[y] == 0) {
　　OSRdyGrp &= ~OSTCBCur?>OSTCBBitY;
}

③ 尋找最高優(yōu)先級的就緒態(tài)任務(wù)。以O(shè)SRdyGrp的值做偏移量，查OSUnMapTbl表，得到1個0到7的數(shù)Y，作為優(yōu)先級高3位，再根據(jù)Y的值，找出OSRdyTbl中對應(yīng)的字節(jié)，并且再次查OSUnMapTbl表，得到1個0到7的數(shù)X，作為優(yōu)先級低3位的值，通過將Y左移3位再加上X的值，得到就緒任務(wù)中優(yōu)先級最高的那個。

y = OSUnMapTbl[OSRdyGrp];
OSPrioHighRdy = (INT8U)((y << 3) + OSUnMapTbl[OSRdyTbl[y]]);

　　μC/OS的任務(wù)調(diào)度算法采用了以空間換時間的策略，將特定字節(jié)值的最低位1所在位的信息預(yù)先計算并保存到表中，運行時通過查表快速得到；每個任務(wù)的TCB中除了保存優(yōu)先級信息本身外，還使用額外的4個字節(jié)保存優(yōu)先級的高低3位和對應(yīng)的OSUnMapTbl值，以避免運行時實時計算這幾個值所帶來的延遲。這些措施增加了系統(tǒng)ROM和RAM的開銷。

3  利用PowerPC“數(shù)出前導(dǎo)零數(shù)目”指令實現(xiàn)任務(wù)調(diào)度

　　PowerPC是Motorola 、IBM和Apple三家公司于20世紀(jì)90年代初期聯(lián)合設(shè)計的32位CPU。Freescale（其前身是Motorola半導(dǎo)體部）發(fā)展了針對汽車電子的MPC5xx系列單片機及后續(xù)基于e200內(nèi)核的MPC5xxx系列單片機；更高端的e500、e600內(nèi)核是用于通信領(lǐng)域的MPC6xxx、7xxx和8xxx系列。

　　下面對μC/OS任務(wù)優(yōu)先級調(diào)度算法的改進(jìn)和優(yōu)化是在MPC5554單片機上實現(xiàn)的。

　　PowerPC處理器具有一條“數(shù)出前導(dǎo)零數(shù)目” 的指令cntlzw(count leading zero word)，可以以硬件指令方式實現(xiàn)優(yōu)先級的多任務(wù)調(diào)度算法。這條指令也可用于圖像處理和算法加密的場合。該指令數(shù)出一個32位寄存器中前置零的數(shù)目，例如，返回0表示b0不為零，即沒有前導(dǎo)零；返回3表示b3不為零，b3位的前面從b0到b2共有3個零；返回32表示RS寄存器中所有的位都為零。（在PowerPC架構(gòu)中，最高位MSB表示為b0，低位MSB根據(jù)位寬表示為b7、b15或b31。）

　　利用這條指令，用匯編語言改寫尋找最高優(yōu)先級的就緒任務(wù)的函數(shù)，則不需要進(jìn)行循環(huán)移位判斷，可以直接從64個任務(wù)中找出優(yōu)先級最高的那個任務(wù)。代碼如下：

asm INT8U FindHighestRdyTask(void){
　　lisr5,OSRdyTbl@ha//讓r5寄存器指向OSRdyTbl[]
　　orir5,r5,OSRdyTbl@l
　　lwzr3,0(r5)//將OSRdyTbl[0]的值載入r3寄存器
　　cntlzwr3,r3//計算OSRdyTbl[0]中前導(dǎo)零數(shù)目
　　cmpi0,0,r3,32//判斷前32個任務(wù)是否就緒
　　bne __FindEnd//如果前導(dǎo)零數(shù)目為32，說明前32個任務(wù)均未就緒，需要從后32個任務(wù)中尋找
　　lwzr4,4(r5)//將OSRdyTbl[1]的值載入r4寄存器
　　cntlzwr4,r4//計算OSRdyTbl[1]的前導(dǎo)零數(shù)目
　　addir3,r4,32//后32個任務(wù)需要加上偏移量
　　__FindEnd:
　　blr //返回值保存在r3寄存器中
}[!--empirenews.page--]

　　在這段代碼中，首先判斷前32個任務(wù)是否有處于就緒態(tài)的，如果沒有的話，再對后32個任務(wù)進(jìn)行判斷。由于優(yōu)先級最低的空閑任務(wù)總是處于就緒態(tài)，所以后32個任務(wù)總能返回一個有效值。該代碼在前32個任務(wù)有就緒態(tài)時運行7條指令，在前32個任務(wù)均沒有就緒時需要執(zhí)行10條指令；而μC/OS原有的代碼編譯出來的匯編程序，則需要運行15條指令。

　　使用這個方法的另一個好處是不再需要使用256字節(jié)的OSUnMapTbl表，任務(wù)控制塊TCB也不需要使用OSTCBX、OSTCBY和OSTCBBitY、OSTCBBitX變量，每個ECB中也不再需要OSRdyGrp，這也減少了對ROM和RAM的占用。

4  改進(jìn)擴展任務(wù)數(shù)的優(yōu)先級調(diào)度性能

　　當(dāng)對μC/OSII支持的任務(wù)數(shù)進(jìn)行擴展時，按照μC/OSII原有的做法，需要按照高低字節(jié)分別查找OSUnMapTbl對照表。任務(wù)數(shù)為256時，尋找最高優(yōu)先級就緒任務(wù)的函數(shù)將需要運行約35條指令。數(shù)出前導(dǎo)零數(shù)目的指令在這種情況下的作用將更加顯著，對于32位PowerPC處理器，精心設(shè)計的代碼可以做到僅需10條指令就將任務(wù)數(shù)擴展到1024個。

　　此時OSRdyGrp擴展為32位，OSrdyTbl擴展成32個32位的數(shù)組。從OSRdyGrp得到的前導(dǎo)零數(shù)目，就是任務(wù)優(yōu)先級高5位的值，乘以4可以得到該字的相對偏移地址；在OSRdyTbl中，定義高位對應(yīng)高優(yōu)先級任務(wù)，低位對應(yīng)低優(yōu)先級任務(wù)，則其前導(dǎo)零數(shù)目就是任務(wù)優(yōu)先級低5位的值，和高5位的值移位相加就得到完整的任務(wù)優(yōu)先級。通過將OSRdyGrp和OSRdyTbl定義成結(jié)構(gòu)體，利用結(jié)構(gòu)體首地址的相對尋址來分別讀取其數(shù)值，可以減少一次取地址的操作。

　　尋找最高優(yōu)先級就緒態(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
　　lwzr3,128(r5)//OSRdy.Grp在結(jié)構(gòu)體中具有固定偏移量
　　cntlzwr3,r3//數(shù)出OSRdyGrp的前導(dǎo)零數(shù)目
　　slwir6,r3,2//得到OSRdyTbl的地址偏移量
　　lwzxr4,r6,r5//通過結(jié)構(gòu)體指針，讀取OSRdy.Tbl的對應(yīng)字
　　cntlzwr4,r4//計算OSRdyTbl對應(yīng)字的前導(dǎo)零數(shù)目
　　slwir3,r3,5//任務(wù)優(yōu)先級高5位移位
　　addr3,r4,r3//和優(yōu)先級低5位相加，得到完整優(yōu)先級
　　blr//返回
}

　　在64位的PowerPC 更有cntlzd(Count Leading Zero Double word)指令，一次就可以找出64個任務(wù)中優(yōu)先級最高的那個，就更沒有必要使用μC/OS?II中的算法了。

5  總結(jié)

　　RTOS實時內(nèi)核μC/OS和μC/OS?II中，任務(wù)調(diào)度算法巧妙，性能優(yōu)異，在嵌入式應(yīng)用領(lǐng)域很有影響力，被移植到各種CPU上。然而由于是為8位CPU設(shè)計的，對于那些具有優(yōu)先級硬件算法指令的16/32/64位CPU，μC/OS?II的軟件算法就完全失去了優(yōu)勢。應(yīng)該利用這類CPU的特有指令，優(yōu)化任務(wù)調(diào)度算法，使RTOS的實時性達(dá)到最佳。對于這類處理器，僅移植μC/OS?II軟件算法是很不夠的，應(yīng)該利用相關(guān)硬件算法指令。