嵌入式系統(tǒng)的細(xì)粒度多處理器實時搶占式調(diào)度算法

李 揚 王春明

1(江蘇商貿(mào)職業(yè)學(xué)院電子與信息學(xué)院 江蘇 南通 226011) 2(南通大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 南通 226019)

0 引 言

如今AMD與Intel等處理器廠商已經(jīng)發(fā)布8個核心以上的CPU，未來CPU的核心數(shù)量更可能達(dá)到百級，由此增加了多處理器、多任務(wù)調(diào)度問題的難度[1]。傳統(tǒng)的研究大多集中于單處理器，而針對單處理器的諸多研究成功無法擴(kuò)展至多處理器系統(tǒng)[2]。為了充分利用多核心處理器的計算能力，任務(wù)調(diào)度算法需要支持任務(wù)之間的并行化[3-4]，此外，對于多線程的任務(wù)，更可能發(fā)生同一任務(wù)的不同線程在多個處理器核心上并發(fā)執(zhí)行的情況，因此，細(xì)粒度的任務(wù)調(diào)度算法成為一個亟待解決的問題[5]。

實時調(diào)度研究中有兩個基本問題：(1) 調(diào)度算法需為任務(wù)或線程分配合適的優(yōu)先級，且滿足系統(tǒng)的截止期約束；(2) 為調(diào)度算法提供可調(diào)度性分析，證明算法滿足系統(tǒng)的截止期約束[6-7]。以往的研究大多從單線程多任務(wù)、多處理器的實時調(diào)度方面解決上述兩個問題。近期，出現(xiàn)多個考慮多線程多任務(wù)的多處理器調(diào)度研究，其中可調(diào)度性分析的研究為主要目標(biāo)，但針對此場景的調(diào)度算法優(yōu)化研究相對較少[8-10]。

單線程任務(wù)中，作業(yè)是基本的調(diào)度單位，該場景的實時調(diào)度算法根據(jù)優(yōu)先級變化的時間點主要分為三類[11]：(1) 任務(wù)級固定優(yōu)先級算法；(2) 作業(yè)級固定優(yōu)先級算法；(3) 動態(tài)優(yōu)先級算法。如果將線程作為調(diào)度單位，則為調(diào)度問題增加了一個維度，從而提升了問題的復(fù)雜度。

文獻(xiàn)[12]提出了最優(yōu)優(yōu)先級分配算法(OPA)，該研究證明了OPA是任務(wù)級固定優(yōu)先級分配問題的最優(yōu)算法，本文期望將OPA算法擴(kuò)展至線程級調(diào)度場景，但由此帶來兩個問題：線程級依賴關(guān)系與線程級調(diào)度算法的可調(diào)度性分析。本文首先采用任務(wù)分解方法[13]為各線程分配偏移時間與截止期；然后，基于干擾的線程級分析證明本文擴(kuò)展調(diào)度算法與OPA算法兼容，從而證明本文線程級調(diào)度算法也是最優(yōu)調(diào)度算法；最終，設(shè)計了完整的線程級調(diào)度算法。

1 系統(tǒng)模型

1.1 有向無環(huán)圖(DAG)任務(wù)

(a) DAG任務(wù)

(b) 任務(wù)分解圖1 任務(wù)示意圖

1.2 任務(wù)分解

可將一個DAG任務(wù)分解為獨立、有序的子任務(wù)集合，線程之間具有依賴關(guān)系與執(zhí)行出口，為DAG任務(wù)的各線程分配對應(yīng)的偏移與截止期。

將任務(wù)τ分解產(chǎn)生的線程集合設(shè)為τdecom，τdecom中線程的數(shù)量設(shè)為n。對于任務(wù)τi，定義任務(wù)的主線程為θi,1,τi中其他各線程θi,p表示為(Ti,p,Ci,p,Di,p,Oi,p)，其中Ti,p是最小間隔(等于Ti)，Ci,p與Di,p分別表示最壞情況的運行時間及其截止期，Oi,p為對應(yīng)的偏移(從Oi,1=0開始)。

1.3 CPU平臺與調(diào)度算法

