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

關(guān)鍵詞: μC/OS；PowerPC；優(yōu)先級調(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開發(fā)的實(shí)時(shí)多任務(wù)內(nèi)核，最初是為Motorola 8位處理器68HC11寫的。在后來的相關(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ì)的，對于那些具有優(yōu)先級算法硬件指令的CPU，僅做移植是很不夠的。

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

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

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

　　在32位機(jī)上運(yùn)行64個(gè)任務(wù)，可使用兩個(gè)32位的整型變量數(shù)組OSRdyTbl [2]，建立一個(gè)64位的任務(wù)就緒態(tài)向量;每一位表示對應(yīng)優(yōu)先級的任務(wù)是否處于就緒態(tài)，例如OSRdyTbl [0]的第4位為1表示優(yōu)先級為4的任務(wù)處于就緒態(tài)。構(gòu)造如下的三個(gè)函數(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);
}

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

　　尋找最高優(yōu)先級就緒態(tài)任務(wù)的函數(shù)調(diào)用頻率高，其執(zhí)行時(shí)間直接影響內(nèi)核的任務(wù)切換延遲時(shí)間，影響系統(tǒng)實(shí)時(shí)性。上述尋找最高優(yōu)先級的就緒態(tài)任務(wù)的代碼，隨當(dāng)前就緒任務(wù)的優(yōu)先級不同，其循環(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寫的，采用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)先級最高的任務(wù)，最后一個(gè)字節(jié)的b7位代表優(yōu)先級最低的空閑任務(wù)，永遠(yuǎn)為1。當(dāng)OSRdyTbl 數(shù)組的數(shù)據(jù)不為0時(shí)（表示對應(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中對應(yīng)的位。

　　尋找最高優(yōu)先級的就緒任務(wù)時(shí)，μC/OS使用了預(yù)先固化的256字節(jié)的對照表OSUnMapTbl，給出特定字節(jié)值的最低位1所在位的信息。查表算法避免了逐位檢測各優(yōu)先級位引起的執(zhí)行時(shí)間的不確定性，程序簡單，執(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變量中，以提高運(yùn)算速度。為了避免函數(shù)調(diào)用所帶來的額外開銷，μC/OS直接用語句實(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)先級的就緒態(tài)任務(wù)。以O(shè)SRdyGrp的值做偏移量，查OSUnMapTbl表，得到1個(gè)0到7的數(shù)Y，作為優(yōu)先級高3位，再根據(jù)Y的值，找出OSRdyTbl中對應(yīng)的字節(jié)，并且再次查OSUnMapTbl表，得到1個(gè)0到7的數(shù)X，作為優(yōu)先級低3位的值，通過將Y左移3位再加上X的值，得到就緒任務(wù)中優(yōu)先級最高的那個(gè)。

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

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

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ā)展了針對汽車電子的MPC5xx系列單片機(jī)及后續(xù)基于e200內(nèi)核的MPC5xxx系列單片機(jī)；更高端的e500、e600內(nèi)核是用于通信領(lǐng)域的MPC6xxx、7xxx和8xxx系列。

　　下面對μC/OS任務(wù)優(yōu)先級調(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)先級的多任務(wù)調(diào)度算法。這條指令也可用于圖像處理和算法加密的場合。該指令數(shù)出一個(gè)32位寄存器中前置零的數(shù)目，例如，返回0表示b0不為零，即沒有前導(dǎo)零；返回3表示b3不為零，b3位的前面從b0到b2共有3個(gè)零；返回32表示RS寄存器中所有的位都為零。（在PowerPC架構(gòu)中，最高位MSB表示為b0，低位MSB根據(jù)位寬表示為b7、b15或b31。）

　　利用這條指令，用匯編語言改寫尋找最高優(yōu)先級的就緒任務(wù)的函數(shù)，則不需要進(jìn)行循環(huán)移位判斷，可以直接從64個(gè)任務(wù)中找出優(yōu)先級最高的那個(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，說明前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)的，如果沒有的話，再對后32個(gè)任務(wù)進(jìn)行判斷。由于優(yōu)先級最低的空閑任務(wù)總是處于就緒態(tài)，所以后32個(gè)任務(wù)總能返回一個(gè)有效值。該代碼在前32個(gè)任務(wù)有就緒態(tài)時(shí)運(yùn)行7條指令，在前32個(gè)任務(wù)均沒有就緒時(shí)需要執(zhí)行10條指令；而μC/OS原有的代碼編譯出來的匯編程序，則需要運(yùn)行15條指令。

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

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

　　當(dāng)對μC/OSII支持的任務(wù)數(shù)進(jìn)行擴(kuò)展時(shí)，按照μC/OSII原有的做法，需要按照高低字節(jié)分別查找OSUnMapTbl對照表。任務(wù)數(shù)為256時(shí)，尋找最高優(yōu)先級就緒任務(wù)的函數(shù)將需要運(yùn)行約35條指令。數(shù)出前導(dǎo)零數(shù)目的指令在這種情況下的作用將更加顯著，對于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)先級高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//計(jì)算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個(gè)任務(wù)中優(yōu)先級最高的那個(gè)，就更沒有必要使用μ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ì)的，對于那些具有優(yōu)先級硬件算法指令的16/32/64位CPU，μC/OS?II的軟件算法就完全失去了優(yōu)勢。應(yīng)該利用這類CPU的特有指令，優(yōu)化任務(wù)調(diào)度算法，使RTOS的實(shí)時(shí)性達(dá)到最佳。對于這類處理器，僅移植μC/OS?II軟件算法是很不夠的，應(yīng)該利用相關(guān)硬件算法指令。