黃土琛，宮輝，邵貝貝

（1.清華大學(xué) 工程物理系，北京100084；2.清華大學(xué) 粒子技術(shù)與輻射成像教育部重點(diǎn)實(shí)驗(yàn)室）

引 言

μC／OS是一個(gè)基于優(yōu)先級(jí)調(diào)度的可剝奪型實(shí)時(shí)多任務(wù)內(nèi)核。在一個(gè)可剝奪型的實(shí)時(shí)內(nèi)核中，最高優(yōu)先級(jí)的任務(wù)一旦處于就緒狀態(tài)，就會(huì)立即搶占正在運(yùn)行的低優(yōu)先級(jí)任務(wù)的運(yùn)行權(quán)。在μC／OS－II中，任務(wù)調(diào)度是完全基于優(yōu)先級(jí)的，不同的任務(wù)被賦予不同的優(yōu)先級(jí)。V2.80以前的版本中，μC／OS－II最多支持64級(jí)優(yōu)先級(jí)，在 V2.80后的版本里增加到了256級(jí)。優(yōu)先級(jí)的數(shù)目決定了最多可支持的任務(wù)數(shù)目，當(dāng)然還要除去一些內(nèi)核占用的優(yōu)先級(jí)。而在μC／OS－III中，內(nèi)核支持任意數(shù)目的優(yōu)先級(jí)，由用戶根據(jù)實(shí)際需求來(lái)配置。更為重要的是，μC／OS－III增加了對(duì)時(shí)間片輪轉(zhuǎn)調(diào)度算法的支持，也就是說(shuō)，允許不同的任務(wù)使用同一個(gè)優(yōu)先級(jí)。這樣，任務(wù)的數(shù)量就可以不受優(yōu)先級(jí)數(shù)目的限制了。本文將介紹μC／OS－III在優(yōu)先級(jí)查找算法上的改進(jìn)，以及時(shí)間片輪轉(zhuǎn)調(diào)度算法的實(shí)現(xiàn)。

1 μC／OS -II最高就緒優(yōu)先級(jí)的查找算法

本文以 V2.80以前的版本為例，簡(jiǎn)單回顧μC／OS－II中查找就緒的最高優(yōu)先級(jí)算法的實(shí)現(xiàn)。以64級(jí)優(yōu)先級(jí)為例，如圖1所示，內(nèi)核通過(guò)一個(gè)8×8的位映射表OSRdyTbl［］來(lái)記錄任務(wù)的就緒狀態(tài)。為了加快查表過(guò)程，又將64級(jí)優(yōu)先級(jí)分為8組，用一個(gè)8位的整型OSRdyGrp來(lái)記錄每一組的就緒狀態(tài)。如果任務(wù)處于就緒態(tài)，其在位映射表OSRdyTbl［］中對(duì)應(yīng)的位就會(huì)被置1。只要一組中有任務(wù)處于就緒態(tài)，則OSRdyGrp中對(duì)應(yīng)的位就會(huì)被置1。OSRdyGrp和OSRdyTbl［］合起來(lái)又叫“就緒表”。因此，查找就緒的最高優(yōu)先級(jí)任務(wù)分兩步：首先在OSRdyGrp中查找就緒的最高優(yōu)先級(jí)所在的組；然后在OSRdyTbl［］里查找其在該組中的位置，便可得到具體的優(yōu)先級(jí)編號(hào)。

圖1 μC／OS- II的就緒表

OSRdyTbl［］中的元素，從低位LSB到高位 MSB對(duì)應(yīng)的優(yōu)先級(jí)編號(hào)是遞增的，也就是說(shuō)，優(yōu)先級(jí)的級(jí)別是逐漸降低的。因此，兩次的查找過(guò)程，本質(zhì)都是要得到一個(gè)8位無(wú)符號(hào)數(shù)的最低非零位。這個(gè)算法在μC／OS－II中是巧妙地通過(guò)一個(gè)“掩碼表”O(jiān)SUnMapTbl［］來(lái)實(shí)現(xiàn)的。OSUnMapTbl［］有256個(gè)元素，將8位的無(wú)符號(hào)數(shù)作為索引查找OSUnMapTbl［］，便得到該數(shù)最低非零位的位置，關(guān)于該表的具體內(nèi)容可查閱μC／OS－II的源代碼。利用事先計(jì)算好的一張表，通過(guò)查表操作來(lái)替代計(jì)算過(guò)程，這是典型的通過(guò)增加代碼量來(lái)?yè)Q取速度的思想（增加的代碼量?jī)H為256字節(jié)）。在獲得就緒的最高優(yōu)先級(jí)編號(hào)后，通過(guò)就緒任務(wù)列表OSTCBPrioTbl［］就可以得到相應(yīng)的任務(wù)控制塊指針了，整個(gè)過(guò)程的關(guān)鍵代碼示意如下：

