基于響應時間的混合關鍵級系統弱約束調度策略研究

金永賢 胡心潔

(浙江師范大學數學與計算機科學學院 浙江 金華 321004)

0 引 言

在傳統實時系統執行過程中，所有任務的響應時間小于其截止期限可以保證系統的順利運行。其中響應時間可通過Joseph等[1]提出的方法進行計算。然而現如今的實時系統日益呈現功能多樣性、計算密集性、時效敏感性的特點，相應的物理平臺越來越小，因此傳統的實時系統不再適用，要求不同重要性的任務共享同一個平臺，混合關鍵級系統應運而生。與傳統的實時系統不同，混合關鍵級系統的任務根據重要性分為不同的關鍵等級，外部環境的變化會引起系統關鍵等級的變化，對應的任務執行模式也會發生變化，從而影響任務的可調度性。因此傳統實時系統的任務可調度算法不再適用于混合關鍵級系統，Vestal[2]首先建立混合關鍵級系統模型，提出響應時間計算方法，并結合Audsley[3]提出的OPA算法對任務進行優先級分配。

研究人員在文獻[2]模型的基礎上進行研究，系統多以任務的最壞情況執行時間(WCET)作為關鍵參數(關鍵參數是任務參數中因系統關鍵級改變而變化的參數)，且保證高關鍵級任務的正確執行，通常需要犧牲低關鍵級任務的執行時間。但在實際應用中，簡單地丟棄低關鍵級任務可能造成資源的浪費以及數據完整性的破壞[4]，且頻繁地丟棄任務也會增加開銷。對此，研究人員開始研究積極調度低關鍵級任務的方法：在關鍵級提升時，不采用簡單地丟棄低關鍵級任務的方法，而將其以較低的服務水平執行，從而保證系統穩定執行，提高資源利用率。

Gettings等[5]在雙關鍵級任務模型下提出積極調度低關鍵級任務的方法：在系統進入高關鍵級階段后，低關鍵級任務以弱約束的模式繼續執行，即允許低關鍵級任務連續幾個工作業不執行，并提出兩個調度策略，這兩個調度策略有一定局限性，在實際應用中任務關鍵級通常多于2個，如：適用于商用飛行器的RTCA DO.178B航空電子軟件標準將任務劃分為成5個安全保證等級；ISO26262將任務劃分為4個安全等級。對此本文建立混合多關鍵級模型，改進弱約束模式，并基于響應時間分析提出調度策略。

1 相關研究

針對經典的混合關鍵級模型，研究人員已基于響應時間計算提出了幾種調度策略。Baruah等[6]在Vestal基礎上進行進一步研究，以混合雙關鍵級系統為模型提出了SMC、AMC調度策略。文獻[7]將AMC調度策略擴展到多關鍵級系統；文獻[8]以悲觀周期作為關鍵參數，基于響應時間分析提出調度算法；文獻[9]提出一種新的計算響應時間的方法，關注系統提升時任務自身的執行時間，降低了響應時間計算的復雜度。Burns等[10]進一步改進混合關鍵系統模型，加入可容錯的概念，保證系統魯棒性和可調度性之間的平衡。

在低關鍵級任務積極調度的研究方面，趙瑞姣等[11]針對異構多處理器調度中存在的問題，引入回收隊列重新調度被丟棄的任務，從而提高低關鍵級任務的調度比率。Bernat等[12]提出弱實時系統的概念，允許任務在某幾個釋放周期錯過截止期限。文獻[5]將弱實時系統的概念引入到混合關鍵系統中，實現低關鍵級任務的弱約束模式執行。此外，許多研究人員引入彈性模型對低關鍵級任務進行積極調度，其中Su等[13]使用提前釋放策略,將高關鍵級任務執行時產生的空閑時隙分配給低關鍵級任務執行，低關鍵級任務釋放周期可以彈性調整，選擇合適的空閑時隙執行。文獻[14]將該算法進行改進使其適用于多處理器平臺。黃麗達等[15]也使用了彈性調度模型的調度算法，積極地調度低關鍵級任務。文獻[16]根據系統負載的變化，實現任務周期的動態延伸或壓縮，從而保證更多任務執行，提高了處理器利用率。Ren等[17]將任務進行分組，高關鍵級任務只能影響與其同組的低關鍵級任務的執行，從而提升低關鍵級任務的可調度性。文獻[18]引入重要性概念，對低關鍵級任務進行重要性分配，低關鍵級任務按照其重要性的逆序被丟棄。Chen等[19]提出一種靈活的混合關鍵級模型，在關鍵級提升時，只有溢出任務本身被認為表現出高關鍵級行為，而其他高關鍵級任務仍然保持以前相同的模式執行，能夠在保證系統可調度的同時確定低關鍵性任務的最大可執行時間。

2 任務模型及相關概念