假設(shè)多核CPU由m個相同的處理器組成，調(diào)度策略為全局任務(wù)-線程級固定優(yōu)先級調(diào)度，每個線程θi,p可以動態(tài)地在處理器之間遷移，且為所有線程分配靜態(tài)的優(yōu)先級Pi,p。將優(yōu)先級高于Pi,p的線程集合設(shè)為hp(θi,p)。

2 可調(diào)度性分析

DAG任務(wù)分解為線程級之后，各線程即設(shè)置了偏移與截止期，無需考慮線程間的依賴關(guān)系?；诟蓴_的可調(diào)度性分析兼容OPA，所以本文采用該方案[15]。

2.1 基于干擾的可調(diào)度性分析

線程級干擾可如下定義：

干擾Ik,q(a,b)：如果θk,q為ready狀態(tài),但[a,b)中更高優(yōu)先級的線程正在運行,此時的時隙總和定義為干擾Ik,q(a,b)。

干擾I(k,q)→(k,q)(a,b)：[a,b)中θi,p正在運行，且θk,q為ready狀態(tài)，此時的時隙總和定義為干擾I(k,q)→(k,q)(a,b)。

Ik,q(a,b)與I(k,q)→(k,q)(a,b)之間的關(guān)系是可調(diào)度性分析的重要基礎(chǔ)，Ik,q(a,b)與I(k,q)→(k,q)(a,b)之間的關(guān)系可推導(dǎo)為[16]：

(1)

(2)

文獻(xiàn)[15-16]定義了以下可調(diào)度性判定條件：

引理1 當(dāng)且僅當(dāng)所有線程θk,q滿足以下條件，則m個相同處理器組成的多處理器平臺中集合τdecom是可調(diào)度的：

(3)

文獻(xiàn)[17]對引理1擴(kuò)展，獲得了以下線程級判定條件：

引理2如果τdecom是可調(diào)度的，則τ也是可調(diào)度的。

2.2 基于工作負(fù)載的可調(diào)度性分析

首先需要確保各線程的截止期早于任務(wù)的截止期(引理1)，然后需要計算其他線程對目標(biāo)線程θk,q的干擾(式(3))。

考慮兩個場景計算最大工作負(fù)載：i≠k與i=k，原因在于i=k表示兩個干擾線程屬于同一個任務(wù)，說明τi中作業(yè)釋放的偏移已經(jīng)自動給定。

2.2.1i≠k情況的負(fù)載最大化

為了簡化描述，對于時間段(x,y]，如果作業(yè)的啟動時間在x之前，截止期在(x,y]內(nèi)，則簡稱為前置作業(yè)；如果作業(yè)的啟動時間與截止期均在(x,y]內(nèi)，則簡稱為期內(nèi)作業(yè)；如果作業(yè)的啟動時間在(x,y]內(nèi)，截止期在y之后，則簡稱為后置作業(yè)。

假設(shè)τi的作業(yè)為周期地啟動，定義Δi(x,y)為(x,y] 中前置任務(wù)啟動時間點與x的差值，如圖2所示。

圖2 τi中所有線程的最大工作負(fù)載

對于一個給定的Δi(x,y)，如果(x,y]時長為l，可將(x,y]時間段分為前置時段CIi(l,Δi(x,y))，期內(nèi)時段BDi(l,Δi(x,y))以及后置時段COi(l,Δi(x,y))，三種時段可表示為：

CIi(l,Δi(x,y))=min(Ti-Δi(x,y),l)

(4)

(5)

COi(l,Δi(x,y))=l-CIi(l,Δi(x,y))-BDi(l,Δi(x,y))

(6)

對于給定的Δi(x,y)，(x,y]中每個線程的負(fù)載貢獻(xiàn)度(如圖2所示)可計算為：

(7)

式中：

對于偶發(fā)任務(wù)：此時可簡單地檢查(x,y]中θi,p的運行量，則Δi(x,y)上界為Wi,p(l,Δi(x,y))。

考慮任務(wù)τi中Δi(x,y)的所有可能值，優(yōu)先級高于θk,q的所有線程工作負(fù)載之和即為τi對線程θk,q的最大干擾的上界，表示為：

