嵌入式多核系統中三維立體調度模型的研究

黃姝娟, 朱怡安, 劉白林, 肖鋒

(1.西安工業大學 計算機科學與工程學院, 陜西 西安 710021; 2.西北工業大學 計算機學院, 陜西 西安 710072)

嵌入式多核平臺下，任務調度是系統的核心，如何優化調度算法，充分發揮多核處理器性能優勢，是當今研究的主要方向[1-3]。當前多核實時任務的調度算法主要分為全局調度算法(global scheduling algorithm)[4-6]和分區調度算法(partitioned scheduling algorithm)[7-8]2大類。GEDF(global earliest deadline first)[9]和PEDF(partitioned earliest deadline first)[10]，是2類調度算法的典型代表。對于全局調度算法來說，如果一個任務不允許搶占，而另外一個任務必須執行，那么就要將該任務遷移到其他核上執行[11]。這種遷移開銷比較大。對于分區調度算法而言，劃分在一個范圍內的任務只能在同一個處理器核上調度，雖避免了遷移，簡化了問題[12]，但對劃分的精確度有很高要求，劃分不好會直接影響丟失時限的任務數量。很多情況下任務劃分方法是很棘手的問題。為此，研究者提出了半分區調度算法(semi-partitioned scheduling algorithm)[13]，該方法將全局調度算法與分區調度算法相結合，旨在減少遷移開銷的同時減少進行劃分的任務數量，降低劃分難度。盡管如此，該類算法仍然存在遷移開銷和劃分方法如何精確的問題。為此，本文提出一種三維立體調度模型和調度算法，該方法以區域面積作為劃分方法，降低劃分的難度，提高劃分算法的精確度，在提高系統效率的同時，降低丟失時限的任務數量。

1 三維調度模型

1.1 實時周期任務模型

假設一個包含n個實時周期任務的嵌入式多核系統I={T0,T1,T2…Tn},其中Ti為一個四元組Ti(Ri,Ci,Di,Pi),Ri表示該任務首次發布時刻,Ci表示該任務的WCET(worst case execution time),Di表示相對時限且Di≥Ci,Pi表示該任務的執行周期且Pi≥Di≥Ci。用Jobi,j(ri,j,ci,j,di,j)表示Ti的第j次執行,其中ri,j為jobi,j的發布時間ri,j=Ri+(j-1)Pi,ci,j為jobi,j的執行時間ci,j=Ci,di,j為jobi,j的絕對時限di,j=ri,j+Di=Ri+(j-1)Pi+Di。

1.2 三維調度模型

定義1對于一個實時周期任務Ti(Ri,Ci,Di,Pi),如果Ci=Di則稱該任務為不可調和任務;如果Ci

