嵌入式多核系統(tǒng)中三維立體調(diào)度模型的研究

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

(1.西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 陜西 西安 710021; 2.西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710072)

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

1 三維調(diào)度模型

1.1 實(shí)時(shí)周期任務(wù)模型

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

1.2 三維調(diào)度模型

定義1對(duì)于一個(gè)實(shí)時(shí)周期任務(wù)Ti(Ri,Ci,Di,Pi),如果Ci=Di則稱該任務(wù)為不可調(diào)和任務(wù);如果Ci

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

定義3對(duì)于任意實(shí)時(shí)調(diào)度系統(tǒng)I={T0,T1,T2…Tn},必然存在一個(gè)三維調(diào)度空間Ω={x,y,z},其中x表示時(shí)間軸,y表示當(dāng)前運(yùn)行在該平面的任務(wù)數(shù),z表示處理器核數(shù)。對(duì)于任何一個(gè)實(shí)時(shí)周期任務(wù)Ti的任何一次執(zhí)行jobi,j,該調(diào)度空間上必然會(huì)存在該job執(zhí)行的一個(gè)矩形區(qū)域Φi,j,該區(qū)域的4個(gè)頂點(diǎn)坐標(biāo)分別為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分配的處理器號(hào),yi,j表示在第zi,j平面上所分配的任務(wù)的個(gè)數(shù);把該矩形區(qū)域Φi,j稱為jobi,j對(duì)應(yīng)在該三維調(diào)度空間Ω上的執(zhí)行區(qū)域,簡(jiǎn)單記為Φi,j={(ri,j,ri,j+ci,j,yi,j,zi,j)}。

對(duì)應(yīng)于該矩形Φi,j區(qū)域上的面積稱為執(zhí)行區(qū)域面積即Si,j=ci,j*yi,j如圖1所示。

圖1 Jobi,j(ri,j,ci,j,di,j) 的執(zhí)行區(qū)域

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

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

定義6對(duì)于任何2個(gè)具有干擾區(qū)的job,如果至少有一個(gè)是可調(diào)和job,且其衍生出來的任意一個(gè)job或者是l-job中存在執(zhí)行區(qū)域與另外一個(gè)job或其任意一個(gè)衍生job或者是l-job相互獨(dú)立,則稱這干擾區(qū)為可調(diào)和干擾區(qū),否則稱為不可調(diào)和干擾區(qū)。

定義7k重干擾區(qū) 如果在某段時(shí)間t內(nèi),存在k個(gè)job的執(zhí)行區(qū)都覆蓋了同一干擾區(qū)且該干擾區(qū)對(duì)于任何一個(gè)job都不可調(diào)和,那么稱該干擾區(qū)為k重干擾區(qū)。

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

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

1.3 可調(diào)度性證明

由上述定義可知,調(diào)度空間面積為執(zhí)行區(qū)面積和閑置區(qū)面積之和。對(duì)于Z=zi的平面,任何一個(gè)區(qū)域無非為干擾區(qū)、執(zhí)行區(qū)和閑置區(qū)三者之一,其中干擾區(qū)必定是執(zhí)行區(qū)。

推論1如果系統(tǒng)I中所有任務(wù)之間在任何時(shí)間段不產(chǎn)生不可調(diào)和干擾區(qū),則該系統(tǒng)中所有任務(wù)可以被調(diào)度在同一個(gè)處理器上。

證:如果在任何時(shí)間段內(nèi)不產(chǎn)生干擾區(qū),就說明所有任務(wù)都有自己的執(zhí)行區(qū)且執(zhí)行區(qū)并不被相互覆蓋,那么所有任務(wù)在任何時(shí)間段內(nèi)產(chǎn)生的job都能在時(shí)限之前被調(diào)度完成。故可以被分配到同一個(gè)處理器上。

如果在任何時(shí)間段內(nèi)產(chǎn)生的干擾區(qū)都是可調(diào)和干擾區(qū),就說明所有任務(wù)都有自己的執(zhí)行區(qū)且執(zhí)行區(qū)通過調(diào)和區(qū)間衍生job或者l-job調(diào)和后并不被相互覆蓋,那么所有任務(wù)在任何時(shí)間段內(nèi)產(chǎn)生的job都能在時(shí)限之前被調(diào)度完成。故可以被分配到同一個(gè)處理器上。

推論2若在某段時(shí)間t內(nèi),系統(tǒng)I產(chǎn)生k重干擾區(qū),則在該時(shí)間段內(nèi)必須有k個(gè)處理器核才能完成調(diào)度。

證:因?yàn)楫a(chǎn)生了k重干擾區(qū),說明有k個(gè)job的執(zhí)行區(qū)域都覆蓋在同一區(qū)域,且沒有任何可調(diào)和空間,若采用小于k個(gè)處理器核來調(diào)度,則必然還會(huì)產(chǎn)生無法調(diào)和的干擾區(qū),一定會(huì)存在一些job無法在時(shí)限之前調(diào)度完成,因此必須采用k個(gè)處理器核來調(diào)度。

可以根據(jù)區(qū)域覆蓋情況來判斷2個(gè)job是否有干擾區(qū)。如果任務(wù)是可以互相搶占的,可以根據(jù)任務(wù)的可調(diào)和性來判斷干擾區(qū)是否為不可調(diào)和干擾區(qū)。下面討論都是可搶占的實(shí)時(shí)任務(wù)。

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