2.1 任務模型

首先建立混合多關鍵級系統的任務模型：在單處理器可搶占平臺上，包含N個獨立任務的任務集τ(τ1，τ2，…，τn)等待運行，且不同關鍵級的任務共享一個平臺。下面定義任務參數和執行模式。

用系統參數L={L1，L2，…，Lm}表示系統當前關鍵等級，L1為系統的初始關鍵等級，Lm為系統可達到的最高關鍵等級。

任務參數可描述任務執行模式。每個任務τi有6個參數(Ci，Ti，Di，Li，(m,sLi(L)),pi)，Ti為任務周期，Di為隱含式截止期限(Di=Ti)，pi代表任務的優先級，Li為任務關鍵等級，任務最壞情況響應時間向量Ci=(Ci(L1)，Ci(L2),…,Ci(Ln))，參數(m,sLi(L))規定任務的弱約束執行模式。

任務的執行模式。任務的最壞情況執行時間在系統處于不同關鍵等級時有以下關系：當L

2.2 相關概念

響應時間：本文在線下對任務的工作業從釋放到執行完畢經歷的總時間做出估計，這個值為任務的響應時間。

任務執行窗口：已知τi首個工作業在0時刻釋放，響應時間為Ri，(0，Ri)即為τi的執行窗口。

任務可調度：若任務τi可被分配合適的優先級，則判定τi為可調度。

可調度任務集：若所有τi∈τ都可被分配到合適的優先級，則該任務集稱為可調度任務集。

3 優先級分配策略

τ為待分配優先級的任務集。結合OPA算法[3]對τ中的每個任務進行優先級分配，以此判斷任務集的可調度性，如算法1所示。

算法1WE-OPA

輸入：任務集τ。

輸出：任務集τ的優先順序集P。

functionFLAG(τ)

fork=N→1do

flag←false

fori=1→length(τi)do

pi←ki

flag←true

τi←[]

break

end if

end for

if flag=flase then

return failure

end if

end for

return success

end function

4 響應時間

任務模型基于可搶占處理器平臺，因此任務執行時會受到高優先級任務的搶占而產生干擾時間。由算法1可知，τi在待分配任務集中處于最低優先級，除τi外的其他任務為干擾任務，生成一個集合hp(i)?，F判斷τi是否可調度，根據文獻[20]，任務總響應時間為本身執行時間與hp(i)中的任務產生的干擾時間的總和，而本文為區分任務的關鍵級別，hp(i)集合又以系統當前關鍵等級L為界限分成兩個子集，對應的干擾時間表示為ILj

Ri(l)=Ci(l)+ILj

(1)

4.1 干擾時間分析

干擾任務τj∈hp(i)在τi的執行窗口內以固定周期Tj釋放多個工作業。傳統實時系統的干擾時間[20]：

(2)

首先求出干擾任務τj在τi執行窗口內釋放的工作業總數(Ri(l))/Tj，與任務i的最壞情況執行時間相乘，類似地得出干擾時間總和。本文在該公式的基礎上進行演變，分析系統在不同執行模式下的干擾時間。

4.2 響應時間的靜態部分和關鍵等級切換部分

系統運行時需經歷穩定運行和關鍵等級切換兩個階段，干擾任務在這兩個階段對τi產生的干擾時間也不一致。因此τi的響應時間分為兩部分：靜態部分和關鍵級切換部分。

4.2.1靜態部分

假設當前系統穩定在關鍵等級k運行，干擾任務在τi的執行窗口內有穩定的執行模式，對于每個τj∈hp(i)，可在整個執行窗口內確定實際執行的工作業個數，修改式(2)為：

(3)

4.2.2關鍵級切換部分

干擾任務的最壞情況執行時間和實際執行工作業數量隨著系統關鍵等級動態變化。假設系統關鍵等級已提升至L，可對執行窗口進行劃分，以關鍵等級提升經歷的時間段作為一個子窗口，如系統關鍵等級從k提升至k+1對應的子窗口為(Ri(k)，Ri(k+1))，Ri(k)是系統關鍵等級在k穩定運行時τi的靜態響應時間。分別計算每個子窗口的干擾時間，并求出總干擾時間：

(4)

特別地，ε取值為L-1時，對應的子窗口為(Ri(L-1)，Ri(L))，Ri(L)作為響應時間值參與迭代計算。

4.3 基于響應時間分析的傳統調度策略

比較的調度策略有SMC、AMC-arb-x以及AMC-max-x。SMC由Baruah等[6]提出，規定所有任務執行時間不超過自身關鍵級對應的Ci(Li)，只在靜態條件下分析響應時間，而AMC進一步地考慮關鍵級的提升對響應時間的影響，Li等[21]在Fleming等[7]的基礎上完善了混合多關鍵級系統的調度策略：包括SMC和AMC-arb-x和AMC-max-x。

