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

高陽，盛德衛，文海

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

0 引言

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

1 傳統的任務調度策略分析

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

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

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

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

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

軟實時周期任務為

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

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

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

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

這種調度策略保證了顯控軟件中價值高的任務具有較高的優先級，從而優先獲取資源來執行，實現了任務執行的輕重緩急，同時時間片輪轉技術保證了相同優先級的任務可以平等的使用CPU資源。而這種調度策略的劣勢在于任務的優先級在任務執行之初就已固定，由于無法根據任務的當前狀態動態地改變優先級，高優先級的任務持續占據CPU資源，而剩余空閑時間較小的低優先級任務由于無法獲取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)，如果采用常規的基于固定優先級的調度策略，顯控軟件對此任務集的調度如圖3所示。

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

2 面向復雜任務集的動態雙優先級任務調度算法

2.1 動態優先級任務調度策略分析

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

(1) 硬實時周期任務

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

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

(1)

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

(2) 軟實時周期任務

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

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

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

2.2 動態雙優先級任務調度算法分析

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

建立如下模型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)，為了方便分析，系統時間片tslot取值1，任務到達時刻tarriv取值0。采用基于剩余空閑時間的調度策略對此任務集的調度如圖4所示。

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

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

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

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

(3)

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

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

3 實測結果驗證及分析

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

(4)

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

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

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

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

4 結束語

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