面向復雜任務集的任務調度算法*

高陽，盛德衛(wèi)，文海

(北京電子工程總體研究所，北京 100854)

0 引言

測控地檢設備需要對測控應答機進行全方位的測試驗證，在顯控軟件中既存在遙測幀解析、測量解算和遙測數(shù)據(jù)存儲等硬實時周期任務，也存在數(shù)傳幀和遙測幀顯示等軟實時周期任務[1-4]。在常規(guī)的任務調度算法中，顯控軟件采用基于固定優(yōu)先級的可搶占式時間片輪轉技術對任務集進行調度，該技術在任務調度之初就給各個任務分配了固定優(yōu)先級，高優(yōu)先級的任務可以搶占低優(yōu)先級的任務，同等優(yōu)先級的任務采用時間片輪轉執(zhí)行[5-8]。由于該算法無法根據(jù)任務當前狀態(tài)更改優(yōu)先級，所以具有高優(yōu)先級但截止期較長的任務將持續(xù)占據(jù)CPU資源，而具有低優(yōu)先級但截止期較短的任務由于無法搶占CPU資源將會夭折。本文在基于優(yōu)先級的可搶占式時間片輪轉技術的基礎之上，綜合考慮了任務周期、相對截止期和空閑時間3個因素動態(tài)計算任務優(yōu)先級，并引入搶占閾值的思想，提出了一種面向復雜任務集的動態(tài)雙優(yōu)先級任務調度策略，旨在提高硬實時周期任務滿足截止期的概率，減小軟實時周期任務的平均響應時間[9-11]。

1 傳統(tǒng)的任務調度策略分析

基于Windows CE操作系統(tǒng)的顯控軟件對于多任務的調度采用基于固定優(yōu)先級的可搶占式時間片輪轉技術，可以將任務調度的時機總結如下：

(1) 顯控軟件為當前任務分配的時間片耗盡，當前任務讓出CPU資源并進入隊尾，調度模塊調度就緒隊列中下一個就緒的任務執(zhí)行。

(2) 在當前任務執(zhí)行過程中，具有更高優(yōu)先級的任務準備就緒，立即保存當前任務的上下文并將其狀態(tài)設置為阻塞態(tài)，高優(yōu)先級的任務獲得CPU資源開始執(zhí)行。

(3) 顯控軟件當前執(zhí)行任務的狀態(tài)發(fā)生改變，如被阻塞或掛起[12-13]。

下面針對相同優(yōu)先級的任務按照時間片輪轉和高優(yōu)先級任務搶占低優(yōu)先級任務兩種情況對顯控軟件中任務調度策略進行分析。本文將基于測控地檢設備顯控軟件中的任務抽象為2種模型：硬實時周期任務和軟實時周期任務。硬實時周期任務為

軟實時周期任務為

(1) 相同優(yōu)先級任務按照時間片輪轉

如圖1所示，任務τH1，τH2和τH3具有相同的優(yōu)先級。其中任務τH1先于τH2先于τH3處于就緒狀態(tài)。顯控軟件調度模塊首先調度任務τH1執(zhí)行，在執(zhí)行完一個時間片后，任務τH1未執(zhí)行完畢，則將τH1的上下文保存，τH1進入就緒隊列的隊尾，等待顯控軟件下一次調度。然后，調度模塊調度任務τH2開始執(zhí)行，與τH1相似，τH2在執(zhí)行完一個時間片后，將上下文狀態(tài)保存并進入隊尾。同理τH3在執(zhí)行完一個時間片后，顯控軟件將重新調度就緒隊列中的任務τH1，τH2和τH3，將狀態(tài)恢復并繼續(xù)執(zhí)行完成。

(2) 高優(yōu)先級任務搶占低優(yōu)先級任務

