支持緩存劃分的全局EDF實(shí)時(shí)系統(tǒng)調(diào)度策略

林宇晗, 嚴(yán) 健, 王侃侃, 鄧慶緒

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 遼寧 沈陽(yáng) 110819)

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

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

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

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

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

1 系統(tǒng)模型

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

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

2 調(diào)度算法

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

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

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

由于本文只考慮限制截止期任務(wù),即di≤pi,因此每個(gè)任務(wù)在任意時(shí)刻最多只有一個(gè)作業(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ù)隊(duì)列Qready,該隊(duì)列包含所有已釋放但還未完成的任務(wù),且按最早絕對(duì)截止期優(yōu)先排序.算法的輸出為執(zhí)行隊(duì)列Qrun.其中,函數(shù)first(Qready)返回的是隊(duì)列Qready中優(yōu)先級(jí)最高(絕對(duì)截止期最早)的任務(wù).函數(shù)schedule(Qrun)表示的是讓系統(tǒng)調(diào)度執(zhí)行任務(wù)隊(duì)列Qrun:如果當(dāng)前正在執(zhí)行的任務(wù)在隊(duì)列Qrun,那么保持執(zhí)行;如果當(dāng)前正在執(zhí)行的任務(wù)不在隊(duì)列Qrun,那么釋放所占用的核和緩存分區(qū)(即被搶占);最后讓在隊(duì)列Qrun中且當(dāng)前不在執(zhí)行的任務(wù)占用剩下的核和資源并開(kāi)始執(zhí)行.

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

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

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

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

3 可調(diào)度分析

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

3.1 問(wèn)題窗口分析

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

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

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

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

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

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

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

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

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

(4)

3.2 優(yōu)化算法

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

輸入: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的時(shí)間復(fù)雜度是O(An),其中處理器緩存分區(qū)總數(shù)A是常數(shù),因此算法2是線性復(fù)雜度的.

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

(5)

3.3 可調(diào)度條件

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

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

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

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

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

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

(6)

(7)

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

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

(8)

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

αi,k≤Xk,

(9)

βi,k≤Yk.

(10)

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

引理6τk的問(wèn)題窗口長(zhǎng)度上界為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無(wú)法執(zhí)行時(shí)間的上限.而且Sk=dk-ek是任務(wù)τk的松弛時(shí)間.因此,如果滿足?τk∈τ,Bk≤Sk,那么?τk∈τ,ek+Bk≤dk,即任務(wù)集τ所有任務(wù)都在截止期內(nèi)完成.證畢.

4 實(shí) 驗(yàn)

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

4.1 實(shí)驗(yàn)設(shè)置

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

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

4.2 可調(diào)度性實(shí)驗(yàn)

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

4.3 可延展性實(shí)驗(yàn)

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

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

5 結(jié) 語(yǔ)

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