定義2對于一個可調和任務Ti(Ri,Ci,Di,Pi),若用hfi表示該任務的調和因子(harmonic factor),則hfi=Di-Ci。則Ti的任何一個jobi,j都會有hfi+1個調和區間HFi,j={[ri,j+k,ri,j+ci,j+k]|

定義3對于任意實時調度系統I={T0,T1,T2…Tn},必然存在一個三維調度空間Ω={x,y,z},其中x表示時間軸,y表示當前運行在該平面的任務數,z表示處理器核數。對于任何一個實時周期任務Ti的任何一次執行jobi,j,該調度空間上必然會存在該job執行的一個矩形區域Φi,j,該區域的4個頂點坐標分別為Ai,j(ri,j,0,zi,j),Bi,j(ri,j+ci,j,0,zi,j)Ci,j(ri,j,yi,j,zi,j),Di,j(ri,j+ci,j,yi,j,zi,j)其中zi,j表示給jobi,j分配的處理器號,yi,j表示在第zi,j平面上所分配的任務的個數;把該矩形區域Φi,j稱為jobi,j對應在該三維調度空間Ω上的執行區域,簡單記為Φi,j={(ri,j,ri,j+ci,j,yi,j,zi,j)}。

對應于該矩形Φi,j區域上的面積稱為執行區域面積即Si,j=ci,j*yi,j如圖1所示。

圖1 Jobi,j(ri,j,ci,j,di,j) 的執行區域

定義4對于在同一Z平面上任何2個jobi,j和jobv,w,如果它們的執行區域面積沒有任何交叉覆蓋情況,則稱jobi,j和jobv,w相互獨立。如果在某段時間t內,2個任務Ti和Tj在該時間段內所有需要執行的job都相互獨立,則稱這2個任務在時間段t內相互獨立。如果t為無窮大都能滿足,則Ti和Tj稱為永久相互獨立任務。

定義5對于任何2個jobi,j和jobv,w的執行區域面積存在交叉覆蓋情況,則稱這2個job具有互干擾性。交叉覆蓋的區域稱為干擾區。相對應的干擾區面積SΛ為交叉覆蓋面積,相對應的jobi,j對jobv,w的干擾因子為ξi,j/v,w=SΛ/Sv,w而相對應的jobv,w對jobi,j的干擾因子為ξv,w/i,j=SΛ/Si,j。

定義6對于任何2個具有干擾區的job,如果至少有一個是可調和job,且其衍生出來的任意一個job或者是l-job中存在執行區域與另外一個job或其任意一個衍生job或者是l-job相互獨立,則稱這干擾區為可調和干擾區,否則稱為不可調和干擾區。

定義7k重干擾區 如果在某段時間t內,存在k個job的執行區都覆蓋了同一干擾區且該干擾區對于任何一個job都不可調和,那么稱該干擾區為k重干擾區。

定義8如果在Z=zi平面上存在某個區域既不是執行區也不是干擾區,則該區域稱為閑置區。

定義9給定一個三維空間Ω={x,y,z}在某段時間t內,假設xt,yt和zt分別為三維空間在該時間段內3個坐標軸所能取到的最大值,則在任意的Z=zi(i=1,2,…t)的平面內,所有單位面積之和稱為可調度空間面積,記為S=xt*yt。

1.3 可調度性證明

由上述定義可知,調度空間面積為執行區面積和閑置區面積之和。對于Z=zi的平面,任何一個區域無非為干擾區、執行區和閑置區三者之一,其中干擾區必定是執行區。

推論1如果系統I中所有任務之間在任何時間段不產生不可調和干擾區,則該系統中所有任務可以被調度在同一個處理器上。

證:如果在任何時間段內不產生干擾區,就說明所有任務都有自己的執行區且執行區并不被相互覆蓋,那么所有任務在任何時間段內產生的job都能在時限之前被調度完成。故可以被分配到同一個處理器上。

如果在任何時間段內產生的干擾區都是可調和干擾區,就說明所有任務都有自己的執行區且執行區通過調和區間衍生job或者l-job調和后并不被相互覆蓋,那么所有任務在任何時間段內產生的job都能在時限之前被調度完成。故可以被分配到同一個處理器上。

推論2若在某段時間t內,系統I產生k重干擾區,則在該時間段內必須有k個處理器核才能完成調度。

證:因為產生了k重干擾區,說明有k個job的執行區域都覆蓋在同一區域,且沒有任何可調和空間,若采用小于k個處理器核來調度,則必然還會產生無法調和的干擾區,一定會存在一些job無法在時限之前調度完成,因此必須采用k個處理器核來調度。

可以根據區域覆蓋情況來判斷2個job是否有干擾區。如果任務是可以互相搶占的,可以根據任務的可調和性來判斷干擾區是否為不可調和干擾區。下面討論都是可搶占的實時任務。

定理假設在不考慮上下文切換和中斷等額外開銷的情況下,任何2個jobi,j(ri,j,ci,j,di,j)和jobv,w(rv,w,cv,w,dv,w)能夠被調度在同一平面z上的充分必要條件是區域Φ={min(ri,j,rv,w),max(di,j,dv,w),2,z}的面積大于等于jobi,j的執行區域面積與jobv,w的執行區域面積之和。

證明先證充分條件:

jobi,j(ri,j,ci,j,di,j)和jobv,w(rv,w,cv,w,dv,w)的ri,j,rv,w,di,j,dv,w有如下4種情況:①ri,j≤rv,w且di,j≤dv,w;②ri,j>rv,w且di,j>dv,w;③ri,j>rv,w且di,j≤dv,w;④ri,j≤rv,w且di,j>dv,w

先證明(1)因為dv,w-ri,j≥dv,w-rv,w≥cv,w且di,j-rv,w≥di,j-ri,j≥ci,j那么由條件知Φ={(ri,j,dv,w,2,z)}的區域面積S=(dv,w-ri,j)×2≥Si,j+Sv,w其中Si,j=ci,j×2;Sv,w=cv,w×2分別是jobi,j和jobv,w的執行面積,如果沒有干擾區,則根據推論1在時間段[ri,j,dv,w]內jobi,j和jobv,w可以調度在同一個處理器核上。若有干擾區如圖2a)所示,則可以在Ω中先滿足jobi,j的執行區域,保證jobi,j在di,j之前執行完畢。剩余的區域劃出與Sv,w等量的區域作為jobv,w的執行區域,則能保證jobv,w在dv,w之前完成,如圖2b)所示。那么jobi,j和jobv,w就可以調度在同一個處理器核上。

