俞佳敏，王成群，徐偉強(qiáng)

(浙江理工大學(xué) 信息學(xué)院，浙江 杭州310018)

0 引言

μC/OS-II作為一個(gè)開源的嵌入式實(shí)時(shí)操作系統(tǒng)，包含任務(wù)管理與任務(wù)調(diào)度，具有小巧、實(shí)時(shí)性強(qiáng)、移植性好[1-4]、基于優(yōu)先級的多任務(wù)可剝奪等優(yōu)點(diǎn)[5]。在μC/OS-II系統(tǒng)運(yùn)行過程中，任務(wù)管理函數(shù)通過中斷操作，確保當(dāng)前處于就緒狀態(tài)的最高優(yōu)先級任務(wù)最先運(yùn)行，能夠保證任務(wù)的實(shí)時(shí)性。近年來，μC/OS-II已在控制器[6]、數(shù)據(jù)采集[7]以及物聯(lián)網(wǎng)[8]等諸多領(lǐng)域取得了諸多應(yīng)用。

除實(shí)際應(yīng)用之外，近年來也出現(xiàn)了諸多對μC/OS-II性能分析及提升的成果。Lv[9]等采用靜態(tài)方法分析了μC/OS-II作為實(shí)時(shí)操作系統(tǒng)的最壞執(zhí)行時(shí)間；朱怡安[10]等基于μC/OS-II提出了一種高可靠性的分區(qū)嵌入式操作系統(tǒng)內(nèi)核，并通過實(shí)驗(yàn)進(jìn)行了驗(yàn)證；隋宇暉[11]等提出了基于FPGA的硬件加速模塊，將μC/OS-II中的調(diào)度器與定時(shí)器進(jìn)行硬件化，有效地提高了系統(tǒng)的實(shí)時(shí)性；李巖[12]等提出基于μC/OS-II的混合調(diào)度算法對同級任務(wù)進(jìn)行分組調(diào)度，并在FPGA中實(shí)現(xiàn)了該算法，有效降低了系統(tǒng)的開銷并提高了關(guān)鍵任務(wù)的實(shí)時(shí)性；許璐璐[13]等提出采用增量鏈表的方式對任務(wù)延時(shí)進(jìn)行高效管理。然而這些成果都是基于μC/OS-II最大64個(gè)優(yōu)先級任務(wù)，隨著μC/OS-II在工業(yè)等行業(yè)運(yùn)用得越來越廣泛，64個(gè)優(yōu)先級任務(wù)已無法滿足目前的需求。因此，本文研究了μC/OS-II的優(yōu)先級擴(kuò)展，實(shí)現(xiàn)了最大512個(gè)優(yōu)先級任務(wù)。

1 μC/OS-II優(yōu)先級機(jī)制

μC/OS-II給每一個(gè)任務(wù)分配一個(gè)惟一優(yōu)先級，各優(yōu)先級用一個(gè)正整數(shù)表示，優(yōu)先級大小與該整數(shù)值成正比，即0為最大優(yōu)先級，數(shù)值越大，優(yōu)先級越小。μC/OS-II系統(tǒng)將在當(dāng)前已處于就緒狀態(tài)的任務(wù)中選擇最高優(yōu)先級的任務(wù)進(jìn)行調(diào)度[14]。μC/OS-II最大支持64個(gè)任務(wù)優(yōu)先級，即優(yōu)先級范圍為(0～63)，其中統(tǒng)計(jì)任務(wù)以及空閑任務(wù)等系統(tǒng)任務(wù)占用最低的兩個(gè)優(yōu)先級，導(dǎo)致實(shí)際可用的任務(wù)優(yōu)先級數(shù)減少。

μC/OS-II中定義了一個(gè)用于存放任務(wù)準(zhǔn)備就緒標(biāo)志的就緒表，就緒表為每次任務(wù)切換提供可確定性的時(shí)間保證。為了就緒表的正常使用，uCOS-II定義了變量OSRdyGrp和OSRdyTbl[7]，以及表格優(yōu)先級判斷表OSUnMapTbl[256][15]。如圖1所示，由于μC/OS-II最大支持64個(gè)優(yōu)先級，就緒表由一個(gè)8乘8的表格組成，每個(gè)格子內(nèi)為0或1，其中置1則代表該優(yōu)先級下的任務(wù)處于就緒狀態(tài)。實(shí)質(zhì)上，就緒表被分成8行，即每一行分別為8個(gè)優(yōu)先級，其中OSRdyGrp為8位正整數(shù)類型，若第n(0≤n≤7)行中有相應(yīng)優(yōu)先級的任務(wù)就緒，則該位置1，否則默認(rèn)為0。

圖1 μC/OS-II就緒表

