一種采用搶占閾值的軟實時動態(tài)調(diào)度策略PT-STDS

王文樂,龔 俊,曹重華,曹遠龍,陳洪琪,柯勝男,涂 珍

1(江西師范大學 軟件學院,南昌 330022)2(江西財經(jīng)大學 軟件與通信工程學院,南昌 330032)3(江西科技師范大學 數(shù)學與計算機科學學院,南昌 330038)

1 引 言

實時應用環(huán)境中,系統(tǒng)首先保證任務的成功率,從而獲得較好的資源利用率.傳統(tǒng)的實時系統(tǒng)研究對象大都是硬實時任務,即任務錯過其截止期即無效.而現(xiàn)實中許多實時應用,如多媒體、網(wǎng)絡傳輸和大數(shù)據(jù)處理等,其任務具備軟實時特性,即:錯過截止期之后一段時間,仍然能夠帶來系統(tǒng)收益.Anderson[1]等提出的調(diào)度方法,獲得較好的調(diào)度性能與任務延遲率.Ma等[2]分析內(nèi)核可靠性和溫度之間的關系,提出一種調(diào)節(jié)內(nèi)核頻率/電壓的啟發(fā)式算法以控制內(nèi)核利用率,提高了軟實時系統(tǒng)的生命期.Y.Du 等[3]研究云計算環(huán)境,在可行的服務質(zhì)量(QoS)區(qū)域開發(fā)非空白資源分配的一般外界,并通過有利于具有最大QoS缺陷實時任務、動態(tài)優(yōu)化其內(nèi)在約束,提高了資源分配效率.Barbieru[4]基于Hadoop大數(shù)據(jù)環(huán)境設計了一個實時作業(yè)調(diào)度程序,能夠處理需要實時執(zhí)行的小任務,并解決了長任務完成時間不確定的問題.Palopoli等[5]提出一種利用無限狀態(tài)離散時間馬爾可夫鏈的調(diào)度算法,通過封閉形式的保守約束,降低了軟實時系統(tǒng)中周期性任務的截止期錯失率.孫景昊等[6]針對偽多項式時間判定算法的局限性,提出同/異步實時系統(tǒng)上EDF可調(diào)度性分析問題統(tǒng)一的多項式時間線性松弛求解方法,提高了可調(diào)度性任務的比例.郭銳鋒等[7]針對不同類型的實時任務,提出了一種分層框架進行相應調(diào)度,降低了任務的截止期錯失率.綜上,現(xiàn)有的軟實時調(diào)度研究,首先考慮系統(tǒng)任務的成功率,而未充分考慮其價值收益.

實時調(diào)度策略按照是否搶占分為非搶占式調(diào)度和搶占式調(diào)度兩種.非搶占式調(diào)度策略可能造成高優(yōu)先級任務被低優(yōu)先級者阻塞而降低系統(tǒng)的可調(diào)度性.搶占式調(diào)度策略中,正在執(zhí)行的任務隨時可能被高優(yōu)先級任務搶占,直到該高優(yōu)先級任務完成.不過,由于任務搶占時,系統(tǒng)需要上下文切換、總線和緩沖區(qū)等相關資源代價,過多的搶占也會消耗系統(tǒng)資源而影響調(diào)度性.因此,需要限制系統(tǒng)中的搶占行為,而設置搶占閾值是一個好的選擇,它具有較低的實施代價和較高的執(zhí)行效率.Bertogna等[8]提出一種單核平臺上的有限搶占動態(tài)調(diào)度策略,具有良好的調(diào)度性能和低的系統(tǒng)開銷.李琦等[9]提出基于EDF思想的動態(tài)模糊閾值軟實時調(diào)度策略,獲得了較好的CPU利用率和系統(tǒng)成功率.夏家莉等[10]對硬實時環(huán)境,提出針基于任務執(zhí)行緊迫度的調(diào)度方法,能夠有效提高任務的成功率和收益.

