嵌入式μC/OS-Ⅱ任務(wù)調(diào)度算法的改進(jìn)

介紹μC／OS-II嵌入式實(shí)時(shí)操作系統(tǒng)的特點(diǎn)，分析單一的基于優(yōu)先級(jí)調(diào)度算法存在的不足。根據(jù)嵌入式應(yīng)用不同的實(shí)時(shí)性要求，將應(yīng)用劃分為實(shí)時(shí)任務(wù)、分時(shí)任務(wù)和后臺(tái)任務(wù)三種類型。針對分時(shí)任務(wù)，新增加時(shí)間片調(diào)度算法，給出調(diào)度算法的實(shí)現(xiàn)方法，同時(shí)增加任務(wù)創(chuàng)建和銷毀的接口；降低基于μC／OS-1I操作系統(tǒng)的嵌入式產(chǎn)品開發(fā)難度和設(shè)計(jì)成本，有利于該操作系統(tǒng)的應(yīng)用推廣。

目前，操作系統(tǒng)內(nèi)核的軟件中，μC，0S-II稱得上是小型實(shí)時(shí)操作系統(tǒng)。它由Jean J.Labrosse于1992年推出第l版，立刻在嵌入式系統(tǒng)領(lǐng)域引起強(qiáng)烈反響。μC／OS II是一個(gè)基于搶占式的實(shí)時(shí)多任務(wù)內(nèi)核，可固化、可剪裁、具有高穩(wěn)定性和可靠性。它最鮮明特點(diǎn)就是源碼公開，便于移植和維護(hù)，而且對于學(xué)校研究完全免費(fèi)，只有在應(yīng)用于盈利項(xiàng)目時(shí)才需要支付少量的版權(quán)費(fèi)，特別適合一般使用者的學(xué)習(xí)、研究和開發(fā)。自問世以來，其穩(wěn)定性和可靠性得到了廣泛的認(rèn)可，現(xiàn)已經(jīng)通過美國FAA認(rèn)證。在嵌入式領(lǐng)域，μc／OS憑借優(yōu)越特性得到了越來越廣泛的應(yīng)用，眾多的研究開發(fā)者將其作為操作系統(tǒng)的樣板，移植到各種硬件平臺(tái)，其外圍的應(yīng)用也越來越多。

另外，雖然μC/OS-Ⅱ內(nèi)核非常優(yōu)秀，但根據(jù)實(shí)際需求仍有一些地方有待改進(jìn)，如任務(wù)數(shù)目的限制等問題。μC/OS-Ⅱ目前版本最多僅支持64個(gè)任務(wù)，而且其中有8個(gè)要保留供系統(tǒng)使用，所以最多有56個(gè)任務(wù)可供用戶使用。隨著應(yīng)用系統(tǒng)日益復(fù)雜，如此有限的任務(wù)數(shù)必將限制其廣泛應(yīng)用，為了使其可應(yīng)用于更復(fù)雜的系統(tǒng)，必須對相關(guān)算法進(jìn)行改進(jìn)。

1 μC/OS-Ⅱ任務(wù)調(diào)度簡介

μC/OS-Ⅱ中的任務(wù)通常是一個(gè)無限循環(huán)，其任務(wù)狀態(tài)有五種：休眠態(tài)、運(yùn)行態(tài)、就緒態(tài)、等待態(tài)和掛起態(tài)。作為一個(gè)搶占式的實(shí)時(shí)內(nèi)核，μC/OS-Ⅱ僅支持按任務(wù)優(yōu)先級(jí)進(jìn)行切換，不支持時(shí)間片輪轉(zhuǎn)等其他調(diào)度方式，它總是運(yùn)行進(jìn)入就緒態(tài)的優(yōu)先級(jí)最高的任務(wù)。μC/OS-Ⅱ中以任務(wù)的優(yōu)先級(jí)作為任務(wù)標(biāo)識(shí)，相同優(yōu)先級(jí)的任務(wù)將無法區(qū)分，也就是說，μC/OS-Ⅱ不支持重復(fù)優(yōu)先級(jí)。因此，μC/OS-Ⅱ內(nèi)核中任務(wù)調(diào)度的主要工作就是查找出進(jìn)入就緒態(tài)的任務(wù)中優(yōu)先級(jí)最高的任務(wù)，并進(jìn)行上下文切換。這里所花費(fèi)的時(shí)間主要有：（1）查找最高優(yōu)先級(jí)任務(wù)時(shí)間；（2）任務(wù)上下文切換時(shí)間。其中，任務(wù)上下文切換時(shí)間是與處理器相關(guān)的，操作系統(tǒng)無法控制。因此，要想提高任務(wù)調(diào)度效率，主要考慮如何提高查找最高優(yōu)先級(jí)就緒任務(wù)的效率。

