支持緩存劃分的全局EDF實時系統調度策略

林宇晗, 嚴 健, 王侃侃, 鄧慶緒

(東北大學 計算機科學與工程學院, 遼寧 沈陽 110819)

近年來,現代多核處理器技術日趨成熟,其在實時嵌入式系統領域的應用也逐漸普及.為了提高系統平均性能,大部分多核處理器都支持共享緩存(Cache)技術.然而由于多核處理器對共享緩存的爭用,在各個核上并行執行的實時任務可能會顯著延遲[1].特別是在緩存資源緊張的嵌入式系統中,緩存爭用導致的延遲發生的時刻,次數和持續時間都是不確定的,因此嚴重影響了實時系統的時間可預測性.傳統上,為了保證調度的時間正確性,系統設計人員通常假設所有實時任務都受到最大的爭用延遲作為最差執行時間(WCET)的一部分從而為任務預留足夠的系統資源.但是這種基于悲觀假設的方法不僅造成極大的系統資源浪費,而且抵消甚至降低了共享緩存對系統性能的提升.

解決多核處理器間緩存干擾的一種有效方法是緩存劃分(cache partition)技術[2],通過頁著色(page coloring)[3]或通路劃分(way partitioning)[4]的方法將緩存劃分成多個緩存分區,并將任務映射到這些分區上執行,比如ARM的LbM技術[5-6],Intel的CAT技術[1，7]等.這樣并行執行的任務總是可使用不同的分區,實現了對共享緩存的隔離.由于并行執行的任務無法訪問別的任務的緩存分區,因此避免了并發的緩存訪問造成的緩存干擾,從而降低了處理器核之間的互相干擾導致的額外開銷并減少了任務的最壞響應時間[2].然而在實時系統中,這種技術需要根據不同任務的實際需求分配緩存分區,而且由于緩存空間有限,還需要保證任意時刻沒有緩存分區重疊.這種約束可能導致任務因緩存空間不足而被阻塞.因此,傳統的實時調度算法與分析方法無法有效地應對緩存共享帶來的難題.

最近研究者們提出了一種緩存敏感的全局調度策略.這種策略允許在系統運行時根據任務的需求將共享緩存動態地分配給各個處理器核,同時還能允許任務在各個核上遷移以充分利用系統資源.文獻[2]提出了一種緩存敏感的不可搶占全局固定優先級調度策略(FPca)和分析方法.由于不允許任務搶占,這種策略雖然避免了搶占帶來的開銷,但是可能導致優先級反轉使得高優先級任務受到過長的阻塞而錯失截止期.在此基礎上,文獻[1]提出了一種緩存敏感的可搶占全局固定優先級調度策略(gFPca)并分析了搶占造成的開銷.然而,以上工作都是基于固定優先級的調度(即任務的優先級是靜態分配的),并不適用于動態優先級調度,特別是全局EDF(earliest deadline first)調度.

可搶占全局EDF調度策略允許系統在運行中根據最早截止期優先的規則動態生成任務的優先級.因此這種調度策略相比于固定優先級更適用于開放系統(open system).文獻[8-11]針對可搶占全局EDF調度研究了基于時間窗口和干涉量估計相結合的分析方法.然而這些方法都沒有考慮緩存劃分技術帶來挑戰.

本文針對可搶占全局EDF采用緩存劃分技術的問題進行研究.結合已有的緩存敏感全局調度及分析的思想[2,5，12],本文提出了一種支持緩存劃分技術的可搶占全局EDF調度算法(gEDFca)及其可調度性分析方法.不同于現有的工作，本文首先提出了一種新的緩存敏感調度算法；在此基礎上分別討論了只考慮處理器和只考慮緩存的可調度條件；并且針對現有分析的缺陷,提出了一個優化算法；綜合以上提出了一個基于線性規劃的可調度條件；最后通過實驗驗證了調度分析的有效性.

1 系統模型

本文研究一個支持共享緩存劃分的多核處理器.這種處理器包含M個相互獨立的同構處理器核(以下簡稱核)以及A個大小相等相互獨立的緩存分區.所有核都可以訪問這些緩存分區.

