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

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

2 調(diào)度算法

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

1) 除了高優(yōu)先級的任務(wù)占用的,當(dāng)前至少有一個處理器核可用；

2) 除了高優(yōu)先級的任務(wù)占用的,當(dāng)前至少有Ai個緩存空間可用；

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

算法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的輸入為就緒任務(wù)隊列Qready,該隊列包含所有已釋放但還未完成的任務(wù),且按最早絕對截止期優(yōu)先排序.算法的輸出為執(zhí)行隊列Qrun.其中,函數(shù)first(Qready)返回的是隊列Qready中優(yōu)先級最高(絕對截止期最早)的任務(wù).函數(shù)schedule(Qrun)表示的是讓系統(tǒng)調(diào)度執(zhí)行任務(wù)隊列Qrun:如果當(dāng)前正在執(zhí)行的任務(wù)在隊列Qrun,那么保持執(zhí)行;如果當(dāng)前正在執(zhí)行的任務(wù)不在隊列Qrun,那么釋放所占用的核和緩存分區(qū)(即被搶占);最后讓在隊列Qrun中且當(dāng)前不在執(zhí)行的任務(wù)占用剩下的核和資源并開始執(zhí)行.

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

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

表1 一個任務(wù)集例子

圖1 gEDFca調(diào)度實例示意圖

3 可調(diào)度分析

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

3.1 問題窗口分析

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

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

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

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

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

(1)

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

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

(2)

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

3.1.1 假設(shè)總是有足夠的緩存空間

引理2 假設(shè)總是有足夠的緩存空間,一個任務(wù)τk∈τ一定可調(diào)度如果滿足:

(3)

3.1.2 假設(shè)總是有足夠的處理器核

在這種情況下,只考慮緩存分區(qū)對任務(wù)的影響.根據(jù)gEDFca算法中作業(yè)被調(diào)度執(zhí)行的三個條件,易得如下引理.

定義4在長度為t時間段內(nèi)的任務(wù)τi緩存負載為:緩存分區(qū)數(shù)ai乘以時間段長度t.

引理3 假設(shè)總是有足夠的處理器核,一個任務(wù)τk就緒后無法被gEDFca調(diào)度執(zhí)行,僅當(dāng)有至少A-ak+1個緩存分區(qū)被高優(yōu)先級任務(wù)占用.

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

引理4 假設(shè)總是有足夠的處理器核,一個任務(wù)τk∈τ一定可調(diào)度如果滿足:

第四，創(chuàng)設(shè)教師發(fā)展場域，能夠凸顯教學(xué)主體獨立人格形成與完善的價值。教師教學(xué)自主性的生成過程也是逐漸擺脫權(quán)力場域的控制過程，是教師主體人格形成的過程，也是越來越擁有專業(yè)自信與專業(yè)自主的過程。

(4)

3.2 優(yōu)化算法

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

輸入: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最多有二重循環(huán),其中第2～6行的外層循環(huán)最多遍歷n次,第3～5行的內(nèi)層循環(huán)最多遍歷A次,因此算法2的時間復(fù)雜度是O(An),其中處理器緩存分區(qū)總數(shù)A是常數(shù),因此算法2是線性復(fù)雜度的.

引理5 假設(shè)總是有足夠的處理器核,一個任務(wù)τk∈τ一定可調(diào)度如果滿足:

(5)

3.3 可調(diào)度條件

在3.1節(jié)中將問題窗口分析技術(shù)分別應(yīng)用在了兩種極端的情況，并得出了相應(yīng)的結(jié)論，之后在3.2節(jié)中進行了優(yōu)化.本節(jié)將考慮綜合上述結(jié)論，得出一般性的可調(diào)度條件.

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

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

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

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

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

(6)

(7)

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

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

(8)

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

αi,k≤Xk,

(9)

βi,k≤Yk.

(10)

通過以上討論,可得如下結(jié)論.

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

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

αi,k≤Xk,

βi,k≤Yk.

(11)

定理1任務(wù)集τ可被gEDFca調(diào)度,如果?τk∈τ都滿足:

Bk≤Sk.

(12)

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

4 實 驗

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

4.1 實驗設(shè)置

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

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

4.2 可調(diào)度性實驗

圖2 調(diào)度接受率結(jié)果

4.3 可延展性實驗

圖3中橫坐標(biāo)表示任務(wù)集中任務(wù)個數(shù),縱坐標(biāo)表示引理6中線性規(guī)劃的求解時間.2 000個任務(wù)的求解時間為15 s,10 000個任務(wù)的求解時間為563 s.實驗結(jié)果表明，在實驗平臺上,一個具有數(shù)千個任務(wù)的任務(wù)集也能在數(shù)分鐘內(nèi)求得解,具有較高的效率.

圖3 求解時間結(jié)果

5 結(jié) 語

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