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

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

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

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開(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)，被移植到幾乎所有類型的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í)間不確定。[!--empirenews.page--]

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)銷，μC/OS直接用語(yǔ)句實(shí)現(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)先級(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];
OSPrioHighRdy = (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)銷。

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寄存器中
}[!--empirenews.page--]

　　在這段代碼中，首先判斷前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
　　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)該利用這類CPU的特有指令，優(yōu)化任務(wù)調(diào)度算法，使RTOS的實(shí)時(shí)性達(dá)到最佳。對(duì)于這類處理器，僅移植μC/OS?II軟件算法是很不夠的，應(yīng)該利用相關(guān)硬件算法指令。