μC／OS- III對任務調度的改進

黃土琛，宮輝，邵貝貝

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

引 言

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

1 μC／OS -II最高就緒優先級的查找算法

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

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

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

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

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

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

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

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

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

圖2 CPU＿DATA聲明為32位時OSPrioTbl［］的結構

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

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

3 μC／OS- III時間片輪轉調度的細節

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

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

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

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

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

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

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

結 語

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

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

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

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