數(shù)組OSRdyTbl[7]中每一個(gè)數(shù)均為8位正整數(shù)類型，OSRdyTbl[n](0≤n≤7)中的8位分別代表第n行中8個(gè)優(yōu)先級任務(wù)就緒情況，若相對應(yīng)位置的任務(wù)就緒，則置1，否則默認(rèn)為0。μC/OS-II中優(yōu)先級prio定義為一個(gè)8位正整數(shù)類型的變量，最大64個(gè)優(yōu)先級時(shí)僅用到前6位，通過規(guī)律可以發(fā)現(xiàn)，低3位X可以代表該優(yōu)先級在就緒表某行中位置，3位Y可以確定該優(yōu)先級具體所在的行數(shù)。圖2為μC/OS-II提供的優(yōu)先級判斷表OSUnMapTbl[256]，優(yōu)先級判斷表由位掩碼表轉(zhuǎn)換而來。通過該表以及OSRdyGrp和OSRdyTbl[7]這兩個(gè)變量，任務(wù)調(diào)度時(shí)能夠快速找到目前處于就緒狀態(tài)的優(yōu)先級最高的任務(wù)。

圖2 μC/OS-II優(yōu)先級判斷表

2 μC/OS-II優(yōu)先級擴(kuò)展

為了使μC/OS-II最大支持512個(gè)優(yōu)先級任務(wù)，首先將變量prio擴(kuò)展至16位正整數(shù)類型，并且采用16乘32的就緒表，即共16行，每行有32個(gè)優(yōu)先級任務(wù)是否就緒的標(biāo)志。相應(yīng)地，OSRdyGrp擴(kuò)展至16位正整數(shù)類型，OSRdyTbl[7]擴(kuò)展至OSRdyTbl[15]，且其中每個(gè)數(shù)擴(kuò)展為32位正整數(shù)類型。但是在這種情況下，按照μC/OS-II所提供在優(yōu)先級判斷表基礎(chǔ)上采用OSRdyGrp和OSRdyTbl[]計(jì)算目前就緒的最高優(yōu)先級任務(wù)的算法不再適用。這是由于當(dāng)前OSRdyTbl[]中個(gè)數(shù)為32位正整數(shù)類型，無法在16乘16的優(yōu)先級判斷表中進(jìn)行匹配查找。一種解決該問題的方法是將優(yōu)先級判斷表擴(kuò)展至16乘32的形式，但這樣無疑會大大浪費(fèi)寶貴的空間資源。為此，本文在擴(kuò)展優(yōu)先級過程中采用按位判斷的方式實(shí)現(xiàn)在原來的優(yōu)先級判斷表中查找當(dāng)前就緒的最高優(yōu)先級任務(wù)。

具體地，對于16位的優(yōu)先級變量，通過低5位可以確定該優(yōu)先級任務(wù)在就緒表中某行中的具體位置X，通過第6～9位可以確定具體所在的行數(shù)Y。X，Y分別可以表示為：

Y= (prio >> 5) & 0xFF,

X= (prio & 0x1F);

為將計(jì)算得到X，Y更新至就緒表中，X，Y需轉(zhuǎn)換為BitX，BitY：

BitX= 1 <

BitY= 1 <

隨后更新變量OSRdyGrp和OSRdyTbl[]：

OSRdyGrp |= BitY,

OSRdyTbl[OSTCBY] |=BitX。

通過上述步驟，已經(jīng)能夠成功將0～511之間的優(yōu)先級變量分解并更新至就緒表中。此外，要實(shí)現(xiàn)擴(kuò)展優(yōu)先級的另一個(gè)重要難點(diǎn)在于如何通過OSRdyGrp和OSRdyTbl[]在μC/OS-II原有的優(yōu)先級判斷表中尋找當(dāng)前就緒的最高優(yōu)先級任務(wù)。對此，采用分類討論的方法去尋找就緒的最高優(yōu)先級任務(wù)。

首先，通過OSRdyGrp確定目前就緒的最高優(yōu)先級任務(wù)所在行y，由于優(yōu)先級判斷表輸入值在0x00～0xFF之間，所以分為以下2種情況計(jì)算y值：

if ((OSRdyGrp & 0xFF) != 0) {

y= OSUnMapTbl[OSRdyGrp & 0xFF];}

else {

y= OSUnMapTbl[(OSRdyGrp >> 8) & 0xFF] + 8;

}。

