uCOS-II優(yōu)先級任務(wù)調(diào)度在PowerPC上的移植和優(yōu)化

uCOS-II優(yōu)先級任務(wù)調(diào)度在PowerPC上的移植和優(yōu)化μC/OS是JeanJ.Labrosse開發(fā)的實(shí)時多任務(wù)內(nèi)核，最初是為Motorola8位處理器68HC11寫的。在后來的相關(guān)著作中，作者將代碼移植到了PC上，以便于更多的讀者學(xué)習(xí)。μC/OSII繼承了μC/OS的算法，有執(zhí)行效率高、占用空間小、實(shí)時性強(qiáng)和可擴(kuò)展性好等特點(diǎn)，被移植到幾乎所有類型的CPU上，成為在嵌入式領(lǐng)域非常有影響力的RTOS。然而，由于該實(shí)時內(nèi)核是為8位CPU設(shè)計(jì)的，對于那些具有優(yōu)先級算法硬件指令的CPU，僅做移植是很不夠的。

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

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

◆將任務(wù)置于就緒態(tài)；

◆將任務(wù)取消就緒態(tài)；

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

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

上述代碼可在任何處理器上實(shí)現(xiàn)所需的功能，沒有考慮任何的優(yōu)化和改進(jìn)。通過這樣的原理性函數(shù)，可以更好地理解多任務(wù)內(nèi)核的任務(wù)調(diào)度。尋找最高優(yōu)先級就緒態(tài)任務(wù)的函數(shù)調(diào)用頻率高，其執(zhí)行時間直接影響內(nèi)核的任務(wù)切換延遲時間，影響系統(tǒng)實(shí)時性。上述尋找最高優(yōu)先級的就緒態(tài)任務(wù)的代碼，隨當(dāng)前就緒任務(wù)的優(yōu)先級不同，其循環(huán)次數(shù)也不同，導(dǎo)致其運(yùn)行時間不確定。

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

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

尋找最高優(yōu)先級的就緒任務(wù)時，μC/OS使用了預(yù)先固化的256字節(jié)的對照表OSUnMapTbl，給出特定字節(jié)值的最低位1所在位的信息。查表算法避免了逐位檢測各優(yōu)先級位引起的執(zhí)行時間的不確定性，程序簡單，執(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個0到7的數(shù)Y，作為優(yōu)先級高3位，再根據(jù)Y的值，找出OSRdyTbl中對應(yīng)的字節(jié)，并且再次查OSUnMapTbl表，得到1個0到7的數(shù)X，作為優(yōu)先級低3位的值，通過將Y左移3位再加上X的值，得到就緒任務(wù)中優(yōu)先級最高的那個。

y=OSUnMapTbl[OSRdyGrp];

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

μC/OS的任務(wù)調(diào)度算法采用了以空間換時間的策略，將特定字節(jié)值的最低位1所在位的信息預(yù)先計(jì)算并保存到表中，運(yùn)行時通過查表快速得到；每個任務(wù)的TCB中除了保存優(yōu)先級信息本身外，還使用額外的4個字節(jié)保存優(yōu)先級的高低3位和對應(yīng)的OSUnMapTbl值，以避免運(yùn)行時實(shí)時計(jì)算這幾個值所帶來的延遲。這些措施增加了系統(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(countleADIngzeroword)，可以以硬件指令方式實(shí)現(xiàn)優(yōu)先級的多任務(wù)調(diào)度算法。這條指令也可用于圖像處理和算法加密的場合。該指令數(shù)出一個32位寄存器中前置零的數(shù)目，例如，返回0表示b0不為零，即沒有前導(dǎo)零；返回3表示b3不為零，b3位的前面從b0到b2共有3個零；返回32表示RS寄存器中所有的位都為零。（在PowerPC架構(gòu)中，最高位MSB表示為b0，低位MSB根據(jù)位寬表示為b7、b15或b31。）

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

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

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

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

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

此時OSRdyGrp擴(kuò)展為32位，OSrdyTbl擴(kuò)展成32個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)的最終代碼如下：

在64位的PowerPC更有cntlzd(CountLeadingZeroDoubleword)指令，一次就可以找出64個任務(wù)中優(yōu)先級最高的那個，就更沒有必要使用μC/OSII中的算法了。

5總結(jié)

RTOS實(shí)時內(nèi)核μC/OS和μC/OSII中，任務(wù)調(diào)度算法巧妙，性能優(yōu)異，在嵌入式應(yīng)用領(lǐng)域很有影響力，被移植到各種