(8)

2.2.2i=k情況的負(fù)載最大化

該情況下τk的作業(yè)被同一個任務(wù)干擾，因此可自動地決定τk中作業(yè)啟動的偏移時間。為了計算i=k情況的最大工作負(fù)載，本文僅需要考慮與線程θk,q重疊的部分執(zhí)行窗口，使用式(7)可計算這些線程的負(fù)載貢獻(xiàn)量。因此，τk中優(yōu)先級高于線程θk,q的其他所有線程最大負(fù)載計算為：

Ck,q+1)

(9)

基于式(8)和式(9)計算的干擾上界，為本文線程級調(diào)度算法設(shè)計了以下可調(diào)度性判定：

理論1對于m個相同的處理器平臺的線程級調(diào)度算法，如果每個線程θk,q滿足以下的不等式，則集合τdecom為可調(diào)度。

(10)

證明上文所述Wk(Dk,q)是θk,q運行窗口中優(yōu)先級高于pk,q的最大運行量。當(dāng)且僅當(dāng)A優(yōu)先級高于B時，A才對B產(chǎn)生干擾，式(3)左式的上界為式(10)的左式。根據(jù)引理1，可證明該理論。

3 線程級最優(yōu)優(yōu)先級分配算法

問題描述為：給定一個分解線程的集合τdecom，為每個線程θi,q∈τdecom分配優(yōu)先級Pi,p，因此根據(jù)基于工作負(fù)載的可調(diào)度性判定(理論1)認(rèn)為分解集合為可調(diào)度的。

OPA算法通過優(yōu)先級分配為各任務(wù)分配一個優(yōu)先級，如果所有任務(wù)τi滿足以下兩個條件，則該可調(diào)度性判定為OPA兼容：

條件1：任務(wù)τi的可調(diào)度性對其他優(yōu)先級的任務(wù)順序不敏感。

條件2：如果交換τk與τi之間的優(yōu)先級使得τk的優(yōu)先級提高，交換前后τk的可調(diào)度性不變。

算法1為本文改進(jìn)的OPA調(diào)度算法，該算法從優(yōu)先級最低的線程開始迭代地為所有線程分配優(yōu)先級，其中τdecom為操作系統(tǒng)中待分配優(yōu)先級的線程集。第k次迭代中，τdecom分為兩個不相交的子集：A(k)與R(k)，其中：

1)A(k)表示第k步之前已分配優(yōu)先級的線程子集；

2)R(k)表示剩余線程的子集。

理論1的可調(diào)度性判定是OPA兼容的，說明該判定滿足線程級可調(diào)度性的條件1與條件2，因此算法1的優(yōu)先級分配過程正確，證明方法如下：

理論2理論1的可調(diào)度性判定兼容算法1。

證明根據(jù)本文的可調(diào)度性判定證明線程級調(diào)度算法滿足條件1與條件2：

(1) 滿足條件1證明：式(10)的左式計算了每個任務(wù)對線程θk,q干擾的上界，任務(wù)的干擾上界計算為優(yōu)先級高于θk,q的其他線程工作負(fù)載之和。而該計算過程不依賴相應(yīng)的優(yōu)先級順序。因此，滿足條件1。

(2) 滿足條件2證明：交換θk,q與θi,p優(yōu)先級，θk,q的優(yōu)先級提高。因為θk,q的優(yōu)先級提高，所以hp(θk,q)交換后變得更小。因此，式(8)、式(9)的Wi(Dk,q)與Wk(Dk,q)交換之后變得更小，滿足條件2。

算法1線程級OPA調(diào)度算法

輸入：τdecom

輸出：調(diào)度狀態(tài)

1:k←0,A(1)←?,R(1)←τdecom

2:DO{

3:k←k+1

4:IF(thread_level_sch(A(k),R(k))==FAILURE);

5:returnFALSE;

//不可調(diào)度

6: }WHILE(R(k)!=NULL)

7:returnTRUE;

//可調(diào)度

算法2thread_level_sch函數(shù)

輸入：A(k),R(k)