在V2.80以后的版本中，支持的優(yōu)先級(jí)數(shù)目增加到256，此時(shí)8×8的位映射表OSRdyTbl［］會(huì)被擴(kuò)展到16×16，OSRdyGrp也增加到16位，但“掩碼表”O(jiān)SUnMapTbl［］仍然沒(méi)有變，因?yàn)楸４嬉粡?16個(gè)元素的表是不實(shí)際的。因此，對(duì)于16位的無(wú)符號(hào)數(shù)的最低非零位的查找過(guò)程分兩步：先查低8位，如果沒(méi)找到再查高8位。

2 μC／OS- III最高就緒優(yōu)先級(jí)查找算法的改進(jìn)

隨著32位微控制器的廣泛普及，尤其是ARM的Cortex－M系列的推廣，微控制器的價(jià)格越來(lái)越低廉，性能卻越來(lái)越高。μC／OS－III也特別針對(duì)一些新的微控制器的特性進(jìn)行了代碼優(yōu)化。在μC／OS－III里，就緒表包括兩部分：就緒優(yōu)先級(jí)位映射表OSPrioTbl［］，用來(lái)標(biāo)明哪個(gè)優(yōu)先級(jí)下有任務(wù)就緒；就緒任務(wù)列表OSRdyList［］，包含指向各個(gè)就緒任務(wù)的指針。OSPrioTbl［］元素的位寬取決于數(shù)據(jù)類型CPU＿DATA（在cpu.h里定義），由用戶根據(jù)所使用的處理器來(lái)確定，如32位的處理器CPU＿DATA定義為32位整型。

μC／OS－III允許的不同優(yōu)先級(jí)數(shù)目由用戶根據(jù)需求來(lái)配置（os＿cfg.h中的宏OS＿CFG＿PRIO＿M(jìn)AX）。如果某一優(yōu)先級(jí)下有任務(wù)就緒，那么在就緒優(yōu)先級(jí)位映射表OSPrioTbl［］中，該優(yōu)先級(jí)對(duì)應(yīng)的位就會(huì)被置1。圖2以CPU＿DATA為32位整型為例，展示了 OSPrioTbl［］的結(jié)構(gòu)。

由圖2可看出，和μC／OS－II不同的是，優(yōu)先級(jí)是按左到右的順序編號(hào)，并且隨著位映射表索引的遞增，優(yōu)先級(jí)編號(hào)也增加（優(yōu)先級(jí)級(jí)別降低）。之所以采用這樣的順序，是為了便于使用一種特殊的硬件指令——計(jì)算前導(dǎo)零數(shù)目（Count Leading Zeros，CLZ），如今很多處理器都支持該指令或類似指令。該指令和μC／OS－II中查找掩碼表的作用本質(zhì)是一樣的，但該硬件指令可以大大地提高查找最高優(yōu)先級(jí)的速度。

當(dāng)要查找包含就緒任務(wù)的最高優(yōu)先級(jí)時(shí)，程序會(huì)逐項(xiàng)掃描就緒優(yōu)先級(jí)位映射表OSPrioTbl［］，直到遇到第一個(gè)非零項(xiàng)為止。一旦找到第一個(gè)非零項(xiàng)，再加上該項(xiàng)的前導(dǎo)零數(shù)目，就可以得到所需的優(yōu)先級(jí)，見(jiàn)下述代碼。計(jì)算前導(dǎo)零數(shù)目函數(shù)CPU＿CntLeadZeros（）是一個(gè)與CPU相關(guān)的函數(shù)，前面提到，現(xiàn)在很多CPU都有專門的硬件指令，可以充分利用該指令來(lái)加速計(jì)算過(guò)程。如果CPU沒(méi)有類似指令，那這部分功能就只能由普通的C代碼來(lái)實(shí)現(xiàn)。

圖2 CPU＿DATA聲明為32位時(shí)OSPrioTbl［］的結(jié)構(gòu)

逐項(xiàng)地掃描位映射表OSPrioTbl［］好像不是很高效。然而，當(dāng)優(yōu)先級(jí)的級(jí)數(shù)比較少時(shí)，這個(gè)查找過(guò)程還是相當(dāng)快的。比如說(shuō)，對(duì)于很多應(yīng)用，32級(jí)優(yōu)先級(jí)已經(jīng)能滿足要求，這時(shí)如果使用支持硬件CLZ指令的32位微控制器，只需一條匯編指令就能完成查找過(guò)程。即使優(yōu)先級(jí)數(shù)目增加到64級(jí)（這已經(jīng)可以滿足絕大多數(shù)系統(tǒng)的需求了），上述過(guò)程也可以進(jìn)行流水線優(yōu)化，僅需多加一條IF語(yǔ)句就可以。請(qǐng)注意，在μC／OS－III里，任務(wù)數(shù)量不再限制于優(yōu)先級(jí)數(shù)目，因?yàn)棣藽／OS－III允許任意數(shù)量的任務(wù)運(yùn)行在同一個(gè)優(yōu)先級(jí)（優(yōu)先級(jí)0和 OS＿CFG＿PRIO＿M(jìn)AX－1除外）。

