基于異構多核系統的混合關鍵任務調度算法

趙瑞姣,朱怡安,李 聯

(西北工業大學 a.計算機學院; b.軟件與微電子學院,西安 710072)

0 概述

面對嵌入式系統功能需求的復雜化和多樣性,目前多核系統已基本取代單核系統,以更好地滿足系統的需要。此外,將不同關鍵級的任務整合到一個普通的計算平臺進行更優調度,已經吸引了包括工業界和學術界在內很多專家的高度重視。在混合關鍵系統[1]中,設計者考慮到成本和能耗等問題將系統分為不同的運行級別,在要求不高的情況下,系統運行在非關鍵等級,此時,不論是成本還是能耗都比較低。但是當系統處于某種特殊情況時,為了確保其安全性,需要提高系統的關鍵級。當前很多認證標準如自動化領域的ISO標準[2]以及航空電子領域的DO-178C標準[3]等都根據每個功能應具備的安全程度明確規定了關鍵級別。

此外,隨著異構多核系統[4]的興起,異構的多核處理器以其優于同構多核處理器的性能被廣泛應用在很多的控制領域,包括航天控制、遙感控制等。然而目前多數混合關鍵系統(Mixed-Criticality System,MCS)任務調度問題都是在同構多核的基礎上被提出,未全面考慮異構多核的特性。為此,本文針對異構多核系統的相關特性,提出一種混合關鍵任務調度算法。

1 研究現狀

文獻[5]提出了混合關鍵系統MCS的概念,并同時運用一種形式化的方法對這一概念進行了定義,此后關于MCS的研究成為一個非常熱門的方向。文獻[6]建立了自適應混合關鍵模型AMC。在該模型中,當系統升級為高關鍵級別時,所有的低關鍵級的任務都會被直接丟棄,這雖然保證了高關鍵級任務的CPU執行時間,但是卻完全忽略了低關鍵級任務的執行,由于所有任務都以最壞執行時間作為調度依據,而在大部分情況下都達不到最壞情況,因此這種在關鍵級切換過程中將低關鍵級任務直接丟棄的做法是極其不合理的。而且對于一些應用來說,偶爾的延時[7]是可以被接受的,這些延時任務的執行結果仍有參考價值。為了彌補AMC任務處理過程的不足,適當地考慮給低關鍵級任務提供一定等級的服務質量,文獻[8]提出了一種類似彈性任務模型的處理機制,當系統處于高關鍵級時,它會調整低關鍵級任務的周期,但該方法是基于固定優先級的任務調度,不能實現系統的動態調度[9-10]。而由于混合關鍵系統處于不同關鍵級別時優先順序可能發生改變,因此從這方面而言,該方法不再適用。

文獻[11]給出了一種對于混合關鍵系統中低關鍵任務的優先級定義方法。對低關鍵任務進行服務等級的劃分,通過服務等級的重新劃分,大幅增加低關鍵任務的調度公平性[12],使得對低關鍵任務的調度更加合理。但是該方法并沒有考慮如何提高關鍵任務的調度成功率,同時也沒有考慮處理器負載情況。為在關鍵級提升時保證高關鍵級任務的正確執行,文獻[13]提出了MCPI算法,在關鍵級提升時對任務的優先級進行重新分配,將高關鍵任務的優先級提高,以便能優先執行高關鍵任務。該方法在很大程度上降低了關鍵任務的丟失率,提高了系統的安全性,但是對低關鍵級任務只是采用了best-effort處理,沒有充分利用任務執行過程中的slack時隙[14],降低了對低關鍵任務的接受能力。

針對混合關鍵系統的任務調度特點,文獻[15]提出了一種雙分區的調度策略,在系統處于不同的關鍵級別時重新對非關鍵任務進行處理器的映射。但該方法僅考慮了非關鍵任務的重新分配以及核間遷移,在非關鍵任務的遷移過程中沒有考慮利用任務執行過程中的slack時隙進行非關鍵任務的處理,所以,該方法仍有很大的改進空間。