圖2 干擾區產生/調整圖

同理可以證明②③④。

證明必要條件

根據推論1可知,如果可以調度在同一個處理器上則說明不存在干擾區或存在可調和的干擾區,如果不存在干擾區,則在[min(ri,j,rv,w),max(di,j,dv,w)]的時間段內Jobi,j和Jobv,w的執行區不存在區域覆蓋的情況,則Jobi,j和Jobv,w的執行區域面積之和必定小于等于Φ={min(ri,j,rv,w),max(di,j,dv,w),2,z}的區域面積。

如果存在的是可調和干擾區,則可以通過調和區間在時間段[min(ri,j,rv,w),max(di,j,dv,w)]內化解為不互相覆蓋的區域,則它們的執行區必定存在該時間段的區域內,Jobi,j和Jobv,w的執行區域面積之和必定小于等于Φ={min(ri,j,rv,w),max(di,j,dv,w),2,z}的區域面積。

得證。

2 調度算法

本文所涉及的分區調度算法是根據實時任務的各項參數特征,計算出所有實時任務的公共周期。在該公共周期內找出實時任務所要執行的job。由文獻[8]可以知道,如果該系統所有實時任務的job在公共周期內可以被調度成功,那么這些實時任務在所有周期內都能被調度成功。

系統開始初始化x,y,z3個參數代表3個坐標軸,分別表示時間、任務個數以及處理器個數;第一次找出發布時間最近的1個job分配到z=1的平面上,按照定義3計算出該job的執行區域,再依次找出相應的job,根據定理和推論3從z=1的平面開始判斷新加入的job是否能被調度到該平面上,直到將所有新加入的job分配到相應的平面上,程序結束。具體算法流程圖如圖3所示。

圖3 三維調度算法主流程圖

在整個流程中,比較難的步驟是如何找出相應的調和區間以便消除干擾區。

方法如下:

1) 從該平面找出所有可調和job和不可調和job分別放入不同的隊列中,將不可調和任務的執行區間放入集合H中;

2) 判斷可調和隊列是否為空?若是,則返回集合H。若不是,則轉入步驟3)。

3) 從可調和任務隊列中取出時限最小的job,從該job的可調和區間找出一個與集合H中的所有執行區間不覆蓋的可調和區間,放入集合H中;轉2。

具體算法流程如圖4所示。

圖4 查找合適的調和區間算法流程圖

3 實驗結果

本文測試的環境是在一個Intel(R)Core(TM)2Quad Q8400多核平臺上。將所提出的三維調度算法和PEDF算法進行比較，測試方法是隨機產生1 000個任務集，每個任務集中產生50個參數不等的實時周期任務，所有周期任務都滿足時限小于或等于周期，且執行時間小于時限。在整個仿真實驗過程中，為了描述算法之間的性能差異，采用多次模擬求平均值的方法按照在某段時間內，系統吞吐率，丟失時限的任務數量所占總任務數的比例，核利用率3個方面進行性能對比，如圖5和表1所示。

圖5 2種算法核利用率

表1 2種算法的系統利用率和丟失時限任務數所占總任務的比例

從圖5中可以看出，隨著核數的增加，采用三維調度算法比PEDF算法在核利用率方面要更加充分。從表1可以看出，在系統吞吐率方面三維調度算法相比PEDF算法優勢不是很明顯。這是因為尋找調和區花費的時間比較長，開銷較大，但在丟失時限的任務數比例方面，三維調度算法明顯占據優勢。這種提高對于解決減少丟失時限的任務數量來說，是能夠滿足某些實際需要的。由于目前實驗條件限制，運行的核數量僅為4個，以后將在核數更多的機器上進行實驗，并會進一步優化尋找調和區的算法，來驗證三維調度算法的優勢。

4 結 論

本文設計了一種新的三維調度模型，在該模型中確立了任務之間的相互獨立和相互干擾關系，并根據調度面積設定了調度方案，給出了相應的調度算法。通過實驗，該算法在核利用率、系統吞吐量以及丟失時限的任務數方面更優于PEDF算法。這為以后在異構多核平臺下的實時任務調度提供了新的思路。