4.4 弱約束執行模式參數分配規則

現有的弱約束執行模式只適用于雙關鍵系系統，且規定任務的幾個工作業必須連續“跳過”執行[5]，而本文的執行模式消除了這個限制，并擴展至多關鍵級系統。假設系統當前關鍵等級為L，對于所有τi∈τ，LisLi+1(L)。例如系統關鍵等級由2提升到3，Li=2的任務以(m，s2(3))的約束模式執行；系統關鍵等級由3提升到4時，Li=3的任務以(m，s3(4))約束模式執行，Li=2的任務以(m，s2(4))的約束模式執行，有s2(3)=s3(4)，s2(4)>s3(4)。

4.5 兩種調度策略的主要區別

調度策略AMCwe-x和AMCwemax-x響應時間計算重點有兩個方面：(1) 根據弱約束模式的分配規則計算干擾任務在執行窗口內實際執行的工作業數量；(2) 確定干擾任務不同工作業的最壞情況執行時間。區別在于兩個調度策略對子窗口的劃分方式不同，且干擾任務工作業的最壞情況執行時間有不同的變化趨勢。

關鍵等級提升至L需經歷L-1次提升階段，AMC-we-x調度策略沒有精準確定系統關鍵等級提升的時間點，將干擾任務在τi的整個執行窗口(0，Ri(L))釋放的工作業的最壞情況執行時間都估計為Cj(L)，而忽略系統關鍵級提升過程中Cj值的變化。AMC-we-max-x策略設定L-1個提升的時間點，并以提升點調整子窗口，每個子窗口內釋放的工作業最壞情況有不同的估值。因此AMC-we-x策略悲觀估計了干擾任務工作業的最壞情況執行時間，在響應時間計算的精確方面低于AMC-we-max-x，但AMC-we-max-x調度策略需枚舉所有提升序列對應的響應時間，算法復雜程度較高。

4.6 AMC-we-x

假設在系統關鍵等級為L時對任務進行調度，由分配算法可知需計算τi響應時間以判斷該任務是否可調度。

4.6.1靜態部分響應時間

系統需經歷L個穩定運行階段。現討論系統穩定在關鍵等級k(k∈(1，L-1))時任務的響應時間?？筛鶕跫s束執行模式計算兩部分干擾時間，從而求得響應時間Ri(k)，過程如下：

1)ILj

(5)

第一部分為τi執行窗口(0，Ri(k))內τj釋放的工作業總數，第二部分為應“跳過”的工作業個數。

2)Lj≥k的干擾任務在τi的執行窗口內以正常模式執行，即sLj(k)=0,τj釋放的總工作業即為實際執行的工作業：

(6)

另一方面，干擾任務τj在τi執行窗口內有固定的最壞情況執行時間Ci(k)，Lj

Cj(Lj)

(7)

(8)

將式(7)和式(8)代入式(1)，可求出靜態部分總響應時間：

Cj(Lj)

(9)

4.6.2關鍵級切換部分響應時間計算

1)ILj≥l(l)部分，干擾任務τj在整個執行窗口內沒有工作業丟失，且τj所有工作業的最壞情況執行時間為Cj(L)，干擾時間計算如下：

(10)

2)ILj

(11)

τj在τi的執行窗口內應跳過的工作業總數如下：

(12)

由此可得出總響應時間為：

(13)

若待分配任務τi的關鍵等級小于L，由于具體的關鍵級提升點未知，可假設任務τi首個工作業沒有被丟棄，且干擾任務在τi窗口內沒有工作業跳過。響應時間為：

(14)

4.7 AMC-we-max-x

現確定關鍵級提升的時間點，從k提升至k+1的提升點tk在(Ri(k-1),Ri(k))之間，τj在tk前釋放的工作業最壞情況執行時間仍為k-1關鍵等級對應的Cj(k-1)，tk后釋放的工作業最壞情況執行時間為Ci(k)。如圖1所示，以提升點為分界調整子窗口，將(tk，tk+1)作為系統關鍵等級處于k+1階段的子窗口。

圖1 調整任務子窗口

1) 計算ILj

(15)

已知系統關鍵等級k

(16)

2)ILj≥l部分的干擾時間如下：

(17)

干擾任務在(tk,tk+1)子窗口對應的最壞情況執行時間為Cj(k+1)。

綜上，得到總響應時間計算公式：

(18)

5 實 驗

實驗參數：任務集包含的任務數量N，任務周期Ti：在10 ns～1 s范圍內按均勻分布生成。任務集利用率u采用UUnifast算法生成[22]，可以通過任務集總利用率和任務個數生成每個任務的利用率。系統最大關鍵等級Lm。任務執行時間Ci(L)：L1關鍵等級下τi的最壞情況執行時間Ci(L)=u×T。不同關鍵級的最壞情況執行時間有如下關系：Ci(L+1)=cf×Ci(L)。cf為Ci的關鍵級擴展參數。不同關鍵級的任務所占比率cp=(cp0,cp1,…,cpm)。cpk代表關鍵級為k的任務所占比率。弱約束執行模式參數(m，sLi(L))。

