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

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

0 引言

測控地檢設(shè)備需要對測控應(yīng)答機進(jìn)行全方位的測試驗證，在顯控軟件中既存在遙測幀解析、測量解算和遙測數(shù)據(jù)存儲等硬實時周期任務(wù)，也存在數(shù)傳幀和遙測幀顯示等軟實時周期任務(wù)[1-4]。在常規(guī)的任務(wù)調(diào)度算法中，顯控軟件采用基于固定優(yōu)先級的可搶占式時間片輪轉(zhuǎn)技術(shù)對任務(wù)集進(jìn)行調(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ù)當(dāng)前狀態(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) 顯控軟件為當(dāng)前任務(wù)分配的時間片耗盡，當(dāng)前任務(wù)讓出CPU資源并進(jìn)入隊尾，調(diào)度模塊調(diào)度就緒隊列中下一個就緒的任務(wù)執(zhí)行。

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

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

下面針對相同優(yōu)先級的任務(wù)按照時間片輪轉(zhuǎn)和高優(yōu)先級任務(wù)搶占低優(yōu)先級任務(wù)兩種情況對顯控軟件中任務(wù)調(diào)度策略進(jìn)行分析。本文將基于測控地檢設(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進(jìn)入就緒隊列的隊尾，等待顯控軟件下一次調(diào)度。然后，調(diào)度模塊調(diào)度任務(wù)τH2開始執(zhí)行，與τH1相似，τH2在執(zhí)行完一個時間片后，將上下文狀態(tài)保存并進(jìn)入隊尾。同理τ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)保存并進(jìn)入隊尾，任務(wù)τS2獲取CPU使用權(quán)開始執(zhí)行，在τS2執(zhí)行過程中，具有更高優(yōu)先級的任務(wù)τH3處于就緒狀態(tài)，則τH3立即搶占CPU資源開始執(zhí)行，τS2將上下文狀態(tài)保存并進(jìn)入隊尾，具有更高優(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ù)的當(dāng)前狀態(tài)動態(tài)地改變優(yōu)先級，高優(yōu)先級的任務(wù)持續(xù)占據(jù)CPU資源，而剩余空閑時間較小的低優(yōu)先級任務(wù)由于無法獲取CPU資源而錯失截止期。

采用下述模型對顯控軟件中更為復(fù)雜的任務(wù)集進(jìn)行分析：假設(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時刻同時達(dá)到，由于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便到達(dá)其截止期，此時TH1還未執(zhí)行完畢，由于TH1是硬實時任務(wù)，所以實際上TH1在這次任務(wù)調(diào)度中已經(jīng)夭折了。TH1繼續(xù)執(zhí)行了10 ms后TH2到來，由于TH2具有更高的優(yōu)先級，因此立即搶占CPU資源開始執(zhí)行，TH1保存上下文狀態(tài)進(jìn)入隊尾。在后續(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ù)到達(dá)時刻tarriv取值0。采用基于剩余空閑時間的調(diào)度策略對此任務(wù)集的調(diào)度如圖4所示。

由于當(dāng)前正在執(zhí)行的任務(wù)剩余空閑時間不變，而處于就緒隊列中的任務(wù)剩余空閑時間隨時間不斷減小，當(dāng)任務(wù)集中存在多個剩余空閑時間相近的任務(wù)時，任務(wù)的優(yōu)先級將會不斷進(jìn)行翻轉(zhuǎn)，產(chǎn)生頻繁的任務(wù)切換，降低軟件的調(diào)度性能。在對上面的任務(wù)集進(jìn)行調(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ù)要搶占當(dāng)前任務(wù)，其動態(tài)優(yōu)先級不僅要比當(dāng)前任務(wù)的動態(tài)優(yōu)先級高，還要比當(dāng)前任務(wù)的搶占閾值高，否則搶占失敗，當(dāng)前任務(wù)繼續(xù)執(zhí)行。

搶占閾值算法是搶占算法和非搶占算法的結(jié)合。當(dāng)搶占閾值比動態(tài)優(yōu)先級小或與之相等時，可以看做是搶占算法；當(dāng)搶占閾值很大時，可以看做是非搶占算法。搶占算法的優(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ù)當(dāng)前的剩余空閑時間；Lmax為剩余空閑時間的最大值，可以表示為任務(wù)的相對截止期與任務(wù)執(zhí)行時間之差，即Lmax=Di-ei；u為臨界參數(shù)，取值Lmax/4。

式(3)的含義為，當(dāng)剩余空閑時間在[0,u]范圍內(nèi)時，認(rèn)為當(dāng)前任務(wù)剩余空閑時間較小，設(shè)置當(dāng)前任務(wù)的搶占閾值為最高優(yōu)先級，禁止其他任務(wù)搶占該任務(wù)，從而有效提高了任務(wù)完成截止期的概率。當(dāng)剩余空閑時間較大時，通過剩余空閑時間所占的比例動態(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ù)集進(jìn)行描述。

(4)

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

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

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

分析圖7可知，改進(jìn)算法和原始算法的任務(wù)切換次數(shù)隨負(fù)載的變化趨勢相似，均在負(fù)載等于一附近達(dá)到峰值，改進(jìn)算法通過引入搶占閾值的概念，改善了由于剩余空閑時間帶來的“顛簸”現(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ù)的當(dāng)前狀態(tài)，針對硬實時周期任務(wù)和軟實時周期任務(wù)采用不同的優(yōu)先級計算策略，并針對引入剩余空閑時間導(dǎo)致的“顛簸”現(xiàn)象，提出了一種搶占閾值的計算方法。理論分析和實測數(shù)據(jù)均證明了動態(tài)雙優(yōu)先級任務(wù)調(diào)度算法的優(yōu)越性，改進(jìn)算法提高了硬實時周期任務(wù)的調(diào)度成功率，減小了軟實時周期任務(wù)的平均響應(yīng)時間，降低了任務(wù)切換次數(shù)，理論分析和實測數(shù)據(jù)均證明了該算法的優(yōu)越性。