根據(jù)μc/Os-Ⅱ就緒表算法在ARM架構(gòu)上的改動
摘要： μc／Os-Ⅱ的就緒表設(shè)置、清除、查找算法,，是高效的,、跨平臺的程序。它使用了兩個查找數(shù)組OSMapTbl[8]和OSUnMapTbl[256]，以提高查找就緒表的速度，盡快獲取就緒任務(wù)的最高優(yōu)先級。
Abstract：
Key words :
μc／Os-Ⅱ的就緒表設(shè)置,、清除、查找算法,，是高效的,、跨平臺的程序。它使用了兩個查找數(shù)組OSMapTbl[8]和OSUnMapTbl[256],，以提高查找就緒表的速度,，盡快獲取就緒任務(wù)的最高優(yōu)先級。
Cortex-M3" title="Cortex-M3">Cortex-M3是ARM公司較新的一種架構(gòu)版本,，主要應(yīng)用在單片機(jī)領(lǐng)域,。基于它生產(chǎn)的32位芯片日益增多,；cortex-M3只支持Thumb-2指令集,，在效能和代碼密度間能取得更佳的表現(xiàn)。
1 在ARM上改動算法的因由利弊
由于就緒表操作是在關(guān)中斷狀態(tài)下運(yùn)行的,，其執(zhí)行影響到系統(tǒng)的中斷響應(yīng)時間,，因此就緒表操作算法的效率是衡量實時操作系統(tǒng)優(yōu)劣的基準(zhǔn)之一。
在Cortex-M3所用的指令集中,，一些指令功能不可小覷,，如前導(dǎo)零計數(shù)clz、字內(nèi)位反轉(zhuǎn)rbit,、位清除bic。其中的clz和bic為μc／Os就緒表的高優(yōu)先級獲取算法指出了另一條道路,。
(1)改動后的優(yōu)勢
?、俟?jié)省存儲空間。不再使用查找數(shù)組OSMapTbl[8]和OSUnMapTbl[256],。設(shè)立這兩個數(shù)組的目的,，是為了提高查找就緒表的效率。
?、谔嵘檎倚?。clz是單周期指令,，使用帶移位的加法指令，大幅縮短運(yùn)算時間,。
?、墼黾恿?mu;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ù)的調(diào)用(跳轉(zhuǎn)返回)降低了執(zhí)行效率。
?、贑語言對clz指令的支持尚有不足,，故新算法跨平臺性差。但鑒于ARM芯片應(yīng)用廣泛,，指令又被ARM9之后的芯片廣泛兼容,，所以應(yīng)用空間還算廣闊。
2 μc／Os-Ⅱ就緒表算法" title="就緒表算法">就緒表算法介紹與具體改動
μc／Os-Ⅱ就緒表是一個數(shù)組,，數(shù)組元素一位的值(1或0)對應(yīng)了一個任務(wù)就緒與否,，該位在數(shù)組中的位置表示任務(wù)的優(yōu)先級。當(dāng)需要調(diào)度已就緒的最高優(yōu)先級任務(wù)運(yùn)行時,，就在就緒表中查找該任務(wù),。
2．1 μc／Os-Ⅱ就緒表算法簡介
一種解決方法是，對數(shù)組各項依次判斷是否為0：若>O,，進(jìn)入該項查找最小權(quán)的置1位位置,；若=0，優(yōu)先級加一個基數(shù),，查下一項,，直至查到該優(yōu)先級。
μc／Os-Ⅱ技高一籌,，設(shè)置了一個對就緒表各項判斷是否為0的變量,，稱之為就緒表組。就緒表組一位為0或1,，對應(yīng)就緒表一項的值是否為0,。通過查找就緒表組最小權(quán)位的置1位位置，就確定了對應(yīng)首個>0的就緒表項的下標(biāo),，從而避免了循環(huán),，大幅度提高了效率。
2．2改動方式與源碼
clz算法接受了μc／Os-Ⅱ的思路,，再通過使用clz指令來進(jìn)行優(yōu)化,。不同的是,，clz是從右往左查，二進(jìn)制的高權(quán)位對應(yīng)高優(yōu)先級,，而μc／Os-Ⅱ優(yōu)先級以值小為高,。
考慮到有時用不到很多任務(wù)，這時用數(shù)組作就緒表不免浪費(fèi),。因此當(dāng)任務(wù)總數(shù)小于32時,，就用32位無符號整數(shù)變量作就緒表。注意,，此時就緒表組變量OSRdyGrp被當(dāng)作就緒表使用,。
常量OS_LES_TSK表示是否使用較小任務(wù)數(shù)，0表示使用最多32個任務(wù),，1表示使用最多1 024個任務(wù),。
常量RdySt是將32位整數(shù)的最高權(quán)位置1，以便移位使用,。
2．3 C語言實現(xiàn)
以下算法利用內(nèi)嵌clz指令的函數(shù)編寫,，實現(xiàn)了指定優(yōu)先級任務(wù)在就緒表的設(shè)置、清除,，在就緒表中查找就緒任務(wù)的最高優(yōu)先級,。
程序中的bx r14，有些資料上要求必須寫,，不過查看反匯編代碼,，編譯程序已經(jīng)給加上了?？磥硎蔷幾g程序已升級,，會不會出錯要看使用的編譯器，建議還是按規(guī)范寫上,。由于內(nèi)嵌函數(shù)調(diào)用返回耗時,，查找算法未能充分發(fā)揮，需改進(jìn)編譯后的匯編代碼以實現(xiàn)更高的效率,，或使用匯編代碼重寫這部分程序,。
關(guān)鍵字：μc Os-Ⅱ 就緒表算法 ARM架構(gòu)" title="ARM架構(gòu)">ARM架構(gòu)
2．4 THUMB-2匯編指令實現(xiàn)
用匯編語言寫程序時的技巧：在最高優(yōu)先級任務(wù)的設(shè)置、清除函數(shù)中,，C語言運(yùn)算符“︱=”對等匯編指令“orr”,，“＆=～”對等匯編指令“bic。這兩條指令都可以進(jìn)行預(yù)移位操作,，大幅提高執(zhí)行效率?？梢圆榭捶磪R編源碼,，看C編譯器是否利用了這一便利,。
在查找函數(shù)中，可以省去C語言程序中的內(nèi)嵌匯編調(diào)用,，減少冗余指令,。示意偽代碼如下：
ldr rO， =OsRdyGrp,；加載就緒表組變量OSRdyGrp地址
可以看出,，除了數(shù)據(jù)加載指令外，查找的核心算法僅3條指令(使用<32個任務(wù)時,，僅1條指令),。不過在實際設(shè)計算法的時候，還需要考慮指令流水線停頓,，方能達(dá)到最佳的效果,。
2．5 μC／OS-Ⅱ2．84版相關(guān)源碼介紹
以下是翻譯整理后的μC／OS-Ⅱ優(yōu)先級查找算法源碼(2．84版)，較長的注釋是添加的算法說明,。
clz最高優(yōu)先級查找算法,，與μC／OS-Ⅱ的新算法有所不同：返回的結(jié)果分別是8位、16位整數(shù),。這是因為8位已經(jīng)不能表示>255的值,；過程中clz算法更多地使用16或32位整數(shù)，以充分利用芯片性能,。
3 適用范圍
等待任務(wù)列表使用了與就緒表操作相似的過程,，注意要同時更改其數(shù)據(jù)類型和算法。算法雖然是在Cortex—M3上執(zhí)行的,，但適用于ARM9及其以后芯片,。支持ARM指令集的芯片，可以在C語言中使用內(nèi)嵌匯編,，不必再編寫匯編查找函數(shù),。
本文所敘述的算法適用于下述兩種情況。
?、偈褂?mu;C／OS-Ⅱ系統(tǒng)：
◆要求更多的任務(wù)優(yōu)先級,；
◆要求產(chǎn)品性能優(yōu)越或是時間關(guān)鍵的應(yīng)用，想進(jìn)一
步提高效率,；
◆學(xué)習(xí),、研究或希望優(yōu)化μC／OS-Ⅱ以擴(kuò)展其應(yīng)用范圍。
?、谖词褂?mu;C／OS-Ⅱ系統(tǒng)：
◆移植改造其他操作系統(tǒng)的就緒表算法,；
◆編寫新操作系統(tǒng)或執(zhí)行調(diào)度程序；
◆編程愛好者借鑒,、改進(jìn)編程方法,。
結(jié) 語
Cortex-M3推出時,，筆者就認(rèn)定它是單片機(jī)過渡到ARM的有力工具，其小存儲量使得它更適合用小型實時系統(tǒng),。在學(xué)習(xí)μC／OS-Ⅱ的過程中,，發(fā)現(xiàn)其就緒表操作算法經(jīng)過改動或許更好，于是就做了本文所述的試驗,。
此內(nèi)容為AET網(wǎng)站原創(chuàng),，未經(jīng)授權(quán)禁止轉(zhuǎn)載。