基于概率性分析的混合關鍵級系統(tǒng)節(jié)能調度算法

冒 航,張鳳登,陸 禹,朱嘉煒

(上海理工大學 光電信息與計算機工程學院,上海 200093)

隨著計算機技術的發(fā)展,實時系統(tǒng)得到了廣泛應用,嵌入式實時系統(tǒng)的復雜度也不斷提升。將不同重要性的任務或功能整合到一個平臺上工作成為一個趨勢,這樣雖可以進一步節(jié)約成本和減少能耗,但導致了混合關鍵級系統(tǒng)(Mixed Criticality System,MCS)的出現[1]?；旌详P鍵級系統(tǒng)主要應用于安全關鍵領域,例如汽車電子、航空航天等領域。汽車的剎車不能實時控制制動、飛機不能有效控制轉向和航速等問題將會產生災難性的后果,這些任務稱為安全關鍵級任務[2]。當資源配置不足或安全關鍵任務需要更多資源時,可以暫時合理放棄某些非安全關鍵任務,以確保安全關鍵任務的實時性和正確性,這也是混合關鍵級系統(tǒng)進行資源調度的顯著特征。

目前,對混合關鍵級系統(tǒng)的研究已經從功能方面逐步深入到非功能方面,例如制約該類系統(tǒng)進一步發(fā)展的能耗問題[3]。由于混合關鍵級系統(tǒng)的實時性要求使得系統(tǒng)建模和分析偏向于較壞的情況,所以容易存在資源配置過度問題。因此,對混合關鍵級系統(tǒng)的節(jié)能問題進行研究具有重要的現實意義。

本文對混合關鍵級系統(tǒng)中存在的固定優(yōu)先級任務節(jié)能問題進行研究,提出了基于概率性分析的混合關鍵級系統(tǒng)節(jié)能調度算法。該算法創(chuàng)新性地將概率性分析方法引入了系統(tǒng)的響應時間分析,通過將DVFS技術和混合關鍵級系統(tǒng)調度算法相結合挖掘空閑時間,從而在保證系統(tǒng)實時性的前提下降低系統(tǒng)的能耗。

1 模型介紹及理論基礎

1.1 任務模型

1)Ti表示任務的周期;

4)pETi是任務的概率分布函數,表示任務在某個時間段內完成的概率值;

5)Li表示任務的關鍵級別。Li∈{L,H},其中L表示低關鍵級任務,H表示高關鍵級任務。

1.2 概率模型

對于具有概率執(zhí)行時間的任務,需要概率模型來進行可調度性分析。文獻[4～5]對實時系統(tǒng)的概率性分析進行了描述分析,本文的概率模型以此為基礎進行了總結分析。概率模型是對任務的執(zhí)行時間進行概率性分析,所以該模型是基于時間的離散概率模型。

本文中任務τi的概率分布函數為pETi,該函數是一個3×n的矩陣,并且與fi概率質量函數[6](Pro-bability Mass Function,PMF)[6]和Fi累積分布函數(Cumulative Distribution Function,CDF)[7]有關。pETi具體定義如下

(1)

其中,n是任務執(zhí)行時間可能性的個數,為提高概率模型的可讀性,通常假設c1

1.3 能耗模型

本文考慮在單處理器上運行混合關鍵級任務。只要系統(tǒng)的CPU(Central Processing Unit)支持DVFS技術,則CPU的頻率可以在任務運行時進行調整。本文采用的功率模型為[8]

(2)

本文采用DVFS以減少動態(tài)功耗從而達到降低總功耗的目的,該策略主要是探索更多的空閑時間來達到預期能耗的最小化。

假設1處理器的頻率范圍為[fmin,fmax],系統(tǒng)以頻率fb為基本頻率運行,并且fmin≤fb≤fmax,該值是系統(tǒng)正常運行時的頻率值,也就是未使用DVFS策略時的頻率。

假設2當處理器在頻率為fmax運行時,此時其處理器的速度值SH=1。因此,處理器按比例在頻率為f運行時,其處理器的相對速度值為f/fmax。

2 算法設計

2.1 算法描述

本文算法的目的是在混合關鍵級系統(tǒng)的實時約束下,滿足系統(tǒng)安全性的同時使得系統(tǒng)任務的能耗最小化。本文提出了基于概率性分析的混合關鍵級系統(tǒng)節(jié)能調度算法來解決周期性非搶占固定優(yōu)先級任務的高功耗問題。該算法使用基于松弛時間的DVFS分析方法,充分挖掘任務的實際完成時間與截止時間之間的差值來降低處理器頻率。

(3)

本文提出概率性分析的節(jié)能調度算法有助于獲得平均最小能耗的調度表,同時滿足系統(tǒng)任務的實時性要求。概率信息僅用于對平均能耗的計算以及能耗最小化,對系統(tǒng)的可調度性沒有影響。偽代碼如下所示。

