張大銘

(北京宇航系統(tǒng)工程研究所，北京 100084)

0 引 言

由于各個國家國土覆蓋面積有限，建立在國家內(nèi)部的地面測量和通信站難以滿足全球性科學(xué)監(jiān)測和通信的需求。為此，越來越多的國家采用遠洋測量艦船來實現(xiàn)在大洋等難以觸及的海域設(shè)立測量通信點的目的。遠洋測量艦船覆蓋范圍廣、靈活性強，是國家內(nèi)陸測量和通信站的有效補充，被廣泛應(yīng)用在測量勘探、飛行器間信息通信和數(shù)據(jù)傳輸、中繼等方面，例如我國投入使用的“遠望”系列測量船等。然而，隨著測量任務(wù)的增多，數(shù)據(jù)通信量的加大，傳輸碼率的與日俱增，在遠洋測量艦船上有限的電子設(shè)備處理和通信硬件資源受限的條件下，很多傳統(tǒng)的、邏輯簡單數(shù)據(jù)通信和處理任務(wù)調(diào)度算法已經(jīng)不能適應(yīng)未來的應(yīng)用需求。為了解決這一問題，研究人員開發(fā)出很多種任務(wù)調(diào)度的算法。這些算法大體可以分為離線和在線調(diào)度兩類。

離線調(diào)度的算法通常使用歷史資源數(shù)據(jù)，同時假設(shè)這些任務(wù)有著不變的屬性（例如，到來時間，截止時間，執(zhí)行時間和資源占用情況等）。Kansal等[1]提出一種在不同資源模式下進行周期性切換的離線調(diào)度方法。Audet等[2]給出一種基于資源占用的、針對周期性任務(wù)的靜態(tài)調(diào)度器。以上 2 種典型的靜態(tài)調(diào)度算法都沒有考慮資源供應(yīng)和任務(wù)執(zhí)行的變化。這一點限制了這兩類調(diào)度算法的使用范圍。

對于在線調(diào)度算法，Liu等[3]提出了一種基于任務(wù)緊急程度的最早截止時間先執(zhí)行（EDF）的調(diào)度算法?；?EDF 算法，Moser等[4 - 5]設(shè)計出了懶惰調(diào)度算法（LSA）并證明了對給定的時間和資源約束，如果供能變化規(guī)律完全已知，則LSA能夠?qū)崿F(xiàn)最小的任務(wù)延誤率（DMR），即理論最優(yōu)值。然而，這些調(diào)度方法都是粗粒度的調(diào)度方法，即不管發(fā)生什么情況，一旦一個任務(wù)開始執(zhí)行，就必須執(zhí)行到最后結(jié)束為止。這給系統(tǒng)帶來了很大的資源浪費，導(dǎo)致了較高的任務(wù)延誤率。

最近一段時間，Zhang等[6]設(shè)計了一種任務(wù)內(nèi)部調(diào)度方法，即任務(wù)在執(zhí)行的過程中可以被中斷并在之后繼續(xù)執(zhí)行。該方法調(diào)度的粒度更細，因此也更加靈活。這樣，任務(wù)延誤率（DMR）也能夠有效得到改善。但是，并不是所有的任務(wù)都可以在執(zhí)行過程中被切分。原子任務(wù)是不可拆分的，需要一次性地連續(xù)執(zhí)行完。此外，突發(fā)性任務(wù)也沒有在該算法中被考慮。

為了進一步減低任務(wù)延誤率，本文針對遠洋測量艦船電子設(shè)備進行數(shù)據(jù)通信和處理時存在的突發(fā)性，周期性和非周期性 3 種任務(wù)，提出了基于資源感知的任務(wù)內(nèi)部調(diào)度算法，其中原子和非原子任務(wù)都被考慮到算法之中。

本文面向遠洋測量艦船應(yīng)用提出了基于資源感知的任務(wù)內(nèi)部調(diào)度算法，在算法設(shè)計之前，首先對遠洋測量艦船數(shù)據(jù)處理和通信任務(wù)的特性進行建模，然后分析了任務(wù)的可調(diào)度性問題；在設(shè)計的調(diào)度算法中，首先針對突發(fā)性、周期性和非周期性幾類任務(wù)分別進行調(diào)度點選取。接著供能變化規(guī)律和遙測任務(wù)特性設(shè)計供能預(yù)測模型和負(fù)載匹配算法，計算任務(wù)的實時優(yōu)先級。最后基于優(yōu)先級選擇任務(wù)執(zhí)行順序。

1 研究動機和設(shè)計挑戰(zhàn)

1.1 研究動機