基于上述方法的不足,本文提出一種基于異構多核系統的混合關鍵任務調度算法。對文獻[15]中DPM算法進行擴展與改進,去除不允許高關鍵任務核間遷移的限制。將混合關鍵任務的調度分為處理器映射以及系統模式切換處理2個階段。在處理器映射階段,優先將關鍵任務分配到強核上進行處理同時以處理器最大剩余帶寬為指標,運用啟發式方法進行任務分配,采用EDF算法[16]進行單處理器上的任務集調度,從而最大化處理器的利用率。此外,引入回收隊列,完成對非關鍵任務的回收再分配,更好地利用slack時隙,使混合關鍵任務調度過程中關鍵任務和非關鍵任務的調度成功率都有所提高。

2 異構多核系統與任務模型

本文算法采用雙關鍵級任務模型。需要強調的是,由于最終要完成異構多核處理器上的混合關鍵任務調度,因此在保證關鍵任務截止期要求的同時也要最大限度地提高非關鍵任務的調度成功率,同時還要考慮異構多核的負載均衡能力。

2.1 異構處理器模型

異構處理器與同構處理器的不同表現為CPU處理能力的非對稱性,每個處理器在未分配任務時,均有一個初始的資源利用率帶寬。本文中對異構處理器做出如下定義:

定義1異構處理器模型表示為C={C1,C2,…,Cm},其中,m表示系統中處理器核數,Ci表示的是第i個處理器的單位時間的計算能力,由于異構并行系統中不同核具有不同的計算能力,因此Ci的值也會有所不同。

定義2異構系統中各個核的計算能力不同,因此,每個任務的處理時間因處理器的不同而變化,可用矩陣M表示如下:

其中,ti(i,j)表示任務i在處理器j上的執行時間。

定義3對于每個處理器都會有剩余的計算帶寬,即每個處理器的最大剩余可用利用率。系統的剩余利用率可用U={U1,U2,…,Um}表示,其中Ui為第i個處理器的剩余計算帶寬。

2.2 任務模型

本文研究的是雙關鍵級模式的混合任務在異構處理器上的調度問題,因此,對以往的任務模型做適當修改,給出以下定義:

定義4對于每一個任務,可由五元組表示為{Li,S,Ci(LO),Ci(HI),Ti(LO),Ti(HI)},其中,S是任務的釋放時間,即到達時間,Li∈{LO,HI}表示任務i所處的關鍵級別,Ci(LO)表示任務wi在LO模式下的最壞執行時間,Ci(HI)表示任務wi在HI模式下的最壞執行時間,Ti(LO)、Ti(HI)分別表示任務wi在非關鍵LO模式和關鍵HI模式下的周期。其中Ci(LO)和Ci(HI)是一個m維向量元素,分別表示任務在不同的處理核上的最壞執行時間,其值與計算能力成反比。同時處于2種不同模式下的任務的最壞執行時間和周期滿足以下關系:當Li=LO時,Ci(LO)=Ci(HI),Ti(LO)≤Ti(HI);當Li=HI時,Ci(LO)≤Ci(HI),Ti(LO)=Ti(HI)。從上式可以看出,當系統從非關鍵LO模式轉換為關鍵HI模式時,降低了對非關鍵任務的服務質量。

定義5每一個任務wi有2個帶寬利用率,用二元組(ui(LO),ui(HI))表示,其中,ui(LO)=Ci(LO)/Ti(LO),ui(HI)=Ci(HI)/Ti(HI)。

定義6如果每一個任務都能在其死限之前完成,那么該任務可調度;如果一個任務集中的所有任務都能在死限前完成,那么該任務集可調度。

3 異構混合關鍵任務調度算法

3.1 調度模型

