μC／OS-II就緒表算法介紹與具體改動(dòng)方法

μc／Os-Ⅱ的就緒表設(shè)置、清除、查找算法，是高效的、跨平臺(tái)的程序。它使用了兩個(gè)查找數(shù)組OSMapTbl[8]和OSUnMapTbl[256]，以提高查找就緒表的速度，盡快獲取就緒任務(wù)的最高優(yōu)先級(jí)。

Cortex-M3是ARM公司較新的一種架構(gòu)版本，主要應(yīng)用在單片機(jī)領(lǐng)域?；谒a(chǎn)的32位芯片日益增多；cortex-M3只支持Thumb-2指令集，在效能和代碼密度間能取得更佳的表現(xiàn)。

1 在ARM上改動(dòng)算法的因由利弊

由于就緒表操作是在關(guān)中斷狀態(tài)下運(yùn)行的，其執(zhí)行影響到系統(tǒng)的中斷響應(yīng)時(shí)間，因此就緒表操作算法的效率是衡量實(shí)時(shí)操作系統(tǒng)優(yōu)劣的基準(zhǔn)之一。

在Cortex-M3所用的指令集中，一些指令功能不可小覷，如前導(dǎo)零計(jì)數(shù)clz、字內(nèi)位反轉(zhuǎn)rbit、位清除bic。其中的clz和bic為μc／Os就緒表的高優(yōu)先級(jí)獲取算法指出了另一條道路。

(1)改動(dòng)后的優(yōu)勢(shì)

①節(jié)省存儲(chǔ)空間。不再使用查找數(shù)組OSMapTbl[8]和OSUnMapTbl[256]。設(shè)立這兩個(gè)數(shù)組的目的，是為了提高查找就緒表的效率。
②提升查找效率。clz是單周期指令，使用帶移位的加法指令，大幅縮短運(yùn)算時(shí)間。
③增加了μc／Os-Ⅱ支持的任務(wù)數(shù)量，從64提升到了1 024(2．84版支持的任務(wù)數(shù)量已經(jīng)到了256，不過效率有所下降)。

(2)存在的不足

①Realview MDK(這里使用的是3．20版及其指令模擬器)尚不支持在C語言程序中使用Thumb-2指令內(nèi)聯(lián)匯編。使用內(nèi)嵌匯編函數(shù)時(shí)，函數(shù)的調(diào)用(跳轉(zhuǎn)返回)降低了執(zhí)行效率。
②C語言對(duì)clz指令的支持尚有不足，故新算法跨平臺(tái)性差。但鑒于ARM芯片應(yīng)用廣泛，指令又被ARM9之后的芯片廣泛兼容，所以應(yīng)用空間還算廣闊。

2 μc／Os-Ⅱ就緒表算法介紹與具體改動(dòng)

μc／Os-Ⅱ就緒表是一個(gè)數(shù)組，數(shù)組元素一位的值(1或0)對(duì)應(yīng)了一個(gè)任務(wù)就緒與否，該位在數(shù)組中的位置表示任務(wù)的優(yōu)先級(jí)。當(dāng)需要調(diào)度已就緒的最高優(yōu)先級(jí)任務(wù)運(yùn)行時(shí)，就在就緒表中查找該任務(wù)。

2．1 μc／Os-Ⅱ就緒表算法簡介

一種解決方法是，對(duì)數(shù)組各項(xiàng)依次判斷是否為0：若>O，進(jìn)入該項(xiàng)查找最小權(quán)的置1位位置；若=0，優(yōu)先級(jí)加一個(gè)基數(shù)，查下一項(xiàng)，直至查到該優(yōu)先級(jí)。

μc／Os-Ⅱ技高一籌，設(shè)置了一個(gè)對(duì)就緒表各項(xiàng)判斷是否為0的變量，稱之為就緒表組。就緒表組一位為0或1，對(duì)應(yīng)就緒表一項(xiàng)的值是否為0。通過查找就緒表組最小權(quán)位的置1位位置，就確定了對(duì)應(yīng)首個(gè)>0的就緒表項(xiàng)的下標(biāo)，從而避免了循環(huán)，大幅度提高了效率。

2．2改動(dòng)方式與源碼

clz算法接受了μc／Os-Ⅱ的思路，再通過使用clz指令來進(jìn)行優(yōu)化。不同的是，clz是從右往左查，二進(jìn)制的高權(quán)位對(duì)應(yīng)高優(yōu)先級(jí)，而μc／Os-Ⅱ優(yōu)先級(jí)以值小為高。

考慮到有時(shí)用不到很多任務(wù)，這時(shí)用數(shù)組作就緒表不免浪費(fèi)。因此當(dāng)任務(wù)總數(shù)小于32時(shí)，就用32位無符號(hào)整數(shù)變量作就緒表。注意，此時(shí)就緒表組變量OSRdyGrp被當(dāng)作就緒表使用。

常量OS_LES_TSK表示是否使用較小任務(wù)數(shù)，0表示使用最多32個(gè)任務(wù)，1表示使用最多1 024個(gè)任務(wù)。
常量RdySt是將32位整數(shù)的最高權(quán)位置1，以便移位使用。

2．3 C語言實(shí)現(xiàn)

以下算法利用內(nèi)嵌clz指令的函數(shù)編寫，實(shí)現(xiàn)了指定優(yōu)先級(jí)任務(wù)在就緒表的設(shè)置、清除，在就緒表中查找就緒任務(wù)的最高優(yōu)先級(jí)。

程序中的bx r14，有些資料上要求必須寫，不過查看反匯編代碼，編譯程序已經(jīng)給加上了?？磥硎蔷幾g程序已升級(jí)，會(huì)不會(huì)出錯(cuò)要看使用的編譯器，建議還是按規(guī)范寫上。由于內(nèi)嵌函數(shù)調(diào)用返回耗時(shí)，查找算法未能充分發(fā)揮，需改進(jìn)編譯后的匯編代碼以實(shí)現(xiàn)更高的效率，或使用匯編代碼重寫這部分程序。

? ? ? ? 2．4 THUMB-2匯編指令實(shí)現(xiàn)

用匯編語言寫程序時(shí)的技巧：在最高優(yōu)先級(jí)任務(wù)的設(shè)置、清除函數(shù)中，C語言運(yùn)算符“︱=”對(duì)等匯編指令“orr”，“＆=～”對(duì)等匯編指令“bic。這兩條指令都可以進(jìn)行預(yù)移位操作，大幅提高執(zhí)行效率。可以查看反匯編源碼，看C編譯器是否利用了這一便利。

在查找函數(shù)中，可以省去C語言程序中的內(nèi)嵌匯編調(diào)用，減少冗余指令。示意偽代碼如下：
ldr rO， =OsRdyGrp；加載就緒表組變量OSRdyGrp地址

可以看出，除了數(shù)據(jù)加載指令外，查找的核心算法僅3條指令(使用<32個(gè)任務(wù)時(shí)，僅1條指令)。不過在實(shí)際設(shè)計(jì)算法的時(shí)候，還需要考慮指令流水線停頓，方能達(dá)到最佳的效果。