摘要: μC/OSII是源碼公開的嵌入式實時操作系統(tǒng)，其任務(wù)調(diào)度算法的實現(xiàn)頗為精彩。本文對該算法做了簡要分析，指出對于一些有硬件算法指令的處理器，僅做移植并直接使用其軟件算法是不明智的，相關(guān)硬件指令為μC/OSII的優(yōu)化開辟了廣闊的空間。

μC/OS是由美國嵌入式系統(tǒng)專家Jean J. Labrosse 先生為嵌入式實時操作系統(tǒng)（RTOS）寫的實時內(nèi)核，最早連載在美國的《嵌入式系統(tǒng)編程》雜志1992 年5 月和6 月刊上，源碼發(fā)布在該雜志的BBS上。 該實時內(nèi)核最初是為MOTOROLA的8位單片機MC68HC11寫的，為便于普及，在后來關(guān)于μC/OS和μC/OSII的3本著作中，該內(nèi)核提供的是PC上的源碼。μC/OSII 比μC/OS增加了很多功能，在任務(wù)調(diào)度算法上并無不同，故本文提及任務(wù)調(diào)度算法時不再區(qū)分μC/OS和μC/OSII。

一項對我國嵌入式應(yīng)用工程師的統(tǒng)計表明，各類嵌入式應(yīng)用工程師正在研究和使用的操作系統(tǒng)中，Linux占38％，μC/OSII占34%，WinCE占16％，VxWorks占5％。這里，Linux加μC/OSII就超過了70％，這兩個操作系統(tǒng)對中國嵌入式應(yīng)用領(lǐng)域的影響可見一斑。它們的共同特點是源碼公開。Linux不是實時的，也不是為嵌入式系統(tǒng)專門設(shè)計的，而μC/OSII是專門為嵌入式應(yīng)用設(shè)計的實時操作系統(tǒng)。將μC/OSII嵌入到產(chǎn)品中用于牟利是要對使用權(quán)付費的，國內(nèi)一些信譽好的企業(yè)購買μC/OSII使用權(quán)的例子很多，而一些不大重視信譽和知識產(chǎn)權(quán)的企業(yè)也不在少數(shù)。

μC/OSII用于教學(xué)與研究是免費的。近些年來，我國各類大學(xué)的嵌入式系統(tǒng)教學(xué)中紛紛采用μC/OSII作為教材。而μC/OSII也被移植到幾乎所有的CPU上。各類雜志上發(fā)表的相關(guān)論文也數(shù)目可觀，雖然大部分論文只談到移植。

μC/OSII是為8位 CPU寫的RTOS小內(nèi)核，任務(wù)調(diào)度算法巧妙，移植到任何處理器上都很好用。而對于一些有RTOS優(yōu)先級算法硬件指令的16/32/64位的處理器，照搬μC/OSII的8位算法、強行移植μC/OSII未必恰當(dāng)。

1 μC/OS的調(diào)度算法

μC/OS采用優(yōu)先級至上的任務(wù)調(diào)度原則：“讓進入就緒態(tài)任務(wù)中優(yōu)先級最高的那個任務(wù)，一進入就緒態(tài)立刻就能立即運行”。這種基于優(yōu)先級的任務(wù)調(diào)度原則，在嵌入式實時系統(tǒng)中最常用。μC/OS實現(xiàn)了一種巧妙的查表算法，利用這種算法能快速實現(xiàn)上述任務(wù)調(diào)度原則。這種查表算法的大致思路是，用8字節(jié)數(shù)組中的64位作為就緒任務(wù)表，每一位表示一個任務(wù)的狀態(tài)，該位為1表示任務(wù)就緒，0為非就緒態(tài)。64位中第一個字節(jié)的b0位代表64個任務(wù)中優(yōu)先級最高的任務(wù)，最后一個字節(jié)的b7位代表優(yōu)先級最低的空閑任務(wù)。通過2次查用一張常數(shù)數(shù)組表，迅速找出任務(wù)就緒表中就緒態(tài)任務(wù)中優(yōu)先級最高的那個。常數(shù)表中，按照0～7表示的8種不同權(quán)重，以一定規(guī)律排列128個0、64個1、32個2、16個3,8個4、4個5、2個6和1個7，再補上1個0后，共256字節(jié)。查表法避免了逐位檢測各優(yōu)先級位引起的執(zhí)行時間的不確定性，程序簡單，執(zhí)行速度快，且時間是固定的，與就緒任務(wù)多少無關(guān)，與任務(wù)優(yōu)先級無關(guān)。這是μC/OS任務(wù)調(diào)度的核心算法。在處理信號量、郵箱、消息隊列等事件時，為了查找等待事件發(fā)生的任務(wù)列表中優(yōu)先級最高的那個任務(wù)，也采用同樣的算法，查的是同一張常數(shù)數(shù)組表。

