高瑋軍 王 通

(蘭州理工大學計算機與通信學院 甘肅 蘭州 730050)

0 引 言

隨著半導體技術的高速發(fā)展，高性能實時系統(tǒng)的應用呈現(xiàn)出爆發(fā)式增長。在這種趨勢下，人們提出了幾種適用于實時系統(tǒng)的并行任務模型，以滿足實時系統(tǒng)對任務執(zhí)行時間的嚴苛要求。最初，Lakshmanan等[1]提出了fork/join模型。在該模型中，任務由交替執(zhí)行的并行段和順序段組成，所有的并行段擁有相同的并行度。隨后，同步并行任務模型的提出[2]，極大地提高了任務模型的靈活性。在同步并行任務模型中，連續(xù)的并行段取代了之前交替執(zhí)行的并行段和順序段。同時，每一個并行段的并行度不再受限。后來，DAG任務模型受到了越來越多研究者的關注。這是一種更加靈活的任務模型。在這種模型中，一個任務由一個DAG表示。由于DAG任務定義了線程級并行，使得優(yōu)先限制的粒度變得更小，進而體現(xiàn)出更好的靈活性。近年來，DAG任務模型被愈來愈多的大數(shù)據(jù)通用引擎使用 (例如，Apache Spark[3])，同時，在實時系統(tǒng)領域，DAG任務也發(fā)揮著越來越重要的作用。

在實時系統(tǒng)中，可調(diào)度性分析一直是一個關鍵性問題。通過可調(diào)度性分析，推出一個可調(diào)度性測試算法，如果任務集被可調(diào)度性測試算法判斷為不可調(diào)度的，那么系統(tǒng)會通過提高處理器計算速度或多分配處理器等方式使得任務集能在截止時間內(nèi)完成。因此可調(diào)度性測試算法的識別率直接影響系統(tǒng)資源利用率。然而過于樂觀的可調(diào)度性分析會使得原本不可調(diào)度的任務集錯誤地被判斷為可調(diào)度的，這會導致在實際情況中由于任務集未能在截止時間內(nèi)完成而破壞系統(tǒng)的實時性，進而產(chǎn)生災難性后果。因此提高可調(diào)度性測試算法的精確性顯得尤為重要。

針對DAG任務模型，Bonifaci等[4]通過分析全局EDF調(diào)度算法的加速界，提出了一種偽多項式時間的可調(diào)度性測試算法。以文獻[4]提出的理論為基礎，通過使用類似于文獻[5-6]提出的技術，Baruah[7]提出了一種適用于全局EDF調(diào)度算法的具有充分性的可調(diào)度性測試算法。Li等[8]證明了全局EDF調(diào)度算法下容量增長界為4-2/m，資源增長界為2-1/m。但是后來，Sun等[9]證明了在全局EDF調(diào)度算法下，當系統(tǒng)中的任務集由采用限制截止時間的DAG任務組成時，并不是在所有情況下都能求出一個固定的容量增長界。后來Qamhieh等[10]將并行粒度細化到線程級并行，通過分析線程執(zhí)行過程中的抖動窗口，提出了一種新的可調(diào)度性測試算法。同樣在線程級并行粒度下，Chwa等[11]通過分析線程的執(zhí)行區(qū)間，提出了一個具有必要性的可調(diào)度性測試算法。針對DAG任務模型，在線程級并行粒度下進行可調(diào)度性分析能夠有效地提高可調(diào)度性測試算法的效率，然而，目前的研究工作并未充分利用圖結(jié)構(gòu)，在分析任務間干擾和任務內(nèi)干擾時，存在過于悲觀或過于樂觀的估計干擾的問題。針對以上問題，我們提出了一個基于圖結(jié)構(gòu)的DAG任務全局EDF可調(diào)度性測試算法。

1 系統(tǒng)模型

定義1可調(diào)度性。當系統(tǒng)使用給定的調(diào)度策略時，對于一個任務集τ，其任意一個任務τk∈τ釋放的每一個作業(yè)都能在其截止時間內(nèi)完成時，稱這個任務集τ在給定的調(diào)度算法下是可調(diào)度的。