本文以軟實時任務為主要研究對象,采用基于搶占閾值的動態(tài)調(diào)度思想,綜合考慮實時任務的緊迫性和價值,提出一種采用搶占閾值的動態(tài)調(diào)度策略(Preemption Threshold in Soft real-time Task Dynamic Scheduling strategy,簡稱 PT-STDS).

2 任務模型

2.1 軟實時任務模型

系統(tǒng)中實時任務集合記為T={T1,T2,…,Tn},對于每一個任務Ti,它具有如下屬性,如表1所示.

表1 任務Ti的屬性列表Table 1 Properties list of task Ti

●Ti的價值函數(shù):Vi(t).軟實時任務Ti滿足:Vi(t)>0,其中t∈[di,cri).任務的價值函數(shù)Vi(t)將在2.2節(jié)詳細分析.

● 價值密度函數(shù):VDi(t).在t0時刻,滿足:VDi(t)=Vi(t)/rti.VDi(t)會隨著rti數(shù)值的減少而不斷增長.

定義1.任務Ti的軟剩余可執(zhí)行時間:slti.在t0時刻,滿足:slti=cri-t0.

為了明確本文的研究內(nèi)容,做出如下假設:

假設1.僅考慮系統(tǒng)中的CPU時間資源,不考慮空間、I/O或數(shù)據(jù)等資源;

假設2.任務之間除了存在CPU競爭外,不存在其它的觸發(fā)、嵌套等依賴關系;

假設3.文中不考慮任務間上下文切換所造成的時間代價;

假設4.系統(tǒng)中進入調(diào)度的任務Ti都滿足slti>rti,即任務在任何時刻都保證有足夠時間完成.

假設5.任務Ti價值函數(shù)Vi(t)在[di,cri)區(qū)間呈線性下降;

假設6.當任務Ti執(zhí)行在[di,cri)區(qū)間執(zhí)行時,為了保護該類任務的執(zhí)行,Ti不允許被搶占.

2.2 軟實時任務的價值函數(shù)和價值密度

根據(jù)假設4,軟實時任務Ti在t時刻的價值函數(shù)Vi(t)滿足(1)式:

(1)

如(1)式中,當t

價值密度函數(shù)VDi(t)=Vi(t)/rti,根據(jù)(1)式可得(2)式:

(2)

從(2)式可知,VDi(t)不僅與Vi(t)有關,而且與rti有關.根據(jù)任務模型定義可知,rti=eti-hti.顯然,當任務Ti保持運行時,rti會隨時間t增長而減小;而當Ti被掛起(阻塞)時,rti則保持不變.下面討論價值密度函數(shù)VDi(t):

①t

(3)

當di≤t

II.當di≤t

綜上,可得到定理1.

定理1.在任務Ti保持執(zhí)行過程中,VDi(t)隨時間增長而遞增.

2.3 任務的緊迫性

任務Ti的緊迫性數(shù)值越大，意味著該任務越需要盡早執(zhí)行.

從定義2可知,Ugi(t)受sti的變化影響,具體討論如下:

● 當Ti保持執(zhí)行時,隨著時間t的增長sti保持不變,Ugi(t)也保持不變;

● 當Ti被搶占掛起時,隨著t的增長sti不斷減小,使得Ugi(t)增長.

3 軟實時任務的優(yōu)先級和閾值

本文用系統(tǒng)調(diào)度基于任務優(yōu)先級驅(qū)動,而任務的優(yōu)先級函數(shù)結合價值密度和緊迫性.

3.1 任務的優(yōu)先級分派函數(shù)構造

根據(jù)任務調(diào)度的目的,在保證任務執(zhí)行的基礎上優(yōu)先考慮任務帶來的系統(tǒng)收益.因此,本文的任務優(yōu)先級分派函數(shù)如下:

pri=Ugi(t)*VDi(t)

(4)

任務需要完成才能獲得價值,任務的緊迫性相對其價值密度更加重要.基于此,將(4)式設計成(5)式:

pri=Ugi(t)*ln[1+VDi(t)]

(5)

根據(jù)第2章分別對價值密度VDi(t)和緊迫性Ugi(t)的分析之后,繼續(xù)討論在t時刻任務Ti的優(yōu)先級pri變化:

● 當Ti在t

(6)

■ 當Ti保持執(zhí)行時,根據(jù)定理1可知,ln[1+Vi/rti]隨著t的增長而遞增,而sti則保持不變,可知(6)式保持遞增;

因此,在t

● 當Ti在di≤t

(7)

當Ti再執(zhí)行Δt時間后,有:

3.2 任務的搶占閾值選取

搶占閾值的選取直接影響調(diào)度算法的性能.當系統(tǒng)中任務的閾值設置為無限時,調(diào)度策略變成了非搶占式策略;因此,任務搶占閾值的選擇會直接影響任務的執(zhí)行.下面將通過分析任務的響應時間來選取搶占閾值.

定義3.任務Ti的影響任務集EJSi(Effect Job Set).在任務Ti的執(zhí)行過程內(nèi),能夠搶占其執(zhí)行的所有任務集合,稱為Ti的影響作業(yè)集EJSi,滿足:

EJSi={Tm|(prim>prii)∧(Dm>Ai)∧(Am

(8)

任務Ti的響應時間Rti應該包括兩個部分:估算執(zhí)行時間和影響任務集的剩余執(zhí)行時間之和,滿足(9)式:

(9)

通過分析任務Ti的響應時間Rti,在保證Ti可調(diào)度情況下獲得閾值θi的取值,選取閾值的過程如算法1所示.

明顯地,算法1中有一個while循環(huán)結構,其計算復雜度為O(n).該算法在保證任務集可調(diào)度情況下,找到一個閾值的最優(yōu)解.

4 基于搶占閾值的調(diào)度策略

本文調(diào)度策略是基于閾值的有限搶占調(diào)度策略,通過限制搶占次數(shù)以減少任務的阻塞時間.

定義4.pri>θj的充分必要條件是：任務Ti能夠搶占任務Tj.

根據(jù)定義4,任務Ti搶占任務Tj,則必然有:pri>prj.

定理2.如果任務Ti和任務Tj互不搶占,則它們滿足:(pri≤θj)∧(prj≤θi)

證明:反證法.假設存在互不搶占的兩個任務:Tp和Tq,滿足((prp≤θq)∧(prq≤θp))

?(prp>θq)∨(prq>θp),則根據(jù)定義4,現(xiàn)在對該式可能的兩種情況進行討論:

● 若prp>θq,任務Tp能夠搶占任務Tq;

● 若prq>θp,任務Tq能夠搶占任務Tp;

顯然地,任務Tp與任務Tq可能相互搶占,與定義4矛盾.因此,定理2得證.

4.1 基于搶占閾值的調(diào)度算法

本文搶占閾值的動態(tài)調(diào)度算法PT-STDS調(diào)用算法1確定搶占閾值,并且確定動態(tài)搶占的調(diào)度隊列,具體如算法2所示.

例1.假設系統(tǒng)中現(xiàn)有以下4個任務,它們具有的屬性如表2所示.

表2 系統(tǒng)任務集合屬性Table 2 Properties of task set

現(xiàn)對以上任務集采用PT-STDS算法進行調(diào)度,調(diào)度過程如下:

● t=0時,T1到達.T1執(zhí)行;

● t=2時,T2到達,T1已執(zhí)行2(ht1=2).此時,根據(jù)(6)式計算任務優(yōu)先級:pr1

● t=3.5時,T1完成.根據(jù)算法2第2行,T2執(zhí)行;

● t=4時,T3到達,T2已執(zhí)行0.5(ht2=0.5).此時,根據(jù)(6)式計算任務優(yōu)先級:pr2>pr3,T2繼續(xù)執(zhí)行;

● t=6時,T2完成.T3執(zhí)行;

● t=7時,T4到達,T3已執(zhí)行1(ht3=1).根據(jù)(6)式計算任務優(yōu)先級:pr4>pr3,根據(jù)算法1計算θ3,得:pr4>θ3.根據(jù)算法2的第13行,T4搶占T3,T3被阻塞;

● t=9時,T4完成.T3執(zhí)行;

● t=12時,T3錯過截止期,延遲2單位至完成;

以上調(diào)度過程,相對于LSF算法或EDF算法,減少了任務間的搶占,從而減少了任務延遲率.

4.2 算法復雜性分析

對4.1節(jié)中基于搶占閾值的調(diào)度算法分析可知,算法2中只有1個循環(huán),即第11步是長度等于就緒隊列中任務數(shù)num的循環(huán).第13步計算閾值的復雜都為O(n),可知整個調(diào)度算法的計算復雜度為O(n*m).

5 實驗仿真與性能分析

5.1 實驗環(huán)境及性能指標

實驗平臺為Inter Core i5 2.5GHz、內(nèi)存為4GB的機器,系統(tǒng)為Ubuntu Linux系統(tǒng),所有實驗程序采用C語言編寫.

本實驗考慮系統(tǒng)中的非周期性任務,任意任務Ti的到達時間服從泊松分布(λ=4),其估算執(zhí)行時間eti服從[5,20]平均分布,其截止期di取值為[1.2,1.5] *eti內(nèi)平均分布,其臨界點cri取值為[1.2,1.5] *di,其價值Vi在[10,50]間隨機選取.

本系統(tǒng)實驗選取2000個時間單位內(nèi)的任務,所有的性能取100次獨立實驗的結果平均值.

性能指標包括以下3個.

1.系統(tǒng)成功率SSR(System Success Ratio):所有成功任務的數(shù)量/系統(tǒng)總?cè)蝿諗?shù)量;