輸出：分配結(jié)果

1:FOREACHthreadθp,q∈R(k) {

2:IF(θp,q可調(diào)度，根據(jù)理論1，R(k)中其他線程的優(yōu)先級均高于k)THEN{

3: 為θp,q分配優(yōu)先級k；

4:R(k+1)←R(k){θp,q}；

5:A(k+1)←A(k){θp,q}；

6:returnSUCCESS；

7: }

8: }

9:returnFAILURE；

4 動態(tài)截止期的線程級調(diào)度算法

4.1 算法設(shè)計

上文考慮了線程靜態(tài)偏移與截止期的情況，本算法的決策目標(biāo)為各線程的偏移、截止期與優(yōu)先級三個目標(biāo)，所以根據(jù)理論1的可調(diào)度性分析，并行任務(wù)系統(tǒng)是可調(diào)度的。本文動態(tài)截止期的線程級優(yōu)先級分配策略的主要思想為：首先通過算法1分配優(yōu)先級，如果算法1分配失敗，則調(diào)節(jié)一些線程的偏移與截止期，使得調(diào)節(jié)后某個線程可成功地分配優(yōu)先級，如果找到該調(diào)節(jié)方法，則繼續(xù)使用算法1分配優(yōu)先級；否則，認(rèn)為調(diào)度失敗，如算法3所示。算法3中輸入為操作系統(tǒng)中待分配優(yōu)先級的線程集，輸出為調(diào)度的狀態(tài)。

將線程結(jié)束時間與截止期之間的最小距離定義為線程θk,q的富余時間，表示為Sk,q。根據(jù)理論1的可調(diào)度性判定，Sk,q可近似為:

(11)

線程間贈予富余時間的目標(biāo)是為受贈線程分配一個優(yōu)先級，使得受贈線程變?yōu)榭烧{(diào)度，然而由此可能對其他可調(diào)度的線程產(chǎn)生邊際效應(yīng)?？紤]該問題，本文設(shè)計了以下三個子問題解決策略：