圖 1給出了本文提出算法的設(shè)計動機實例。資源供應(yīng)曲線在該例子中給出。選擇4個任務(wù)調(diào)度進行調(diào)度。其中，任務(wù)1和任務(wù)2是周期性的任務(wù)，即它們的開始時間和截止時間都是固定的。任務(wù)3是一個非周期性的任務(wù)，即需要在一段時間內(nèi)被執(zhí)行，但是沒有固定的開始時間。任務(wù)4是一各突發(fā)性緊急任務(wù)，即該任務(wù)的開始時間和截止時間是預(yù)先未知的。一旦緊急突發(fā)性任務(wù)出現(xiàn)，它就具有最高優(yōu)先級需要立刻被執(zhí)行。這對系統(tǒng)的任務(wù)延誤率影響很大。因此，調(diào)度算法在設(shè)計時必須謹(jǐn)慎對待這一類任務(wù)。此外，白色的任務(wù)為原子任務(wù)，這說明在它們在執(zhí)行的過程中不可拆分?；疑臑榉窃尤蝿?wù)，即它們在執(zhí)行過程中可以被拆分。

圖1 提出本文算法的設(shè)計動機的實例Fig.1 Example of the design motivation for the proposed algorithm

從圖1可以看出，如果沒有針對資源供應(yīng)和緊急任務(wù)預(yù)測的步驟，則資源從t0-t1時間段會被浪費。但是資源在t1-t2時間段非常有限，傳統(tǒng)的任務(wù)間調(diào)度方法不能滿足突發(fā)性任務(wù)和其他正在執(zhí)行的原子任務(wù)的執(zhí)行能耗需求。因此，包括緊急任務(wù)在內(nèi)的幾個任務(wù)最終都錯過了截止時間，導(dǎo)致系統(tǒng)的任務(wù)延誤率很高。相反地，本文提出的調(diào)度算法能夠同時考慮資源供應(yīng)和任務(wù)的不同類型。這樣，更多的任務(wù)在t0-t1這個資源供應(yīng)充足的時間被執(zhí)行。由于在t1時刻資源供應(yīng)突然減少，本文提出的調(diào)度算法及時停止了周期性任務(wù)（任務(wù)1和任務(wù)2）。這樣，積極任務(wù)（任務(wù)4）就可以在其截止時間到來前按時完成。之后，被中斷的 2 個任務(wù)繼續(xù)完成。最終，與傳統(tǒng)的任務(wù)間調(diào)度相比，采用本算法的系統(tǒng)任務(wù)延誤率就得到了有效地降低。這個例子說明，本文提出的面向遠洋測量船應(yīng)用的基于資源感知的任務(wù)內(nèi)部調(diào)度算法能夠有效地實現(xiàn)復(fù)雜任務(wù)的調(diào)度。

1.2 設(shè)計挑戰(zhàn)

設(shè)計這樣的調(diào)度算法，面臨如下挑戰(zhàn)：

1）對于非原子任務(wù)，什么時候停止執(zhí)行一個任務(wù)而開始執(zhí)行另一個？算法的設(shè)計復(fù)雜度很高。

2）對于資源感知的調(diào)度算法，如何同時考慮資源應(yīng)變化和緊急任務(wù)？

3）怎樣提高緊急任務(wù)預(yù)測的準(zhǔn)確性？

2 系統(tǒng)建模

2.1 調(diào)度模型參數(shù)

對于任務(wù)調(diào)度問題，主要針對一個時間段內(nèi)的調(diào)度。每個時間段持續(xù)時間為T，該時間段包含M個時間片段，時間片段是最小不可分的任務(wù)調(diào)度單元，每個時間片段持續(xù)時間為t。因此，有

每個任務(wù)有8個參數(shù)，一共有N個任務(wù)。Di任務(wù)i的截止時間。Ti和Ni分別是任務(wù)i在一段時間內(nèi)一次執(zhí)行所需的時間和執(zhí)行次數(shù)。這說明一些任務(wù)在這段時間內(nèi)可能會執(zhí)行不止一次（Ni≥1）。Pi任務(wù)i的執(zhí)行功耗。Si任務(wù)i執(zhí)行所需的硬件資源百分比。如果任務(wù)i為原子任務(wù)，則Ai=1; 如果任務(wù)i為非原子任務(wù)，則Ai=0; Bi是任務(wù)i的類型。當(dāng)任務(wù)i為周期性任務(wù)時，Bi=1；當(dāng)任務(wù)i為非周期任務(wù)時，Bi=2；當(dāng)任務(wù)為緊急任務(wù)時，Bi=3。Wi是任務(wù)i的權(quán)重。它代表了該任務(wù)的重要性。