因?yàn)棣藽／OS－III允許多個(gè)任務(wù)運(yùn)行在同一個(gè)優(yōu)先級(jí)，因此就緒任務(wù)列表（數(shù)組OSRdyList［］）也進(jìn)行了改動(dòng)，比之前稍微復(fù)雜了一些，這將在下一節(jié)提到。

3 μC／OS- III時(shí)間片輪轉(zhuǎn)調(diào)度的細(xì)節(jié)

和μC／OS－II相比，μC／OS－III在調(diào)度方面一個(gè)大的改進(jìn)就是增加了對(duì)時(shí)間片輪轉(zhuǎn)調(diào)度的支持。所謂時(shí)間片輪轉(zhuǎn)調(diào)度，就是兩個(gè)或更多的任務(wù)擁有相同的優(yōu)先級(jí)時(shí)，一個(gè)任務(wù)運(yùn)行一段指定的時(shí)間（即時(shí)間片），然后輪到下一個(gè)任務(wù)。如果一個(gè)任務(wù)不需要執(zhí)行完其時(shí)間片，也可以主動(dòng)放棄CPU的控制權(quán)而讓下一個(gè)任務(wù)運(yùn)行。μC／OS－III允許用戶為不同的任務(wù)指定不同的時(shí)間片長(zhǎng)度（任務(wù)的時(shí)間片長(zhǎng)度是在任務(wù)建立時(shí)指定的，在運(yùn)行時(shí)也可以改變），并且可以在運(yùn)行時(shí)使能或者禁止時(shí)間片輪轉(zhuǎn)調(diào)度。

在μC／OS－III中，一個(gè)優(yōu)先級(jí)下允許存在多個(gè)任務(wù)，因此就緒任務(wù)列表OSRdyList［］也變得復(fù)雜了，其元素不再是簡(jiǎn)單地指向一個(gè)任務(wù)，而是構(gòu)成一個(gè)雙向鏈表，鏈接對(duì)應(yīng)優(yōu)先級(jí)下所有就緒的任務(wù)，如圖3所示。圖中，優(yōu)先級(jí)“prio”下有兩個(gè)就緒任務(wù)，其任務(wù)控制塊OS＿TCB構(gòu)成一個(gè)雙向鏈表，HeadPtr指向鏈表頭部，TailPtr指向鏈表尾部，Entries域用來(lái)記錄該優(yōu)先級(jí)下就緒的任務(wù)數(shù)目。最高優(yōu)先級(jí)0和最低優(yōu)先級(jí)OS＿CFG＿PRIO＿M(jìn)AX－1供內(nèi)核使用，用戶任務(wù)不能使用這兩個(gè)優(yōu)先級(jí)。

圖3 μC／OS- III的就緒任務(wù)列表示意圖

μC／OS－III的任務(wù)調(diào)度過(guò)程和μC／OS－II類似，找到就緒的最高優(yōu)先級(jí)后，用優(yōu)先級(jí)號(hào)作為索引，查找就緒任務(wù)列表OSRdyList［］，從對(duì)應(yīng)的雙向鏈表頭部（即OSRdyList［hightest priority］.HeadPtr）便可獲得最高優(yōu)先級(jí)任務(wù)的控制塊指針。如果該指針和當(dāng)前運(yùn)行任務(wù)的控制塊指針不一致，則表明需要進(jìn)行任務(wù)切換。也就是說(shuō)，當(dāng)獲得就緒的最高優(yōu)先級(jí)后，μC／OS－III調(diào)度的總是其對(duì)應(yīng)的雙向鏈表頭部的任務(wù)，與該優(yōu)先級(jí)下存在多少任務(wù)無(wú)關(guān)。換句話說(shuō)，一個(gè)優(yōu)先級(jí)下存在多個(gè)任務(wù)，這對(duì)調(diào)度過(guò)程來(lái)說(shuō)似乎是“透明”的。

