混合關鍵任務可靠調度方法與調度性分析

景維鵬，霍帥起，陳廣勝，劉亞秋

(1. 東北林業大學 信息與計算機工程學院，黑龍江 哈爾濱 150040; 2. 黑龍江省林業生態大數據存儲與高性能(云)計算工程研究中心，黑龍江 哈爾濱 150040)

?

混合關鍵任務可靠調度方法與調度性分析

景維鵬1,2，霍帥起1,2，陳廣勝1,2，劉亞秋1,2

(1. 東北林業大學 信息與計算機工程學院，黑龍江 哈爾濱 150040; 2. 黑龍江省林業生態大數據存儲與高性能(云)計算工程研究中心，黑龍江 哈爾濱 150040)

為了解決云計算環境下混合關鍵性任務的可靠調度問題，提出了一種基于主副版本兩階段的混合關鍵任務可靠調度方法．算法首先對需要調度的混合關鍵性任務進行優先級劃分，按照調度截止期最短的原則將主版本任務調度到目標虛擬機上，對副版本任務按照復制成本最低的原則使用重疊方法進行調度；再對調度到不同虛擬機上的主副版本任務進行可調度分析，對于不能滿足分析的任務啟動更高關鍵性等級進行處理．實驗結果表明了混合關鍵任務可靠調度方法具有較高的可靠性和負載平衡能力．

云計算;混合關鍵性任務;可靠調度;主副版本

隨著計算機和網絡技術的迅猛發展以及數據獲取手段的不斷豐富，在越來越多的領域出現了對海量、高速數據進行實時處理的需求．例如在工程及運輸領域實時地對工作部件在運行過程中產生的數據進行有效的分析，可以及時了解部件的當前工作狀態；在運輸和生產運行環節出現故障后，采用某些特定的解決措施，這樣有利于對作業環境中風險的控制[1]; 又如，在林業遙感應用中需要對實時的遙感數據進行處理、分析，從而為林業主管部門決策提供依據，這也需要對數據進行實時、細粒度的處理．可以看到，這類具有海量數據分析與要求的云計算系統不但能處理周期的任務的需要，同時也要滿足系統偶發任務的實時處理的需要，這些任務有著不同的關鍵性等級，這類任務被稱之為實時關鍵任務，因此需要云計算系統依據任務特點能夠有效完成這類任務的調度．

對于實時任務的調度問題，文獻[2]已證明最早期限優先(Earliest Deadline First，EDF)方法是實時任務調度的最佳調度算法；文獻[3]則表明了EDF算法在混合關鍵任務系統中的可調度性能較差；針對目前已有的混合關鍵任務的調度算法[4-5]存在不同關鍵級別任務調度不均衡的問題，一些改進這種不均衡問題的方法相繼被提出[6-7]．然而這些算法的可調度性都不理想．文獻[8]通過計算任務的資源利用率來確定是否在虛擬截止期前使用EDF調度算法，從而提高調度算法的可調度性；文獻[9]則在文獻[8]的基礎上提出可變虛擬截止期的調度算法EY來平衡系統在不同的關鍵等級可調度性；文獻[10]提出了一種針對混合關鍵偶發任務的截止期調整方法，該方法能夠在任務的高關鍵等級和低關鍵等級通過調整相對釋放時間進行調整，從而提高系統的可調度性．

針對多處理器系統中的混合關鍵任務性實時調度問題，文獻[11]將不同關鍵等級任務進行封裝，然后在多虛擬機系統利用任務的優先級進行調度；文獻[12]將EY算法進行擴展，使其可以適用于多處理器系統的混合關鍵實時任務的調度；文獻[13] 提出了一種中央處理器(Central Processing Unit，CPU)速率可變的混合關鍵實時任務多處理器調度方法，該方法能有效提高虛擬機利用率．然而上述方法更多將調度混合關鍵實時任務的目標放到任務的不同關鍵等級情況下的可調度性方面，忽略了任務在可靠性、服務質量(Quality of Service，QoS)、安全性等方面的要求．目前，針對混合關鍵任務性實時任務調度的云計算系統的可靠調度問題研究較少，而在云計算環境下解決任務可靠調度的方法中，基于主副版本的調度方法被認為是一種簡單而又高效的方法．

對于單關鍵性任務的實時調度通常可以使用全局調度和劃分調度兩種方法[14]: 全局調度方法是指在任務執行時可以被調度到任意的虛擬機上執行，而劃分調度方法是在執行前將任務劃分到指定的虛擬機，在執行時則就在已指定的虛擬機上執行．文獻[15]已證明了劃分調度方法具有更好的可調度性．綜上，筆者提出一種滿足混合關鍵實時任務可靠劃分調度策略．該策略能在有效平衡不同關鍵等級任務可調度性前提下，提高調度系統的可靠性．