定義2EDF調(diào)度算法。最早截止時間優(yōu)先調(diào)度算法是一種固定作業(yè)優(yōu)先級調(diào)度算法。其優(yōu)先級取決于作業(yè)的絕對截止時間。絕對截止時間越小，優(yōu)先級越高。絕對截止時間等于作業(yè)釋放時間加相對截止時間。在該調(diào)度算法下，作業(yè)中的節(jié)點和作業(yè)保持相同的優(yōu)先級。對于全局EDF調(diào)度，系統(tǒng)會維護一個調(diào)度隊列，該隊列根據(jù)節(jié)點的絕對截止時間以非遞減方式排列，在每次調(diào)度時，選取前m個節(jié)點。

定義3帶入作業(yè)和體作業(yè)。對于區(qū)間[a,b)，若一個作業(yè)在時刻a之前被釋放，同時，其絕對截止時間在[a,b)內(nèi)，則該作業(yè)稱為帶入作業(yè)。若一個作業(yè)的釋放時間和絕對截止時間都在區(qū)間[a,b)內(nèi)，則稱該作業(yè)為體作業(yè)。

定義4運行窗口。線程的運行窗口是由線程的開始執(zhí)行時間和執(zhí)行結(jié)束時間確定的區(qū)間。

定義5最早開始時間和最遲開始時間。對于節(jié)點θk,v，其最早開始時間Ok,v是指，在一個能使用無限多個處理器的系統(tǒng)中，當所有節(jié)點在不受到干擾的情況下盡可能早地執(zhí)行完成時，θk,v開始執(zhí)行的時間。最遲完成時間Dk,v是指，在一個具有無限多個處理器的系統(tǒng)中，在不超過截止時間的條件下，所有節(jié)點都盡可能遲地完成執(zhí)行，此時，在保證θk,v的所有后驅(qū)節(jié)點都能剛好在絕對截止時間處完成的條件下，θk,v最遲完成執(zhí)行的時間[10]。根據(jù)定義可知，如果某些節(jié)點擁有相同的直接前驅(qū)節(jié)點和直接后繼節(jié)點，則它們具有相同的最早開始時間和最遲結(jié)束時間。Ok,v和Dk,v通過深度優(yōu)先遍歷的思想即可求出，如算法1和算法2所示[12]。

算法1Earliest start time (τk)

1 for everyθk,v∈Vk

2 procedurelocal_offset(θk,v)

3 ifθk,v是τk的源節(jié)點

4Ok,v=0

5 else

7 end if

8 end procedure

9 end for

算法2Latest deadline time(τk)

1 for everyθk,v∈Vk

2 procedurelocal_deadline(θk,v)

3 ifθk,v是τk的終節(jié)點

4Ok,v=0

5 else

7 end if

8 end procedure

9 end for

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

進行可調(diào)度性分析需要知道關于任務的三個重要指標：執(zhí)行時間、受到的干擾和截止時間。通過判斷執(zhí)行時間與任務受到的干擾之和與截止時間的大小關系，判斷任務的可調(diào)度性，進而判斷整個任務集的可調(diào)度性。由于截止時間是系統(tǒng)模型中的已知量，故下文著重分析執(zhí)行時間和任務受到的干擾。

2.1 執(zhí)行時間

(1)

(2)

根據(jù)式(1)和式(2)，可推導出任務集τ在全局EDF調(diào)度策略下是可調(diào)度的必要條件為[11]：

(3)

通過計算不等式左側(cè)的各項，即可對給定任務集τ的可調(diào)度性做出判斷。但是由于無法知道系統(tǒng)運行時的調(diào)度細節(jié)，所以不等式左側(cè)的兩項無法準確計算，因此，我們轉(zhuǎn)向去求它們的上界。通過求一個精確的上界，將這個必要條件轉(zhuǎn)換為一個可調(diào)度性測試算法。

在計算干擾的范圍時，使用工作負載進行計算。τi的工作負載Wi(a,b)表示在區(qū)間[a,b)內(nèi)，τi所有節(jié)點的執(zhí)行時間總和。

定義τi中節(jié)點θi,v的工作負載Wi,v(a,b)為θi,v在區(qū)間[a,b)內(nèi)執(zhí)行時間的總和。文獻[11]給出如下關系：

(4)

(5)

2.2 任務受到的干擾

按照干擾的來源不同，將任務受到的干擾分為任務間干擾和任務內(nèi)干擾

2.2.1任務間干擾

當任務τi對任務τk產(chǎn)生任務間干擾時，任務間干擾的總和一定小于等于τi中所有節(jié)點在區(qū)間[a,b)內(nèi)的工作負載之和。由于無法準確計算任務間干擾，通過計算工作負載，可求出任務間干擾的一個上界。