如圖2所示，任務τS1和τS2具有同等的低優(yōu)先級，任務τH3具有較高優(yōu)先級。其中任務τS1和任務τS2首先處于就緒狀態(tài)。由于任務τS1和τS2具有相同的優(yōu)先級，2個任務將按照時間片輪轉交替執(zhí)行，任務τS1在執(zhí)行完一個時間片后，將狀態(tài)保存并進入隊尾，任務τS2獲取CPU使用權開始執(zhí)行，在τS2執(zhí)行過程中，具有更高優(yōu)先級的任務τH3處于就緒狀態(tài)，則τH3立即搶占CPU資源開始執(zhí)行，τS2將上下文狀態(tài)保存并進入隊尾，具有更高優(yōu)先級的任務τH3將持續(xù)占據(jù)CPU資源直至其執(zhí)行完畢，然后任務τS1和τS2被喚醒繼續(xù)按照時間片輪轉交替執(zhí)行。

這種調度策略保證了顯控軟件中價值高的任務具有較高的優(yōu)先級，從而優(yōu)先獲取資源來執(zhí)行，實現(xiàn)了任務執(zhí)行的輕重緩急，同時時間片輪轉技術保證了相同優(yōu)先級的任務可以平等的使用CPU資源。而這種調度策略的劣勢在于任務的優(yōu)先級在任務執(zhí)行之初就已固定，由于無法根據(jù)任務的當前狀態(tài)動態(tài)地改變優(yōu)先級，高優(yōu)先級的任務持續(xù)占據(jù)CPU資源，而剩余空閑時間較小的低優(yōu)先級任務由于無法獲取CPU資源而錯失截止期。

采用下述模型對顯控軟件中更為復雜的任務集進行分析：假設顯控軟件中存在2個硬實時周期任務和1個軟實時周期任務，硬實時任務模型可以表示為THi=(Ti,Di,di,Pi,tslot,ei,tarriv)，軟實時任務表示為TSi=(Ti,Di,di,Pi,tslot,ei,tarriv)，2個硬實時任務分別為TH1=(80,80,80,253,100,20,0)，TH2=(90,90,90,248,100,30,0)，軟實時任務為TS1=(110,100,100,251,100,40,0)，如果采用常規(guī)的基于固定優(yōu)先級的調度策略，顯控軟件對此任務集的調度如圖3所示。

在上述模型中，3個任務在0時刻同時達到，由于TH2優(yōu)先級高于TS1高于TH1，所以TH2優(yōu)先執(zhí)行，TH2執(zhí)行了30 ms后執(zhí)行完畢，交出CPU使用權，顯控軟件的調度模塊調度具有第2優(yōu)先級的TS1開始執(zhí)行，TS1在40 ms后執(zhí)行完畢，調度模塊調度TH1開始執(zhí)行，TH1執(zhí)行了10 ms便到達其截止期，此時TH1還未執(zhí)行完畢，由于TH1是硬實時任務，所以實際上TH1在這次任務調度中已經(jīng)夭折了。TH1繼續(xù)執(zhí)行了10 ms后TH2到來，由于TH2具有更高的優(yōu)先級，因此立即搶占CPU資源開始執(zhí)行，TH1保存上下文狀態(tài)進入隊尾。在后續(xù)任務調度中，可以發(fā)現(xiàn)TH1由于優(yōu)先級較小且無法動態(tài)改變而多次夭折。這種任務調度對于地檢設備顯控軟件而言顯然是不合理的。

2 面向復雜任務集的動態(tài)雙優(yōu)先級任務調度算法

2.1 動態(tài)優(yōu)先級任務調度策略分析

針對顯控軟件中硬實時周期任務和軟實時周期任務本身不同的特點，提出2種不同的優(yōu)先級計算公式，對于硬實時周期任務，主要考慮相對截止期和剩余空閑時間2種因素，對于軟實時周期任務，主要考慮任務周期和剩余空閑時間2種因素。

(1) 硬實時周期任務

硬實時周期任務的優(yōu)先級計算結合剩余空閑時間、相對截止期和系統(tǒng)時間片3方面因素。由于相對截止期對于硬實時周期任務具有重要意義，故將其作為優(yōu)先級計算的因素，可如果只考慮相對截止期，會使截止期較長的任務由于優(yōu)先級較低而遲遲得不到響應，從而錯過截止期，故引入剩余空閑時間這一因素，通過相對截止期和剩余空閑時間共同作用計算優(yōu)先級。硬實時周期任務的優(yōu)先級計算公式為