實(shí)時(shí)性是實(shí)時(shí)系統(tǒng)最重要的性能指標(biāo)之一。操作系統(tǒng)的實(shí)時(shí)性主要體現(xiàn)在：當(dāng)高優(yōu)先級(jí)的任務(wù)就緒時(shí)，操作系統(tǒng)盡快將此任務(wù)調(diào)度到CPU執(zhí)行。μC/OS-Ⅱ巧妙地通過構(gòu)造一張就緒表，并使用查表法來實(shí)現(xiàn)對最高優(yōu)先級(jí)的就緒任務(wù)的查找，這樣可保證查找時(shí)間與應(yīng)用程序中的任務(wù)數(shù)無關(guān)，確保查找時(shí)間的確定性，從而保證內(nèi)核的實(shí)時(shí)性并提高任務(wù)切換效率。

2 μC/OS-Ⅱ任務(wù)調(diào)度算法分析

2.1 就緒表結(jié)構(gòu)

μC/OS-Ⅱ內(nèi)核采用任務(wù)的優(yōu)先級(jí)作為任務(wù)標(biāo)識(shí)，通過查找就緒表實(shí)現(xiàn)對就緒任務(wù)的管理。這種巧妙的設(shè)計(jì)能夠保證任務(wù)調(diào)度的效率和任務(wù)調(diào)度時(shí)對最高優(yōu)先級(jí)就緒任務(wù)的查找時(shí)間的確定性。

如圖1所示的就緒表中有兩個(gè)變量OSRdyGrp（8 bit，每bit代表一組）和OSRdyTbl[8]（數(shù)組中每個(gè)bit代表一個(gè)優(yōu)先級(jí)），如果某個(gè)任務(wù)就緒，就將就緒表中相應(yīng)位置1。為了提高任務(wù)切換效率，μC/OS-Ⅱ任務(wù)調(diào)度算法采取分級(jí)查詢的方法?？紤]到任務(wù)數(shù)不超過64，可以用6 bit（26=64）來表示，μC/OS-Ⅱ?qū)θ蝿?wù)按優(yōu)先級(jí)進(jìn)行分組，優(yōu)先級(jí)的高三位決定任務(wù)在就緒表的第幾組，而低三位用于確定在該組的第幾位。這樣便形成了的二級(jí)查詢，先選組，再選組內(nèi)偏移，這樣可大大提高查詢效率。

2.2 使一個(gè)任務(wù)進(jìn)入或退出就緒態(tài)

如果要使優(yōu)先級(jí)為22的任務(wù)進(jìn)入就緒態(tài)，優(yōu)先級(jí)22用二進(jìn)制表示為0b00010110，其高3位和低3位分別為010和110。由就緒表的定義可知，優(yōu)先級(jí)為22的任務(wù)在就緒表的第2組第6位，要使其進(jìn)入就緒態(tài)，只需將OSRdyGrp的第2位和OSRdyTbl[]的第6位分別置1即可。

為了便于對某一位進(jìn)行位操作，μC/OS-Ⅱ又建立了一個(gè)掩碼數(shù)組OSMapTbl[]（如表1，定義在OS_CORE.C文件中）。若要將第k位置位，只需同OSMapTbl[k]按位進(jìn)行與操作即可。通過如下算法可使一個(gè)任務(wù)進(jìn)入就緒態(tài)（其中prio是任務(wù)的優(yōu)先級(jí)）：

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，便可得到所在的組。用移位實(shí)現(xiàn)是為了提高程序效率，后面的prio《3同樣如此；而OSMapTbl[prio & 0x07]中，prio & 0x07即只保留prio的低三位，這樣便可得到任務(wù)在該組中的位置。

