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

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

0 引言

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

1 傳統(tǒng)的任務(wù)調(diào)度策略分析

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

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

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

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

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

軟實時周期任務(wù)為

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

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

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

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

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

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

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

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

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

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

(1) 硬實時周期任務(wù)

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

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

(1)

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

(2) 軟實時周期任務(wù)

軟實時周期任務(wù)的優(yōu)先級計算結(jié)合任務(wù)周期、剩余空閑時間和系統(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)先級任務(wù)調(diào)度算法分析

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

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

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

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

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

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

(3)

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

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

3 實測結(jié)果驗證及分析

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

(4)

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

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

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

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

4 結(jié)束語

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