高利用率集合Sporadic實時任務調度方法研究

黃姝娟，肖 鋒，曹子建

(西安工業大學計算機與工程學院 西安 710021)

當前嵌入式多核平臺對具有嚴格時間限制的復雜應用提供了強有力的計算執行能力[1]。然而隨著嵌入式系統復雜性的攀升，實時調度也更具挑戰性[2]。在嵌入式多核平臺下，大部分算法基于Partitioned[3]或Global[4-5]調度方法，近年來Semipartitioned[6-7]調度方法逐漸獲得大家的重視。該類調度算法吸取了前兩者的優點，即在Partitioned調度算法的基礎上允許少部分任務遷移，被建議用在支持暗含時限的軟實時Sporadic任務系統中[8]。此后，還被應用于混合關鍵系統中[9-12]。然而，無論哪種應用，該類調度算法始終要求在一定的時限延遲的基礎上進行討論，而且任務遷移僅在job的邊界上進行，否則系統開銷太大。但隨著當前多核能力的提高，嵌入式系統的集成度越來越高，導致高利用率的任務也越來越集中，系統運行的負荷增大，因此Semi-partitioned調度算法劃分方案的精確性以及減少遷移和系統運行開銷就成為研究熱點。

目前針對高利率集合的semi-partitioned調度算法，如EDF-fm[13](earliest-deadline- first-based fixed and migrating)和 EDF-os[14](earliest-deadline-firstbased optimal semi-partitioned)，都存在遷移次數較多和上下文切換開銷較大的問題。本文在這兩種調度算法的基礎上，提出一種基于最少遷移度和分割度(earliest-deadline-first-based migrating and splitting tasks least, EDF-MSTL)的調度方法，旨在提高系統效率的同時，減少分割任務的數量和不必要的遷移和任務切換開銷。

1 Sporadic實時系統任務調度模型

假設一個實時系統 τ由n個周期性任務組成，記為 τ ={τ1,τ2,···,τn}。每個周期任務都包含4個參數。即 τi(ri,ei,pi,di)(1≤i≤n)， 其中ri表示發布時刻(release time)，即處理器核響應的時刻，ei表示任務Ti最壞情況下的執行時間(worst-case execution time, WCET），pi是 τi的 周 期 時 間，di表 示 時 限(deadline)，ei≤di≤pi。 若di=pi，稱該系統為隱含時限系統(implicit deadlines)，將其任務稱為隱含時限任務。如果di＜pi，稱該系統為包含時限系統(constrained deadline system)，將其任務稱為包含時限任務。如果兩者沒有強制性的約束條件則稱為任意時限系統(arbitrary deadline system)。用τi(ri,ei,pi,di)表示包含或任意時限系統， τi(ri,ei,pi)表示暗含時限系統。τi的 第j(j≥1)個 job，用Ji,j表示。一個任務的第一個job可以在任何時刻被發布。將Ji,j的發布時間記為ri,j， 將其絕對時限di,j定 義為ri,j+di，Ji,j的 執行時間記為ei,j。

Sporadic任務模型指n個重復發生的任務τ={τ1,τ2,···,τn}， 每個 τi具 有3個參數特征：ei(ei≥0)指示WCET；周期pi＞ei， 指示一個 τi連續兩次job之間的最小間隔。時限di≥ei， 指示τi的每個job在它發布之后到其完成時的最大時間間隔。τi是順序執行的，在同一個時間只有一個job在執行。Sporadic任務模型與周期模型不同之處在于兩個連續job發布的時間間隔不固定，其中最小的時間間隔成為該任務的周期。周期型任務模型可以視為Sporadic任務模型的一個特殊情況，即該任務中連續job發布是由固定pi時間單元分割的。本文著重討論隱含時限的周期任務和Sporadic任務都存在的系統。

多核模型：P={P1,P2,···,PM}為含有M個具有相同處理能力的處理器集合。在某個時間段內，分配到某個處理器Pm上 的任務 τi的 第j次job被激活，那么在該處理器上執行該任務的第j次job的時間片段記為Ti,j,m。

由以上可知，實時系統中的周期任務具有4個重要屬性：發布時間ri、 時限di、 最壞執行時間ei和周期pi。

2 相關定義、定理和結論

定義5 如果存在高利用率系統SH，在某種調度算法S下，定義該系統遷移度 migrat_λs為所有任務需要遷移的次數之和與所有任務利用率因子總和的比值。遷移度越小說明需要遷移的次數也越少，系統遷移開銷也就越少。定義該系統任務的分割度 split_λs為被分割的任務數量與系統任務總數量的比值。任務分割度越少，說明需要被遷移的任務數量越少，系統的執行效率就越好。

3 高利用率任務集合

將具有6個暗含時限的實時周期任務 τ1(4,6)、τ2(2,3)、 τ3(5,6)、 τ4(2,3)、 τ5(1,2)、 τ6(2,3)分配到4個處理器上，從0時刻發布，按照GEDF調度方法會得到調度圖序列如圖1所示?？梢钥闯?， τ2和 τ4在3個處理器上來回遷移， τ5也在兩個處理器上遷移， τ3和 τ6仍然有丟失時限發生?？梢钥闯鲞@種調度遷移開銷太大且仍有時限丟失現象。而semipartitioned算法將調度過程分為兩個階段：離線分配階段和執行階段。在分配階段只允許少部分任務為遷移任務，其他任務不允許遷移。EDF-fm算法、EDF-os算法和EDF-MSTL算法區別在于離線分配階段：EDF-fm算法類似深度優先分配，即將一個處理器份額全部占用完之后再分配下一個處理器，如圖2所示，所以任務最多在兩個處理器上遷移。EDF-os算法類似廣度優先遍歷，先將任務按照利用率從高到低降序排列，然后將和處理器數量相同的任務依次分配到處理器上作為非遷移任務，再從第一個處理器上依次分配該處理器的剩余份額，如圖3所示。

圖1 GEDF算法執行12個時間片結果

圖2 EDF-fm算法任務分配的份額

圖3 EDF-os算法任務分配的份額

這兩種算法中的遷移任務都會按照一定的比例將不同數量的job分配到指定的處理器上，比例計算方法為：

式中，fi,j為第i個任務分配到第j個處理上job數量的比例；si,j為該第i個任務在第j個處理器上獲得的份額。本例中EDF-fm算法分配給任務對應的份額矩陣為：

EDF-fm算法任務對應的job比例矩陣為：

從這里可以看到τ2(2,3)被分配到處理器P1和P2上，分配的job比例為1∶1；那么調度時就會將奇數項job配到P1，偶數項job分配到P2。τ3(5,6)在P2和P3分配的job的比例為4∶1，那么5個job中就有一個job被分配到P3處理器上。 τ5(1,2)在P3和P4處理器上job分配的比例為1∶2。同理，可以得到EDF-os算法的分配份額和任務job的執行比例。

這兩種算法在執行階段，遷移任務要比非遷移任務優先級高，而當某處理器執行兩個遷移任務時，該處理器為非第一次分配處理器的遷移任務優先級最高。

EDF-os算法分配給任務對應的份額矩陣為：

EDF-os算法任務對應的job比例矩陣為：EDF-fm和EDF-os具體執行結果如圖4和圖5所示。

圖4 EDF-fm算法執行12個時間片結果

圖5 EDF-os算法執行12個時間片結果

EDF-MSTL算法任務對應的job比例矩陣為：

圖6 EDF-MSTL算法執行12個時間片結果

4 算法實現

EDF-MSTL調度方法描述如下：

1) 首先將n個任務的利用率因子按照從大到小順序排列放入集合SH，m個處理器順序放入集合P中，初始化矩陣sn,n，si,i=ui，其他值為0。

