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

關鍵詞: μC/OS；PowerPC；優(yōu)先級調(dià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ā)的實時多任務內(nèi)核，最初是為Motorola 8位處理器68HC11寫的。在后來的相關著作中，作者將代碼移植到了PC上，以便于更多的讀者學習。μC/OSII繼承了μC/OS的算法，有執(zhí)行效率高、占用空間小、實時性強和可擴展性好等特點，被移植到幾乎所有類型的CPU上，成為在嵌入式領域非常有影響力的RTOS。然而，由于該實時內(nèi)核是為8位CPU設計的，對于那些具有優(yōu)先級算法硬件指令的CPU，僅做移植是很不夠的。

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

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

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

　　在32位機上運行64個任務，可使用兩個32位的整型變量數(shù)組OSRdyTbl [2]，建立一個64位的任務就緒態(tài)向量;每一位表示對應優(yōu)先級的任務是否處于就緒態(tài)，例如OSRdyTbl [0]的第4位為1表示優(yōu)先級為4的任務處于就緒態(tài)。構造如下的三個函數(shù)，用來完成設置任務就緒、取消任務就緒和尋找當前最高優(yōu)先級的就緒任務。

void SetTaskRdyBit(INT8U Prio){/*設置任務就緒態(tài)*/
　　if(Prio>32) OSRdyTbl [1] |= (1 << (63Prio) );
　　else OSRdyTbl [0] |= (1 << (31Prio) );
}
void ClrTaskRdyBit(INT8U Prio){ /*取消任務就緒態(tài)*/
　　if(Prio>32) OSRdyTbl[1] &= ~(1 << (63Prio) );
　　else OSRdyTbl[0] &= ~(1 << (31Prio) );
}
INT8U FindHighestRdyTask(void){ /*尋找最高優(yōu)先級的就緒態(tài)任務*/
　　INT32U temp;//中間變量
　　INT8Uprio=0;
　　if(OSRdyTbl[0] != 0){
　　　　temp = OSRdyTbl[0];//就緒態(tài)任務中優(yōu)先級最高者在OSRdyTbl[0]中
　　}
　　else{
　　　　temp = OSRdyTbl[1]; //就緒態(tài)任務中優(yōu)先級最高者在OSRdyTbl[1]中
　　　　prio +=32;
　　}
　　while(temp <0x80000000){//逐位查找就緒態(tài)任務中優(yōu)先級最高者
　　　　temp <<=1;
　　　　prio ++;
　　}
　　return(prio);
}

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

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

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

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

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

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

① 設置任務進入就緒態(tài)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　尋找最高優(yōu)先級就緒態(tài)的最終代碼如下：

typedef struct {//定義結構體
　　INT32U Tbl[32];
　　INT32U Grp;
} OSTaskRdyBlock;
OSTaskRdyBlock  OSRdy;//定義全局變量OSRdy
asm INT16U FindHighestRdyTask(void){
　　lisr5,OSRdy@ha//將OSRdy結構體指針載入r5寄存器
　　orir5,r5,OSRdy@l
　　lwzr3,128(r5)//OSRdy.Grp在結構體中具有固定偏移量
　　cntlzwr3,r3//數(shù)出OSRdyGrp的前導零數(shù)目
　　slwir6,r3,2//得到OSRdyTbl的地址偏移量
　　lwzxr4,r6,r5//通過結構體指針，讀取OSRdy.Tbl的對應字
　　cntlzwr4,r4//計算OSRdyTbl對應字的前導零數(shù)目
　　slwir3,r3,5//任務優(yōu)先級高5位移位
　　addr3,r4,r3//和優(yōu)先級低5位相加，得到完整優(yōu)先級
　　blr//返回
}

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

5  總結

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