王華忠, 王文凱, 顏秉勇

(華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化教育部重點實驗室 上海 200237)

分級調(diào)度實時架構(gòu)中處理器資源預(yù)設(shè)值的預(yù)借性

王華忠, 王文凱, 顏秉勇

(華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化教育部重點實驗室 上海 200237)

分層多級自適應(yīng)調(diào)度(AdHierSched)架構(gòu)是Linux操作系統(tǒng)中的虛擬實時架構(gòu),在系統(tǒng)運(yùn)行時,它通過監(jiān)測各子系統(tǒng)對處理器資源的需求動態(tài)調(diào)整資源分配。本文在分級調(diào)度架構(gòu)中提出了處理器資源預(yù)借機(jī)制(BBM),通過服務(wù)器間資源的動態(tài)分配達(dá)到處理器資源在各個實時系統(tǒng)中優(yōu)化配置的目的,并針對AdHierSched架構(gòu)中資源預(yù)設(shè)值的預(yù)借性進(jìn)行設(shè)計和實現(xiàn),通過靜態(tài)任務(wù)和動態(tài)任務(wù)對該資源預(yù)設(shè)值預(yù)借控制器進(jìn)行實驗評估。實驗結(jié)果表明:當(dāng)AdHierSched架構(gòu)伴隨著處理器預(yù)借機(jī)制和資源調(diào)整機(jī)制同時運(yùn)行時,內(nèi)部運(yùn)行任務(wù)整體的截止期限超出率減小。此外,資源預(yù)借性機(jī)制的添加導(dǎo)致的系統(tǒng)額外開銷相比系統(tǒng)總的開銷很小,表明該方案適合在實際分級調(diào)度實時系統(tǒng)內(nèi)推廣使用。

虛擬實時架構(gòu); 動態(tài)任務(wù); 分級調(diào)度; 截止期限超出率; 資源預(yù)設(shè)值預(yù)借機(jī)制

系統(tǒng)虛擬技術(shù)的廣泛應(yīng)用使得實時操作系統(tǒng)(RTOSs)能夠與Linux、Windows或者其他系統(tǒng)在同臺機(jī)器上同時運(yùn)行。當(dāng)多個實時系統(tǒng)在虛擬系統(tǒng)中同時運(yùn)行時,保持其各自建立時的時序?qū)傩圆蛔冿@得尤為重要。通過運(yùn)用分級調(diào)度(Hierarchical scheduling)技術(shù)可使組合后的各個系統(tǒng)相對安全地按照實時系統(tǒng)的時序要求進(jìn)行運(yùn)行[1]。同一硬件平臺上CPU資源的分配方式嚴(yán)重影響著各系統(tǒng)性能的發(fā)揮,將CPU資源分為一系列分區(qū)并分配給各個實時系統(tǒng)是分級調(diào)度技術(shù)中資源分配的主要方式,通過將單個系統(tǒng)獲得的CPU資源和其實際的需求進(jìn)行比較和調(diào)整,可達(dá)到CPU資源在各個系統(tǒng)中的最優(yōu)配置[2]。而單個系統(tǒng)實際資源需求是通過其內(nèi)部任務(wù)的最壞情況執(zhí)行時間(WCET)獲得的,但在實際應(yīng)用中有些實時任務(wù)的WCET不是先驗已知的,例如視頻解碼器應(yīng)用程序,其執(zhí)行時間主要決定于輸入視頻包含的內(nèi)容,因視頻的不同會有顯著的改變;依靠傳感器來控制物理環(huán)境變化的控制任務(wù),其對CPU需求也因環(huán)境的改變而改變。即使WCET是已知的,其值通常比平均執(zhí)行時間大,若按照WCET對每個實時系統(tǒng)進(jìn)行資源分配,必將導(dǎo)致處理器資源的浪費(fèi),而且任務(wù)偶爾超出截止期限的情況在大多數(shù)軟實時系統(tǒng)中是可以接受的,所以在資源有限的嵌入式系統(tǒng)中過多分配CPU資源是極不可取的。

