面向遠(yuǎn)洋測(cè)量艦船的任務(wù)內(nèi)部調(diào)度算法

張大銘

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

0 引 言

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

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

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

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

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

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

1 研究動(dòng)機(jī)和設(shè)計(jì)挑戰(zhàn)

1.1 研究動(dòng)機(jī)

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

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

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

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

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

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

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

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

2 系統(tǒng)建模

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

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

每個(gè)任務(wù)有8個(gè)參數(shù)，一共有N個(gè)任務(wù)。Di任務(wù)i的截止時(shí)間。Ti和Ni分別是任務(wù)i在一段時(shí)間內(nèi)一次執(zhí)行所需的時(shí)間和執(zhí)行次數(shù)。這說(shuō)明一些任務(wù)在這段時(shí)間內(nèi)可能會(huì)執(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ù)時(shí)，Bi=1；當(dāng)任務(wù)i為非周期任務(wù)時(shí)，Bi=2；當(dāng)任務(wù)為緊急任務(wù)時(shí)，Bi=3。Wi是任務(wù)i的權(quán)重。它代表了該任務(wù)的重要性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）任務(wù)變化

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)分析

4.1 試驗(yàn)設(shè)置

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

4.2 實(shí)驗(yàn)評(píng)估

基于系統(tǒng)建模和硬件測(cè)試，比較傳統(tǒng)基于最早截止時(shí)間原則的任務(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)度效果更好。這是因?yàn)橥至６鹊娜蝿?wù)間調(diào)度相比，任務(wù)內(nèi)部調(diào)度是細(xì)粒度的調(diào)度，可以更加靈活地進(jìn)行資源管理和非周期性任務(wù)執(zhí)行。如果非周期性任務(wù)比例不變，隨著突發(fā)性任務(wù)比例的增加，本文提出的調(diào)度算法更好。這是因?yàn)楸疚奶岢龅乃惴ɑ谫Y源預(yù)測(cè)情況考慮了緊急任務(wù)的優(yōu)先級(jí)和出現(xiàn)的概率。因此，延誤率最多可以降低31%。這說(shuō)明本文提出的調(diào)度算法對(duì)于天基系統(tǒng)中中繼衛(wèi)星上的任務(wù)調(diào)度非常有效。

表3給出了 3 種調(diào)度方法總資源消耗的比較。從表中可以看出，能夠得出和表2類似的結(jié)論。這說(shuō)明相比其他 2 種調(diào)度方法，本文提出的算法浪費(fèi)的資源更少，資源利用率提高比率更高（最高可達(dá)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é) 語(yǔ)

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

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