證明先證充分條件:

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)因?yàn)閐v,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)}的區(qū)域面積S=(dv,w-ri,j)×2≥Si,j+Sv,w其中Si,j=ci,j×2;Sv,w=cv,w×2分別是jobi,j和jobv,w的執(zhí)行面積,如果沒有干擾區(qū),則根據(jù)推論1在時(shí)間段[ri,j,dv,w]內(nèi)jobi,j和jobv,w可以調(diào)度在同一個(gè)處理器核上。若有干擾區(qū)如圖2a)所示,則可以在Ω中先滿足jobi,j的執(zhí)行區(qū)域,保證jobi,j在di,j之前執(zhí)行完畢。剩余的區(qū)域劃出與Sv,w等量的區(qū)域作為jobv,w的執(zhí)行區(qū)域,則能保證jobv,w在dv,w之前完成,如圖2b)所示。那么jobi,j和jobv,w就可以調(diào)度在同一個(gè)處理器核上。

圖2 干擾區(qū)產(chǎn)生/調(diào)整圖

同理可以證明②③④。

證明必要條件

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

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

得證。

2 調(diào)度算法

本文所涉及的分區(qū)調(diào)度算法是根據(jù)實(shí)時(shí)任務(wù)的各項(xiàng)參數(shù)特征,計(jì)算出所有實(shí)時(shí)任務(wù)的公共周期。在該公共周期內(nèi)找出實(shí)時(shí)任務(wù)所要執(zhí)行的job。由文獻(xiàn)[8]可以知道,如果該系統(tǒng)所有實(shí)時(shí)任務(wù)的job在公共周期內(nèi)可以被調(diào)度成功,那么這些實(shí)時(shí)任務(wù)在所有周期內(nèi)都能被調(diào)度成功。

系統(tǒng)開始初始化x,y,z3個(gè)參數(shù)代表3個(gè)坐標(biāo)軸,分別表示時(shí)間、任務(wù)個(gè)數(shù)以及處理器個(gè)數(shù);第一次找出發(fā)布時(shí)間最近的1個(gè)job分配到z=1的平面上,按照定義3計(jì)算出該job的執(zhí)行區(qū)域,再依次找出相應(yīng)的job,根據(jù)定理和推論3從z=1的平面開始判斷新加入的job是否能被調(diào)度到該平面上,直到將所有新加入的job分配到相應(yīng)的平面上,程序結(jié)束。具體算法流程圖如圖3所示。

圖3 三維調(diào)度算法主流程圖

在整個(gè)流程中,比較難的步驟是如何找出相應(yīng)的調(diào)和區(qū)間以便消除干擾區(qū)。

方法如下:

1) 從該平面找出所有可調(diào)和job和不可調(diào)和job分別放入不同的隊(duì)列中,將不可調(diào)和任務(wù)的執(zhí)行區(qū)間放入集合H中;

2) 判斷可調(diào)和隊(duì)列是否為空?若是,則返回集合H。若不是,則轉(zhuǎn)入步驟3)。

3) 從可調(diào)和任務(wù)隊(duì)列中取出時(shí)限最小的job,從該job的可調(diào)和區(qū)間找出一個(gè)與集合H中的所有執(zhí)行區(qū)間不覆蓋的可調(diào)和區(qū)間,放入集合H中;轉(zhuǎn)2。

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

圖4 查找合適的調(diào)和區(qū)間算法流程圖

3 實(shí)驗(yàn)結(jié)果

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

圖5 2種算法核利用率

表1 2種算法的系統(tǒng)利用率和丟失時(shí)限任務(wù)數(shù)所占總?cè)蝿?wù)的比例

從圖5中可以看出，隨著核數(shù)的增加，采用三維調(diào)度算法比PEDF算法在核利用率方面要更加充分。從表1可以看出，在系統(tǒng)吞吐率方面三維調(diào)度算法相比PEDF算法優(yōu)勢(shì)不是很明顯。這是因?yàn)閷ふ艺{(diào)和區(qū)花費(fèi)的時(shí)間比較長，開銷較大，但在丟失時(shí)限的任務(wù)數(shù)比例方面，三維調(diào)度算法明顯占據(jù)優(yōu)勢(shì)。這種提高對(duì)于解決減少丟失時(shí)限的任務(wù)數(shù)量來說，是能夠滿足某些實(shí)際需要的。由于目前實(shí)驗(yàn)條件限制，運(yùn)行的核數(shù)量?jī)H為4個(gè)，以后將在核數(shù)更多的機(jī)器上進(jìn)行實(shí)驗(yàn)，并會(huì)進(jìn)一步優(yōu)化尋找調(diào)和區(qū)的算法，來驗(yàn)證三維調(diào)度算法的優(yōu)勢(shì)。

4 結(jié) 論

本文設(shè)計(jì)了一種新的三維調(diào)度模型，在該模型中確立了任務(wù)之間的相互獨(dú)立和相互干擾關(guān)系，并根據(jù)調(diào)度面積設(shè)定了調(diào)度方案，給出了相應(yīng)的調(diào)度算法。通過實(shí)驗(yàn)，該算法在核利用率、系統(tǒng)吞吐量以及丟失時(shí)限的任務(wù)數(shù)方面更優(yōu)于PEDF算法。這為以后在異構(gòu)多核平臺(tái)下的實(shí)時(shí)任務(wù)調(diào)度提供了新的思路。