李巖+王簡+遲歡歡+崔浩鑫

摘要：針對μC/OS-Ⅱ過于單一的調(diào)度算法引起的應(yīng)用局限性，提出一種混合調(diào)度算法。在原有的基于優(yōu)先級的搶占式調(diào)度算法基礎(chǔ)上，擴(kuò)展了同級調(diào)度。對于具有同一優(yōu)先級的多任務(wù)的任務(wù)組，按照用戶設(shè)定的優(yōu)先級閾值進(jìn)行劃分，優(yōu)先級高于該閾值為實時任務(wù)組，否則為非實時任務(wù)組。同級實時任務(wù)組采用較公平的時間片輪轉(zhuǎn)算法，同級非實時任務(wù)組采用開銷較少的先來先服務(wù)算法。算法基于FPGA實現(xiàn)，由VHDL描述，通過ISE 10.1仿真，仿真結(jié)果表明，硬件任務(wù)調(diào)度器保證了調(diào)度的正確性。提高了系統(tǒng)的實時性。

關(guān)鍵詞：實時操作系統(tǒng)；調(diào)度算法；硬件任務(wù)調(diào)度器

DOI：10.15938/j.jhust.2016.03.008

中圖分類號：TP316.2 文獻(xiàn)標(biāo)志碼：A 文章編號：1007—2683（2016）03—0039—04

0引言

隨著大規(guī)模集成電路技術(shù)的發(fā)展，嵌入式系統(tǒng)的軟、硬件界限越來越模糊，理論上任何操作指令既可以由軟件實現(xiàn)，也可以由硬件實現(xiàn)。而且硬件邏輯在執(zhí)行過程中可以與處理器并行，相較于純軟件實現(xiàn)的實時操作系統(tǒng)，可以極大的發(fā)揮系統(tǒng)的并行特性，使系統(tǒng)的處理效率提高到6～50倍。因此實時操作系統(tǒng)的硬件化在嵌入式領(lǐng)域擁有廣闊的發(fā)展空間。

μC/OS-Ⅱ是一個基于優(yōu)先級的搶占式實時內(nèi)核，不支持同級調(diào)度，對任務(wù)實時性也沒有劃分。但實際應(yīng)用有時卻需要同級調(diào)度，如同等地位的多點信息采集，而且沒有必要對非實時任務(wù)采用實時任務(wù)的調(diào)度算法。另外，僅依靠算法改進(jìn)已無法顯著的提高RTOS的實時性。文章針對以上問題，在μC/OS-Ⅱ原有算法的基礎(chǔ)上擴(kuò)展了同級調(diào)度。通過原內(nèi)核的調(diào)度算法選出優(yōu)先級最高的就緒同級任務(wù)組。對同級實時任務(wù)組內(nèi)的任務(wù)采用時間片輪轉(zhuǎn)算法，對同級非實時任務(wù)組內(nèi)的任務(wù)采用先來先服務(wù)算法。并實現(xiàn)基于該算法的硬件任務(wù)調(diào)度器，降低系統(tǒng)開銷低，提高系統(tǒng)實時性。

1硬件任務(wù)調(diào)度器的設(shè)計原理

1.1算法的設(shè)計

操作系統(tǒng)的任務(wù)調(diào)度算法多種多樣，但是每種調(diào)度算法都有自己的應(yīng)用局限性，比如短任務(wù)優(yōu)先算法可能產(chǎn)生長任務(wù)“饑餓”的現(xiàn)象，混合調(diào)度算法雖然不是完美的調(diào)度策略，但是將幾種調(diào)度算法的特性適當(dāng)?shù)恼壑?，?yōu)點盡量突出，缺點盡量回避，就可以滿足具體應(yīng)用場合的需求。針對～C/OS—n原有的單一調(diào)度算法的應(yīng)用局限性，提出一種混合調(diào)度算法。

算法啟用μC/OS-Ⅱ內(nèi)核預(yù)留的任務(wù)標(biāo)識符OSTCBId作為任務(wù)的唯一標(biāo)識，使得一個優(yōu)先級對應(yīng)一個任務(wù)組，該任務(wù)組由4個OSTCBId不同的同級任務(wù)組成。算法分為兩級調(diào)度。通過查找μC/OS-Ⅱ的就緒表和優(yōu)先級判定表，第一級調(diào)度選擇出優(yōu)先級最高的就緒的同級任務(wù)組，第二級調(diào)度對上面的同級任務(wù)組進(jìn)行組內(nèi)任務(wù)的調(diào)度。

第二級調(diào)度需要用戶事先設(shè)定一個優(yōu)先級閾值。若同級任務(wù)組的優(yōu)先級小于該閾值，則該任務(wù)組為實時的，否則為非實時的。對于實時任務(wù)組內(nèi)的任務(wù)采用較公平的時間片輪轉(zhuǎn)算法，但是頻繁的任務(wù)切換必然增加系統(tǒng)開銷。先來先服務(wù)算法是時間片輪轉(zhuǎn)算法的退化算法，不利于短任務(wù)，但是非實時任務(wù)可接受較長的響應(yīng)時間，所以對非實時任務(wù)組內(nèi)的任務(wù)采用先來先服務(wù)算法，從而減少任務(wù)切換帶來的不必要開銷。