為了充分利用異構并行系統的特性,同時考慮到運用計算能力強的核來處理關鍵任務可以使其更快更好地完成,本文將異構處理器模型進一步表示為C={πq,πr},其中πq代表強核集,即Ci>1的處理器構成的集合,πr代表弱核集,即Ci≤1的處理器核構成的集合,由于關鍵任務的死限丟失會給系統造成很嚴重的后果,直接關系到系統的安全性,因此此處優先考慮將其映射到強核集合上進行調度,將非關鍵任務映射到弱核集進行調度,并同時記錄各個核的剩余負載情況U={U1,U2,…,Um},當任務到來時優先考慮將任務分配到剩余負載較高的核上調度。圖1為本文算法的調度模型,其中虛線箭頭表示對不能直接調度的任務的重新分配再調度。

圖1 異構多核系統的調度模型

為使關鍵任務能有效地利用強核的計算能力,保證系統的安全性,在異構多核的調度過程中始終堅持以下原則:1)每個任務都是獨立執行的;2)忽略核間遷移和級別切換的開銷;3)同一時刻一個任務只能在一個核上執行。

3.2 算法實現

本文算法考慮異構多核中CPU的執行能力不同的特性以及關鍵任務和非任務的核間遷移,并且對于被迫中止執行的非關鍵任務采取回收再調度的策略,一方面為關鍵任務提供了更多的執行時間和更優的服務質量,保證系統的安全;另一方面也彌補了直接將非關鍵任務丟棄的不足,降低了非關鍵任務的死限丟失率。

階段1異構處理器的映射階段

1)對于m個異構處理器C={πq,πr},πq={C1,C2,…,Cm1},其中,Ci>1,1≤i≤m1,πr={C1,C2,…,Cm2},其中,Cj≤1,1≤j≤m2,HI-Que={w1,w2,…,wn1},LO-Que={w1,w2,…,wn2},系統關鍵級ζ∈{HI,LO},初始值為LO,REC-Que=?,利用率U={U1max,U2max,…,Ummax}。

2)若HI-Que≠?,將HI任務wi按照死限時間(默認T)遞增的順序進行排序,作為任務調度的優先級,跳轉至步驟4)。

3)若LO-Que≠?,LO任務wi按照死限時間(默認T)遞增的順序進行排序,作為任務調度的優先級,跳轉至步驟4);否則,跳轉至步驟5)。

4)?wi∈HI-Que,若?Uj>0,1≤j≤m1,則將wi按照計算的優先級順序在πq中選擇U最大的核Cj進行處理,若調度成功,更新Ujmax=Ujmax-Ci(i,j)/Ti(LO),若不能成功調度,將系統關鍵級升高,即更新ζ=HI,進入階段2。

5)?wi∈LO-Que,若Uj>0,1≤j≤m2,將wi依據優先級先后分配給πr中利用率U最大的核Cj調度,調度成功,更新Ujmax=Ujmax-Ci(i,j)/Ti(LO),否則,關鍵級提升,更新ζ=HI。

6)退出算法。

階段2系統關鍵級切換的處理階段

2)當ζ=HI時,?wi∈HI-Que∩wiπq,此時進行強核集πq中HI任務的重新分配,直至任務可以調度。

3)若步驟2)不成立,將HI任務wi映射到弱核集πr中進行調度,并強行中止利用率U最大的核上的LO任務的執行,進行HI任務的調度,計算該核的剩余利用率Ujmax=Ujmax-Ci(i,j)/Ti(HI)+Cj(i,j)/Tj(HI),并同時將被終止的任務wj∈LO-Que在πr中其他核心進行重分配,若分配失敗,跳轉至步驟4)處理。

3.3 算法復雜度分析

對于每一個關鍵任務來說,最好情況是一次性成功映射到強核集中的某個處理器并成功在該核調度,復雜度為O(1),最壞情況是遍歷完整個強核集都沒能成功調度,此時在弱核集中搶占非關鍵級任務的執行時間來執行,時間復雜度是O(m1+1),其中m1表示強核集的CPU個數。所以,對全部的關鍵任務調度的復雜度為O((m1+1)×n1),n1表示關鍵任務的數量。