AdHierSched[3]架構(gòu)具有在線監(jiān)測任務(wù)資源需求的能力,從而解決了上述問題。該架構(gòu)是一個將硬實時系統(tǒng)和軟實時系統(tǒng)組合在一起的虛擬嵌入式實時系統(tǒng),運(yùn)用分級調(diào)度技術(shù)和基于服務(wù)器調(diào)度算法[4],不但能夠為硬實時系統(tǒng)分配靜態(tài)的CPU資源,而且可根據(jù)軟實時系統(tǒng)運(yùn)行時的實際需求而動態(tài)調(diào)整其獲得的CPU資源[5]。分級調(diào)度架構(gòu)(HSF)[6-8]運(yùn)用CPU分區(qū)技術(shù),將CPU資源分割成一定數(shù)量的區(qū)域,并將每個區(qū)域分配給架構(gòu)中的子系統(tǒng)。架構(gòu)內(nèi)的全局調(diào)度器調(diào)度其內(nèi)部所有子系統(tǒng),每個子系統(tǒng)內(nèi)包含一個調(diào)度其內(nèi)部任務(wù)或其子系統(tǒng)的本地調(diào)度器。分級調(diào)度系統(tǒng)中采用何種方式分配處理器資源至關(guān)重要,目前雖有文獻(xiàn)對分級調(diào)度架構(gòu)中處理器資源分配領(lǐng)域做了研究,但對處理器資源借用機(jī)制的研究鮮有報道。本文針對該問題,提出了處理器資源預(yù)借適應(yīng)機(jī)制,并將該機(jī)制運(yùn)用于Linux內(nèi)核可加載模塊AdHierSched架構(gòu)中,通過動態(tài)任務(wù)和靜態(tài)任務(wù)對該機(jī)制進(jìn)行評估,并對引入該機(jī)制而增加的額外開銷進(jìn)行分析。

1 分層多級調(diào)度架構(gòu)

圖1 AdHierSched架構(gòu)框架圖Fig.1 AdHierSched framework

2 分級調(diào)度實時架構(gòu)中處理器資源預(yù)設(shè)值預(yù)借機(jī)制

2.1 服務(wù)器資源預(yù)借機(jī)制

2.2 資源預(yù)借機(jī)制觸發(fā)時機(jī)的設(shè)計

因不明確任務(wù)的執(zhí)行時間,服務(wù)器很難確定觸發(fā)資源預(yù)借機(jī)制的時機(jī),針對此問題,本文提出了一種新方法來告知服務(wù)器何時需要借用資源。動態(tài)任務(wù)τj的執(zhí)行時間Cj未知,其截止期限與任務(wù)周期相等,當(dāng)服務(wù)器沒有系統(tǒng)資源時,其下面運(yùn)行的任務(wù)因資源問題而暫停,直到該服務(wù)器資源得到補(bǔ)充才可以繼續(xù)執(zhí)行。任務(wù)截止期限與其停止時間tk之間的時間間隔為Δt,通過比較Δt與服務(wù)器周期的大小并檢查該任務(wù)是否完成執(zhí)行就可決定其是否會錯過截止期限。如果Δt小于服務(wù)器周期,而且該任務(wù)還沒有執(zhí)行完,那么將不能在截止時間以前執(zhí)行完。因為在服務(wù)器的資源沒有得到補(bǔ)充前,該任務(wù)只能處于等待狀態(tài),當(dāng)?shù)却隣顟B(tài)結(jié)束時,其已經(jīng)超出截止期限。為確保任務(wù)能夠在Δt時間內(nèi)繼續(xù)執(zhí)行,服務(wù)器需要在結(jié)束當(dāng)前周期前觸發(fā)資源預(yù)借機(jī)制,從即將到來的下一個服務(wù)器周期中借一定數(shù)量的資源,進(jìn)而維持任務(wù)能夠繼續(xù)執(zhí)行。