(1) 受贈線程的決策策略：應(yīng)當(dāng)保證已分配優(yōu)先級線程具有足夠的富余時間，所以決策策略為最小化總贈予時間的量。據(jù)此將所需贈予時間最少的線程作為受贈線程，時期變?yōu)榭烧{(diào)度狀態(tài)，見算法4的第3行。

(2) 贈予線程的決策策略：確定受贈線程后，建立一個贈予線程候選集合(算法4第4行)，屬同一個任務(wù)的候選線程已經(jīng)分配了優(yōu)先級，應(yīng)當(dāng)能夠贈予富余時間，且不影響所有線程的可調(diào)度性。為了避免破壞已分配優(yōu)先級線程的可調(diào)度狀態(tài)，本文選擇候選集合中歸一化富余時間量最大的線程作為贈予線程(算法4第6行)。

(3) 贈予時間量的分配：

引理3如果線程θk,q的截止期Dk,q減小，則對θk,q最壞情況的干擾隨之單調(diào)減小。

證明式(8)、式(9)中，分別計算了τi與τk的最大執(zhí)行量。式(7)中給定t，Wi,p(Di,p,t)與Wk,q(Dk,q,t)隨Dk,q下降而單調(diào)下降。式(8)中，因為需要調(diào)節(jié)Δi(x,y)使得Wi(Dk,q)最大化，所以Wk(Dk,q)不會隨Dk,q下降而提高，因此，可看出Wi(Dk,q)與Wk(Dk,q)隨Dk,q下降呈單調(diào)下降。由此證明引理3。

引理3說明如果贈予線程減小其截止期(將富余時間贈予受贈線程)，贈予線程可能獲得其他的富余時間。因此，每個贈予步驟中將贈予時間設(shè)置較小，從而增加找到其他富余時間的概率(算法第7行)，贈予完成后，每個贈予線程保持更新其富余時間量，以期找到其他的富余時間(算法11行)。

算法3動態(tài)截止期的線程級調(diào)度算法

輸入：τdecom

輸出：調(diào)度狀態(tài)

1:k←0,A(1)←?,R(1)←τdecom

2:DO{

3:IF(thread_level_sch(A(k),R(k))==FAILURE) {

4:IF(deadline_change(A(k),R(k))==FAILURE) {

5:returnFALSE;

6: }

7: }WHILE(R(k)!=NULL);

8:returnTRUE

算法4deadline_change函數(shù)

輸入：A(k),R(k)

//A(k)已調(diào)度的任務(wù)集，R(k)尚未調(diào)度的任務(wù)集

輸出：分配結(jié)果

1:F←R(k);

2:DO{

5: 保存τs中所有線程的當(dāng)前偏移與截止期；

10:returnSUCCESS;

12: }

13: 保存τs中所有線程的偏移與截止期；

14: }WHILE(F!=NULL)

15:returnFAILURE

4.2 計算復(fù)雜度分析

5 仿真實驗與結(jié)果分析

5.1 仿真環(huán)境

為了簡化表達(dá)，定義以下術(shù)語：Ci表示τi(∑qCi,q)內(nèi)所有線程最差情況的運行時間總和，Usys表示系統(tǒng)利用率，Li是τi最壞情況的執(zhí)行時間，LUsys定義為任務(wù)τi∈τ中最大的Li/Di值。

采用文獻(xiàn)[18]的方法生成DAG任務(wù)，對于任務(wù)τi，其參數(shù)如下設(shè)置：節(jié)點數(shù)量ni均勻選擇于區(qū)間[1,Nmax]內(nèi)，其中Nmax為單個任務(wù)的線程數(shù)量上限。每對節(jié)點之間邊隨機(jī)地生成，概率為p。根據(jù)Ci,p值所屬的三個范圍[1,5]、(6,10]、(11,40]，分別為任務(wù)τi與每個線程分配一個類型(輕型、中等、重型)，同時確定Ti(=Di)參數(shù)，因此Ci/Ti值分別在[0.1, 0.3]，(0.3, 0.6]或(0.6, 1.0]隨機(jī)地選擇。

為了全面地測試本算法對并行DAG任務(wù)的性能，共設(shè)計了三種測試統(tǒng)計量：(1) 系統(tǒng)利用率;(2) 并行度;(3) 節(jié)點總數(shù)量。第一組實驗評估了系統(tǒng)對Usys的調(diào)度性能變化情況，結(jié)果如圖3所示。第二組實驗評估了算法對不同任務(wù)內(nèi)并行度的調(diào)度性能變化情況，結(jié)果如圖4所示。第三組實驗評估了算法對τ中節(jié)點總數(shù)量的調(diào)度性能變化情況，結(jié)果如圖5、圖6所示。將本文算法與基本OPA算法[12]、B_task_EDF[19]以及C_task_EDF[20]三種算法進(jìn)行橫向比較，評估本算法的性能。

圖3 不同Usys的調(diào)度性能變化情況

圖4 不同任務(wù)內(nèi)并行度的調(diào)度性能變化情況

圖5 對τ中節(jié)點總數(shù)量的調(diào)度性能變化情況

圖6 本調(diào)度算法的計算時間與任務(wù)內(nèi)節(jié)點總數(shù)量的關(guān)系

5.1.1 第一組實驗的任務(wù)集生成方法

步驟1：隨機(jī)地將任務(wù)逐個加入任務(wù)集中；

將U*從1增加至8，步長設(shè)為0.4，因此實驗的任務(wù)集數(shù)量為18 000。

5.1.2 第二組實驗的任務(wù)集生成方法

設(shè)置m=8、Nmax=10、p為變量因子，生成1 000個任務(wù)集，步驟如下：

步驟1：使用上述參數(shù)生成m個任務(wù)的任務(wù)集；

步驟2：如果任務(wù)集的Usys大于m，則忽略該任務(wù)集并返回步驟1；

步驟3：采用此時的任務(wù)集進(jìn)行實驗，然后向該任務(wù)集添加一個任務(wù)，并返回步驟2直至生成1 000個任務(wù)集。

對于節(jié)點間的邊，如果p=0，則沒有邊(不存在父線程)，此時任務(wù)內(nèi)的并行度為最大；如果p=1，每個節(jié)點均與其他節(jié)點連接，說明一個任務(wù)內(nèi)同時僅一個線程運行；隨著p值增加，每個DAG任務(wù)τi內(nèi)邊的數(shù)量增加，由此導(dǎo)致關(guān)鍵的執(zhí)行路徑Li變長，然后LUsys增加。

為了針對不同的任務(wù)內(nèi)并行度進(jìn)行仿真，在10個不同的p值下，進(jìn)行仿真實驗，p值從0.1增加至1，步長為0.1，共有10 000個仿真。

5.1.3 第三組實驗的任務(wù)集生成方法

第三組實驗采用第一組實驗的參數(shù)設(shè)置，將任務(wù)逐個加入任務(wù)集直至τ中節(jié)點數(shù)量達(dá)到給定的節(jié)點總數(shù)量，任務(wù)的節(jié)點數(shù)量范圍為[1，給定的總節(jié)點數(shù)量-τ中節(jié)點數(shù)量]。將節(jié)點總數(shù)量從10增加至100，p=0.5，U*=m/2。每個數(shù)據(jù)點包含1 000個仿真，共有10 000個仿真。

5.2 實驗結(jié)果與分析

從圖3中可看出，U*從1到5.8，本算法的檢測率遠(yuǎn)超過其他三個算法。將本算法與OPA基本算法相比，可看出本文細(xì)粒度的調(diào)度算法(線程為調(diào)度單位)明顯提高了調(diào)度算法的性能，同時本算法優(yōu)于兩個EDF的增強(qiáng)算法，可看出本算法中采用線程級調(diào)度、動態(tài)線程截止期等設(shè)計具有顯著的效果。

圖4所示為檢測率與p值的關(guān)系，p值增加引起每個DAG任務(wù)的邊數(shù)量增加，從而使得節(jié)點間依賴的關(guān)系度升高。從圖中可看出，線程級優(yōu)先級分配算法在p值較小時具有較好的性能，而當(dāng)p值為1時，本算法與基本OPA算法、C_task_EDF性能接近，此時一個DAG任務(wù)中所有節(jié)點均被連接，任務(wù)均為單線程任務(wù)。B_task_EDF的檢測率隨著p值的增加而降低，主要原因是該方法的調(diào)度性判定LUsys是否小于閾值m/(2m-1),隨著p值的增加，LUsys值升高，導(dǎo)致可調(diào)度性下降。

為了測試本算法對不同數(shù)量線程的性能，將線程數(shù)量設(shè)為因變量，統(tǒng)計系統(tǒng)檢測率的變化情況。圖5中可看出，節(jié)點數(shù)量較多時，本算法優(yōu)于其他三個算法。節(jié)點數(shù)量越多，本算法調(diào)節(jié)線程截止期的機(jī)會越多，因此可調(diào)度性越高。

圖6是本算法計算時間與任務(wù)內(nèi)節(jié)點數(shù)量的關(guān)系，可看出節(jié)點數(shù)量越高，算法的計算時間越高。雖然對于100個線程的任務(wù)，本算法的計算時間約為2.2 s，但是本算法將實時系統(tǒng)的檢測率提高到約60%。

6 結(jié) 語

現(xiàn)有實時系統(tǒng)調(diào)度算法將任務(wù)作為調(diào)度單位，嚴(yán)重限制了多線程任務(wù)的調(diào)度性能，并且已有的算法大多對一些經(jīng)典的調(diào)度算法進(jìn)行可調(diào)度性分析，以期通過優(yōu)化可調(diào)度性判定條件提高算法的可調(diào)度性。然而受限于原調(diào)度算法的性能限制，通過收緊可調(diào)度性判定條件所獲得的性能提升往往較為有限。本文提出了一種細(xì)粒度的線程級多處理器實時調(diào)度算法，并給出了詳細(xì)的可調(diào)度性分析，仿真實驗結(jié)果表明，本算法對于多線程任務(wù)的實時系統(tǒng)具有較好的性能，對高線程數(shù)量的任務(wù)具有明顯地優(yōu)勢。