μc/Os-Ⅱ就緒表算法在ARM架構上的改動

引 言

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

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

1 在ARM上改動算法的因由利弊

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

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

(1)改動后的優(yōu)勢

①節(jié)省存儲空間。不再使用查找數組OSMapTbl[8]和OSUnMapTbl[256]。設立這兩個數組的目的，是為了提高查找就緒表的效率。

②提升查找效率。clz是單周期指令，使用帶移位的加法指令，大幅縮短運算時間。

③增加了μc/Os-Ⅱ支持的任務數量，從64提升到了1 024(2.84版支持的任務數量已經到了256，不過效率有所下降)。

(2)存在的不足

①Realview MDK(這里使用的是3.20版及其指令模擬器)尚不支持在C語言程序中使用Thumb-2指令內聯(lián)匯編。使用內嵌匯編函數時，函數的調用(跳轉返回)降低了執(zhí)行效率。

②C語言對clz指令的支持尚有不足，故新算法跨平臺性差。但鑒于ARM芯片應用廣泛，指令又被ARM9之后的芯片廣泛兼容，所以應用空間還算廣闊。

2 μc/Os-Ⅱ就緒表算法介紹與具體改動

μc/Os-Ⅱ就緒表是一個數組，數組元素一位的值(1或0)對應了一個任務就緒與否，該位在數組中的位置表示任務的優(yōu)先級。當需要調度已就緒的最高優(yōu)先級任務運行時，就在就緒表中查找該任務。

2.1 μc/Os-Ⅱ就緒表算法簡介

一種解決方法是，對數組各項依次判斷是否為0：若>O，進入該項查找最小權的置1位位置;若=0，優(yōu)先級加一個基數，查下一項，直至查到該優(yōu)先級。

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

2.2改動方式與源碼

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

考慮到有時用不到很多任務，這時用數組作就緒表不免浪費。因此當任務總數小于32時，就用32位無符號整數變量作就緒表。注意，此時就緒表組變量OSRdyGrp被當作就緒表使用。

常量OS_LES_TSK表示是否使用較小任務數，0表示使用最多32個任務，1表示使用最多1 024個任務。

常量RdySt是將32位整數的最高權位置1，以便移位使用。

2.3 C語言實現(xiàn)

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

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

2.4 THUMB-2匯編指令實現(xiàn)

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

在查找函數中，可以省去C語言程序中的內嵌匯編調用，減少冗余指令。示意偽代碼如下：

ldr rO， =OsRdyGrp;加載就緒表組變量OSRdyGrp地址

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

2.5 μC/OS-Ⅱ2.84版相關源碼介紹

以下是翻譯整理后的μC/OS-Ⅱ優(yōu)先級查找算法源碼(2.84版)，較長的注釋是添加的算法說明。

clz最高優(yōu)先級查找算法，與μC/OS-Ⅱ的新算法有所不同：返回的結果分別是8位、16位整數。這是因為8位已經不能表示>255的值;過程中clz算法更多地使用16或32位整數，以充分利用芯片性能。

3 適用范圍

等待任務列表使用了與就緒表操作相似的過程，注意要同時更改其數據類型和算法。算法雖然是在Cortex—M3上執(zhí)行的，但適用于ARM9及其以后芯片。支持ARM指令集的芯片，可以在C語言中使用內嵌匯編，不必再編寫匯編查找函數。

本文所敘述的算法適用于下述兩種情況。

①使用μC/OS-Ⅱ系統(tǒng)：[!--empirenews.page--]

◆要求更多的任務優(yōu)先級;

◆要求產品性能優(yōu)越或是時間關鍵的應用，想進一步提高效率;

◆學習、研究或希望優(yōu)化μC/OS-Ⅱ以擴展其應用范圍。

②未使用μC/OS-Ⅱ系統(tǒng)：

◆移植改造其他操作系統(tǒng)的就緒表算法;

◆編寫新操作系統(tǒng)或執(zhí)行調度程序;

◆編程愛好者借鑒、改進編程方法。

結 語

Cortex-M3推出時，筆者就認定它是單片機過渡到ARM的有力工具，其小存儲量使得它更適合用小型實時系統(tǒng)。在學習μC/OS-Ⅱ的過程中，發(fā)現(xiàn)其就緒表操作算法經過改動或許更好，于是就做了本文所述的試驗。