圖2 服務(wù)器預(yù)設(shè)資源以及任務(wù)執(zhí)行時間在運(yùn)行時的追蹤圖Fig.2 Example of server borrow budget and task execution tine

圖3 觸發(fā)資源預(yù)借機(jī)制時機(jī)實例圖Fig.3 Example diagram of resource BBM

2.3 資源借用量的設(shè)計

在運(yùn)行資源預(yù)借機(jī)制之前,通過計算系統(tǒng)總的可用帶寬,可以獲得系統(tǒng)內(nèi)總的可用資源。因系統(tǒng)總的CPU帶寬為1,所以總的CPU帶寬減去系統(tǒng)應(yīng)用占用的帶寬即為可借用帶寬,計算公式如下:

(1)

其中:Ufree為可借用帶寬;Ui為服務(wù)器i所占用帶寬。由系統(tǒng)CPU可借用帶寬可計算出服務(wù)器在當(dāng)前周期中最大可借資源值BMax,其計算公式如下:

BMax=UfreeTj

(2)

為了估計實際需要借用資源的量,本文運(yùn)用自回歸模型(Autoregressive (AR) model)[12]估計每個服務(wù)器周期中所需分配資源的量。自回歸是變量對自身的回歸,根據(jù)歷史數(shù)據(jù)估計出相對準(zhǔn)確的估計值,通過AR模型獲得的估計值可用式(3)表述。

Bk+1=c+[θ1B1+θ2B2+…+θkBk]+ek

(3)

(4)

(5)

(6)

2.4 系統(tǒng)過載的處理

服務(wù)器獲得系統(tǒng)分配的資源后,計算所得的借用資源θ有可能大于最大可借資源BMax,導(dǎo)致系統(tǒng)出現(xiàn)過載現(xiàn)象。為了避免該情形的發(fā)生,借用資源θ需要與最大可借資源BMax進(jìn)行比較,當(dāng)θBMax時,BMax數(shù)量的借用資源會被分配給服務(wù)器;但當(dāng)過載不可避免時,重要性值較高的應(yīng)用程序會從重要性值較低的應(yīng)用程序那里獲取資源,以此來維持其內(nèi)部任務(wù)的運(yùn)行。

3 實驗設(shè)計與驗證

3.1 實驗環(huán)境配置

3.2 實驗任務(wù)的選擇和實驗設(shè)計

運(yùn)用動態(tài)任務(wù)和靜態(tài)任務(wù)對AdHierSched架構(gòu)進(jìn)行評估,其中動態(tài)任務(wù)由兩部分組成,一部分動態(tài)任務(wù)的執(zhí)行時間由泊松分布隨機(jī)產(chǎn)生,剩下的任務(wù)來自Mplayer音樂播放器程序。當(dāng)播放音樂時,為了使AdHierSched架構(gòu)能夠收到Mplayer音樂播放器中的任務(wù),Mplayer的源代碼被稍微改動。在3種不同條件下進(jìn)行實驗:(1)架構(gòu)僅伴隨資源預(yù)借控制器運(yùn)行;(2)架構(gòu)僅伴隨資源調(diào)節(jié)器運(yùn)行;(3)架構(gòu)同時伴隨資源預(yù)借控制器和資源調(diào)節(jié)器運(yùn)行。

3.3 實驗結(jié)果

表1 任務(wù)和服務(wù)器參數(shù)表