PHi=Pinit+(di-t-eri+Di)/n/tslot·Prange，

(1)

式中：Pinit設置為顯控軟件中用戶應用程序的最高級，取值248，由于優(yōu)先級最小等于255，故優(yōu)先級變化范圍Prange取值7；(di-t-eri+Di)/n/tslot為優(yōu)先級變化系數(shù)Ki，顯然Ki要在0至1之間變化，下面給出證明如下。周期任務的相對截止期Di小于任務周期Ti，而剩余空閑時間di-t-eri

(2) 軟實時周期任務

軟實時周期任務的優(yōu)先級計算結合任務周期、剩余空閑時間和系統(tǒng)時間片3方面因素。優(yōu)先級計算公式為

PSi=Pinit+(di-t-eri+Ti)/n/tsolt·Prange，(2)

式中:Pinit取值248；Prange取值7；系數(shù)Ki=(di-t-eri+Ti)/n/tslot，下面對系數(shù)0

2.2 動態(tài)雙優(yōu)先級任務調度算法分析

計算動態(tài)優(yōu)先級時引入了剩余空閑時間，會產(chǎn)生“顛簸”現(xiàn)象。下面通過建立一個模型分析一下“顛簸”現(xiàn)象給任務調度帶來的影響。

建立如下模型Ti=(di,ei,eri,tslot,tarriv)，顯控軟件任務集中存在3個任務T1=(12,5,5,1,0)，T2=(13,5,5,1,0)和T3=(14,7,7,1,0)，為了方便分析，系統(tǒng)時間片tslot取值1，任務到達時刻tarriv取值0。采用基于剩余空閑時間的調度策略對此任務集的調度如圖4所示。

由于當前正在執(zhí)行的任務剩余空閑時間不變，而處于就緒隊列中的任務剩余空閑時間隨時間不斷減小，當任務集中存在多個剩余空閑時間相近的任務時，任務的優(yōu)先級將會不斷進行翻轉，產(chǎn)生頻繁的任務切換，降低軟件的調度性能。在對上面的任務集進行調度的過程中，只有任務1在截止期內執(zhí)行完畢，其余任務均夭折。由于3個任務均分CPU資源，使得CPU利用率非常低。解決“顛簸”現(xiàn)象的方法是在任務調度時引入搶占閾值，形成雙優(yōu)先級策略。本文在動態(tài)優(yōu)先級的算法基礎之上提出了一種基于剩余空閑時間的搶占閾值算法，有效降低了任務的切換次數(shù)，提高了CPU利用率。

搶占閾值算法采用雙優(yōu)先級調度策略，即顯控軟件中每個任務除了擁有一個根據(jù)其參數(shù)狀態(tài)計算的動態(tài)優(yōu)先級外，還會在任務執(zhí)行時被賦予第2優(yōu)先級，稱之為搶占閾值。規(guī)定如果顯控軟件中其余任務要搶占當前任務，其動態(tài)優(yōu)先級不僅要比當前任務的動態(tài)優(yōu)先級高，還要比當前任務的搶占閾值高，否則搶占失敗，當前任務繼續(xù)執(zhí)行。

搶占閾值算法是搶占算法和非搶占算法的結合。當搶占閾值比動態(tài)優(yōu)先級小或與之相等時，可以看做是搶占算法；當搶占閾值很大時，可以看做是非搶占算法。搶占算法的優(yōu)勢在于能夠對緊急任務做出及時響應，但容易造成過多的任務切換。非搶占算法的優(yōu)勢在于能夠降低任務截止期的錯失率，但對于緊急任務的響應不夠及時。搶占閾值算法結合了2種算法的優(yōu)勢，通過對閾值的合理取值，既能保證對緊急任務的及時響應，又能降低任務錯過截止期的概率。

本文提出的基于剩余空閑時間的搶占閾值計算方法如式(3)所示：

(3)

