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