3.3.2 多服務(wù)器多靜態(tài)任務(wù)實驗 本實驗采用4個靜態(tài)任務(wù)和3個服務(wù)器,詳細(xì)參數(shù)見表2,服務(wù)器的重要性值與服務(wù)器的編號一致,即ζ0>ζ1>ζ2。圖4示出了實驗結(jié)果。實驗表明,當(dāng)AdHierSched在條件2下工作時,所有任務(wù)具有最低的DMR值;當(dāng)任務(wù)在條件3下運(yùn)行時,由于有過載發(fā)生,因服務(wù)器S0重要性值最高,系統(tǒng)為使其下面任務(wù)具有相對較低的DMR值,導(dǎo)致分配到服務(wù)器S2內(nèi)的資源有所減少,造成任務(wù)τ3DMR值在此實驗中有所增加。

表2 靜態(tài)任務(wù)和服務(wù)器參數(shù)表

圖4 多靜態(tài)任務(wù)多服務(wù)器實驗結(jié)果Fig.4 Multiple static tasks and severs experiment

3.3.3 單服務(wù)器單動態(tài)任務(wù)實驗 本實驗中,動態(tài)任務(wù)的執(zhí)行時間在40～90 ms之間變化。任務(wù)和服務(wù)器的詳細(xì)參數(shù)見表3。圖5示出了本實驗中任務(wù)執(zhí)行時間的正態(tài)分布圖。本實驗共有20組,每組包含100個不同的執(zhí)行時間。因動態(tài)任務(wù)的執(zhí)行時間不同導(dǎo)致每組的DMR輸出有所變化。圖6所示為本次實驗中服務(wù)器在不同運(yùn)行條件下的最高、最低和平均截止期限超出率。實驗結(jié)果表明,該架構(gòu)在條件3下工作的表現(xiàn)性能最好,其平均DMR值僅為13%,運(yùn)行在條件1和條件2下的平均DMR值分別為51%和19%。

表3 單服務(wù)器單動態(tài)任務(wù)實驗

圖5 動態(tài)任務(wù)的工作執(zhí)行時間正態(tài)分布圖Fig.5 Normal distribution of all the dynamic tasks

圖6 單動態(tài)任務(wù)實驗結(jié)果Fig.6 Single dynamic task deadline miss ratio experiment results

3.3.4 多服務(wù)器多動態(tài)任務(wù)實驗 本實驗采用5個動態(tài)任務(wù)和3個服務(wù)器,其詳細(xì)參數(shù)見表4,實驗結(jié)果見圖7。由圖7可知,當(dāng)架構(gòu)在條件1下運(yùn)行時,每個服務(wù)器下面的任務(wù)都有錯過截止期限的情況發(fā)生。然而當(dāng)架構(gòu)在條件2下運(yùn)行時,其表現(xiàn)性能好于前者,各個任務(wù)的平均DMR值都有所下降;當(dāng)架構(gòu)在條件3下運(yùn)行時,任務(wù)τ0、τ1和τ2的平均DMR值比在條件2時更低,但是任務(wù)τ3和τ4的DMR值反而有所增加,造成此情況是因有過載發(fā)生,所以系統(tǒng)根據(jù)各服務(wù)器的重要性值進(jìn)行分配資源。因S0具有最高的重要性值,因此該架構(gòu)以減少對服務(wù)器S1、S2資源分配為代價來提高τ0和τ1的DMR值,因此任務(wù)τ3和τ4的DMR值才會增加。

表4 多動態(tài)任務(wù)多服務(wù)器實驗參數(shù)表

圖7 多動態(tài)任務(wù)多服務(wù)器實驗結(jié)果Fig.7 Multiple dynamic tasks and severs experiment

3.3.5 系統(tǒng)開銷分析 去除Linux系統(tǒng)調(diào)度開銷外,實驗運(yùn)行時系統(tǒng)內(nèi)共有3種開銷:(1)用來計算調(diào)度任務(wù)的分級調(diào)度開銷;(2)資源預(yù)借控制器中用來計算和借用服務(wù)器資源的開銷;(3)資源調(diào)控器中用來計算和調(diào)節(jié)服務(wù)器資源的開銷。本文通過程序運(yùn)行時的時間戳來測量開銷。針對多服務(wù)器多動態(tài)任務(wù)的實驗,當(dāng)架構(gòu)在條件3下運(yùn)行時,3種開銷所占的比例見圖8。用來計算資源預(yù)借控制器和資源調(diào)控器的額外開銷都很小,幾乎相同,且3種開銷的總和約為0.224 % CPU時間,故因添加資源預(yù)借控制器而添加的額外開銷在實際應(yīng)用中是可以接受的。