2.平均任務延遲率ATDR(Average Tasks Delay Ratio):所有任務延遲率的平均值,其中 任務延遲率= (執(zhí)行延遲時間/成功任務的執(zhí)行時間);

3.系統(tǒng)累積價值TV(Total Value):所有成功任務所獲得的價值之和.

5.2 性能結果分析

基于軟實時環(huán)境下的搶占閾值調(diào)度策略PT-STDS,與EDF策略和LSF策略進行對照實驗,仿真的結果及性能分析如下.

1)系統(tǒng)成功率SSR.如圖1中所示,橫軸表示系統(tǒng)負載Load,縱軸為SSR.隨著系統(tǒng)負載增加,任務之間的搶占加劇,造成SSR不斷降低.SSR性能按從高到低的順序依次為:PT-STDS > LSF > EDF.因為SSR的動態(tài)搶占能夠適應系統(tǒng)環(huán)境,而其具有的搶占閾值減少了無效搶占;LSF算法雖然總是動態(tài)選擇空閑時間最短的任務,但其無限制的搶占會造成系統(tǒng)資源浪費,導致任務錯過臨界點;EDF算法則選擇任務的截止期最短而非最緊迫的任務執(zhí)行,會造成許多任務失敗,其帶來的SSR最低.

2)總?cè)蝿昭舆t率ATDR.如圖2所示,ATDR隨系統(tǒng)負載Load加劇呈增加最后下降的趨勢,這是由于負載越大任務間的資源競爭越劇烈,導致任務延遲率加重;當系統(tǒng)負載太大時,系統(tǒng)會根據(jù)響應時間丟開部分不能完成的任務，從而減少了任務延遲.ATDR性能最優(yōu)的是PT-STDS算法,而EDF算法導致的ATDR最高.因為PT-STDS選擇緊迫性高者執(zhí)行,

圖1 SSR性能比較結果Fig.1 SSR performance results

并且限制了任務間搶占次數(shù),從而減少任務的延遲.LCF算法選擇空閑時間最短者時,負載較輕時ATDR性能與PT-STDS方法相當,不過當系統(tǒng)負載較大時,其無效搶占造成CPU資源浪費，而使得ATDR急劇增加.EDF算法選擇截止期最短者執(zhí)行,而截止期最短并非空閑時間最短,從而造成系統(tǒng)ATDR最高.

圖2 ATDR性能比較結果Fig.2 ATDR performance results