然后需要計(jì)算的是第y行中最高優(yōu)先級所在的位置x。在優(yōu)先級任務(wù)擴(kuò)展為512時(shí)，就緒表每行為32個(gè)不同優(yōu)先級，即x取值范圍為0～31，而μC/OS-II原有的優(yōu)先級判斷表輸出的x最大值為7，顯然無法滿足此時(shí)的需求。因此采用逐級查找的方式確定x值，即首先判斷OSRdyTbl[y]的低8位是否為0x00，若為0，則在該行的第0～7個(gè)位置對應(yīng)已就緒的優(yōu)先級任務(wù)不存在；若不為0x00，則代表在第0～7個(gè)位置上有對應(yīng)已就緒的優(yōu)先級任務(wù)，則直接用OSRdyTbl[y]的低8位放入優(yōu)先級判斷表中得到x。當(dāng)OSRdyTbl[y]的低8位為0時(shí)，檢查OSRdyTbl[y]的第9～16位是否為0x00，若是，則表示在該行的第8～15個(gè)位置對應(yīng)已就緒的優(yōu)先級任務(wù)不存在；反之則代表在第8～15個(gè)位置上有對應(yīng)已就緒的優(yōu)先級任務(wù)，則直接用OSRdyTbl[y]的低8位放入優(yōu)先級判斷表中，將判斷表輸出的值加8即為所求x的值，加上數(shù)值8是由于優(yōu)先級判斷表只輸出該x在第8～15個(gè)位置中的相對位置，所以需要再加上未包含進(jìn)去的數(shù)值8。同樣地，依次類推，當(dāng)OSRdyTbl[y]的第1～16位為0x0000時(shí)，依次計(jì)算第17～24位以及第25～32位的情況，若滿足條件，則分別加上數(shù)值16或24以得到x。具體關(guān)鍵實(shí)現(xiàn)代碼如下：

ptbl = &OSRdyTbl[y];

if ((*ptbl & 0xFF) != 0) {

x= OSUnMapTbl[(*ptbl & 0xFF)];}

else{

if (((*ptbl >> 8) & 0xFF) != 0) {

x= OSUnMapTbl[((*ptbl >> 8) & 0xFF)]

+ 8;}

else {

if (((*ptbl >> 16) & 0xFF) != 0){

x= OSUnMapTbl[((*ptbl >> 16) & 0xFF] +16;}

else{

if (((*ptbl >> 24) & 0xFF) != 0){

x= OSUnMapTbl[((*ptbl >> 24) &0xFF)]+ 24;}

}

}

}

}

計(jì)算得到x，y便可以計(jì)算當(dāng)前就緒的最高優(yōu)先級任務(wù)的優(yōu)先級數(shù)值OSPrioHighRdy，具體如下：

OSPrioHighRdy = (y<< 5) +x;

至此，通過上述分類考慮的方法，成功實(shí)現(xiàn)了通過OSRdyGrp和OSRdyTbl[]在μC/OS-II原有的優(yōu)先級判斷表中找到當(dāng)前就緒的最高優(yōu)先級任務(wù)。同時(shí)實(shí)現(xiàn)了將μC/OS-II支持的最大優(yōu)先級任務(wù)個(gè)數(shù)從64個(gè)提高到512個(gè)。

3 實(shí)驗(yàn)驗(yàn)證及分析

在實(shí)驗(yàn)驗(yàn)證中，分別創(chuàng)建優(yōu)先級為2，14，48，128，255，300，356，454，508的任務(wù)，并且上述任務(wù)創(chuàng)建后即進(jìn)入就緒狀態(tài)。由于兩個(gè)系統(tǒng)任務(wù)統(tǒng)計(jì)任務(wù)以及空閑任務(wù)分別占用了最低的510與511兩個(gè)優(yōu)先級，為了體現(xiàn)這一點(diǎn)，設(shè)置上述創(chuàng)建的任務(wù)分別執(zhí)行一次就停止，并只運(yùn)行一次統(tǒng)計(jì)任務(wù)，這樣系統(tǒng)才會開始運(yùn)行空閑任務(wù)。實(shí)驗(yàn)結(jié)果如圖3所示，所有任務(wù)被成功創(chuàng)建，且按照優(yōu)先級順序從高往低運(yùn)行，當(dāng)系統(tǒng)無就緒的用戶任務(wù)時(shí)，空閑任務(wù)將一直運(yùn)行。圖3中y與x值分別體現(xiàn)了該任務(wù)在就緒表中的位置。同時(shí)，統(tǒng)計(jì)任務(wù)以及空閑任務(wù)占據(jù)最低的兩個(gè)優(yōu)先級，符合實(shí)驗(yàn)的預(yù)期結(jié)果。

圖3 實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文提出的優(yōu)先級擴(kuò)展方法成功地將μC/OS-II支持的最大優(yōu)先級任務(wù)個(gè)數(shù)提高到了512。

4 結(jié)束語

通過研究μC/OS-II的優(yōu)先級設(shè)置機(jī)制，在原優(yōu)先級判斷表的基礎(chǔ)上，采用分類判斷的方式將其支持的最大優(yōu)先級數(shù)擴(kuò)展到512個(gè)。通過實(shí)驗(yàn)驗(yàn)證，該方法成功地實(shí)現(xiàn)了最大優(yōu)先級數(shù)的擴(kuò)展，并未增加系統(tǒng)的空間。擴(kuò)展μC/OS-II支持的最大優(yōu)先級數(shù)能夠使其被應(yīng)用得更加廣泛，進(jìn)一步促進(jìn)μC/OS-II的發(fā)展。