μC/ OSⅡ優(yōu)先級(jí)擴(kuò)展的兩種方法探討

郝強(qiáng) 山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院；濟(jì)南職業(yè)學(xué)院 250103

μC/ OSⅡ優(yōu)先級(jí)擴(kuò)展的兩種方法探討

郝強(qiáng) 山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院；濟(jì)南職業(yè)學(xué)院 250103

在μC/ OSⅡ操作系統(tǒng)上運(yùn)行的任務(wù)數(shù)目不斷增加時(shí)，任務(wù)數(shù)目過(guò)多造成效率下降，本文根據(jù)μC/ OSⅡ本身的任務(wù)可擴(kuò)展性，在原有的優(yōu)先級(jí)調(diào)度算法基礎(chǔ)上，提出了兩種可行的大量增加可管理任務(wù)的算法。

實(shí)時(shí)操作系統(tǒng)；調(diào)度算法；實(shí)時(shí)性；優(yōu)先級(jí)

1、引言

本文引入嵌入式操作系統(tǒng)μ C/OSII是一個(gè)多任務(wù)的實(shí)時(shí)內(nèi)核,它具有嵌入式軟件共有的可裁剪、低資源、低功耗等特點(diǎn)；作為實(shí)時(shí)操作系統(tǒng)除了要滿足應(yīng)用的功能需區(qū)域以外，更重要的是還要滿足應(yīng)用提出的實(shí)時(shí)性要求。

2、簡(jiǎn)介

為增加μ C/ OSⅡ內(nèi)核可管理任務(wù)的數(shù)目，該算法利用μC/ OSⅡ原有的優(yōu)先級(jí)判定表格，重新定義了存放任務(wù)優(yōu)先級(jí)的字節(jié)，并重新建立任務(wù)就緒表,把64個(gè)任務(wù)擴(kuò)充到256個(gè)任務(wù)，把任務(wù)放入就緒表中，給出了新的最高就緒任務(wù)的查找算法。

3、用快表索引優(yōu)先級(jí)

在μ C/ OSⅡ中，原有的基于64個(gè)任務(wù)調(diào)度的優(yōu)先級(jí)調(diào)度算法分別用3 個(gè)比特位來(lái)定位任務(wù)優(yōu)先級(jí)在就緒表(ready list) 中的行和列，即0～2 位標(biāo)識(shí)該任務(wù)在總就緒表中的列信息，3～5 位標(biāo)識(shí)該任務(wù)在就緒表中的行信息。因此，存放任務(wù)優(yōu)先級(jí)的字節(jié)中8個(gè)比特位只會(huì)用到6位，而有兩個(gè)比特位空閑。該算法直接擴(kuò)展定位就緒任務(wù)優(yōu)先級(jí)在就緒表中位置的行和列信息的比特位，使其能夠區(qū)分256個(gè)不同的任務(wù)優(yōu)先級(jí)。擴(kuò)展后的算法規(guī)定任務(wù)優(yōu)先級(jí)字節(jié)的定義如上圖所示。套用μ C/ OS2 Ⅱ中定義的就緒表變量OSRdyGrp 和OSRdyTbl [ ]，仍舊用變量OSRdyGrp 來(lái)表示優(yōu)先級(jí)在就緒表中所在的行，在OSRdyGrp 中，任務(wù)按優(yōu)先級(jí)分組，1 6個(gè)任務(wù)為一組。OSRdyGrp 的每一位表示16 組任務(wù)中是否有進(jìn)入就緒態(tài)的任務(wù)，如果存在進(jìn)入就緒態(tài)的任務(wù)，則相應(yīng)位置為1。使用OSRdyTbl[ ]數(shù)組(根據(jù)上面的擴(kuò)展規(guī)則將該數(shù)組的大小由原來(lái)的8 位擴(kuò)展為16 位)表示優(yōu)先級(jí)在就緒表中的列信息，即存放每個(gè)優(yōu)先級(jí)的任務(wù)是否就緒的信息，如果某一位對(duì)應(yīng)的任務(wù)處于就緒態(tài)，則將該位的值置為1。例如，OSRdyTbl[0]對(duì)應(yīng)優(yōu)先級(jí)為0～15的任務(wù)，OSRdyTbl [1]對(duì)應(yīng)優(yōu)先級(jí)為1 6～3 1的任務(wù)，依次類(lèi)推，OSRdyTbl[15 ]對(duì)應(yīng)優(yōu)先級(jí)為240～255 的任務(wù)。優(yōu)先級(jí)為78 的任務(wù)處于就緒狀態(tài)，不僅要將OSRdyTbl[4]的第14位置1，而且要將OSRdyGrp 的第4位置1。也就是說(shuō)只要OSRdyTbl[n]中有一位為1，則OS2RdyGrp 的第n 位就為1。變量OSRdyGrp 和OSRdyTbl[ ]之間的關(guān)系如下圖所示(圖中OSRdyGrp 下表格中標(biāo)注的數(shù)字0～15 僅為清楚起見(jiàn)表示16組任務(wù)，并非表示OSRdyGrp 中每一位的狀態(tài)信息，同理，OSRdyTbl[ ]下表格中的數(shù)字0～255 也僅表示256 個(gè)任務(wù)，并非實(shí)際存放的狀態(tài)信息)。

