分級調度實時架構中處理器資源預設值的預借性

王華忠, 王文凱, 顏秉勇

(華東理工大學化工過程先進控制和優化教育部重點實驗室 上海 200237)

分級調度實時架構中處理器資源預設值的預借性

王華忠, 王文凱, 顏秉勇

(華東理工大學化工過程先進控制和優化教育部重點實驗室 上海 200237)

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

虛擬實時架構; 動態任務; 分級調度; 截止期限超出率; 資源預設值預借機制

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

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

1 分層多級調度架構

圖1 AdHierSched架構框架圖Fig.1 AdHierSched framework

2 分級調度實時架構中處理器資源預設值預借機制

2.1 服務器資源預借機制

2.2 資源預借機制觸發時機的設計

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

圖2 服務器預設資源以及任務執行時間在運行時的追蹤圖Fig.2 Example of server borrow budget and task execution tine

圖3 觸發資源預借機制時機實例圖Fig.3 Example diagram of resource BBM

2.3 資源借用量的設計

在運行資源預借機制之前,通過計算系統總的可用帶寬,可以獲得系統內總的可用資源。因系統總的CPU帶寬為1,所以總的CPU帶寬減去系統應用占用的帶寬即為可借用帶寬,計算公式如下:

(1)

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

BMax=UfreeTj

(2)

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

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

(3)

(4)

(5)

(6)

2.4 系統過載的處理

服務器獲得系統分配的資源后,計算所得的借用資源θ有可能大于最大可借資源BMax,導致系統出現過載現象。為了避免該情形的發生,借用資源θ需要與最大可借資源BMax進行比較,當θBMax時,BMax數量的借用資源會被分配給服務器;但當過載不可避免時,重要性值較高的應用程序會從重要性值較低的應用程序那里獲取資源,以此來維持其內部任務的運行。

3 實驗設計與驗證

3.1 實驗環境配置

3.2 實驗任務的選擇和實驗設計

運用動態任務和靜態任務對AdHierSched架構進行評估,其中動態任務由兩部分組成,一部分動態任務的執行時間由泊松分布隨機產生,剩下的任務來自Mplayer音樂播放器程序。當播放音樂時,為了使AdHierSched架構能夠收到Mplayer音樂播放器中的任務,Mplayer的源代碼被稍微改動。在3種不同條件下進行實驗:(1)架構僅伴隨資源預借控制器運行;(2)架構僅伴隨資源調節器運行;(3)架構同時伴隨資源預借控制器和資源調節器運行。

3.3 實驗結果

表1 任務和服務器參數表

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

表2 靜態任務和服務器參數表

圖4 多靜態任務多服務器實驗結果Fig.4 Multiple static tasks and severs experiment

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

表3 單服務器單動態任務實驗

圖5 動態任務的工作執行時間正態分布圖Fig.5 Normal distribution of all the dynamic tasks

圖6 單動態任務實驗結果Fig.6 Single dynamic task deadline miss ratio experiment results

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

表4 多動態任務多服務器實驗參數表

圖7 多動態任務多服務器實驗結果Fig.7 Multiple dynamic tasks and severs experiment

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

3.3.6 與分級調動架構中其他資源調節機制的比較 文獻[13]通過采用反饋控制理論實現分級調度架構中處理器資源在子系統中的動態調整,反饋控制雖有很多優點,但當多個任務同時執行時,反饋控制器上的時滯問題嚴重,系統資源不能及時分配到相應的子系統中,因此執行任務的截止期限超

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

出率雖略有下降,但依然不是很理想;文獻[14]在分級調度架構內采用模糊控制來調整CPU資源在子系統中的分配。模糊控制雖具有較強的魯棒性和容錯能力,但是由于分級架構內僅對資源信息進行模糊處理,導致架構內動態調整資源分配的能力不是很強。分級調度架構內CPU資源不同調節機制對比參見表5。

表5 分級調度架構內CPU資源不同調節機制對比

4 結 論

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

[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

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

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

TP316.2

A