μC/OS最初是為MOTOROLA的增強型8位處理器MC68HC11寫的，算法精彩，將其移植到其他8位、16位處理器，這種8位機算法無懈可擊。除任務(wù)就緒表外，μC/OSII在多處使用了上述調(diào)度算法。典型地，在事件控制塊ECB中有：

INT8UOSEventTbl[OS_EVENT_TBL_SIZE];

INT8UOSEventGrp;

這里，OS_EVENT_TBL_SIZE 的默認(rèn)值為8，即以8個8位數(shù)的數(shù)組表示最多64個不同優(yōu)先級的任務(wù)；OSEventGrp是OSEventTbl的索引字節(jié)，這就是μC/OS算法中著名的8+1個字節(jié)數(shù)據(jù)結(jié)構(gòu)。當(dāng)OSEventTbl 中的某一個字節(jié)不為0時（表示該字節(jié)代表的8個任務(wù)中至少有1個在等待事件發(fā)生），OSEventGrp 中的相應(yīng)位置1。首先以O(shè)SEventGrp的值做偏移量，查那張256字節(jié)的常數(shù)表，獲得1個0到7的數(shù)Y，作為優(yōu)先級高3位，再根據(jù)Y的值，找出OSEventTbl中8個字節(jié)中最先出現(xiàn)的那個不為零的字節(jié)；然后再次查那張表，得到1個0到7的數(shù)X，找出字節(jié)中最靠近b0的那一位，作為優(yōu)先級低3位的值，通過將Y左移3位再加上X的值，得到等待事件發(fā)生任務(wù)中優(yōu)先級最高的那個任務(wù)的優(yōu)先級。

在每個任務(wù)的任務(wù)控制塊TCB中有下列定義，可以看出，任務(wù)優(yōu)先級被拆分成兩個8進制數(shù)X和Y,用來以空間換時間，加快優(yōu)先級查找速度：

INT8UOSTCBX;/*=priority & 0x07;*/

INT8UOSTCBY;/*=priority >> 3;*/

INT8UOSTCBBitX;/*=OSMapTbl[priority & 0x07];*/

INT8UOSTCBBitY;/*=OSMapTbl[priority >> 3];*/

以上是μC/OS任務(wù)調(diào)度算法的簡要介紹，Jean J. Laborosse 先生最先用這種算法實現(xiàn)了RTOS中基于優(yōu)先級的調(diào)度策略，是μC/OS任務(wù)調(diào)度算法的精華與核心技術(shù)。

2 優(yōu)先級算法指令

對于32位和64位處理器，特別是一些精簡指令流類型的處理器，其內(nèi)部有可直接用于RTOS優(yōu)先級算法的硬件指令。以PowerPC 處理器為例，予以說明。這里順便解釋一下，PowerPC是IBM、MOTOROLA和Apple三家公司于90年代初期聯(lián)合設(shè)計的32位處理器，90年代后期出現(xiàn)增強型32位處理器，大量用于嵌入式系統(tǒng)，特別是汽車、通信等行業(yè)。本世紀(jì)初期，還出現(xiàn)了64位的處理器。在64位PowerPC 處理器指令中，有2條可供RTOS算法使用的指令：

cntlzd (Count Leading Zeros Double Word)

cntlzw (Count Leading Zeros Word)

上述指令也可簡稱為CLZ指令。設(shè)某通用源寄存器RS中有一個64位數(shù)，b0是高位，b63是低位，執(zhí)行cntlzd指令后，在目標(biāo)寄存器RD中返回源寄存器RS中64位數(shù)的前導(dǎo)零的數(shù)目。返回0表示b0不為0，即該64位數(shù)沒有前導(dǎo)0；返回n表示bn不為0，bn位的前面n位（b0～bn-1）共有n個零;返回64表示RS寄存器中所有位都為0。

如果用一個64位數(shù)表示64個任務(wù)的優(yōu)先級，從b0開始到b63，b0為最高優(yōu)先級，b63表示最低優(yōu)先級，使用cntlzd指令，可迅速找出優(yōu)先級最高的那個任務(wù)。RISC類型的處理器，執(zhí)行1條指令一般只需要1個CPU時鐘周期。執(zhí)行該指令，僅一個CPU時鐘周期就可完成對64個不同優(yōu)先級任務(wù)的判選。在這類處理器上直接移植和套用μC/OSII軟件算法，顯然不合理。

對于32位的PowerPC，也有匯編指令cntlzw。 數(shù)出一個32位數(shù)前置零的數(shù)目。指令執(zhí)行后，RD中返回指定源寄存器RS中32位數(shù)的前置零的數(shù)目，返回0表示b0不為0，即沒有前導(dǎo)0，返回32表示寄存器RS中所有的位都為0。這一條指令可從32個任務(wù)中迅速找出優(yōu)先級最高的那個任務(wù)。若使用2個32位數(shù)表示64個不同任務(wù)的優(yōu)先級，則下面是使用該指令實現(xiàn)μC/OSII算法的示意性代碼。

來源：維庫開發(fā)網(wǎng)