系統(tǒng)一共包含4個參數(shù)。T和t分別是任務(wù)執(zhí)行的周期和時間片段。Ps（t）在第m個時間片段的供能功率。TS是總的硬件資源，歸一化后該參數(shù)的值為1。

任務(wù)調(diào)度的變量定義如下。xi（m）是一個獨立變量，它表示任務(wù)i在第m個時間片段的執(zhí)行狀態(tài)。如果該任務(wù)在執(zhí)行，則xi（m）=1。如果該任務(wù)沒有被執(zhí)行，則 xi（m）=0。

由于所有正在執(zhí)行的硬件資源的需求百分比之和應(yīng)滿足系統(tǒng)總的硬件資源限制，則有

ri（m）是一個獨立變量，它表示任務(wù)i在第m個時間片段的剩余執(zhí)行時間，有

給定上述的參數(shù)和相應(yīng)的變量，該調(diào)度問題可以用如下的關(guān)系式來表示：設(shè)計目標(biāo)是找到一種最優(yōu)的調(diào)度方案{xi（m）}（m∈[1,M]），使其能夠最小化天氣測量系統(tǒng)中某一個具體的中繼衛(wèi)星上的任務(wù)延誤率（DMR）。

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

一般而言，如果所有任務(wù)在有限的約束條件（比如，硬件資源，資源供應(yīng)等）下，都能夠在它們的截止時間到來之前被執(zhí)行完，則該調(diào)度問題是可調(diào)度的；否則，該調(diào)度問題不可調(diào)度，在這種情況下，就存在一個理論最優(yōu)的任務(wù)延誤率。對于本文的調(diào)度問題，可調(diào)度性可以用如下的公式去描述：

在一段時間內(nèi)的第m個時間片段上的資源和硬件供應(yīng)約束（Es（m）和Hs（m））可以表示為

在一段時間內(nèi)的第m個時間片段上的資源和硬件需求（Er（m） and Hr（m））可以表示為

其中：zi（m）為任務(wù)i的最晚開始時間（基于該任務(wù)的截止時間）。這樣，如果任務(wù)是可調(diào)度的，需要滿足下面的條件：

否則，該調(diào)度問題為不可調(diào)度問題，能夠根據(jù)式（5）-式（9）來估計最優(yōu)的任務(wù)延誤率。

3 調(diào)度算法設(shè)計

3.1 調(diào)度算法設(shè)計框圖

調(diào)度算法設(shè)計框圖如圖2所示。首先針對突發(fā)性、周期性和非周期性幾類任務(wù)分別進行調(diào)度點選取。接著供能變化規(guī)律和遙測任務(wù)特性設(shè)計供能預(yù)測模型和負(fù)載匹配算法，計算任務(wù)的實時優(yōu)先級。最后基于優(yōu)先級選擇任務(wù)執(zhí)行順序，得到具體的任務(wù)調(diào)度方案。

圖2 本文提出的調(diào)度算法設(shè)計框圖Fig.2 Design diagram of the proposed scheduling algorithm

3.2 觸發(fā)機制設(shè)計

基于任務(wù)特征，時間狀態(tài)和實際的資源供應(yīng)情況，資源感知的任務(wù)內(nèi)部調(diào)度算法在以下兩類情況下執(zhí)行：

1）任務(wù)變化

①一個新的任務(wù)（例如緊急任務(wù)）進入調(diào)度隊列；

②一個調(diào)度隊列中的任務(wù)到了它最晚執(zhí)行時間；

③一個任務(wù)執(zhí)行完畢；

2）資源供應(yīng)變化

①資源供應(yīng)增加，可以讓調(diào)度隊列中的一個或多個任務(wù)開始執(zhí)行；

②資源供應(yīng)減少，正在執(zhí)行的一個或多個任務(wù)需要停止。

3.3 預(yù)測和負(fù)載匹配算法設(shè)計

對于資源供應(yīng)的預(yù)測，采用一個資源供應(yīng)情況移動平均法來估計資源供應(yīng)的曲線變化趨勢，這是因為該趨勢在遠洋測量艦船運行環(huán)境中有著較為穩(wěn)定的規(guī)律。首先，收集多年的運行環(huán)境資源供應(yīng)情況曲線。為了有效保存這些曲線，采用一個K均值的方法來對這些曲線進行壓縮。然后，實際的資源變化會與存儲在存儲單元中的最接近的歷史資源供應(yīng)曲線去比較，基于保存的曲線，可以獲取估計的下一個時間片段的資源值以及接下來一段時間內(nèi)的資源變化趨勢。

