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

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

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

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

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

1 模型介紹及理論基礎(chǔ)

1.1 任務(wù)模型

1)Ti表示任務(wù)的周期;

4)pETi是任務(wù)的概率分布函數(shù),表示任務(wù)在某個時間段內(nèi)完成的概率值;

5)Li表示任務(wù)的關(guān)鍵級別。Li∈{L,H},其中L表示低關(guān)鍵級任務(wù),H表示高關(guān)鍵級任務(wù)。

1.2 概率模型

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

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

(1)

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

1.3 能耗模型

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

(2)

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

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

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

2 算法設(shè)計

2.1 算法描述

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

(3)

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

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

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

(4)

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

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

2.2 可調(diào)度性分析

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

圖1 可調(diào)度性分析流程Figure 1. Flow of schedulability analysis

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

(5)

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

(6)

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

(7)

情況1任務(wù)τi在低關(guān)鍵級模式下的最壞響應(yīng)時間分析

(8)

(9)

Ri=Bi+Ci+Ii

(10)

情況2對于高關(guān)鍵級任務(wù)τi在高關(guān)鍵級模式下運行完成,其最壞響應(yīng)時間如下所示。

(11)

(12)

(13)

(14)

(15)

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

(16)

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

(17)

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

(18)

所以在經(jīng)歷轉(zhuǎn)換時間的情況下的任務(wù)的最大響應(yīng)時間的計算如式(19)所示。

(19)

2.3 能耗計算

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

(20)

(21)

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

3.1 實驗平臺搭建

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

圖2 調(diào)度算法驗證過程Figure 2. Scheduling algorithm verification process

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

圖3 任務(wù)產(chǎn)生及調(diào)度過程Figure 3. Task generation and scheduling process

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

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

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

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

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

3.2 結(jié)果及分析

在低關(guān)鍵級模式下不同處理器速度可調(diào)度性對比如圖4所示。

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

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

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

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

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

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

4 結(jié)束語

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