1 任務模型

考慮典型的異構虛擬機和實時任務集構成的云計算系統．以下進行形式化定義:

定義1 云計算系統一組虛擬機集合描述為P={P1，P2，…，PM}，其中M代表虛擬機數．

定義2 對于混合關鍵實時任務模型，與文獻[17]的相同．集合v=(v1，v2，v3，…，vN)，表示系統中的一組混合關鍵任務．與傳統的隨機任務不同，將每個關鍵性混合關鍵任務定義為一個四元組，其中，Ti為實時偶發任務的周期，即兩個相鄰任務的最小時間間隔; Di表示任務的相對截止期; ζi表示作業的關鍵性等級; Ci表示任務的最差執行時間．為了簡化系統的描述和算法，假設系統中存在兩個關鍵性作業，其中Ci(tHI)和Ci(tLO)分別表示在高、低兩個關鍵等級時作業在所有異構虛擬機上的最差執行時間，通常情況下，Ci(tLO)< Ci(tHI)，任務的利用率分別被定義為 ui(tLO)= Ci(tLO)/Ti和 ui(tHI)= Ci(tHI)/Ti．

定義3 混合關鍵實時任務vi的絕對截止期 di= ri+ Di，其中ri表示任務的釋放時間，任務完成時間表示為fi，三者的關系為 ri≤ fi≤ di．

2 混合關鍵任務可靠調度策略

在調度器模型的基礎上，使用主副版本技術提出一種適用于混合關鍵實時任務調度的可靠調度策略及可靠性調度方法．

2.1 主副版本任務調度

在混合關鍵任務可靠調度方法(Mixed-Criticality Reliability Scheduling Strategy，MCRSS)中，任務的優先級是按照關鍵性(關鍵性等級)的降序排序，對于具有相同關鍵性等級的任務則按照任務的平均利用率的降序排列進行調度．調度器每次為混合關鍵任務選擇虛擬機時，按照固定的順序在虛擬機中選擇第1個滿足條件的虛擬機進行調度．調度主版本任務的目標是確認主版本任務可以盡早地完成，因此，在云計算環境中選擇任務執行時間最短的虛擬機進行調度，因而

(1) 副版本任務不能與其主版本任務調度到相同的虛擬機上．

2.2 可調度性分析

文獻[8]對混合關鍵實時任務在高、低兩個關鍵級的虛擬截止期做了規定．由于不同關鍵等級的任務被調度到不同虛擬機上，首先是按照每個任務的低關鍵模式進行執行，Di(tLO)、Ci(tLO)分別表示任務vi在低關鍵模式下的截止期和任務的完成時間，低關鍵模式下的任務vi的虛擬截止期為

其中，t為當前時間．在低關鍵模式下的主副版本任務在虛擬機上的優先級是按照其釋放的時間ri與虛擬截止期之和，即

在虛擬機上隊列中，任務的主版本與副版本任務按照式(3)所示的優先級進行調度，相同情況下副版本任務的優先級高于主版本優先級，可以按照搶占的方式搶占當前優先級低的任務，并插入所分配虛擬機的就緒隊列中等待調度．在低關鍵模式的可靠性檢測過程中，首先對主版本任務的任務完成時間與虛擬截止期進行判斷，即任務vi的主版本任務的最晚開始時間應滿足:

當在云計算系統中正在執行的任務不能在任務的虛擬截止期之前完成，或是其開設時間小于式(4)的開始時間時，則系統有兩種模式可供選擇，一種是系統進入到高關鍵模式，另一種則是系統開設調度其副版本任務，下面分別就兩種情況的時間開銷進行說明．

如果任務切換到高關鍵性模式，則所有在該虛擬機隊列中等待執行的作業將被終止執行，并被清除出隊列．此時系統中保留一個正在執行作業，該作業的執行時間為

高關鍵模式下的任務vi的虛擬截止期為

高關鍵性作業的優先級將被修改作業的釋放時間與高關鍵模式下的虛擬截止期之和為式(7)所示，系統按照該優先級將任務插入到高關鍵性作業優先級隊列進行調度．

進行不同關鍵等級模式切換的時間開銷為

因此，其副版本任務的最晚開始執行時間為

3 實驗結果與分析

通過可調度任務數量集與總任務數量的百分比，以及不同失效概率下云計算系統的可靠性這兩個方面來驗證MCRSS算法的性能．仿真實驗采用與文獻[8]中相同的混合關鍵任務的生成方法，隨機生成的偶發混合關鍵任務的具體參數設置如下:

(1) 每組測試中實時周期任務集合100≤N≤1000;

(2) 測試的任務是兩個關鍵等級即高關鍵等級HI和低關鍵等級LO;

(4) 任務的執行時間在[1，α Ti]之間均勻分布，α值分別設為0.2，0.8．實驗重復進行10次，以10次的平均值為最終結果;

通過兩組實驗測試實時關鍵任務集的可調度性．兩組實驗分別選取隨機生成的實時關鍵任務隊列，其中任務集的規模分別是100個和 1 000 個．測試在云計算平臺計算節點數為20情況下，MCRSS算法與MC-MP-EDF[17]以及P-EDF[17]在不同雙關鍵實時任務的平均利用率條件下，任務集的可接受比率．

圖1表明在任務集為100情況下，MCRSS、MC-MP-EDF和P-EDF算法相比，能有效提高任務的可接受比率，這是由于MCRSS采用主副兩個版本任務的虛擬截止期的測試，同時采用主副版本兩個版本的調度，也能有效提高算法的可調度性．圖2表明在任務集為 1 000 情況下，MCRSS與MC-MP-EDF和P-EDF算法的可調度性．可以看到，隨著任務數量的增加，任務集的可調度性降低，但是MCRSS依然有較大優勢．MC-MP-EDF和P-EDF性能相差不多，原因是兩種算法選用完全相同任務的劃分方法．

圖1 任務集為100的可接受比率(可調度性)圖2 任務集為1000的可接受比率(可調度性)

通過兩組實驗來測試在不同的負載情況下，任務集為[100，1 000] 的實時關鍵任務的性能．所有實時關鍵任務的最大負載 α= max{U1，U2，…，UN}，其中 Ui= Ci/ Ti; 性能度量標準為給定任務集進行調度所需虛擬機數與任務集負載和的比值，即定義 U= U1+ U2+ …+ UN．α為0.8，表示任務的緊迫度較高；α為0.2，則緊迫度較低．由于任務的最大負載與負載和已知，設M為任務的實際完成時間．在主副版本的調度過程中，任務的實際完成時間，應為其副版本任務的執行時間(Makespan)．由圖3和圖4可以看到，隨著任務的不斷增加，算法MCRSS的 M/U 小于FTRMFF[18]和TPFTRM[18]兩種方法的．其原因是MCRSS能依據主版本任務運行的情況，使用被動和重疊的方式進行調度，因此其具有較好的性能．而FTRMFF采用固定的重疊方式，而TPFTRM采用可調節的副版本重疊方式，因此其性能優于FTRMFF．

圖3 α=02時，3種算法性能比較圖4 α=08時，3種算法性能比較

4 結 束 語

筆者提出了一種在云計算系統中針對混合關鍵任務的主副版本調度策略．該策略能有效地提高混合關鍵任務的調度性能和可靠性．實驗結果表明， MCRSS的性能優于其它算法，適合于異構集群環境，尤其是任務達到速度變化較大，節點動態加入或退出集群等情況，使得系統具有較強的靈活性和可靠性．

[1] 崔星燦, 禹曉輝, 劉洋, 等. 分布式流處理技術綜述[J]. 計算機研究與發展, 2015, 52(2): 318-332.

CUI Xingcan, YU Xiaohui, LIU Yang, et al. Distributed Stream Processing: a Survey[J]. Journal of Computer Research and Development, 2015, 52 (2): 318-332.

[2]BARUAH S, BONIFACI V, D'ANGELO G, et al. Preemptive Uniprocess or Scheduling of Mixed-criticality Sporadic Task Systems[J]. Journal of the ACM, 2015, 62(2): 14.

[3]VESTAL S. Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance[C]//Proceedings of the 28th IEEE International Real-time Systems Symposium. Piscataway: IEEE, 2007: 239-243.

[4]DE NIZ D, LAKSHMANAN K, RAJKUMAR R. On the Scheduling of Mixed-criticality Real-time Task Sets[C]//Proceedings of the Real-time Systems Symposium. Piscataway: IEEE, 2009: 291-300.

[5]LI H, BARUAH S. An Algorithm for Scheduling Certifiable Mixed-criticality Sporadic Task Systems[C]//Proceedings of the 31th Real-time Systems Symposium. Piscataway: IEEE, 2010: 183-192.

[6]BARUAH S K, BUMS A, DAVIS R I. Response-time Analysis for Mixed Criticality Systems[C]//Proceedings of the 32nd Real-time Systems Symposium. Piscataway: IEEE, 2011: 34-43.