考慮一個相互獨立的偶發性(sporadic)任務集τ={τ1,τ2,…,τn}.任務τi由一個四元組(ei,di,pi,ai)表示,其中,ei表示任務的最差執行時間(worst-case execution time, WCET),di表示任務的相對截止期(relative deadline),即任務釋放后必須完成的時間長度,pi表示任務的周期,即兩個連續釋放的任務實例之間的最小時間間隔,ai表示的是任務需要占用的緩存分區的個數.任務的松弛時間為Sk=dk-ek.需要注意的是,本文僅考慮限制截止期(constrained deadline)任務,即0

2 調度算法

上節討論了系統的模型與定義,本節給出一種支持緩存劃分的可搶占全局EDF調度算法(gEDFca).這種算法將EDF策略應用到緩存敏感的全局調度中:絕對截止期越早的作業被分配的優先級越高.與經典的全局EDF(gEDF)策略[11]不同,在gEDF中系統總是可以并行執行M個就緒任務,而在gEDFca中系統還需要考慮可用緩存分區數量的限制.

1) 除了高優先級的任務占用的,當前至少有一個處理器核可用；

2) 除了高優先級的任務占用的,當前至少有Ai個緩存空間可用；

由于本文只考慮限制截止期任務,即di≤pi,因此每個任務在任意時刻最多只有一個作業正在執行.算法的偽代碼如下所示.

算法1 gEDFca算法.

輸入:Qready

輸出:Qrun

1:Qrun←?;Qready←All ready tasks

2:whileQready≠?do

3:τi←first(Qready)

4:if(1+|Qrun|≤M)∧(Ai+∑τk∈QrunAk≤A)then

5:Qrun←Qrun∪{τi}

6:endif

7:Qready←Qready{τi}

8:endwhile

9:returnschedule(Qrun)

算法1的輸入為就緒任務隊列Qready,該隊列包含所有已釋放但還未完成的任務,且按最早絕對截止期優先排序.算法的輸出為執行隊列Qrun.其中,函數first(Qready)返回的是隊列Qready中優先級最高(絕對截止期最早)的任務.函數schedule(Qrun)表示的是讓系統調度執行任務隊列Qrun:如果當前正在執行的任務在隊列Qrun,那么保持執行;如果當前正在執行的任務不在隊列Qrun,那么釋放所占用的核和緩存分區(即被搶占);最后讓在隊列Qrun中且當前不在執行的任務占用剩下的核和資源并開始執行.

算法的第1行首先初始化了隊列Qrun和Qready.算法的第2～8行循環是算法生成執行隊列Qrun的主要過程.在每次循環中,找到當前就緒任務中具有最早截止絕對期的任務(第3行),并檢查是否滿足當前核和緩存分區的約束(第4行),如果滿足就將該任務加入執行隊列Qrun中(第5行),循環最后將該任務從就緒隊列Qready中移除(第7行).算法重復執行上述循環直到Qready為空.算法結束時就可以得到當前的執行隊列.

需要注意,雖然算法采用了最早截止期優先的策略,有些緩存需求較大的高優先級任務可能會由于緩存空間的限制而被阻塞.為了減少系統資源的浪費,算法允許其他具有較晚截止期卻滿足緩存空間約束的任務在這種情況下利用空閑資源優先執行.

表1 一個任務集例子

圖1 gEDFca調度實例示意圖

3 可調度分析

結合gEDF和FPca調度分析方法的思想[2，12]對gEDFca的可調度性問題進行分析,并針對已有方法的缺陷,提出一種優化算法,最后結合優化算法提出一種基于線性規劃的gEDFca的可調度條件.

3.1 問題窗口分析

在介紹關于gEDFca的問題窗口分析技術之前，需要引入幾個有用的概念.

定義1在時間長度為t的時間段內,任務τi對任務τk的干涉Ii,k(t)表示為:任務τi在該時間段內使得τk就緒后無法執行所累積的最長執行時間.

定義2在時間長度為t的時間段內,任務的工作負載表示為:該任務在該時間段內需要的計算量.

引理1[2]不針對具體的調度算法,一個任務τi在長度為t的時間段內的工作負載上界為Wi(t):

