邵貝貝

（清華大學(xué) 工程物理系，北京100084）

μ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／OS－ⅠⅠ的3本著作中［1－3］，該內(nèi)核提供的是PC上的源碼。μC／OS－ⅠⅠ比μC／OS增加了很多功能，在任務(wù)調(diào)度算法上并無不同，故本文提及任務(wù)調(diào)度算法時不再區(qū)分μC／OS和μC／OS－ⅠⅠ。

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

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

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

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

μC／OS采用優(yōu)先級至上的任務(wù)調(diào)度原則：“讓進(jìn)入就緒態(tài)任務(wù)中優(yōu)先級最高的那個任務(wù)，一進(jìn)入就緒態(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／OS－ⅠⅠ在多處使用了上述調(diào)度算法。典型地，在事件控制塊ECB中有：

這里，OS＿EVENT＿TBL＿SⅠZE 的默認(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進(jìn)制數(shù)X和Y，用來以空間換時間，加快優(yōu)先級查找速度：

以上是μ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處理器［5］為例，予以說明。這里順便解釋一下，PowerPC是ⅠBM、Motorola和Apple三家公司于90年代初期聯(lián)合設(shè)計的32位處理器，90年代后期出現(xiàn)增強型32位處理器，大量用于嵌入式系統(tǒng)，特別是汽車、通信等行業(yè)。本世紀(jì)初期，還出現(xiàn)了64位的處理器。在64位PowerPC處理器指令中，有2條可供RTOS算法使用的指令：

上述指令也可簡稱為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ù)。RⅠSC類型的處理器，執(zhí)行1條指令一般只需要1個CPU時鐘周期。執(zhí)行該指令，僅一個CPU時鐘周期就可完成對64個不同優(yōu)先級任務(wù)的判選。在這類處理器上直接移植和套用μC／OS－ⅠⅠ軟件算法，顯然不合理。

對于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／OS－ⅠⅠ算法的示意性代碼。

這樣，很少幾條指令，就完成了μC／OS中需要查表來完成的算法，不僅速度快，還省去了程序中256字節(jié)的那張常數(shù)表。上述實現(xiàn)方法并非唯一的，還可進(jìn)一步優(yōu)化。對于增強型32位PowerPC［6］，還有一條指令可對2個地址連續(xù)的32位數(shù)做并行操作，同時數(shù)出前導(dǎo)零的數(shù)目。此時若低32位不為0，則最高優(yōu)先級者被立即找出；若為0，則取高32位中的優(yōu)先級再加32即可。

其他32位機，如MⅠPS的處理器，也有同類指令。一些處理器還有與上述指令對稱的“數(shù)出前置1的數(shù)目”指令。總之，在有類似CLZ指令的處理器上，直接移植和使用μC／OS－ⅠⅠ的任務(wù)調(diào)度算法并不合理。移植后需要摒棄μC／OS－ⅠⅠ中的軟件算法，代之以硬件指令算法指令，實現(xiàn)RTOS任務(wù)調(diào)度算法的優(yōu)化。

早期的ARM系列處理器并不支持CLZ指令，但從ARM Cortex開始，或者說ARM v5及以后的ARM類CPU，如Cortex－A8、Cortex－M3等，開始支持 CLZ指令。因此對于Cortex單片機，也沒有必要套用μC／OS算法，這類處理器可運行μC／OS－ⅠⅠⅠ［7］。μC／OS－ⅠⅠⅠ是在μC／OS－ⅠⅠ的基礎(chǔ)上發(fā)展起來的商業(yè)產(chǎn)品，目前還只能在ST的ARM Cortex 32位微控制器上實現(xiàn)。Cortex有RTOS硬件算法指令，不再需要使用μC／OS的查表算法。μC／OS－ⅠⅠⅠ還增加了同優(yōu)先級任務(wù)的時間片輪轉(zhuǎn)調(diào)度法等很多新功能，已經(jīng)是一個全新的RTOS商業(yè)產(chǎn)品了，不再是μC／OS－ⅠⅠ的升級版。由于目前μC／OS－ⅠⅠⅠ產(chǎn)品單一且源碼不再開放，以及價格方面等原因，我們還無法預(yù)見其未來。因此，深入研究和討論μC／OS－ⅠⅠ的移植和優(yōu)化是很有意義的。

除了上面提到的幾種處理器，還有一些16位處理器也支持CLZ這樣的RTOS運算指令。在這類處理器上強行移植和直接使用μC／OS－ⅠⅠ也會有弄巧成拙的感覺。

以16位的MC9S12XE系列和XF系列單片機為例，片內(nèi)有2個CPU，一個是傳統(tǒng)的CⅠSC類型的CPU S12，另外一個是名為XGate的RⅠSC類型CPU，XGate中有一條類似指令BFFO（Bit Field Find First One）指令格式為：

意為找出第一個1，和數(shù)出前導(dǎo)零的數(shù)目其實是一回事。目標(biāo)寄存器RD中得到源寄存器RS中16位數(shù)的第一個1的位置，如果RS中為全零，則C標(biāo)志置位。在XGate處理器上，特別是使用v2內(nèi)核的處理器，可以利用BFFO指令優(yōu)化μC／OS－ⅠⅠ任務(wù)調(diào)度算法。且對于μC／OS－ⅠⅠ的改進(jìn)并不限于用BFFO指令替代查表算法，還可以嘗試將RTOS和其管理的任務(wù)分別加載到2個CPU上。內(nèi)核和任務(wù)調(diào)度在RⅠSC類型的XGate上運行，被管理的任務(wù)放到CⅠSC類型的S12處理器上運行；XGate v1CPU雖然有BFFO指令，由于中斷無法嵌套，無法完整地運行XGate，但至少可以將XGate－ⅠⅠ中的時鐘節(jié)拍函數(shù)放到XGate上運行［8］。具有硬件優(yōu)先級算法指令的處理器，以及多內(nèi)核單片機，為μC／OS－ⅠⅠ的改進(jìn)和性能優(yōu)化開拓了豐富的想象空間。在決定移植和使用μC／OS－ⅠⅠ之前，應(yīng)該仔細(xì)研究一下擬用處理器的指令集，切莫盲目移植了事。

3 移植和優(yōu)化中還應(yīng)思考的問題

因為越來越多的RⅠSC類型處理器有了能用于RTOS任務(wù)調(diào)度算法的硬件指令，μC／OS－ⅠⅠ調(diào)度算法可以用硬件指令迅速完成，而不必依賴原來的軟件查表算法，大大簡化了程序，提高了運算速度。但由于RⅠSC類型的處理器，沒有直接對存儲器操作的指令，所有操作都只能通過CPU內(nèi)部寄存器完成，不能如同8位處理器那樣直接對存儲器做位操作，這類RⅠSC類型處理器中有很多內(nèi)部寄存器，可以設(shè)一些寄存器變量類型的指針來操作。如何用好寄存器變量，是要仔細(xì)研究的。

RⅠSC類型的CPU一般沒有讓存儲器的某一位置位或把存儲器的某一位清零的指令。往往需要先讀存儲器到CPU寄存器，再使用“與”、“或”等指令讓寄存器某一位復(fù)位或置位，再寫回到存儲器。這一連串的操作可能需要保護(hù)，防止其間被中斷。可以想象，若移植μC／OS－ⅠⅠ，在填寫任務(wù)就緒表的時候，操作并不簡單，要考慮全面，避免任何疏漏和隱患。另外還有編譯器方面的問題。我們看到，上述討論中涉及了不少匯編指令，如同cntlz，在C語言中是無法直接表達(dá)的，編譯器對這樣的匯編指令能支持到什么程度，是用戶要細(xì)心研究的?，F(xiàn)在，越來越聰明的編譯器能將我們寫的C程序按照執(zhí)行速度或代碼長度等用戶定義的條件進(jìn)行優(yōu)化，能優(yōu)化到什么程度？什么條件下能把類似cntlz這樣的指令優(yōu)化進(jìn)去？這些都是要研究的。

對于中高端的處理器，一般都有系統(tǒng)態(tài)模式和用戶態(tài)模式（有的CPU稱之為保護(hù)模式），過去看到的很多移植文章都對此不予理會，讓CPU完全工作在系統(tǒng)態(tài)。如果讓RTOS內(nèi)核工作在系統(tǒng)態(tài)，任務(wù)工作在用戶態(tài)，有助于提高系統(tǒng)安全性。這類討論也是過去那些關(guān)于μC／OS－ⅠⅠ移植的文章中極少見到的。

4 小 結(jié)

μC／OS－ⅠⅠ是在中國嵌入式系統(tǒng)應(yīng)用中很有影響力的RTOS內(nèi)核，已經(jīng)被移植到幾乎所有能想到的處理器上。其技術(shù)亮點體現(xiàn)在優(yōu)先級調(diào)度算法上。由于當(dāng)初是為8位處理器寫的，對于8位處理器和多數(shù)16位處理器，運行μC／OS－ⅠⅠ是很不錯的選擇。處理器硬件技術(shù)的不斷發(fā)展，為RTOS任務(wù)調(diào)度算法的實現(xiàn)方法開拓了廣闊的想像空間。一些原來需要軟件實現(xiàn)的算法可以硬件化。典型地，對于32／64位和部分高端16位處理器，有可用于RTOS優(yōu)先級算法的硬件指令，例如文中提到的Power－PC、MⅠPS、ARM Cortex和 XGate等，直接移植μC／OS－ⅠⅠ代碼，套用其調(diào)度算法實際上很不合理。使用CLZ或BFFO等硬件指令替代μC／OS－ⅠⅠ中的軟件算法，可大大簡化μC／OS－ⅠⅠ代碼并優(yōu)化RTOS性能。本文提到的方法也決非唯一。技術(shù)在發(fā)展，對于μC／OS－ⅠⅠ，千萬不要移植了事，盡管已經(jīng)討論了十來年，仍然需要靜下心來學(xué)習(xí)并做些深入細(xì)致的研究，希望今后能夠看到更多深入探討μC／OS－ⅠⅠ優(yōu)化的文章。

［1］Labrosse Jean J.μC／OS The real Time Kernel［M］.R＆D Publication，1992.

［2］Labrosse Jean J.μC／OS－ⅠⅠ The real Time Kernel［M］.R＆D Publication，1999.

［3］Labrosse Jean J.μC／OS－ⅠⅠ The real Time Kernel［M］.2nd E－dition.R＆D Publication，2002.

［4］《電子產(chǎn)品世界》編輯部.2008年度嵌入式應(yīng)用調(diào)查報告［J］.電子產(chǎn)品世界，2009，16（1）.

［5］Freescale.e200z6PowerPC Core Reference Manual，2004.

［6］ⅠBM.Book E：Enhanced PowerPC Architecture，2002.

［7］Labrosse Jean J.μC／OS－ⅠⅠⅠ The real Time Kernel［M］.Micrium Press，2009.

［8］邵貝貝，等.嵌入式系統(tǒng)中的雙核技術(shù)［M］.北京航空航天大學(xué)出版社，2008.