3.3.6 與分級調(diào)動架構(gòu)中其他資源調(diào)節(jié)機(jī)制的比較 文獻(xiàn)[13]通過采用反饋控制理論實現(xiàn)分級調(diào)度架構(gòu)中處理器資源在子系統(tǒng)中的動態(tài)調(diào)整,反饋控制雖有很多優(yōu)點,但當(dāng)多個任務(wù)同時執(zhí)行時,反饋控制器上的時滯問題嚴(yán)重,系統(tǒng)資源不能及時分配到相應(yīng)的子系統(tǒng)中,因此執(zhí)行任務(wù)的截止期限超

圖8 條件3下系統(tǒng)開銷實驗Fig.8 Overhead experiment when the framework runs under condition 3

出率雖略有下降,但依然不是很理想;文獻(xiàn)[14]在分級調(diào)度架構(gòu)內(nèi)采用模糊控制來調(diào)整CPU資源在子系統(tǒng)中的分配。模糊控制雖具有較強(qiáng)的魯棒性和容錯能力,但是由于分級架構(gòu)內(nèi)僅對資源信息進(jìn)行模糊處理,導(dǎo)致架構(gòu)內(nèi)動態(tài)調(diào)整資源分配的能力不是很強(qiáng)。分級調(diào)度架構(gòu)內(nèi)CPU資源不同調(diào)節(jié)機(jī)制對比參見表5。

表5 分級調(diào)度架構(gòu)內(nèi)CPU資源不同調(diào)節(jié)機(jī)制對比

4 結(jié) 論

本文對分級調(diào)度實時系統(tǒng)內(nèi)部的資源配置進(jìn)行研究,提出了處理器資源預(yù)借機(jī)制,并在AdHierSched架構(gòu)內(nèi)對該機(jī)制進(jìn)行研究、設(shè)計和實驗驗證。首先運(yùn)用自回歸模型為即將運(yùn)行的服務(wù)器估計新的預(yù)設(shè)資源,然后通過運(yùn)用實時系統(tǒng)中動態(tài)任務(wù)和靜態(tài)任務(wù)來對該機(jī)制進(jìn)行評估,實驗結(jié)果表明:當(dāng)AdHierSched架構(gòu)伴隨著處理器預(yù)借機(jī)制和資源調(diào)整機(jī)制同時運(yùn)行時,內(nèi)部運(yùn)行任務(wù)整體的截止期限超出率減小,實時系統(tǒng)中資源的分配得到優(yōu)化。此外,資源預(yù)借性機(jī)制的添加沒有明顯增加系統(tǒng)額外開銷,因而本文提出的方案在分級調(diào)度實時應(yīng)用系統(tǒng)中具有較高的實用價值。

[1] Chris Grujon.Gnu operating system[EB/OL].[2016-07-08].http://embedded-computing.com/articles/the-multiprocessor-multi-os-systems

[2] YAMAGUCHI A,NAKAMOTO Y,SATO K,etal.EDF-PStream:Earliest deadline first scheduling of preemptable data streams:Issues related to automotive applications[C]//2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications.Hong Kong,China,IEEE,2015:257-267.

[3] KHALILZAD N,BEHNAM M,NOLTE T.Multi-level adaptive hierarchical scheduling framework for composing real-time systems[C]//2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications.Taipei,China:IEEE,2013:320-329.

[4] LUCA M,GIUSEPPE L,PATRICIA B,etal.Iris:A new reclaiming algorithm for server-based real-time systems[C]//10th IEEE Real-Time and Embedded Technology and Applications Symposium.USA:IEEE,2004, 211-218.

