μC／OS- III對任務調(diào)度的改進

黃土琛，宮輝，邵貝貝

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

引 言

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

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

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

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

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

在V2.80以后的版本中，支持的優(yōu)先級數(shù)目增加到256，此時8×8的位映射表OSRdyTbl［］會被擴展到16×16，OSRdyGrp也增加到16位，但“掩碼表”O(jiān)SUnMapTbl［］仍然沒有變，因為保存一張216個元素的表是不實際的。因此，對于16位的無符號數(shù)的最低非零位的查找過程分兩步：先查低8位，如果沒找到再查高8位。

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

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

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

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

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

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

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

因為μC／OS－III允許多個任務運行在同一個優(yōu)先級，因此就緒任務列表（數(shù)組OSRdyList［］）也進行了改動，比之前稍微復雜了一些，這將在下一節(jié)提到。

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

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

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

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

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

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

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

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

結(jié) 語

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

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

［2］Jean J Labrosse.嵌入式實時操作系統(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任務調(diào)度算法的硬件實現(xiàn)［J］.單片機與嵌入式系統(tǒng)應用，2010（9）：5－7.

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