對于非關鍵任務來說,在弱核集的某個處理器上調度成功的最小復雜度為O(1),最大時間復雜度為O(m2),其中m2為弱核集的CPU個數。當其不能在弱核集中成功調度時,將其暫時存放入REC-Que回收隊列,以便進行一個利用空閑時間的全局調度,此時時間復雜度為O(m×n2′),其中n2′表示回收隊列中的非關鍵任務數量。對于有n2個非關鍵任務的調度的復雜度為O(m2×n2)。綜上所述,算法的總復雜度可表示為O(n1×(m1+1)+m2×n2+m×n2′)。可以看出,算法復雜度與異構處理器核的處理能力和數量、關鍵任務與非關鍵任務的個數有直接關系,并且該復雜度在可接受的范圍內。

4 仿真實驗

仿真實驗依據文獻[15]方法進行。仿真實驗均基于以下假設:處理器核數為4,調整其中2個核的頻率為1 GHz,另外2個核心頻率為1.5 GHz,系統的整體CPU資源利用率區間為[1.0,3.8],對于實驗中非關鍵任務的周期T(LO),隨機從{10,20,40,50,100,200,400,500,1 000} ms中選取,為保證系統關鍵級提升后的周期約束關系,即Ti(LO)≤Ti(HI),此處假設T(HI)=2×T(LO)。當系統處于非關鍵LO模式下,每個任務的最壞執行時間Ci(LO)為0.2～0.8倍的任務周期T(LO),且保證Ci(HI)=2×Ci(LO)。

1)驗證不同CPU利用率下算法的調度成功率。

實驗方案:控制實驗數據中關鍵任務數量與非關鍵任務數量的比值為1∶1,并隨機生成1 000個實驗任務集,每個任務集中包括10個～20個相互獨立的任務來進行實驗,并對實驗數據進行平均。圖2展示了本文算法與DPM算法[13]的對比結果,從中可以看出,在系統處于相同CPU利用率的情況下,本文算法有更高的任務接受能力,尤其是當系統利用率越高時,本文算法可以接受更多的任務。

圖2 CPU利用率與任務接受能力的關系

2)驗證不同任務數情況下算法的可靠性。

實驗方案:控制實驗數據中關鍵任務數量與非關鍵任務數量的比值為1∶1,并且設定每個核的CPU利用率為85%,同時使任務集中的任務數量在20～100中均勻分布,以此為輸入進行驗證,圖3展示了實驗結果。可以看出,隨著任務集中任務數量的不斷增多,本文算法的任務丟失率明顯低于DPM算法,并且在任務數量增加時對任務的接受能力趨于穩定。

圖3 任務數與任務接受能力的關系

3)驗證關鍵任務和非關鍵任務的比例發生變化時,算法是否能保持優越性。

實驗方案:將任務集中2種任務所占百分比在20%～70%之間進行調整,實驗的結果如圖4所示。可以看出,當關鍵任務占比小于30%時,使用不同的算法對任務可調度性的影響并不大,但是隨著關鍵任務占比的不斷增加,本文算法可以很大程度上提高系統對任務的接受能力,這主要是因為DPM算法并沒有考慮關鍵任務的核間遷移。

圖4 HI任務比例與任務接受能力的關系

5 結束語

針對異構多核特性以及混合關鍵任務調度過程中存在的問題,本文提出一種更適用于異構多核系統的混合關鍵任務調度算法。從2個方面著手進行任務調度,首先將關鍵任務和非關鍵任務劃分為不同的集合進行處理器映射,綜合考慮異構處理器的特性盡量將關鍵任務優先分配給計算能力強的核,并且允許任務的核間遷移,保證系統的安全;其次考慮在系統關鍵級切換時對于非關鍵任務的處理,本文對于被迫中止的非關鍵級任務并沒有采用直接丟棄的處理方式,而是將其回收,并采用全局的調度策略,通過任務執行過程中的空閑時隙進行調度,從而提高對低關鍵級任務的接受能力。仿真實驗結果表明,本文算法可有效提高系統任務接受能力。下一步將從關鍵級切換時間以及核間遷移時間出發對該算法進行擴展,提高其精確度與實用性。

