高利用率集合Sporadic實(shí)時(shí)任務(wù)調(diào)度方法研究

黃姝娟，肖 鋒，曹子建

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算法實(shí)現(xiàn)

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

6 結(jié) 束 語(yǔ)

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