黃姝娟，肖 鋒，曹子建

(西安工業(yè)大學(xué)計算機與工程學(xué)院 西安 710021)

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

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

1 Sporadic實時系統(tǒng)任務(wù)調(diào)度模型

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

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

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

由以上可知，實時系統(tǒng)中的周期任務(wù)具有4個重要屬性：發(fā)布時間ri、 時限di、 最壞執(zhí)行時間ei和周期pi。

2 相關(guān)定義、定理和結(jié)論

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

3 高利用率任務(wù)集合

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

圖1 GEDF算法執(zhí)行12個時間片結(jié)果

圖2 EDF-fm算法任務(wù)分配的份額

圖3 EDF-os算法任務(wù)分配的份額

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

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

EDF-fm算法任務(wù)對應(yīng)的job比例矩陣為：

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

這兩種算法在執(zhí)行階段，遷移任務(wù)要比非遷移任務(wù)優(yōu)先級高，而當(dāng)某處理器執(zhí)行兩個遷移任務(wù)時，該處理器為非第一次分配處理器的遷移任務(wù)優(yōu)先級最高。

EDF-os算法分配給任務(wù)對應(yīng)的份額矩陣為：

EDF-os算法任務(wù)對應(yīng)的job比例矩陣為：EDF-fm和EDF-os具體執(zhí)行結(jié)果如圖4和圖5所示。

圖4 EDF-fm算法執(zhí)行12個時間片結(jié)果

圖5 EDF-os算法執(zhí)行12個時間片結(jié)果

EDF-MSTL算法任務(wù)對應(yīng)的job比例矩陣為：

圖6 EDF-MSTL算法執(zhí)行12個時間片結(jié)果

4 算法實現(xiàn)

EDF-MSTL調(diào)度方法描述如下：

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

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

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

圖7 EDF-MSTL計算任務(wù)份額的流程圖

5 實驗結(jié)果

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

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

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

圖8 3種算法任務(wù)遷移度

圖9 3種算法的任務(wù)分割度

6 結(jié) 束 語

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