匹配算法來進行任務(wù)選擇的工作流程如圖3所示。首先，所有選中任務(wù)優(yōu)先級基于它們的特征，狀態(tài)和當(dāng)前估計的資源供應(yīng)情況計算得到。如果還有任務(wù)沒有進行判定，則當(dāng)前沒有判定的任務(wù)種優(yōu)先級最高的任務(wù)被選中，如果遠洋測量艦船硬件電子設(shè)備系統(tǒng)中還有足夠的資源來執(zhí)行該任務(wù)，則該任務(wù)在下一個時間片段到來時開始執(zhí)行。否則，該任務(wù)在本次調(diào)度判定中被放棄，不執(zhí)行。然后接著判定其他的任務(wù)。如果當(dāng)前所有的任務(wù)都已經(jīng)被判定，則算法流程結(jié)束。這樣，就得到了最終選擇出來的、要在下一個時間片段到來時開始執(zhí)行的任務(wù)。

圖3 負(fù)載匹配算法的工作流程Fig.3 Workflow of load-matching algorithm

4 實驗分析

4.1 試驗設(shè)置

選擇10～15種任務(wù)（例如，關(guān)鍵數(shù)據(jù)通信，數(shù)據(jù)加密和解密，遙測數(shù)據(jù)傳輸，圖像數(shù)據(jù)處理等）來進行調(diào)度實驗。這些任務(wù)分屬于3種類型（周期性，非周期性和突發(fā)性）。這些任務(wù)和衛(wèi)星系統(tǒng)的相關(guān)參數(shù)通過仿真和實際測試獲取。實際測試指的是基于遙測數(shù)據(jù)軟硬件分析以及實驗用天基系統(tǒng)部分硬件等效器分析得到的結(jié)果。本實驗中所采用的資源供應(yīng)數(shù)據(jù)采用的是某遠洋測量船工作運行數(shù)據(jù)庫中2014年的部分?jǐn)?shù)據(jù)。

4.2 實驗評估

基于系統(tǒng)建模和硬件測試，比較傳統(tǒng)基于最早截止時間原則的任務(wù)間調(diào)度（EDF），傳統(tǒng)任務(wù)內(nèi)部調(diào)度（Intra）以及本文提出的調(diào)度方法（Proposed）。

表2給出了 3 種調(diào)度方法的任務(wù)延誤率的比較結(jié)果。從表中我們可以看出，如果突發(fā)性任務(wù)比例不變，隨著非周期性任務(wù)比例的增加，任務(wù)內(nèi)部調(diào)度與任務(wù)間調(diào)度效果更好。這是因為同粗粒度的任務(wù)間調(diào)度相比，任務(wù)內(nèi)部調(diào)度是細粒度的調(diào)度，可以更加靈活地進行資源管理和非周期性任務(wù)執(zhí)行。如果非周期性任務(wù)比例不變，隨著突發(fā)性任務(wù)比例的增加，本文提出的調(diào)度算法更好。這是因為本文提出的算法基于資源預(yù)測情況考慮了緊急任務(wù)的優(yōu)先級和出現(xiàn)的概率。因此，延誤率最多可以降低31%。這說明本文提出的調(diào)度算法對于天基系統(tǒng)中中繼衛(wèi)星上的任務(wù)調(diào)度非常有效。

表3給出了 3 種調(diào)度方法總資源消耗的比較。從表中可以看出，能夠得出和表2類似的結(jié)論。這說明相比其他 2 種調(diào)度方法，本文提出的算法浪費的資源更少，資源利用率提高比率更高（最高可達22%）。

表1 調(diào)度模型參數(shù)Tab.1 Parameters of scheduling model

表2 任務(wù)延誤率的比較Tab.2 Comparison of deadline miss rates

表3 資源利用率的比較Tab.3 Comparison of resource utilization rates

5 結(jié) 語

本文提出了一種基于資源感知（Resource-aware）的任務(wù)內(nèi)部（Intra-task）調(diào)度設(shè)計方法來提高任務(wù)調(diào)度的有效性。與傳統(tǒng)的粗粒度的任務(wù)間調(diào)度算法不同，采用任務(wù)內(nèi)部調(diào)度方法，任務(wù)可以在執(zhí)行中進行被中斷。遠洋測量艦船通信和處理的數(shù)據(jù)仿真分析及模擬硬件的實驗結(jié)果表明，與EDF方式相比，采用本算法可以有效降低任務(wù)延誤率30%，提升資源利用效率20%。

針對未來的研究，會進一步嘗試探索長期任務(wù)調(diào)度的方法。另外，基于能量資源管理的約束也會納入我們的研究之中，以此來設(shè)計針對長期調(diào)度的、更為高效的調(diào)度算法。