3)系統(tǒng)累積價值TV.如圖3所示,各種調(diào)度策略下TV隨系統(tǒng)負載加劇的變化呈逐漸減少的趨勢.PT-STDS算法獲得了最高的TV,因為PT-STDS傾向于選擇高價值密度的任務,然后依次是LSF算法與EDF算法.同種負載情況下,LSF算法獲得的TV優(yōu)于EDF,因為LSF總能獲得更好的SSR,從而帶來更高的TV性能.

圖3 TV性能結果Fig.3 TV performance results

6 總 結

本文考慮軟實時環(huán)境,首先,綜合考慮任務的空閑時間和價值密度因素組合,給出其優(yōu)先級構造函數(shù);通過任務之間的搶占關系,確定任務被搶占的閾值.并且,提出基于搶占閾值的動態(tài)調(diào)度策略PT-STDS.實驗結果顯示,相對于經(jīng)典的LSF或EDF方法,PT-STDS策略能夠獲得更好的系統(tǒng)性能.

下一步,我們將考慮在諸如物聯(lián)網(wǎng)等實時約束環(huán)境,研究相關的任務處理技術.

：

[1] James H.Anderson,Jeremy P.Erickson,UmaMaheswari C.Devi,et al.Optimal semi-partitioned scheduling in soft real-time systems[C].Proceedings of the 20th International Conference on Embedded and Real-Time Computing Systems and Applications(RTCSA),Chongqing,2014:1-21.

[2] Ma Y,Chantem T,Hu X S,et al.Improving lifetime of multicore soft real-time systems through global utilization control[C].Proceedings of the 25th Edition on Great Lakes Symposium on VLSI,Pittsburgh,PA.ACM,2015:79-82.

[3] Du Y,G.de Veciana.Scheduling for cloud-based computing systems to support soft real-time applications[C].Proceedings of the 35th Annual IEEE International Conference on Computer Communications(INFOCOM),San Francisco,CA,2016:1-9.

[4] Barbieru C,Pop F.Soft real-time hadoop scheduler for big data processing in smart cities[C].Proceedings of the IEEE 30th International Conference on Advanced Information Networking and Applications(AINA),Crans-Montana，Swofzerland,2016:863-870.

[5] Palopoli L,Fontanelli D,Abeni L,et al.An analytical solution for probabilistic guarantees of reservation based soft real-time systems[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(3):640-653.

[6] Sun Jing-hao,Sun Jing-chang,Guan Nan,et al.Integer programming approach for schedulability of sporadic real-time systems[J].Journal of Software,2017,28(2):411-428.

[7] Guo Rui-feng,Peng A-zhen,Deng Chang-yi,et al.Adaptive scheduling strategy oriented to hybrid tasks[J].Journal of Chinese Computer Systems,2016,37(1):61-64.

[8] Bertogna M,Baruah S.Limited preemption EDF scheduling of sporadic task systems[J].IEEE Transactions on Industrial Informatics,2010,6(4):579-591.

[9] Li Qi,Ba Wei.Two improved EDF dynamic scheduling algorithms in soft real-time systems[J].Chinese Journal of Computers,2011,34(5):943-950.

[10] Xia Jia-li,Cao Chong-hua,Wang Wen-le,et al.Real-time task scheduling strategy based on load execution urgency[J].Computer Science,2014,41(2):215-218.

附中文參考文獻：

[6] 孫景昊,孫景昶,關 楠,等.偶發(fā)實時系統(tǒng)可調(diào)度性分析問題的整數(shù)規(guī)劃方法[J].軟件學報,2017,28(2):411-428.

[7] 郭銳鋒,彭阿珍,鄧昌義,等.面向混合任務的自適應調(diào)度策略研究[J].小型微型計算機系統(tǒng),2016,37(1):61-64.

[9] 李 琦,巴 巍.兩種改進的EDF軟實時動態(tài)調(diào)度算法[J].計算機學報,2011,34(5):943-950.

[10] 夏家莉,曹重華,王文樂,等.基于負載執(zhí)行緊迫度的實時補償任務調(diào)度策略TSCTTL[J].計算機科學,2014,41(2):215-218.