算法1 基于概率性分析的混合關鍵級系統(tǒng)節(jié)能調度算法輸入:MCS周期任務集Γ={τ1,τ2,…,τn};輸出:任務調度表。1Begin:2input Γ=τ1,τ2…,τn /*輸入任務集*/3for τi from 1 to n4 for pL→H from(pL→H)min to (pL→H)max5 CLi=F-1i(pL→H) /*計算任務執(zhí)行時間*/6 if Ri≤Di then7 SL←Smin /*選擇最小處理器速度*/8 end if9 Calcu(Eε ) /*計算單個任務平均能耗*/10 end for11 ∑ni=1Calcu(Eε ) /*計算任務集平均能耗*/12end for13end

該算法的可調度性通過確定任務的WCET來保證,分析流程可以分為以下幾步:

(4)

2)內部優(yōu)化:該部分主要是計算最小的SL。為確保系統(tǒng)可調度性,本文進行了基于最大響應時間的分析,從而得出在滿足可調度性的條件下處理器速度的最小值。根據處理器的速度值SL可得到作業(yè)的輸出時間表,該時間調度表作為能耗估算的輸入在外部優(yōu)化中使用。

3)能耗比較:在以上流程完成后,通過將系統(tǒng)平均能耗進行比較可得出平均能耗最小值以及最佳的SL和pL→H。

2.2 可調度性分析

本文使用最大響應時間分析方法。該方法先計算任務的最大響應時間Ri,如果任務的最大響應時間小于其截止期Di,則該任務可以被調度。如果任務集中的任務都可以被調度,則該系統(tǒng)可調度并且安全,其算法分析流程如圖1所示。

圖1 可調度性分析流程Figure 1. Flow of schedulability analysis

從任務到達時刻直至任務執(zhí)行完成的時刻,這段時間間隔稱為響應時間。文獻[13～14]提出了較先進的非搶占固定優(yōu)先級調度的響應時間分析方法。非搶占固定優(yōu)先級的最壞響應時間Ri具體計算如下所示

(5)

其中,Bi是由較低優(yōu)先級任務引起的最大阻塞時間;Ci是任務τi執(zhí)行所產生的時間;Nj是優(yōu)先級高于任務τi的干擾作業(yè)數;Cj是任務τj執(zhí)行所產生的時間;Bi的計算式如下所示

(6)

其中,對于混合關鍵級系統(tǒng)來說,lp(i)是優(yōu)先級低于任務τi的一組任務集;hep(i)代表優(yōu)先級高于任務τi的一組任務集;Nj是較高優(yōu)先級任務的干擾作業(yè)數量,計算式如下所示。

(7)

情況1任務τi在低關鍵級模式下的最壞響應時間分析

(8)

(9)

Ri=Bi+Ci+Ii

(10)

情況2對于高關鍵級任務τi在高關鍵級模式下運行完成,其最壞響應時間如下所示。

(11)

(12)

(13)

(14)

(15)

情況3由任務τi發(fā)布的作業(yè)在經歷模式轉換后其最壞響應時間計算如下所示

(16)

在模式的切換之前,任務τi以速度SL執(zhí)行,發(fā)生模式切換后任務以速度SH執(zhí)行,則該任務執(zhí)行時間Ci的計算式所示。

(17)

任務τi只在低關鍵級模式下受到任務τj的干擾,干擾時間Ii的計算方法如下

(18)

所以在經歷轉換時間的情況下的任務的最大響應時間的計算如式(19)所示。

(19)

2.3 能耗計算

基于上述的高關鍵級作業(yè)概率數,可推導出作業(yè)執(zhí)行時間的概率質量函數。其具體計算式為

(20)

(21)

3 實驗及結果分析

3.1 實驗平臺搭建

混合關鍵級系統(tǒng)調度仿真軟件(MCSIMU)主要由任務輸入模塊、節(jié)能調度算法調度模塊以及輸出模塊3部分組成,在該仿真軟件中需要對一些優(yōu)化算法以插件的形式插入系統(tǒng)內核,該算法需要在內核當中重新進行編譯,在標準任務集正確調度的基礎上進行系統(tǒng)開銷測試實驗,對存在的異常問題進行算法插件的修正,以保證插入算法的正確性,其算法驗證過程如圖2所示。

圖2 調度算法驗證過程Figure 2. Scheduling algorithm verification process

本文的節(jié)能調度算法作為軟件運行插件實現,即在內核當中加入一個新的調度器,主要根據需求實現具體的調度算法,維護相關數據結構。采用任務控制塊(Task Control Block,TCB)[15]來實現對任務調度參數以及任務運行狀況的保存,其任務調度過程如圖3所示。

