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

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

關鍵詞：實時操作系統(tǒng)；調度算法；硬件任務調度器

DOI：10.15938/j.jhust.2016.03.008

中圖分類號：TP316.2 文獻標志碼：A 文章編號：1007—2683（2016）03—0039—04

0引言

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

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

1硬件任務調度器的設計原理

1.1算法的設計

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

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

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

1.2調度器的數(shù)據(jù)結構

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

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

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

2.1調度器的整體設計

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

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

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

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

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

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

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

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

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

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

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

若Prio

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

最后以Sel為選擇條件，輸出相應的任務編號Cur_Id。

3實驗結果分析

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

仿真結果分析如下：

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

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

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

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

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

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

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

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

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

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

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

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

4結論

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