1.2調(diào)度器的數(shù)據(jù)結(jié)構(gòu)

在μC/OS-Ⅱ中，每個任務(wù)都需要一個任務(wù)控制塊TCB來管理。調(diào)度器通過一組FPGA片內(nèi)寄存器實現(xiàn)TCB隊列。TCB的參數(shù)包括任務(wù)標(biāo)識符OS-TCBId、任務(wù)狀態(tài)OSTCBStat、等待時間OSTCBWait、棧頂指針OSTCBStkPtr、棧底指針OSTCBStkBottom、事件控制塊指針OSTCBEventPtr。該數(shù)據(jù)結(jié)構(gòu)保留了部分μC/OS-Ⅱ的TCB參數(shù)，最重要的修改是增加等待時間OSTCBWait，其初值為0，隨時鐘節(jié)拍不斷增加，被執(zhí)行后清零。

第一級調(diào)度的核心數(shù)據(jù)結(jié)構(gòu)是就緒表和優(yōu)先級判定表。就緒表由2個變量OSRdyTbl[]和OSRdyG～組成，基于FPGA片內(nèi)寄存器實現(xiàn)。優(yōu)先級判定表OSUnMapTbl[]由FPGA片內(nèi)RAM實現(xiàn)。第二級調(diào)度的核心數(shù)據(jù)結(jié)構(gòu)是優(yōu)先級閾值Prio-Threshold，基于FPGA片內(nèi)寄存器實現(xiàn)。

2硬件任務(wù)調(diào)度器的電路實現(xiàn)

2.1調(diào)度器的整體設(shè)計

調(diào)度器支持64個優(yōu)先級，每個優(yōu)先級最多支持4個同級任務(wù)，以任務(wù)狀態(tài)為觸發(fā)信號，輸出下一個要執(zhí)行的任務(wù)標(biāo)識符。調(diào)度器的整體設(shè)計如圖1所示。

在第一級調(diào)度中，將所有同級任務(wù)組的優(yōu)先級狀態(tài)PrioStat都輸入到就緒表的內(nèi)部變量OSRdyTbl[]和OSRdyGrp中，再將這兩個變量輸入給任務(wù)組調(diào)度電路，從而得到最高的就緒組優(yōu)先級Prio。

