摘 要： 在深入分析嵌入式實時系統μC/OS-Ⅱ的任務調度算法的基礎上，提出一種在確保其內核性能且調度時間可確定的前提下增大支持任務數的改進方案，使該內核可應用于更復雜的系統。
關鍵詞： μC/OS-Ⅱ；實時操作系統；任務調度；任務優先級；就緒表
μC/OS-Ⅱ是一款源代碼開放的嵌入式實時操作系統(RTOS)，具有可移植性強、可裁剪、可固化、穩定性高等特點。作為一個基于優先級搶占式的實時內核，μC/OS-Ⅱ任務調度算法效率高，任務切換速度快。該內核工作穩定可靠，在諸多領域得到了廣泛應用，并顯示出了強大的功能和巨大的商業價值。該內核提供任務調度與管理、時間管理、任務間同步與通信、內存管理和中斷服務等功能，適合中小型控制系統，具有執行效率高、占用空間小、實時性高和可擴展性強等優點。內核最小可編譯至2 KB。
另外，雖然μC/OS-Ⅱ內核非常優秀，但根據實際需求仍有一些地方有待改進，如任務數目的限制等問題。μC/OS-Ⅱ目前版本最多僅支持64個任務，而且其中有8個要保留供系統使用，所以最多有56個任務可供用戶使用。隨著應用系統日益復雜，如此有限的任務數必將限制其廣泛應用，為了使其可應用于更復雜的系統，必須對相關算法進行改進。
1 μC/OS-Ⅱ任務調度簡介
μC/OS-Ⅱ中的任務通常是一個無限循環，其任務狀態有五種：休眠態、運行態、就緒態、等待態和掛起態。作為一個搶占式的實時內核，μC/OS-Ⅱ僅支持按任務優先級進行切換，不支持時間片輪轉等其他調度方式，它總是運行進入就緒態的優先級最高的任務。μC/OS-Ⅱ中以任務的優先級作為任務標識，相同優先級的任務將無法區分，也就是說，μC/OS-Ⅱ不支持重復優先級。因此，μC/OS-Ⅱ內核中任務調度的主要工作就是查找出進入就緒態的任務中優先級最高的任務，并進行上下文切換。這里所花費的時間主要有：(1)查找最高優先級任務時間；(2)任務上下文切換時間。其中，任務上下文切換時間是與處理器相關的，操作系統無法控制。因此，要想提高任務調度效率，主要考慮如何提高查找最高優先級就緒任務的效率。
實時性是實時系統最重要的性能指標之一。操作系統的實時性主要體現在：當高優先級的任務就緒時，操作系統盡快將此任務調度到CPU執行。μC/OS-Ⅱ巧妙地通過構造一張就緒表，并使用查表法來實現對最高優先級的就緒任務的查找，這樣可保證查找時間與應用程序中的任務數無關，確保查找時間的確定性，從而保證內核的實時性并提高任務切換效率。
2 μC/OS-Ⅱ任務調度算法分析
2.1 就緒表結構
μC/OS-Ⅱ內核采用任務的優先級作為任務標識，通過查找就緒表實現對就緒任務的管理。這種巧妙的設計能夠保證任務調度的效率和任務調度時對最高優先級就緒任務的查找時間的確定性。
如圖1所示的就緒表中有兩個變量OSRdyGrp(8 bit，每bit代表一組）和OSRdyTbl[8]（數組中每個bit代表一個優先級)，如果某個任務就緒，就將就緒表中相應位置1。為了提高任務切換效率，μC/OS-Ⅱ任務調度算法采取分級查詢的方法。考慮到任務數不超過64，可以用6 bit(26=64)來表示，μC/OS-Ⅱ對任務按優先級進行分組，優先級的高三位決定任務在就緒表的第幾組，而低三位用于確定在該組的第幾位。這樣便形成了的二級查詢，先選組，再選組內偏移，這樣可大大提高查詢效率。
2.2 使一個任務進入或退出就緒態
如果要使優先級為22的任務進入就緒態，優先級22用二進制表示為0b00010110，其高3位和低3位分別為010和110。由就緒表的定義可知，優先級為22的任務在就緒表的第2組第6位，要使其進入就緒態，只需將OSRdyGrp的第2位和OSRdyTbl[]的第6位分別置1即可。
為了便于對某一位進行位操作，μC/OS-Ⅱ又建立了一個掩碼數組OSMapTbl[]（如表1，定義在OS_CORE.C文件中）。若要將第k位置位,只需同OSMapTbl[k]按位進行與操作即可。通過如下算法可使一個任務進入就緒態（其中prio是任務的優先級）：
INT8U const OSMapTbl[]={0x01，0x02，0x04，0x08，0x10，
0x20，0x40，0x80}；
OSRdyGrp |=OSMapTbl[prio>>3]；
OSRdyTbl[prio>>3] |=OSMapTbl[prio & 0x07]；
在OSMapTbl[prio>>3]中，prio右移3位即prio/8，便可得到所在的組。用移位實現是為了提高程序效率，后面的prio<<3同樣如此；而OSMapTbl[prio & 0x07]中，prio & 0x07即只保留prio的低三位，這樣便可得到任務在該組中的位置。
從就緒任務列表中刪除一個任務則正好相反。對于OSRdyGrp，只有當被刪除任務所在任務組中全組任務一個都沒有進入就緒態時，也就是說OSRdyTbl[prio>>3]所有的位都是零時，才將OSRdyGrp相應位清零。可通過如下程序清單從就緒表中刪除一個任務：
if ((OSRdyTbl[prio>>3]&=～OSMapTbl[prio & 0x07])==0)
OSRdyGrp &=～OSMapTbl[prio>>3]；
2.3 查找最高優先級就緒任務
就緒表建立后，如何高效地查找出最高優先級就緒任務是任務調度的關鍵。優先級越高的任務，其優先級值越小，越在就緒表的右上方。因此，為了找出最高優先級的就緒任務，只需對OSRdyGrp從右往左找到第一個為1的位，假設為第m位；再從該組OSRdyGrp[m]中，從右往左找到第一個為1的位，假設為第n位。即就緒表中的第m組第n個任務為最高優先級的就行任務，組合一下，便得到了最高優先級就緒任務的優先級。該操作可通過一個while循環掃描整個就緒表實現，但隨著就緒表中就緒任務的數目不同，這樣做最多要查找64步，最少才需查找1步，顯然其查找時間是不確定的；而任務切換時間的不確定性讓系統的實時性難以得到保證，這對實時系統是致命的。為了解決這個問題，μC/OS-Ⅱ又建立了一個比較大的掩碼數組OSUnMapTbl[k]（定義在OS_CORE.C文件中），其下標值范圍為k∈[0，255]，值域為[0，7]。
這樣，通過如下算法可在保證查找時間確定的前提下，較快地查找出進入就緒態的優先級最高的任務：
y=OSUnMapTbl[OSRdyGrp]；
x=OSUnMapTbl[OSRdyTbl[y]]；
OSPrioHighRdy=(y<<3)+x；
以上查找算法和通過循環直接從就緒表查找相比，只需3行代碼便可實現對最高優先級就緒任務的查找。
2.4 μC/OS-Ⅱ任務調度算法
任務調度算法是μC/OS-Ⅱ中最主要的算法之一。該算法通過建立OSUnMapTbl[]和OSMapTbl[]兩張表，使任務切換執行時間恒定，不隨任務數目變化，從而保證了系統的確定性和實時性。這里對μC/OS-Ⅱ的設計思想進行臆測，即“以空間換時間”。這點也可以從μC/OS-Ⅱ中存在眾多的全局變量看出，如OSRdyTbl[]、OSEventTabl[]、OSTCBTbl[]等。這種設計思想避免了動態初始化。對于一個操作系統，任務調度十分頻繁，這一點空間相對其換取的寶貴CPU時間是微不足道的。
μC/OS-Ⅱ正是采用這種策略使其性能得到了大大的提升，這種處理方法也是μC/OS-Ⅱ任務管理效率如此之高的關鍵因素。
3 μC/OS-Ⅱ調度算法的改進
μC/OS-Ⅱ目前的版本最多僅能支持64個任務， 除去保留系統使用的優先級，最多只支持56個任務。隨著應用系統日益復雜，如此有限的任務數必將限制其廣泛應用。為了使其可應用于更多更復雜的系統，必須對相關算法進行改進，擴展其可支持的任務數目。在對μC/OS-Ⅱ任務調度算法進行深入分析的基礎上，下面將討論如何將其支持的任務數由64個擴展為256個。
按μC/OS-Ⅱ原有思想不難想到直接將就緒表擴展為16×16，但這樣做會出現內存消耗嚴重的問題。根據就緒表及數組OSUnMapTbl[]的定義，可推導出計算掩碼數組OSUnMapTbl[]大小的公式(其中MAX_TASK_NUM為內核最大可支持任務數)：
OSUnMapTblSize=2sqrt(MAX_TASK_NUM) (1)
由式(1)可知：當系統最大支持任務數為64時，OSUnMapTbl[]數組元素個數為256個；而當任務數增加到256時， OSUnMapTbl[]數組元素的個數卻指數級地增長到65 536個。這會導致很嚴重的問題：OSUnMapTbl[]是一個常駐內存的全局數組， 因此OSUnMapTbl[]數組的大小將直接決定系統對RAM的需求量。在32位的ARM處理器上，每個int型數占4 B(32 bit)，則當任務數為64時，OSUnMapTbl[]數組僅消耗8 kB(256×32 bit)內存；而當任務數增加到256時，OSUnMapTbl[]這個常駐內存的全局數組將消耗掉2 MB(65 536×32 bit)內存。顯然，一個普通的嵌入式設備是耗不起這么大的內存的，任務調度時系統將會崩潰。因此，必須對原有調度算法進行改進。
3.1 改進的就緒表結構
為了解決由于任務數增加引起的OSUnMapTbl[]數組大小指數級增長而導致內存消耗過大問題，考慮對就緒表再多進行一次索引。
任務數擴展到256個時，將256個任務按優先級分成4塊，每塊64個任務。為此，增加一個變量OSRdyIdx。改進后的就緒表(如圖2)由OSRdyIdx、OSRdyGrp[p]、OSRdyTbl[p][q]（p∈[0，3]，q∈[0，7]）三個變量組成。其中，OSRdyIdx某一位置1，表示該塊中存在就緒任務；OSRdyGrp[p]數組的某一位置1則表示該組中存在就緒任務；而OSRdyTbl[p][q]的某一位置1，表示該優先級所對應的任務就緒。256個任務時改進的就緒表結構示意圖如圖2所示。
當任務數擴展到256個時， 任務的優先級用二進制表示如圖3。在改進的就緒表結構中，仍將μC/OS-Ⅱ的任務按優先級進行分組。由圖2可知，優先級的最高兩位ZZ確定任務在就緒表中的哪一塊，即變量OSRdyIdx的第幾位為1； 中間三位YYY確定任務在就緒表某一塊的哪一組，即數組OSRdyGrp[p]的第幾位為1；而低3位XXX確定就緒任務在就緒表某一組的哪一位。這樣形成了的三級查詢，先選塊，再選組，最后再選組內偏移。改進就緒表結構后，對OSMapTbl也要相應擴展。根據OSMapTbl[]數組的意義對其就緒擴展，擴展后的數組如表2。
3.2 對相關算法的改進
3.2.1 使一個任務進入或退出就緒態
與原有算法類似，任務進入就緒態時，需將就緒表中相應位置1，即利用OSMapTbl[]將OSRdyIdx、OSRdyGrp[]和OSRdyTbl[][]數組中相應位分別置位。改進后使一個任務進入就緒態的算法如下：
OSRdyIdx |=OSMapTbl[prio>>6]；
OSRdyGrp[prio>>6]|=OSMapTbl[(prio>>3)&0x07]
OSRdyTbl[prio>>6][(prio>>3)&0x07]|=OSMapTbl[prio & 0x07]；
相反，要從就緒表中刪除一個任務，只需將就緒表中相應位清零。同理，要在任務所在塊所在組的所有任務都不在就緒態的情況下，才能將相應的塊標志和組標志置0。改進的使任務退出就緒態的算法如下：
if((OSRdyTbl[prio>>6][(prio>>3)&0x07] &=～OSMapTbl
[prio & 0x07])==0)
OSRdyGrp[prio>>6]&=～OSMapTbl[(prio>>3)&0x07])
if(OSRdyTbl[prio>>6]==0)
OSRdyIdx&=～OSMapTbl[prio>>6]；
3.2.2 從就緒態任務中查找優先級最高的任務
為了保證查找已就緒任務中優先級最高任務的時間確定，并提高查詢效率，同樣不能簡單地使用while循環實現。μC/OS-Ⅱ仍需構造一個掩碼數組SUnMapTbl[]。改進的就緒表以多進行一次索引的方法，有效地解決了OSUnMapTbl[]表過大導致消耗大量內存的問題，使掩碼數組的大小從65 536有效地減小到256，從而使這個常駐內存的全局數組內存消耗量從2 MB減小到8 KB。
改進后的就緒表(見圖2)中最后每張子表中仍然只有64個任務，因此，就緒表結構改進后掩碼表并不需要改變，仍與64個任務時相同號，見圖4。對于OSUnMapTbl[]掩碼表的構造，由于該表比較大，不宜人工推算，可寫一個小程序生成，不難實現。限于篇幅，構造OSUnMapTbl[]表的代碼不在此列出。
就緒表構造好后，通過如下算法，便可方便地找出進入就緒態的任務中優先級最高的任務在就緒表中的位置，以便進行任務切換。改進的算法如下：
z=OSUnMapTbl[OSRdyIdx]；
y=OSUnMapTbl[OSRdyGrp[z]]；
x=OSUnMapTbl[OSRdyTbl[z][y]]；
OSPrioHighRdy=(z<<6)+(y<<3)+x；
以上查找就緒表算法與直接通過while循環從就緒中查找法相對比，只需4行代碼就實現了最高優先級任務查找的過程，這樣時間復雜度從O(n3)降低到了O(1)，從而大大提高了任務調度效率,并且保證了系統的實時性和確定性。
3.3 改進方案測試及分析
本文提出的方案繼承了μC/OS-Ⅱ優秀設計思想，在保證內核性能和實時性的前提下，成功地將μC/OS-Ⅱ可支持的最大任務數由64個擴展為256個，從而達到升級μC/OS-Ⅱ內核的目的，使其可應用于更多更復雜的系統。
該改進方案有如下優點：
(1)實現簡單。只需對就緒表結構稍加改進，并對調度算法相關部分作出相應的修改。
(2)調度時間確定。引進OSMapTbl[]、OSUnMapTbl[]兩張表能保證μC/OS-Ⅱ任務調度時間的確定性,并降低時間復雜度和內存消耗。
(3)保證實時性。實時性是RTOS的生命，該改進方案能保證重要任務總是優先占有CPU。
(4)可擴展性。如果還需擴大任務數，可按改進方案的思路進一步改進就緒表，以適應應用系統的需要；并可按該方案根據實際需要來定制任務數目，以更加有效地利用系統資源。
作為一個高實時性操作系統，μC/OS-Ⅱ必須有高效的任務調度算法作為支撐，任務調度算法是μC/OS-Ⅱ中最主要的算法之一。本文深入分析了嵌入式實時操作系統μC/OS-Ⅱ的任務調度算法，找出了其任務管理效率如此之高的關鍵原因，并在此基礎上提出了一種增大其支持任務數的改進方案。該方案算法執行時間確定，不隨實際任務數目變化，從而保證了系統的實時性；且能保證內存消耗，擴展可支持任務數而不對系統效率產生太大的影響。利用本文提出的方案，用戶還可根據實際需要定制任務數，以更加有效地利用系統資源，并使μC/OS-Ⅱ能應用在更多更復雜的場景。
參考文獻
[1] LABROSSE J.嵌入式實時操作系統μC/OS-Ⅱ[M].北京：北京航空航天大學出版社，2003.
[2] 劉育芳，張立臣.實時系統最壞執行時間分析[J].計算機應用研究，2005(11)：8-10.
[3] 楊科峰.嵌入式實時系統調度策略[J].計算機應用研究，2001(8)：31-33.
[4] 沈勝慶.嵌入式操作系統的內核研究[J].微計算機信息，2006(2).
[5] 毛德梅，何建忠.μC/OS-Ⅱ中任務切換機理及中斷調度技術研究[J].微計算機信息，2007(29).
[6] LEHOCZKY J，DING Y，DING Y.The rate-monotonic scheduling algorithm：exact characterization and average case behavior[C].Santa Monica California：IEEE Computer Society Press，1989，7(3)：166-171.
[7] LIU CL.Scheduling algorithms for multiprogramming in a hard real-time environment[J].Journal of the ACM，2001，20(1)：46-61.
[8] CHENG Zhang，CORDES D.Resource access control for dynamic priority distributed real-time systems[M].Springer Netherlands，2006：101-127.
[9] 唐寅.實時操作系統應用開發指南[M].北京：中國電力出版社，2002.
[10] 徐甲同.計算機操作系統教程[M].西安：西安電子科技大學出版社，2001.