既然μC／OS－III每次調(diào)度的都是雙向鏈表頭部的任務(wù)，那么同一優(yōu)先級(jí)下的多個(gè)任務(wù)又是如何實(shí)現(xiàn)輪轉(zhuǎn)調(diào)度的呢？這個(gè)細(xì)節(jié)的實(shí)現(xiàn)由函數(shù)OS＿SchedRoundRobin（）來(lái)完成。該函數(shù)在每次時(shí)鐘節(jié)拍到來(lái)時(shí)，由OSTimeTick（）（direct post模式）或 OS＿IntQTask（）（deferred post模式）調(diào)用。OS＿SchedRoundRobin（）函數(shù)的偽代碼如下：

OS＿SchedRoundRobin（）首先檢查時(shí)間片輪轉(zhuǎn)調(diào)度是否使能，然后將當(dāng)前任務(wù)時(shí)間片計(jì)數(shù)器減1。如果時(shí)間片計(jì)數(shù)器已減到零，OS＿SchedRoundRobin（）就會(huì)檢查當(dāng)前優(yōu)先級(jí)下是否還有其他就緒任務(wù)。如果有，并且調(diào)度器也沒(méi)被上鎖的話，會(huì)將當(dāng)前任務(wù)的控制塊OS＿TCB從雙向鏈表的頭部移到尾部，而之前處于雙向鏈表第二個(gè)位置的任務(wù)將會(huì)移到頭部位置，成為下一個(gè)運(yùn)行的任務(wù)。在退出時(shí)鐘節(jié)拍中斷時(shí)會(huì)進(jìn)行任務(wù)調(diào)度，假設(shè)沒(méi)有其他更高優(yōu)先級(jí)的任務(wù)就緒，這時(shí)μC／OS－III依然會(huì)檢查到當(dāng)前優(yōu)先級(jí)對(duì)應(yīng)的雙向鏈表頭部位置的任務(wù)已發(fā)生變化，因此會(huì)進(jìn)行任務(wù)切換，這就實(shí)現(xiàn)了同一優(yōu)先級(jí)下多個(gè)任務(wù)的輪轉(zhuǎn)調(diào)度。

值得注意的是，在建立任務(wù)時(shí)，如果在指定的優(yōu)先級(jí)下已經(jīng)存在其他任務(wù)，μC／OS－III會(huì)把新建的任務(wù)插入到對(duì)應(yīng)優(yōu)先級(jí)所指向的雙向鏈表的尾部。而當(dāng)一個(gè)任務(wù)轉(zhuǎn)入就緒態(tài)時(shí)，如果和當(dāng)前正在運(yùn)行的任務(wù)是在同一優(yōu)先級(jí)下，則轉(zhuǎn)入就緒態(tài)的任務(wù)將會(huì)被插入到雙向鏈表的尾部；如果轉(zhuǎn)入就緒態(tài)的任務(wù)和當(dāng)前正在運(yùn)行的任務(wù)的優(yōu)先級(jí)不一樣，則轉(zhuǎn)入就緒態(tài)的任務(wù)將會(huì)被插入到雙向鏈表的頭部。

結(jié) 語(yǔ)

μC／OS－III在基于優(yōu)先級(jí)的搶占式調(diào)度算法基礎(chǔ)上，增加了對(duì)時(shí)間片輪轉(zhuǎn)調(diào)度算法的支持，從而允許多個(gè)任務(wù)運(yùn)行在同一優(yōu)先級(jí)。μC／OS－III允許用戶為不同的任務(wù)指定不同的時(shí)間片大小，而且在運(yùn)行時(shí)還可以動(dòng)態(tài)改變，也可以在運(yùn)行時(shí)使能或禁止時(shí)間片輪轉(zhuǎn)調(diào)度，從而給用戶提供了很大的靈活性。同時(shí)，對(duì)查找就緒的最高優(yōu)先級(jí)任務(wù)的算法也進(jìn)行了改進(jìn)，充分利用特殊的硬件指令，極大地提高了查找的速度。

［1］Jean J Labrosse.μC／OS－II源碼公開的實(shí)時(shí)嵌入式操作系統(tǒng)［M］.邵貝貝，等譯.北京：中國(guó)電力出版社，2001.

［2］Jean J Labrosse.嵌入式實(shí)時(shí)操作系統(tǒng)μC／OS－II［M］.邵貝貝，等譯.2版.北京：北京航空航天出版社，2003.

［3］Jean J Labrosse.μC／OS－III the Real Time Kernel for the Freescale Kinetis［EB／OL］.［2012－07－25］.http：／／micrium.com／page／downloads／os－iii＿projects.

［4］邵貝貝.淺談μC／OS任務(wù)調(diào)度算法的硬件實(shí)現(xiàn)［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2010（9）：5－7.

［5］龔光華，車惠軍.μC／OS優(yōu)先級(jí)調(diào)度機(jī)制在PowerPC上的優(yōu)化［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2010（10）：9－11.