μC/OS—Ⅱ混合調度算法的硬件實現

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

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

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

DOI：10.15938/j.jhust.2016.03.008

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

0引言

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

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

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

1.1算法的設計

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

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

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

1.2調度器的數據結構

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

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

2硬件任務調度器的電路實現

2.1調度器的整體設計

調度器支持64個優先級，每個優先級最多支持4個同級任務，以任務狀態為觸發信號，輸出下一個要執行的任務標識符。調度器的整體設計如圖1所示。

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

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

2.2任務組調度電路的實現

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

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

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

2.3同級任務調度電路的實現

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

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

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

若Prio

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

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

3實驗結果分析

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

仿真結果分析如下：

1）在Ons時不妨設置優先級閾值prio_threshold為5。

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

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

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

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

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

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

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

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

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

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

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

4結論

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