2) 找到具有最小利用率因子的任務un，將其拆分為兩部分un=ui+uj， 其中ui與第一個具有最大利用率因子任務的利用率之和為1，即ui+u1=1，設置sn,k=ui，sn,n=uj，并將這兩個利用率因子從集合SH中刪除，如果uj為0，則也將其從SH中刪除，將處理器k從集合P中刪除。

3) 在剩下的SH集合中繼續重復步驟1)的工作，直到處理器集合為空為止。得到sn,m即為所分配份額。根據該份額通過式(1)計算fn,m。利用fn,m中的值，在調度執行過程中進行按比例分配相應的任務job，可以得到相依的執行序列。具體計算任務份額的算法流程圖如圖7所示。

圖7 EDF-MSTL計算任務份額的流程圖

5 實驗結果

本文測試的環境是在一個Intel?Core?2 Quad Q8400多核平臺上。分別采用EDF-fm，EDF-os，EDF-MSTL這3種調度方法進行比較。測試方法隨機產生1 000個任務集，每個任務集中產生50個參數不等的Sporadic軟實時周期任務，所有周期任務都滿足利用率大于0.5，執行時間小于時限，時限小于或等于周期。在整個仿真實驗過程中，為了描述算法之間的性能差異，采用多次模擬求平均值的方法得到某時間段內的系統吞吐率以及任務切換job數量所占總job數的比例，如表1所示。

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

另外，選擇對應這10個任務集的平均任務遷移度和任務分割度兩個方面進行性能對比。從表1、圖8和圖9可以看出，EDF-算法和EDF-MSTL算法在系統吞吐率、任務切換job數、任務遷移度和任務分割度方面，后者算法明顯占據優勢。

圖8 3種算法任務遷移度

圖9 3種算法的任務分割度

6 結 束 語

本文的目的是為了解決在嵌入式多核平臺下，任務全部屬于高利用率因子集合的軟實時系統中的實時周期任務的調度問題。在EDF-fm和EDF-os算法的基礎上，提供一種基于最少遷移度的多核實時調度方法，減少了現有技術中存在由于遷移帶來的過多開銷以及上下文切換次數，在任務量很大的情況下可以大大提高系統的整體效率。