Wi(t)=eiNi(t)+min(t+di-ei-piNi(t),ei) .

(1)

因此根據引理1,可以很容易得到干涉Ii,k(t)一個安全的上界:

Ii,k(t)=Wi(t) .

(2)

注意由于gEDFca允許任務間搶占,τk的問題窗口可能包含許多子區間,其總長度為Sk.根據緩存敏感調度的問題窗口分析框架理論[1-2],分析一個任務是否能被調度,首先可以討論兩種極端的情況:1)假設總是有足夠的緩存空間;2)假設總是有足夠的處理器核,然后放松上述約束綜合出一個一般性的可調度條件.本文結合了類似文獻 [1-2]中的思想,引入gEDFca問題窗口分析方法.

3.1.1 假設總是有足夠的緩存空間

引理2 假設總是有足夠的緩存空間,一個任務τk∈τ一定可調度如果滿足:

(3)

3.1.2 假設總是有足夠的處理器核

在這種情況下,只考慮緩存分區對任務的影響.根據gEDFca算法中作業被調度執行的三個條件,易得如下引理.

定義4在長度為t時間段內的任務τi緩存負載為:緩存分區數ai乘以時間段長度t.

引理3 假設總是有足夠的處理器核,一個任務τk就緒后無法被gEDFca調度執行,僅當有至少A-ak+1個緩存分區被高優先級任務占用.

證明:假設一個任務τk無法執行,且存在最多A-ak個緩存分區被高優先級任務占用.那么存在至少有A-A+ak=ak個緩存分區空閑或被低優先級任務占用.由于有足夠的處理器核,那么任務τk滿足被gEDFca調度執行的條件而被調度執行,與假設矛盾.證畢.

引理4 假設總是有足夠的處理器核,一個任務τk∈τ一定可調度如果滿足:

第四，創設教師發展場域，能夠凸顯教學主體獨立人格形成與完善的價值。教師教學自主性的生成過程也是逐漸擺脫權力場域的控制過程，是教師主體人格形成的過程，也是越來越擁有專業自信與專業自主的過程。

(4)

3.2 優化算法

根據觀察發現,引理4的調度條件之所以能成立關鍵在于引理3的結論,即一個任務無法執行,僅當有至少A-ak+1個緩存分區被高優先級任務占用.雖然引理3的估計是安全的,但是卻過于悲觀.實際上,高優先級任務占用的緩存空間大于或等于1,所以由這些使得任務τk無法執行的高優先級任務占用緩存空間的組合之和的最小值大于或等于A-ak+1,即至少有A′個緩存被高優先級任務占用,其中A-ak+1≤A′≤A.直觀上意味著在τk恰好滿足截止期時系統實際可以利用更多的緩存空間.具體可以參考以下的例子.

輸入:k,τ,A

1: ?x∈[1,A],v[x]←False;v[0]←True;τ′←τ/{τk};

2:fori←0to|τ′|-1do

3:forj←Atoaido

4:v[j]←v[j]∨v[j-ai]

5:endfor

6:endfor

10:endif

11:endfor

算法2最多有二重循環,其中第2～6行的外層循環最多遍歷n次,第3～5行的內層循環最多遍歷A次,因此算法2的時間復雜度是O(An),其中處理器緩存分區總數A是常數,因此算法2是線性復雜度的.

引理5 假設總是有足夠的處理器核,一個任務τk∈τ一定可調度如果滿足:

(5)

3.3 可調度條件

在3.1節中將問題窗口分析技術分別應用在了兩種極端的情況，并得出了相應的結論，之后在3.2節中進行了優化.本節將考慮綜合上述結論，得出一般性的可調度條件.

定義6在某個時刻,處理器處于τk忙碌狀態(非忙碌狀態)如果所有(不是所有)M個處理器核都在執行τk的高優先級任務.在某個時間段內,如果該時間段內所有時刻處理器核都處于忙碌狀態(非忙碌狀態),那么這個時間段定義為忙碌期(非忙碌期).