要使得τi對τk的任務間干擾最大，需要：(1)τi以其最小時間間隔Ti釋放作業(yè)。(2)τi釋放的其中一個作業(yè)的截止時間和τk釋放的作業(yè)的截止時間對齊。(3)τi釋放的作業(yè)的所有線程都執(zhí)行得盡可能遲 (不超過其截止時間)[11]。在這種釋放模式下，當區(qū)間[a,b)越大時，τi中運行窗口與[a,b)有重疊的節(jié)點就越多，即所產(chǎn)生的任務間干擾越大。對于被干擾的任務τk，區(qū)間[a,b)的最大長度為Dk，因此，我們考慮在長度為Dk的區(qū)間內(nèi)，τk所受到的任務間干擾。

算法3Carry in workload(τi,L)

1 for everyθi,v∈Vi

2 ifOi,v≥Di-Lthen

4 else

5 ifOi,vDi-L

7 end if

8 else

10 end if

11 end for

由于在最壞情況作業(yè)釋放模式下，只存在帶入作業(yè)和體作業(yè)[11]，因此，這兩種作業(yè)產(chǎn)生的干擾的總和即為任務間干擾。由此，可以得到τi的節(jié)點θi,v對τk的任務間干擾的上限為：

(6)

則τi對τk的任務間干擾的上界為：

(7)

2.2.2任務內(nèi)干擾

采用關鍵鏈路法對任務內(nèi)干擾進行分析。在關鍵鏈路法中，關鍵鏈路中的節(jié)點稱為關鍵節(jié)點，其他節(jié)點稱為非關鍵節(jié)點。由此，對任務內(nèi)干擾的分析就轉(zhuǎn)換為對關鍵節(jié)點所受到的來自非關鍵節(jié)點的干擾的分析。

由優(yōu)先限制的定義可知，能對關鍵節(jié)點θk,v產(chǎn)生干擾的只有那些可能和θk,v同時執(zhí)行的節(jié)點。這些節(jié)點的執(zhí)行會搶占本該由θk,v使用的處理器，從而使得θk,v被迫進行等待。這些有可能和θk,v同時執(zhí)行的節(jié)點稱為θk,v的兄弟節(jié)點，它們既不屬于θk,v的所有前驅(qū)節(jié)點組成的集合，也不屬于θk,v的所有后驅(qū)節(jié)點組成的集合[10]。通過分析θk,v與其兄弟節(jié)點在執(zhí)行窗口上的相對位置關系，即可近似確定θk,v所受到的干擾。

(8)

對每一個關鍵節(jié)點，計算其受到的來自兄弟節(jié)點的干擾便可得到τk的任務內(nèi)干擾。令τk的關鍵鏈路為λk，則τk的任務內(nèi)干擾的上界為：

(9)

3 可調(diào)度性測試

通過分析任務間干擾和任務內(nèi)干擾，將式(7)和式(9)代入式(5)即可推導出一個在全局EDF調(diào)度策略下針對DAG任務的可調(diào)度性測試算法：

即當系統(tǒng)中有m個相同的處理器時，在全局EDF調(diào)度算法下，如果一個任務集合τ是可調(diào)度的，那么對于任意一個任務τk∈τ必須滿足該不等式。

4 實 驗

為測試本文提出的可調(diào)度性測試算法的性能，設計如下實驗。

實驗中的參數(shù)設置：對于任務τi，其最小釋放周期Ti服從[800,1 000]內(nèi)的均勻分布，其相對截止時間Di服從[700,Ti]內(nèi)的均勻分布，其節(jié)點個數(shù)和單個節(jié)點的WCET服從[10,30]內(nèi)的均勻分布。

