面向遠洋測量艦船的任務內部調度算法

張大銘

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

0 引 言

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

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

對于在線調度算法，Liu等[3]提出了一種基于任務緊急程度的最早截止時間先執行（EDF）的調度算法。基于 EDF 算法，Moser等[4 - 5]設計出了懶惰調度算法（LSA）并證明了對給定的時間和資源約束，如果供能變化規律完全已知，則LSA能夠實現最小的任務延誤率（DMR），即理論最優值。然而，這些調度方法都是粗粒度的調度方法，即不管發生什么情況，一旦一個任務開始執行，就必須執行到最后結束為止。這給系統帶來了很大的資源浪費，導致了較高的任務延誤率。

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

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

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

1 研究動機和設計挑戰

1.1 研究動機

圖 1給出了本文提出算法的設計動機實例。資源供應曲線在該例子中給出。選擇4個任務調度進行調度。其中，任務1和任務2是周期性的任務，即它們的開始時間和截止時間都是固定的。任務3是一個非周期性的任務，即需要在一段時間內被執行，但是沒有固定的開始時間。任務4是一各突發性緊急任務，即該任務的開始時間和截止時間是預先未知的。一旦緊急突發性任務出現，它就具有最高優先級需要立刻被執行。這對系統的任務延誤率影響很大。因此，調度算法在設計時必須謹慎對待這一類任務。此外，白色的任務為原子任務，這說明在它們在執行的過程中不可拆分。灰色的為非原子任務，即它們在執行過程中可以被拆分。

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

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

1.2 設計挑戰

設計這樣的調度算法，面臨如下挑戰：

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

2）對于資源感知的調度算法，如何同時考慮資源應變化和緊急任務？

3）怎樣提高緊急任務預測的準確性？

2 系統建模

2.1 調度模型參數

對于任務調度問題，主要針對一個時間段內的調度。每個時間段持續時間為T，該時間段包含M個時間片段，時間片段是最小不可分的任務調度單元，每個時間片段持續時間為t。因此，有

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

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

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

由于所有正在執行的硬件資源的需求百分比之和應滿足系統總的硬件資源限制，則有

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

給定上述的參數和相應的變量，該調度問題可以用如下的關系式來表示：設計目標是找到一種最優的調度方案{xi（m）}（m∈[1,M]），使其能夠最小化天氣測量系統中某一個具體的中繼衛星上的任務延誤率（DMR）。

2.2 可調度性分析

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

在一段時間內的第m個時間片段上的資源和硬件供應約束（Es（m）和Hs（m））可以表示為

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

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

否則，該調度問題為不可調度問題，能夠根據式（5）-式（9）來估計最優的任務延誤率。

3 調度算法設計

3.1 調度算法設計框圖

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

圖2 本文提出的調度算法設計框圖Fig.2 Design diagram of the proposed scheduling algorithm

3.2 觸發機制設計

基于任務特征，時間狀態和實際的資源供應情況，資源感知的任務內部調度算法在以下兩類情況下執行：

1）任務變化

①一個新的任務（例如緊急任務）進入調度隊列；

②一個調度隊列中的任務到了它最晚執行時間；

③一個任務執行完畢；

2）資源供應變化

①資源供應增加，可以讓調度隊列中的一個或多個任務開始執行；

②資源供應減少，正在執行的一個或多個任務需要停止。

3.3 預測和負載匹配算法設計

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

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

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

4 實驗分析

4.1 試驗設置

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

4.2 實驗評估

基于系統建模和硬件測試，比較傳統基于最早截止時間原則的任務間調度（EDF），傳統任務內部調度（Intra）以及本文提出的調度方法（Proposed）。

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

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

表1 調度模型參數Tab.1 Parameters of scheduling model

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

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

5 結 語

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

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