式中：Pinit為顯控軟件中用戶應用程序的最高級；Prange為優(yōu)先級的取值范圍，取值7；Li為任務當前的剩余空閑時間；Lmax為剩余空閑時間的最大值，可以表示為任務的相對截止期與任務執(zhí)行時間之差，即Lmax=Di-ei；u為臨界參數(shù)，取值Lmax/4。

式(3)的含義為，當剩余空閑時間在[0,u]范圍內時，認為當前任務剩余空閑時間較小，設置當前任務的搶占閾值為最高優(yōu)先級，禁止其他任務搶占該任務，從而有效提高了任務完成截止期的概率。當剩余空閑時間較大時，通過剩余空閑時間所占的比例動態(tài)計算搶占閾值，降低了任務的切換次數(shù)，提高了顯控軟件性能。

3 實測結果驗證及分析

測試平臺選用基于OMAP3530芯片的Devikit8000硬件平臺，Windows CE6.0操作系統(tǒng)。顯控軟件任務集包括測量解算和遙測數(shù)據(jù)解析2個硬實時周期任務及遙測數(shù)據(jù)顯示和網(wǎng)絡通信2個軟實時周期任務，使用如下模型對任務集進行描述。

(4)

采用原始算法和動態(tài)雙優(yōu)先級調度算法分別對顯控軟件任務集進行調度。通過設置定時器任務的數(shù)量調整系統(tǒng)的負載值，采集2種算法在不同負載下運行2 500 ms后的執(zhí)行情況，重點關注硬實時周期任務調度成功率、軟實時周期任務平均響應時間和任務切換次數(shù)3個性能指標。對5次實驗的測試結果取平均值，記錄如表1所示。

為了更加直觀地分析原始算法和改進算法各類性能指標隨負載變化的情況，將表1繪制成圖5、圖6和圖7。分析圖5可知，對于測量解算等硬實時周期任務而言，采用動態(tài)雙優(yōu)先級調度算法比原始算法獲得更高的調度成功率，隨著顯控軟件負載增加，動態(tài)雙優(yōu)先級調度算法的優(yōu)越性也更加明顯，這是因為硬實時周期任務優(yōu)先級的計算結合了相對截止期和剩余空閑時間2種任務屬性，優(yōu)先級分配更加合理。分析圖6可知，對于遙測數(shù)據(jù)顯示等軟實時周期任務而言，由于其優(yōu)先級的計算結合了剩余空閑時間，改進算法比原始算法獲得更低的平均響應時間，同樣隨著顯控軟件負載增加，改進算法的優(yōu)勢也更加明顯。

表1 調度算法優(yōu)化前后各類性能指標對比Table 1 Comparison of various performance indexes before and after the optimization of scheduling algorithm

分析圖7可知，改進算法和原始算法的任務切換次數(shù)隨負載的變化趨勢相似，均在負載等于一附近達到峰值，改進算法通過引入搶占閾值的概念，改善了由于剩余空閑時間帶來的“顛簸”現(xiàn)象，有效降低了任務切換次數(shù)。

4 結束語

本文針對常規(guī)任務調度算法無法根據(jù)任務狀態(tài)實時更改優(yōu)先級，高優(yōu)先級任務持續(xù)占據(jù)CPU資源，而截止期較短但優(yōu)先級較低的任務由于無法搶占CPU資源而夭折的問題，提出了一種面向復雜任務集的動態(tài)雙優(yōu)先級任務調度算法，在時間片輪轉技術的基礎上，綜合考慮任務的當前狀態(tài)，針對硬實時周期任務和軟實時周期任務采用不同的優(yōu)先級計算策略，并針對引入剩余空閑時間導致的“顛簸”現(xiàn)象，提出了一種搶占閾值的計算方法。理論分析和實測數(shù)據(jù)均證明了動態(tài)雙優(yōu)先級任務調度算法的優(yōu)越性，改進算法提高了硬實時周期任務的調度成功率，減小了軟實時周期任務的平均響應時間，降低了任務切換次數(shù)，理論分析和實測數(shù)據(jù)均證明了該算法的優(yōu)越性。