基于圖結構的DAG任務可調度性分析

高瑋軍 王 通

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

0 引 言

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

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

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

1 系統模型

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

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

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

定義4運行窗口。線程的運行窗口是由線程的開始執行時間和執行結束時間確定的區間。

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

算法1Earliest start time (τk)

1 for everyθk,v∈Vk

2 procedurelocal_offset(θk,v)

3 ifθk,v是τk的源節點

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的終節點

4Ok,v=0

5 else

7 end if

8 end procedure

9 end for

2 可調度性分析

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

2.1 執行時間

(1)

(2)

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

(3)

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

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

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

(4)

(5)

2.2 任務受到的干擾

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

2.2.1任務間干擾

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

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

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

(6)

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

(7)

2.2.2任務內干擾

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

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

(8)

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

(9)

3 可調度性測試

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

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

4 實 驗

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

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

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

圖1 可調度性測試結果(m=8)

圖2 可調度性測試結果(m=16)

圖3 可調度性測試結果(m=32)

定義ORI的識別率減去OUR的識別率為糾正率。實驗數據顯示，當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 結 語

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