通過上述方法構(gòu)造4 000個任務集[11]，針對m取不同值的情況，對本文提出的可調(diào)度性測試算法(記為OUR)、文獻[11]提出的可調(diào)度性測試算法(Theorem 1，記為ORI)、文獻[14]中的可調(diào)度性測試算法(Theorem 4，記為ANA)以及文獻[4]中提出的可調(diào)度性測試算法 (Theorem 21，記為FEA) 進行對比測試。將識別率定義為可調(diào)度性測試算法判斷為可調(diào)度的任務集個數(shù)除以總?cè)蝿占瘮?shù)量的值。為模擬真實環(huán)境中的多核環(huán)境，分別取核數(shù)m=8、m=16和m=32進行測試[11]。從圖1、圖2和圖3中可以看出，OUR在糾正ORI的識別率后仍然體現(xiàn)出比ANA和FEA更高的識別率。另外，在m取不同值時，OUR始終體現(xiàn)出穩(wěn)定的高識別率，說明了OUR具有良好的伸縮性。當m=8時，令參數(shù)p從0.1取到0.9。當p越大時，任務的圖結(jié)構(gòu)中邊的數(shù)量越大，即優(yōu)先限制的程度越大。從圖1中可以看出，ORI、ANA和FEA總體表現(xiàn)平穩(wěn)，識別率分別維持在0.74、0.53和0.44左右。OUR呈現(xiàn)上升趨勢，整體上明顯優(yōu)于ANA和FEA。這是因為：① 在分析任務間干擾時，ORI過于樂觀地使用節(jié)點的最遲開始時間作為節(jié)點運行窗口的開始時刻，這使得節(jié)點的運行窗口的長度變成最小值，進而使得任務間干擾被縮小。由于在判斷一個任務能否在其截止時間內(nèi)完成時，任務受到的任務間干擾比任務內(nèi)干擾對判斷結(jié)果有著更大的影響，因此，當任務間干擾被過于樂觀地縮小后，被可調(diào)度性測試算法判斷為可調(diào)度的任務的數(shù)量會大幅提升。相反，OUR使用節(jié)點的最早開始時間作為節(jié)點運行窗口的起始時刻，使得節(jié)點的運行窗口的長度為最大值，這樣，在計算任務間干擾時，OUR始終計算出最壞情況下任務所受到的任務間干擾。實驗發(fā)現(xiàn)，在絕大多數(shù)情況下，節(jié)點的WCET能夠完全轉(zhuǎn)換為任務間干擾。② 在分析任務內(nèi)干擾時，ORI采用的方法是，任務中所有節(jié)點的WCET之和減去關鍵鏈路的長度。這種方法的缺點是：在計算任務內(nèi)干擾時，沒有考慮圖結(jié)構(gòu)對任務內(nèi)干擾的直接影響。另外，隨著p的增大，關鍵鏈路的長度不會產(chǎn)生大幅變化。相反，通過分析圖結(jié)構(gòu)可知，在OUR中，隨著p的增大，每個關鍵節(jié)點的兄弟節(jié)點的數(shù)量下降，即關鍵節(jié)點受到來自兄弟節(jié)點的干擾變小，進而使得任務內(nèi)干擾變小。對于ANA和FEA，由于二者在判斷任務的可調(diào)度性時對任務的關鍵鏈路的長度有較強的依賴關系。所以，當關鍵鏈路的長度相對穩(wěn)定時，可調(diào)度性測試算法的識別率也相對穩(wěn)定。由于對節(jié)點執(zhí)行窗口進行改進和對圖結(jié)構(gòu)的充分利用，使得OUR體現(xiàn)出較高的識別率。

圖1 可調(diào)度性測試結(jié)果(m=8)

圖2 可調(diào)度性測試結(jié)果(m=16)

圖3 可調(diào)度性測試結(jié)果(m=32)

定義ORI的識別率減去OUR的識別率為糾正率。實驗數(shù)據(jù)顯示，當p=0.1時，OUR的識別率最小，為50.2%；ORI的識別率為72.1%，此時糾正率為21.9%。隨著p的增大，OUR的識別率不斷提高，糾正率逐漸降低。當p=0.9時，OUR的識別率最大，為71.8%；ORI的識別率為74.7%，此時糾正率為2.95%。m=16和m=32的情況和m=8的情況類似，不再贅述。

5 結(jié) 語

本文對全局EDF調(diào)度策略下DAG任務的可調(diào)度性進行研究，通過修正任務節(jié)點的執(zhí)行窗口，考慮任務的DAG結(jié)構(gòu)特征，提出一種對任務間干擾和任務內(nèi)干擾具有更高計算精度的可調(diào)度性測試算法，在保證算法具有較高識別率的同時，使可調(diào)度性測試結(jié)果更加符合實際情況。實驗結(jié)果表明，本文方法是行之有效的。下一步的工作是將基于容量增長界的方法和基于圖結(jié)構(gòu)的方法相結(jié)合，提出性能更好的可調(diào)度性測試算法。