[1] BURNS A,DAVIS R.Mixed Criticality Systems-A Review[D].York,UK:University of York,2013.

[2] HEFFERNAN D,MACNAMEE C,FOGARTY P.Runtime Verification Monitoring for Automotive Embedded Systems Using the ISO 26262 Functional Safety Standard as a Guide for the Definition of the Monitored Properties[J].IET Software,2014,8(5):193-203.

[3] MOLLISON M S,ERICKSON J P,ANDERSON J H,et al.

Mixed-criticality Real-time Scheduling for Multicore Systems[C]//Proceedings of IEEE International Conference on Computer and Information Technology.Washington D.C.,USA:IEEE Press,2010:1864-1871.

[4] 姚麗莎,王占鳳,程家興.基于人工魚群遺傳算法的異構多核系統任務調度研究[J].計算機工程與科學,2014,36(10):1866-1871.

[5] VESTAL S.Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance[C]//Proceedings of RTSS’07.Washington D.C.,USA:IEEE Press,2008:239-243.

[6] BARUAH S K,BURNS A,DAVIS R I.Response-time Analysis for Mixed Criticality Systems[C]//Proceedings of RTSS’11.Washington D.C.,USA:IEEE Press,2011:34-43.

[7] YIP E,KUO M,BROMAN D,et al.Relaxing the Synchronous Approach for Mixed-criticality Systems[C]//Proceedings of the 20th IEEE Real-time and Embedded Technology and Application Symposium.Washington D.C.,USA:IEEE Press,2014:89-100.

[8] BURNS A,BARUAH S.Towards a More Practical Model for Mixed Criticality Systems[EB/OL].[2016-05-10].http://www-users.cs.york.ac.uk/～robdavis/wmc2013/paper3.pdf.

[9] 劉 懷,費樹岷.基于雙優先級的實時多任務動態調度[J].計算機工程,2005,31(18):16-18.

[10] SU Hang,ZHU Dakai,MOSSE D.Scheduling Algorithms for Elastic Mixed-criticality Tasks in Multicore Systems[C]//Proceedings of IEEE International Conference on Embedded and Real-time Computing Systems and Applications.Washington D.C.,USA:IEEE Press,2013:352-357.

[11] HIKMET M,KUO M M,ROOP P S,et al.Mixed-criticality Systems as a Service for Non-critical Tasks[C]//Proceedings of IEEE International Symposium on Real-time Distributed Computing.Washington D.C.,USA:IEEE Press,2016:221-228.

[12] 王 濤,安 虹,孫 濤,等.面向動態異構多核處理器的公平調度算法[J].軟件學報,2014,25(S2):80-89.

[13] SOCCI D,POPLAVKO P,BENSALEM S,et al.Multiprocessor Scheduling of Precedence-constrained Mixed-critical Jobs[C]//Proceedings of International Symposium on Real-time Distributed Computing.Washington D.C.,USA:IEEE Press,2015:198-207.

[14] 朱怡安,黃姝娟,段俊花,等.新的混合關鍵任務調度算法的研究[J].電子科技大學學報,2014,43(2):268-271,286.

[15] AL-BAYATI,Z,ZHAO Qingling,YOUSSEF A,et al.Enhanced Partitioned Scheduling of Mixed-criticality Systems on Multicore Platforms[C]//Proceedings of ASP-DAC’15.Chiba,Japan:[s.n.],2015:630-635.

[16] LEE J.New Response Time Analysis for Global EDF on a Multiprocessor Platform[J].Journal of Systems Architecture,2016,65:59-63.