從就緒任務(wù)列表中刪除一個(gè)任務(wù)則正好相反。對于OSRdyGrp，只有當(dāng)被刪除任務(wù)所在任務(wù)組中全組任務(wù)一個(gè)都沒有進(jìn)入就緒態(tài)時(shí)，也就是說OSRdyTbl[prio》3]所有的位都是零時(shí)，才將OSRdyGrp相應(yīng)位清零?？赏ㄟ^如下程序清單從就緒表中刪除一個(gè)任務(wù)：

if （（OSRdyTbl[prio》3]&=～OSMapTbl[prio & 0x07]）==0）

OSRdyGrp &=～OSMapTbl[prio》3]；

2.3 查找最高優(yōu)先級(jí)就緒任務(wù)

就緒表建立后，如何高效地查找出最高優(yōu)先級(jí)就緒任務(wù)是任務(wù)調(diào)度的關(guān)鍵。優(yōu)先級(jí)越高的任務(wù)，其優(yōu)先級(jí)值越小，越在就緒表的右上方。因此，為了找出最高優(yōu)先級(jí)的就緒任務(wù)，只需對OSRdyGrp從右往左找到第一個(gè)為1的位，假設(shè)為第m位；再從該組OSRdyGrp[m]中，從右往左找到第一個(gè)為1的位，假設(shè)為第n位。即就緒表中的第m組第n個(gè)任務(wù)為最高優(yōu)先級(jí)的就行任務(wù)，組合一下，便得到了最高優(yōu)先級(jí)就緒任務(wù)的優(yōu)先級(jí)。該操作可通過一個(gè)while循環(huán)掃描整個(gè)就緒表實(shí)現(xiàn)，但隨著就緒表中就緒任務(wù)的數(shù)目不同，這樣做最多要查找64步，最少才需查找1步，顯然其查找時(shí)間是不確定的；而任務(wù)切換時(shí)間的不確定性讓系統(tǒng)的實(shí)時(shí)性難以得到保證，這對實(shí)時(shí)系統(tǒng)是致命的。為了解決這個(gè)問題，μC/OS-Ⅱ又建立了一個(gè)比較大的掩碼數(shù)組OSUnMapTbl[k]（定義在OS_CORE.C文件中），其下標(biāo)值范圍為k∈[0，255]，值域?yàn)閇0，7]。

這樣，通過如下算法可在保證查找時(shí)間確定的前提下，較快地查找出進(jìn)入就緒態(tài)的優(yōu)先級(jí)最高的任務(wù)：

y=OSUnMapTbl[OSRdyGrp]；

x=OSUnMapTbl[OSRdyTbl[y]]；

OSPrioHighRdy=（y《3）+x；

以上查找算法和通過循環(huán)直接從就緒表查找相比，只需3行代碼便可實(shí)現(xiàn)對最高優(yōu)先級(jí)就緒任務(wù)的查找。

2.4 μC/OS-Ⅱ任務(wù)調(diào)度算法

任務(wù)調(diào)度算法是μC/OS-Ⅱ中最主要的算法之一。該算法通過建立OSUnMapTbl[]和OSMapTbl[]兩張表，使任務(wù)切換執(zhí)行時(shí)間恒定，不隨任務(wù)數(shù)目變化，從而保證了系統(tǒng)的確定性和實(shí)時(shí)性。這里對μC/OS-Ⅱ的設(shè)計(jì)思想進(jìn)行臆測，即“以空間換時(shí)間”。這點(diǎn)也可以從μC/OS-Ⅱ中存在眾多的全局變量看出，如OSRdyTbl[]、OSEventTabl[]、OSTCBTbl[]等。這種設(shè)計(jì)思想避免了動(dòng)態(tài)初始化。對于一個(gè)操作系統(tǒng)，任務(wù)調(diào)度十分頻繁，這一點(diǎn)空間相對其換取的寶貴CPU時(shí)間是微不足道的。

μC/OS-Ⅱ正是采用這種策略使其性能得到了大大的提升，這種處理方法也是μC/OS-Ⅱ任務(wù)管理效率如此之高的關(guān)鍵因素。