圖3 任務產生及調度過程Figure 3. Task generation and scheduling process

本實驗借鑒了文獻[16～18]的實驗操作步驟與方法。首先在隨機任務集上進行可調度分析系統(tǒng),對于任務集的生成采用UUnifast算法,有利于分析任務利用率與任務集中任務數量之間的關系。其仿真實驗參數設定如下:

1)系統(tǒng)利用率U=[0.4,1.0];

2)任務間釋放的時間間隔Td= [6,60];

3)任務高關鍵級模式下的WCET與低關鍵級模式下的WCET之比Z=[1∶4]和Z=[1∶8];

4)高關鍵級任務的概率值CP=[0.1,0.9],默認為0.5。

3.2 結果及分析

在低關鍵級模式下不同處理器速度可調度性對比如圖4所示。

圖4 低關鍵級模式下不同處理器速度可調度性對比(a)WCET之比為1∶4時的可調度性對比 (b)WCET之比為1∶8時的可調度性對比Figure 4. Comparison of different processor speed schedulability in low critical mode(a)Schedulability comparison when the ratio of WCET is 1∶4 (b)Schedulability comparison when the ratio of WCET is 1∶8

圖4(a)和圖4(b)只有在高關鍵級模式下最壞執(zhí)行時間(WCET)與在低關鍵級模式下最壞執(zhí)行時間比值Z的取值范圍不同,其他參數均相同。圖4反應了任務集可調度性隨著系統(tǒng)利用率增加的趨勢。任務可調度性隨著系統(tǒng)利用率的增加而降低。在系統(tǒng)利用率接近1時,此時大多數的任務集變得不可調度。在系統(tǒng)利用率較低時,大多數任務集可調度。在本文仿真實驗中,由于一開始就固定了低關鍵級模式下處理器的速度值SLO,故實驗結果對可調度性造成了一定的負面影響。由圖4(a)和圖4(b)對比可知,低關鍵級模式下的最壞執(zhí)行時間較少,可使得任務相對較早進入高關鍵級模式,相對而言其可調度性也有一定提高。

本文實驗對7組任務集進行能耗的最小化分析。該實驗的系統(tǒng)平均利用率為0.4,固定優(yōu)先級的分配算法為RM(Rate Monotonic)算法。如圖5所示,熱力圖的形式展示了任務集中pL→H從0.05～0.50的節(jié)能情況,實驗結果進行了可視化分析使得節(jié)能效果簡單直觀。在實際系統(tǒng)中,利用本文提出的方法,根據系統(tǒng)所處的工作模式,在滿足任務實時性的前提下,動態(tài)地調節(jié)處理器的工作頻率或者供電電壓,當電壓或者頻率降低時,處理器耗降低以立方級減少,從而使系統(tǒng)的功耗也顯著降低。

圖5 不同模式轉換概率值下任務集的節(jié)能效果Figure 5. Energy-saving effect of task set under different mode conversion probability values

在圖5中,節(jié)能效果以顏色深淺來顯示,小方塊的灰度值越大或顏色越深代表其節(jié)能效果越好。通過顏色對比分析和能耗計算可為任務集求得最小的能耗值以及相應的設置參數。任務集1～7節(jié)能效果的最優(yōu)參數設置如表1所示。

表1 實驗任務集以及相應最優(yōu)實驗參數Table 1. Set of experimental tasks and corresponding optimal experimental parameters

與上述實驗相類似,通過改變系統(tǒng)的利用率進行2 000個任務集的模擬仿真實驗。通過該算法得到的最優(yōu)能耗值與隨機選擇而得到的能耗值進行比較,結果顯示本文算法的平均能耗降低大約10%。與未進行節(jié)能調度的能耗值即該任務集中頻率一直為最大值相比,平均能耗約降低45%。

4 結束語

本文提出了一種基于概率性分析的混合關鍵級系統(tǒng)節(jié)能調度算法,創(chuàng)新性地將概率性分析方法引入最壞響應時間分析,考慮了系統(tǒng)任務實時性和能耗最小化之間的平衡,由概率性分析方法獲得處理器能耗最小化的速度或者頻率值,最終獲得相對最小化的平均能耗。本文對其進行理論證明,并通過對比實驗驗證了該算法的有效性。 實驗結果表明,與未使用節(jié)能調度算法相比,其節(jié)能效果高達45%。但是本文研究針對系統(tǒng)節(jié)能調度算法主要是動態(tài)功耗的降低從而達到系統(tǒng)能耗降低的目的。隨著處理器尺寸的越來越小,靜態(tài)功耗問題也不容忽視,在未來研究中可以進一步將靜態(tài)功耗的影響也考慮在內,使得系統(tǒng)能耗進一步降低。