把任務(wù)放入就緒表的程序是:

0 X 0 1 0 0，0 X 0 2 0 0，0 X 0 4 0 0，0X0800，0X1000，0X2000，0X4000，0X8000}，用于限制OSRdyTbl [ ]數(shù)組的元素下標(biāo)在0 到15 之間，prio 表示任務(wù)的優(yōu)先級(jí)。

4、用線性表索引優(yōu)先級(jí)

在μ C/ OSⅡ中,原來(lái)的優(yōu)先級(jí)調(diào)度算法只使用了一個(gè)字節(jié)中的6 位，剩余兩位空閑。在第一種改進(jìn)方法中，我們是直接擴(kuò)展了定位就緒任務(wù)優(yōu)先級(jí)在就緒表中位置的行和列信息的比特位。現(xiàn)在介紹的第二種方法是利用原來(lái)存放優(yōu)先級(jí)的字節(jié)中剩余的兩位作為索引，重建就緒表，使任務(wù)優(yōu)先級(jí)擴(kuò)展到256個(gè)。這里需要增加一個(gè)變量OSRdyXY，用于存放索引信息，另外還要使用變量OSRdyGrp [ ]存放任務(wù)優(yōu)先級(jí)的行信息，OSRd y Tb l0[ ]，OSRd y Tb l1[ ]，OSRdyTbl2[ ]和OSRdyTbl3[ ]4 個(gè)8 位數(shù)組用于存放每個(gè)優(yōu)先級(jí)的任務(wù)是否就緒的信息。這種方法的任務(wù)優(yōu)先級(jí)字節(jié)的定義如下圖所示。

在這種方法中，用一個(gè)字節(jié)的最高兩位存放索引信息(對(duì)應(yīng)于下圖中的OSRdyXY)，則意味著將就緒表分為4 個(gè)部分，因此，若要將任務(wù)放入就緒表，首先要通過(guò)索引信息確定任務(wù)優(yōu)先級(jí)在就緒表中的哪個(gè)部分,然后再通過(guò)行和列信息確定任務(wù)優(yōu)先級(jí)的具體位置。其中，變量OSRd y XY， OSRd y Grp [ ]以及OS2RdyTbl0[ ]～OSRdyTbl3[ ]的關(guān)系如左圖所示，圖中的數(shù)字0～255 僅為清楚起見(jiàn)表示索引信息或任務(wù)優(yōu)先級(jí)，并非實(shí)際存放的狀態(tài)信息。

將就緒任務(wù)放入就緒表的具體代碼可用如下方法實(shí)現(xiàn):

5、兩種方法的比較

上面詳細(xì)介紹了擴(kuò)展μ C/ OSⅡ內(nèi)核可管理任務(wù)數(shù)目的兩種方法。下面從幾個(gè)方面討論兩種改進(jìn)的調(diào)度算法的優(yōu)劣。從把就緒任務(wù)放入就緒表的所用時(shí)間來(lái)看,第一種方法可以直接確定位置，將就緒任務(wù)放入就緒表，而第二種方法中，必須順序查找，然后才能確定就緒任務(wù)在就緒表中的位置，第一種方法所用時(shí)間明顯少于第二種方法；最后，從查找最高優(yōu)先級(jí)就緒任務(wù)所需的時(shí)間來(lái)看，第一種方法通過(guò)變量ox 和oy 直接確定所有就緒任務(wù)中的哪一個(gè)任務(wù)優(yōu)先級(jí)最高，而第二種方法必須從最高優(yōu)先級(jí)開(kāi)始順序查找，直到找到第一個(gè)處于就緒狀態(tài)的任務(wù)才結(jié)束查找，這種方法花費(fèi)的時(shí)間顯然要比第一種方法多。是否能夠快速判定最高優(yōu)先級(jí)就緒任務(wù)是整個(gè)調(diào)度算法的最關(guān)鍵問(wèn)題，因此通過(guò)以上分析，可以看出第一種方法顯然要大大優(yōu)于第二種方法。

[1]吳旭光, 何軍紅. 嵌入式操作系統(tǒng)原理與應(yīng)用[M]. 化學(xué)工業(yè)出版社. 2007.

[2]吳明暉. 基于ARM的嵌入式系統(tǒng)開(kāi)發(fā)與應(yīng)用. 人民郵電出版社.2004.

[3]Labrosse J J. 基于ARM的嵌入式系統(tǒng)開(kāi)發(fā)與應(yīng)用.北京：北京航空航天大學(xué)出版社.2003 .

10.3969/j.issn.1001-8972.2010.18.060