[5] KHALILZAD N,BEHNAM M, NOLTE T.Implementation of the multi-level adaptive hierarchical scheduling framework[C]//9th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Appllication.Paris,France:ACM,2013:11-19.

[6] BIONDI A,GIORGIO C B,MARKO B.Schedulability analysis of hierarchical real-time systems under shared resources[J].IEEE Transactions on Computers,2016,65(5):1593-1605.

[7] VAN DEN H,MARTIJN M H P,REINDER J.Budget allocations for hierarchical fixed-priority scheduling of sporadic tasks with deferred preemptions upon EDP resources[J].ACM SIGBED Review,2015,12(1):19-27.

[8] LUNNISS W,SEBASTIAN A,ROBERT I D.Accounting for cache related pre-emption delays in hierarchical scheduling with local EDF scheduler[J].Real-Time Systems,2014,52(2):13-16.

[9] INSIK S,LEE I.Periodic resource model for compositional real-time guarantees[C]// RTSS '03 Proceedings of the 24th IEEE International Real-Time Systems Symposium.USA:IEEE,2003:2-13.

[10] CHEN M S,HWANG C P,WANG H F.Analysis of the queue service probability for the EDF scheduling algorithm[C]//2016 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA).Switzerland:IEEE Computer Society,2016:960-963.

[11] NATHAN F,DEWAN F.A bandwidth allocation scheme for compositional real-time systems with periodic resources[J].Real-Time Systems,2012,48(3):223-263.

[12] HIROTUGU A.Fitting autoregressive models for prediction[J].Annals of the Institute of Statistical Mathematics,1969,21(1):243-247.

[13] KHALILZAD N M,BEHNAM M,NOLTE T,etal.On adaptive hierarchical scheduling of real-time systems using a feedback controller[C]//3rd Workshop on Adaptive and Reconfigurable Embedded Systems (APRES’11).Chicago:[s.n.],2011:159-165.

[14] KHALILZAD N M,BEHNAM M,SPAMPINATO G,etal.Bandwidth adaptation in hierarchical scheduling using fuzzy controllers[C]//7th IEEE International Symposium on Industrial Embedded Systems (SIES’12).USA:IEEE,2012:148-157.

ResourceBorrowingMechanismBasedonHierarchicalSchedulingReal-TimeFramework

WANGHua-zhong,WANGWen-kai,YANBing-yong

(KeyLaboratoryofAdvancedControlandOptimizationforChemicalProcesses,MinistryofEducation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

Multi-level adaptive hierarchical scheduling (AdHierSched) framework is a virtualized real-time framework in Linux operating system,which dynamically schedules the CPU partition sizes by monitoring the demand of every subsystem during running process.This paper presents a Budget Borrowing Mechanism (BBM) in hierarchical scheduling framework.The proposed BBM can dynamically assign the CPU resource between servers in real-time systems.Moreover,in AdHierSched framework,the proposed BBM is designed and implemented for dynamical adaptation the resource parameters.Both static and dynamic tasks are utilized to evaluate the budget borrowing controller.Experiment results show that while different tasks execute in the framework with the proposed BBM,the task’s deadline miss ratio is lower than those without using this mechanism.Compared with the total overhead of system,the extra overhead from budget borrowing calculation is very small.Hence,the proposed mechanism is suitable in actual applications.

virtualized real-time framework; dynamic task; hierarchical scheduling; deadline miss ratio; resource budget borrowing mechanism

1006-3080(2017)06-0837-07

10.14135/j.cnki.1006-3080.2017.06.013

2016-12-06

國家自然科學(xué)基金青年基金(51407078)

王華忠(1965-),男,副教授,主要研究方向為復(fù)雜工業(yè)過程建模、控制與故障診斷。E-mail:hzwang@ecust.edu.cn

TP316.2

A