[7]BURNS A, FLEMING T, BARUAH S. Cyclic Executives, Multi-core Platforms and Mixed Criticality Applications[C]//Proceedings of the 27th Euromicro Conference on Real-time Systems,. Piscataway: IEEE, 2015: 3-12.

[8]BARUAH S K, BONIFACI V, D’ANGELO G, et al. Mixed-criticality Scheduling of Sporadic Task Systems[C]//Lecture Notes in Computer Science: 6942 LNCS. Heidelberg: Springer Verlag, 2011: 555-566.

[9]EKBERG P, WANG Y. Outstanding Paper Award: Bounding and Shaping the Demand of Mixed-criticality Sporadic Tasks[C]//Proceedings of the 24th Euromicro Conference on Real-time Systems. Piscataway: IEEE Computer Society, 2012: 135-144.

[10]EKBERG P, WANG Y. Bounding and Shaping the Demand of Generalized Mixed-criticality Sporadic Task Systems[J]. Real-time Systems, 2014, 50(1): 48-86.

[11]BARUAH S, BONIFACI V, D’ANGELO G, et al. Scheduling Real-time Mixed-criticality Jobs[J]. IEEE Transactions on Computers, 2012, 61(8): 1140-1152.

[12]BARUAH S, CHATTOPADHYAY B, LI H, et al. Mixed-criticality Scheduling on Multiprocessors [J]. Real-time Systems, 2014, 50(1): 142-177.

[13]BARUAH S. Implementing Mixed-criticality Synchronous Reactive Programs Upon Uniprocessor Platforms [J]. Real-time Systems, 2014, 50(3): 317-341.

[14]CARPENTER J, FUNK S, HOLMAN P, et al. A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms[EB/OL].[2015-02-20]. http://www.docin.com/p-902276394.html.

[15]BASTONI A, BRANDENBURG B B, ANDERSON J H. An Empirical Comparison of Global, Partitioned, and Clustered Multiprocessor EDF Schedulers[C]//Proceedings of the 31st IEEE Real-time Systems Symposium. Piscataway: IEEE, 2010: 14-24.

[16]王吉, 包衛東, 朱曉敏. 虛擬化云平臺中實時任務容錯調度算法研究[J]. 通信學報, 2014, 35(10): 171-180.

WANG Ji, BAO Weidong, ZHU Xiaomin. Fault-tolerant Scheduling Alorithm for Real-time Tasks in Virtualized Cloud[J]. Journal on Communications, 2014, 35(10):171-180.

[17]谷傳才, 關楠, 于金銘, 等. 多處理器混合關鍵性系統中的劃分調度策略[J].軟件學報, 2014, 25(2): 284-297.

GU Chuancai, GUAN Nan, YU Jinming, et al. Partitioned Scheduling Policies on Multi-processor Mixed-criticality System[J]. Journal of Software, 2014, 25(2): 284-297.

[18]AL-OMARI R, SOMANI A K, MANIMARAN G. An Adaptive Scheme for Fault-tolerant Scheduling of Soft Real-time Tasks in Multiprocessor Systems[J]. Journal of Parallel and Distributed Computing, 2005, 65(5): 595-608.

(編輯：王 瑞)

Novel mixed-criticality reliability scheduling strategy and schedulability test

JINGWeipeng1,2，HUOShuaiqi1,2，CHENGuangsheng1,2，LIUYaqiu1,2

(1. The College of Information and Computer Engineering, Northeast Forestry Univ., Harbin 150040, China; 2. Heilongjiang Province Engineering Technology Research Center For Forestry Ecological Big Data Storage and High Performance (Cloud) Computing, Harbin 150040, China)

In order to solve the reliable scientific workflow scheduling problem for the Mixed-Criticality task in cloud computing, we proposed the Mixed-Criticality reliability scheduling strategy (MCRSS) based on Primary/Backup. First, the priority of the primary Mixed-Criticality task is determined and the task is scheduled for the virtual processor with the deadline being the shortest, the backup is the virtual processor with the cost of copy being the lowest. Second, the schedulability test of the primary and backup task are proposed. If the task does not satisfy the schedulability test, then the task will change to high criticality. Experimental results show that the MCRSS algorithm is of high reliability and load balancing capabilities.

cloud computing;mix-criticality task;reliable scheduling;primary/backup

2016-03-16

中央高校基本科研業務費專項資金資助項目(2572014EB05-4)；黑龍江省自然科學基金重點資助項目(ZD201403)；林業公益性行業科研專項經費資助項目(201504307)

景維鵬(1979-)，男，副教授，博士，E-mail: nefujwp@163.com．

10.3969/j.issn.1001-2400.2016.06.027

TP306

A

1001-2400(2016)06-0158-06