μ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];

　　SPrioHighRdy = (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軟件算法是很不夠的，應該利用相關硬件算法指令。