淺談μC／OS任務(wù)調(diào)度算法的硬件實(shí)現(xiàn)

邵貝貝

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

除了上面提到的幾種處理器，還有一些16位處理器也支持CLZ這樣的RTOS運(yùn)算指令。在這類(lèi)處理器上強(qiáng)行移植和直接使用μC／OS－ⅠⅠ也會(huì)有弄巧成拙的感覺(jué)。

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

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

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

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

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

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

4 小 結(jié)

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