根據定義6,易知對于任意時刻t要么處于忙碌狀態,要么處于非忙碌狀態,不存在其他中間狀態或者t既處于忙碌狀態又處于非忙碌狀態.因此,可以安全地將τk問題窗口劃分為兩個部分:核忙碌區間和緩存忙碌區間.

定義7任務τk的核忙碌區間為τk問題窗口中的忙碌期,任務τk的緩存忙碌區間為τk問題窗口中的非忙碌期.

定義8任務τi在任務τk的核忙碌區間的工作負載為αi,k,在任務τk的緩存忙碌區間的工作負載為βi,k.

根據定義8,任務集τ在τk的核忙碌區間工作負載之和為∑τi∈ταi,k.根據定義6,在τk的核忙碌區間,所有的處理器都在忙碌,因此τk問題窗口中的忙碌期長度的上界Xk為

(6)

(7)

根據定義1與引理1,τi在問題窗口的工作負載不超過干涉Ii,k(t)的上界,即

αi,k+βi,k≤Ii,k(Sk) .

(8)

根據定義8,任務τi在任務τk的核忙碌區間的工作負載不大于忙碌期長度的上界Xk.同理,任務τi在任務τk的緩存忙碌區間的工作負載不大于忙碌期長度的上界Yk,結合式(6)和式(7),得

αi,k≤Xk,

(9)

βi,k≤Yk.

(10)

通過以上討論,可得如下結論.

引理6τk的問題窗口長度上界為Bk,其中Bk是如下線性規劃的最優解:

subject to ?i:αi,k+βi,k≤Ii,k(Sk) ,

αi,k≤Xk,

βi,k≤Yk.

(11)

定理1任務集τ可被gEDFca調度,如果?τk∈τ都滿足:

Bk≤Sk.

(12)

證明:根據引理6,Bk是任務τk無法執行時間的上限.而且Sk=dk-ek是任務τk的松弛時間.因此,如果滿足?τk∈τ,Bk≤Sk,那么?τk∈τ,ek+Bk≤dk,即任務集τ所有任務都在截止期內完成.證畢.

4 實 驗

為驗證本文提出的可調度分析方法的有效性與效率,使用隨機生成數據集進行大量的仿真實驗對分析方法的可調度性和可延展性進行評估.首先進行可調度性實驗來評估可調度條件的性能，然后進行可延展性實驗來評估方法的效率.

4.1 實驗設置

本文采用隨機生成的任務集,參數設置如下:首先設置任務集的任務周期均勻分布在[10,20]內,任務資源利用率(任務的最差執行時間與周期之比)根據任務類型分為三類:輕型任務,均勻分布在[0.05,0.1]內；中型任務,均勻分布在[0.1,0.2]內；重型任務，均勻分布在[0.2,0.4]內.任務的最差執行時間由利用率與任務周期的乘積求得.任務所需的緩存均勻分布在[8,10]內.處理器核的個數M設為4,處理器緩存分區的個數A設為20.任務集通過迭代的方式生成,將每次迭代生成1個滿足設置的隨機任務加入到任務集中直到任務集的利用率之和大于目標值為止.最后降低最后一個任務的利用率使得任務集利用率之和等于目標值.

實驗采用開源的整數規劃求解工具Python-MIP工具集進行求解.實驗運行在Intel Xeon 4110處理器(2.6 GHz),32 GB主存的Linux PC上.

4.2 可調度性實驗

圖2 調度接受率結果

4.3 可延展性實驗

圖3中橫坐標表示任務集中任務個數,縱坐標表示引理6中線性規劃的求解時間.2 000個任務的求解時間為15 s,10 000個任務的求解時間為563 s.實驗結果表明，在實驗平臺上,一個具有數千個任務的任務集也能在數分鐘內求得解,具有較高的效率.

圖3 求解時間結果

5 結 語

共享緩存劃分技術提供了一種減少任務執行時間不確定性的手段.本文提出一種支持緩存劃分的全局EDF調度算法,并針對該算法提出了一種可調度性分析技術.通過線性規劃的方法判斷任務集的可調度性來保證系統的可預測性.本文還提出了一種分析優化算法,進一步提高了可調度性.隨機實驗顯示本文的分析方法具有較高的效率和性能.