在第二級調(diào)度中，以第一級調(diào)度的輸出結(jié)果Prio為選擇條件，選擇一個同級任務(wù)組輸入給同級任務(wù)調(diào)度電路，電路內(nèi)部根據(jù)優(yōu)先級閾值Prio-Threshold選擇適當(dāng)?shù)恼{(diào)度算法，從而得到該任務(wù)組中的下一個要執(zhí)行的任務(wù)標(biāo)識符Cur_Id，即調(diào)度器的最終輸出結(jié)果。

2.2任務(wù)組調(diào)度電路的實現(xiàn)

任務(wù)組調(diào)度電路需要兩個時鐘周期的執(zhí)行時間，通過查找就緒表和優(yōu)先級判定表得到優(yōu)先級最高的就緒任務(wù)組。任務(wù)組調(diào)度電路如圖2所示。

第1個時鐘周期，計數(shù)器為1，選擇器將OSRdyGrp輸入譯碼器，轉(zhuǎn)換成RAM中相應(yīng)地址，讀取OSUnMapTbl[]的數(shù)據(jù)，由分配器更新優(yōu)先級高三位Y。

第2個時鐘周期，計數(shù)器為0，以y為選擇條件，將OSRdyTbl[]中相應(yīng)元素輸入選擇器，再輸入譯碼器，轉(zhuǎn)換成RAM中相應(yīng)地址，讀取OSUnMapT-bl[]的數(shù)據(jù)，由分配器更新優(yōu)先級低三位X。然后運算器完成（Y<<3）+X，輸出最高就緒任務(wù)組優(yōu)先級Prio。

2.3同級任務(wù)調(diào)度電路的實現(xiàn)

同級任務(wù)調(diào)度提供兩種可選的策略。若任務(wù)組調(diào)度電路的輸出Prio小于優(yōu)先級閾值Prio_Thresh-old，則該任務(wù)組為實時的，通過RR電路實現(xiàn)組內(nèi)任務(wù)的時間片輪轉(zhuǎn)算法，否則為非實時的，通過FCFS電路實現(xiàn)組內(nèi)任務(wù)的先來先服務(wù)算法。同級任務(wù)調(diào)度電路如圖3所示。

RR電路主要實現(xiàn)時間片輪轉(zhuǎn)算法，在同級任務(wù)組中從第一個就緒的任務(wù)開始，依次循環(huán)的給每個就緒任務(wù)分配一個時間片的處理器時間。FCPS電路主要實現(xiàn)先來先服務(wù)算法，在同級任務(wù)組中根據(jù)就緒任務(wù)的任務(wù)等待時間OSTCBWait，選擇出等待時間最長的就緒任務(wù)，使之優(yōu)先運行，以此類推。

State是任務(wù)組狀態(tài)寄存器。若State=1010，則組內(nèi)1號和3號任務(wù)就緒。Current是當(dāng)前任務(wù)寄存器，有且只有一位為1。若Current=0010，則正在執(zhí)行的任務(wù)是3號任務(wù)。Nell和Next2是下一個執(zhí)行任務(wù)寄存器，有且只有一位為1。若Nextl=1000，則下一個執(zhí)行的是1號任務(wù)。

若Prio

若Prio>=Prio—Threshold，則將State輸入FCFS電路，電路比較全部就緒任務(wù)的OSTCBWmt，選出等待時間最長的任務(wù)，在Next2中將其對應(yīng)的位置設(shè)為1，其他位置設(shè)為0.Sel設(shè)為Next2。

最后以Sel為選擇條件，輸出相應(yīng)的任務(wù)編號Cur_Id。

3實驗結(jié)果分析

為了驗證算法硬件實現(xiàn)的正確性和高效性，整個設(shè)計基于FPGA實現(xiàn)，采用VHDL語言描述，通過ISE 10.1進(jìn)行功能仿真，硬件調(diào)度器的功能仿真圖如圖4所示。

仿真結(jié)果分析如下：

1）在Ons時不妨設(shè)置優(yōu)先級閾值prio_threshold為5。

2）在5ns時建立優(yōu)先級為2的2號任務(wù)，由于只有一個就緒任務(wù)，輸出的下一個要執(zhí)行的任務(wù)標(biāo)識符out_cur_taskid為2。

3）在10ns時建立優(yōu)先級為1的1號任務(wù)，由于1號任務(wù)的優(yōu)先級最高，out_cur_taskid為1。

4）在15ns、20ns、25ns、30ns時，依次建立優(yōu)先級為3的3號任務(wù)和4號任務(wù)，以及優(yōu)先級為6的6號任務(wù)和7號任務(wù)，由于1號任務(wù)的優(yōu)先級最高，out_cur__taskid仍為1。

5）在40ns時將1號任務(wù)掛起，由于2號任務(wù)優(yōu)先級在就緒任務(wù)中最高，out_cur_taskid為2。

6）在45ns時將2號任務(wù)掛起，同級且實時的3號任務(wù)和4號任務(wù)的優(yōu)先級在就緒任務(wù)中最高，由out_cur_taskid可以看出，3號任務(wù)和4號任務(wù)基于時間片輪轉(zhuǎn)執(zhí)行。

7）在90ns時查詢4號任務(wù)，由輸出端口可以看到4號任務(wù)的參數(shù)。

8）在100ns和105ns時分別掛起3號任務(wù)和4號任務(wù)，同級且非實時的6號任務(wù)和7號任務(wù)的優(yōu)先級在就緒任務(wù)中最高，系統(tǒng)采用先來先服務(wù)調(diào)度算法，由于6號任務(wù)先建立，故out_cur_taskid為6。

9）在115ns時刪除6號任務(wù)，out_cur_taskid為7，符合先來先服務(wù)算法的預(yù)計結(jié)果。

10）在130ns時恢復(fù)2號任務(wù)，由于2號任務(wù)優(yōu)先級高于7號任務(wù)，out_cur_taskid為2。

以上任務(wù)調(diào)度過程模擬了任務(wù)的創(chuàng)建、刪除、掛起、恢復(fù)、查詢涉及的調(diào)度情況，以及存在同級實時任務(wù)組和同級非實時任務(wù)組的調(diào)度情況，可以看出調(diào)度器實現(xiàn)了調(diào)度算法的預(yù)計功能。調(diào)度器消耗的的硬件資源如表1所示。

由以上分析可知，實驗結(jié)果驗證了硬件任務(wù)調(diào)度器的正確性和高效性，而且對于硬件資源的消耗也比較合理，符合了系統(tǒng)設(shè)計的需求。

4結(jié)論

文章提出的混合調(diào)度算法保留μC/OS-Ⅱ原有的基于優(yōu)先級的搶占式調(diào)度算法，以保證系統(tǒng)的兼容性和實時性。在此基礎(chǔ)上擴(kuò)展了同級調(diào)度，對于同級實時任務(wù)組內(nèi)的任務(wù)采用時間片輪轉(zhuǎn)算法，實現(xiàn)同級調(diào)度的公平性；對于同級非實時任務(wù)組內(nèi)的任務(wù)采用先來先服務(wù)算法，從而減少不必要的系統(tǒng)開銷。算法在擴(kuò)展同級調(diào)度的同時，盡可能減少功能改進(jìn)產(chǎn)生的開銷，并且基于FPGA實現(xiàn)，獨立的硬件邏輯較充分的發(fā)揮了系統(tǒng)潛在的并行性和實時性。如果硬件任務(wù)調(diào)度器能與實時內(nèi)核的其它部分有更深入的結(jié)合，那么調(diào)度芯片與處理器并行的模式必將成為未來嵌入式系統(tǒng)的一種發(fā)展趨勢。