通過六組實驗對比相同任務集在AMC-arb-x、AMC-max-x、SMC、AMC-we-x、AMC-we-max-x 5個調度策略下估計所得的可調度比率以及低關鍵級任務丟棄比率。

除實驗四和實驗六外，弱約束模式中的參數值取為s2(3)=s1(2)=1,s1(3)=2，N取固定值20，可調度比率f(p)=可調度任務集個數/總任務集個數。

實驗一分析利用率變化對任務集可調度比率的影響，u在(0.025，0.975)之間變化，步長為0.025，每個利用率下生成1 000個任務集，結果如圖2所示。

圖2 任務可調度比率隨u變化曲線

實驗二至實驗五分析cp、cf、弱約束模式參數變化與可調度比率的關系，使用加權可調度比率公式[20]：

(19)

式中：Wy(p)代表參數p下由算法y計算得到的加權任務可調度比率；sy(τ,p)表示任務τ集在參數p下用算法y計算得到的可調度比率；u(τ)表示總利用率，在每個參數p下計算在利用率(0.025,0.975)之間任務的可調度比率，且每個利用率生成100個任務集。

實驗二觀察cp值變化對任務可調度比率的影響，如圖3所示。

圖3 任務可調度比率隨cp3變化曲線

實驗三觀察cf變化時任務可調度比率的變化趨勢，如圖4所示。

圖4 任務可調度比率隨cf變化曲線

實驗四通過改變參數s，觀測任務集可調度比率的變化趨勢，如圖5所示。

圖5 任務可調度比率隨s變化曲線

實驗五通過改變參數m，觀測任務集可調度比率的變化趨勢，如圖6所示。

圖6 任務可調度比率隨m變化曲線

實驗六通過改變參數s，研究Li<3的任務丟棄比率變化趨勢，如圖7所示。

圖7 丟棄工作業數量隨s變化曲線

可得出以下結論：在所有調度策略下任務集的可調度比率隨著u、cf、cp的增加而下降，AMC-we-max-x以及AMC-max-x的整體調度性能分別優于AMC-we-x以及AMC-arb-x。

表1和表2分別為AMC-we-max-x提升比率隨cp3和cf的變化情況?？梢钥闯?，當Li=3的任務所占比例為0.1時，AMC-we-x與AMC-we-max-x的任務可調度比率接近，隨著cp3的增大兩者差距呈現增長趨勢，說明AMC-we-max-x策略對有較多高關鍵級任務的任務集的調度有明顯優勢。cp值在0.4左右時提升效果最明顯。同樣地，當cf取值2.2左右時，AMC-we-max-x任務可調度優勢比較明顯。

表1 AMC-we-max-x提升比率隨cp3變化情況

表2 AMC-we-max-x提升比率隨cf變化情況

續表2

對比實驗四到實驗六數據，分析弱約束執行模式參數的變化對任務可調度比率的影響，當m=sLi(L)時，AMC-we-x與AMC-we-max-x的執行模式與AMC-arb-x與AMC-max相同，因此任務可調度比率也一致(見圖5-圖6)。當固定sLi(L)值，改變m，因為隨著m增加，Li<3任務工作業的丟棄比率減少，導致整體調度比率下降；同理，隨著s增加，Li<3任務丟棄的工作業增加(見圖7)，整體調度比率隨之增加。

6 結 語

本文建立了一種新的混合多關鍵級任務模型，并基于響應時間分析提出兩種調度策略，在系統未實際運行前對任務集進行優先級分配，并在悲觀條件下分析可調度比率。修改了原有的弱約束執行模式并擴展至多關鍵級，給任務在不同系統關鍵級下設置對應的弱約束執行模式參數，通過實驗得出結論：由于AMC-we-x和AMC-we-max-x沒有簡單地丟棄所有低關鍵級任務工作業，因此線下估計的整體調度比率較AMC-arb-x和AMC-max-x有所下降，而任務實際運行時的執行時間往往小于Ci值，低關鍵級任務的弱約束執行對高關鍵級任務的實際影響小于估計值，因此本文提出調度策略能夠在保證高關鍵級任務正確執行的情況下提升低關鍵級任務的調度比率，從而減少丟棄任務的開銷，提高資源利用率。此外，AMC-we-max-x策略的響應時間計算精確度較高，估計所得的任務集可調度比率整體高于AMC-we-x。在實際應用中，可以根據任務的性能分配弱約束模式中的參數值，為任務的服務水平提供多種選擇。