面向物聯網終端的任務相關性調度策略

向 敏，戴柯宇，周 恩，劉 榆，雷儒杰

重慶郵電大學 工業物聯網與網絡化控制教育部重點實驗室，重慶 400065

1 引言

物聯網作為新一代信息技術，可以廣泛地應用于各個領域[1-3]。在物聯網終端應用領域廣，場景多，主要進行的工作大多利用RFID、信號采集、傳感器等技術獲取各類數據，然后通過通信技術與云端相連，根據具體的應用需求進行數據匯報或根據云端指令做出相應控制動作[4-5]。因此，物聯網終端軟件中的許多任務之間都存在一定的相關性，如果任務所依賴的前驅任務沒有被執行，那么調度該任務會產生額外的等待開銷甚至死鎖，這將對系統整體實時性和穩定性產生極大影響[6]。如何動態地安排這些具有相關性的任務，使CPU 能夠根據相關性進行任務調度，對系統實時性和穩定性具有重要意義。

對于考慮任務相關性的任務調度，目前已經有一些研究成果。Geng提出了一種結合任務之間相關性和依賴性的調度方案，以相關約束和依賴約束為條件設計了禁忌搜索擴展算法來縮短任務完成時間[7]。Wu 等人提出一種在多媒體云計算平臺中的數據動態調度方法，利用動態任務之間存在的數據依賴性確定優先級來提高調度性能[8]。Boyer等人提出應用在分布式系統中任務調度算法，該調度利用隨機排序技術搜索最佳時間表用以估計遷移任務執行時間，同時考慮了任務間的相關性進行平衡負載的任務遷移，減小了時間估計中的不確定性[9]。Zotkiewicz等人提出一種在數據中心使用的調度方法，利用任務間相互依賴性動態調度工作流，達成了降低服務器能耗的目的[10]。李文君等人提出一種考慮數據關聯性的調度算法，在可重構系統中協調內部通信數量，減少了CPU 和FPGA 之間的通信開銷[11]。

Wang 等人提出了一種數據依賴性驅動的調度方案，通過盡可能將具有相關性的任務數據放在同個計算節點來解決在大數據處理過程中產生過多數據遷移的問題[12]。丁男等人提出了一種多核系統中基于數據依賴性的調度算法，文中主要思路是將所有計算型任務通過評價函數量化它們相關性的大小，然后通過將相關性強的任務分配到同一個核內，避免了過多核間通信造成的時間開銷，達到降低任務調度長度，提高實時性的目的[13]。這兩篇文獻的主要成果是根據任務的相關性，在空間上進行處理，將相關性強的任務放在同個計算區域，減少任務處理過程中不同計算區域間的可能產生的通信開銷，但并沒有在同個節點中利用相關性從時間上進行任務執行順序的處理。黃姝娟等人針對有相關關系的周期任務提出了基于ST（Simple-Tree）的調度模型和可延遲時間越短越優先調度方法，提高了核利用率[14]，但缺少對具有相關性的非周期任務的處理。

為此，提出面向物聯網終端軟件的任務調度策略，將具有相關性的任務劃分到一個作業輪詢組，以優先級因子矩陣作為調度憑據，通過優先級因子增量矩陣來動態修改各任務優先級，通過對作業輪詢組的調用完成需求功能，從時間上對任務執行順序進行安排，減少了任務集執行時間和調度失敗次數。對于非周期任務采用組成臨時作業輪詢組的優化處理方案，降低了實時性敏感非周期任務的響應時間。

2 基于任務相關性的任務模型

2.1 任務模型

為了對具有相關系的任務進行有效管理，終端軟件部分將邏輯相關的任務組成一個相對獨立的“作業輪詢組”，整個軟件實體由若干個作業輪詢組構成。同時為了能夠更加直觀地表現任務相關性，利用有向無環圖（DAG圖）對任務間的相關性進行描述。相關的具體定義描述如下。

定義1（任務相關性描述圖）使用DAG圖來描述任務相關性，一個任務相關性描述圖D={V,U}，其中V表示節點集合{S,a1,a2,a3,a4,…,F} 。為了便于在圖中對任務流進行更清晰的展示，引入邏輯節點S、F，這兩個節點不代表實體任務，僅表示邏輯上任務流的開始與結束。其中節點S表示邏輯開始，節點F邏輯結束。其他每個節點{a1,a2,a3,a4,…} 均表示一個實體任務。U?V×V表示有向邊集合，每條有向邊上的數字表示發出這條邊的節點的任務時限，兩個任務之間存在有向邊表示這兩個任務存在相關關系，且發出有向邊的任務為有向邊指向任務的前驅任務，后續任務只有在其前驅任務全部完成后才可執行。一個示例系統的任務相關性描述圖如圖1所示。

圖1 樣例系統任務相關性描述圖

如圖1中有向邊(a1,a2)表示任務a1是任務a2的前驅任務，任務a2是任務a1的后續任務，且a1的任務時限為t1。僅與S、F節點相連的節點任務為孤立任務，例如圖1中的任務a9和a10，孤立任務與其他任務之間無相關關系。

定義2（作業輪詢組）通過任務相關性描述圖，終端軟件部分組成n個作業輪詢組，每個作業輪詢組包含最多m個任務，將邏輯相關的任務放入一個組里，形成一條相對獨立的任務流。系統通過對作業輪詢組的調度來完成既定功能。作業輪詢組中的任務位置被排定后便不會更改，為了方便描述，文中用Vn,m來表示第n個作業輪詢組的第m個任務，其中，n=1,2,…，m=1,2,…。

2.2 作業輪詢組任務劃分

在進行任務調度之前，首先需要將具有相關性的任務預先劃分到同一個作業輪詢組中。在進行任務劃分的時候，如果區分顆粒太粗會造成過多任務被放入同一個作業輪詢組，使得該機制作用降低；如果區分顆粒太細則會產生過多的作業輪詢組消耗更多的內存空間。因此任務分組結果尤為重要。在此，提出作業輪詢組中任務劃分機制，為作業輪詢組安排合適的成員任務，以降低調度失敗任務切換次數。

在進行任務分組之前，首先需要根據輸入任務相關性描述圖確定最大作業輪詢組n和組內最大任務容量m的值。輸入任務相關性描述圖D，輸入任務數量Ntask，則n和m確定的步驟如下：

（1）從任務相關性描述圖D中找到從S節點到F節點擁有最多任務節點數的路徑Dmax，如果有多條最長路徑則選取其中節點度數最少的路徑。m的值為找到的第一個Dmax中包含任務節點數。

（2）從圖D中刪除Dmax所包含節點及邊，然后按照步驟（1）的規則繼續尋找擁有最多任務節點的路徑Dmax，重復本步驟直到Dmax中只包含孤立任務。此時n的值為找到路徑Dmax的數量。

（3）考慮到孤立任務數量不定，還需要判斷n×m與Ntask的大小關系，根據式（1）確定n的值：

式（1）中，ceil(x)表示取不小于x的最小整數，如ceil( 3.1)=ceil( 3.9)=4。

通過上述步驟完成n、m值的確定工作，之后開始將任務相關性描述圖中的任務按相關關系，劃分到作業輪詢組中。對于任意待分配任務Ve，描述該任務與任意作業輪詢組Gx的相關性強度的任務劃分函數如式（2）所示：

其中，R(Ve,Gx)代表任務Ve與作業輪詢組Gx的相關性強度；tj表示作業輪詢組Gx中第j個任務的任務時限，表示作業輪詢組Gx中第j個任務與待分配任務Ve是否存在相關關系，如果是該值為1，否則為0。式（2）表示，對于待分配任務Ve，與作業輪詢組的相關性強度取決這個作業輪詢組中與Ve存在相關性的任務個數和它們的任務時限。作業輪詢中存在越多與Ve具有相關性的任務，這些任務的時限越小，則Ve與這個作業輪詢的相關性越強。

在進行任務劃分的過程中，作業輪詢組分配狀態與已被分配任務數量的關系如表1所示。

表1 作業輪詢組分配狀態

對于還未分配到作業輪詢組的任務，首先利用式（2）求得該任務與每個作業輪詢組的相關性強度值，將該任務分配到相關性強度值最大的作業輪詢組內。如果有任務根據式（2）輸出的相關性強度全為0，則需要查詢所有作業輪詢組的分配狀態，并按照以下步驟完成該任務的劃分：

（1）當還存在作業輪詢組的分配狀態為未分配時，將待分配任務劃分到這個未分配任務的作業輪詢組中。

（2）當所有作業輪詢組的分配狀態都為分配中或分配滿時，相關性強度全為0說明待分配任務與其他任務均沒有相關關系，屬于孤立任務，則將該任務隨機分配至還未滿的作業輪詢組中。

以圖1所示任務相關性描述圖為例，演示任務劃分過程。圖1 中任務節點數最多的路徑有兩條，分別是(a1,a2,a3,a4)和(a1,a5,a6,a7)，選擇其中度數更小的路徑(a1,a2,a3,a4)=Dmax，如圖2（a）中虛線所示，求得組內最大任務容量m=4。然后從圖1中刪除(a1,a2,a3,a4)，余下的圖如圖2（b）所示，從中找到任務節點數最多路徑(a5,a6,a7)=Dmax。接著從圖2（b）中刪除(a5,a6,a7)，余下的圖如圖2（c）所示，由于其中僅包含孤立任務，結束尋找Dmax的步驟，此時n=2 。由于輸入任務數量Ntask=10，根據式（1）可知，當n×m=8

圖2 任務劃分示意圖

結合式（2），計算任務與各作業輪詢組的相關性強度，并根據計算結果進行作業輪詢組任務劃分，其統計結果如表2所示。

表2 任務劃分結果

2.3 作業輪詢組優先級管理

作業輪詢組以優先級機制進行調度，系統通過對作業輪詢組的調度來進行功能表達。在作業輪詢組內，同樣也以優先級為依據對組內任務進行調度，為描述方便，以父優先級因子表示作業輪詢組的優先級因子，子優先級因子表示組內任務的優先級因子。在作業輪詢組中的任務被劃分完畢后，包含最多m個任務的第x個作業輪詢組的父優先級因子?x表示為：

其中，αx,j的取值為0或1，表示第x個作業輪詢組中的第j個位置是否已經被分配實體任務，如果該位置有實體任務則αx,j為1，否則為0；tx,j表示任務Vx,j的任務時限；wx,j表示任務Vx,j的等待時間，wx,j的初始值為1，如果任務處于就緒狀態而沒有被調度則等待時間會一直累加，直到任務被調度后恢復為初始值1。

3 基于任務相關性的調度策略

3.1 基于任務相關性的動態調度算法

利用上文提出的任務劃分機制將作業輪詢組成員安排完畢后，提出基于任務相關性的任務調度算法，算法的整體描述如下：通過任務時限確定父優先級因子和子優先級因子，依次選取當前父優先級因子最大的就緒作業輪詢組進行執行。每個作業輪詢組在執行完畢之后將失效，當前作業周期將不會再被調度，直到所有作業輪詢組都執行完畢，新周期開始時會將所有作業輪詢組狀態設置為就緒。在一個作業輪詢組被執行時，組內以任務為最小調度單位，總是執行當前優先級最高的就緒任務。每個任務執行完畢觸發一次調度計算，此時會根據任務就緒表生成一個優先級因子增量矩陣，通過增量矩陣動態改變父優先級因子和子優先級因子來達到使具有相關性任務快速完成的目的。

系統的優先級因子矩陣Φ是調度的唯一依據。通過式（4）可以發現，系統運行過程中父優先級因子和子優先級因子都是依賴于任務時限和任務等待時間。為了在運行過程中根據任務相關性動態改變優先級，系統在每一個任務執行完畢后輸出一個相關性增量矩陣ΔΦ，利用ΔΦ疊加到任務優先級因子矩陣Φ上的方式進行優先級修改。ΔΦ的產生步驟如下：

（1）對于系統中任意任務Vp,q可以根據任務相關性描述圖生成對應的相關性信息矩陣Ep,q，βi,j為Ep,q矩陣中第i行第j列的元素，βi,j數值與對應任務的相關性關系如表3所示。

表3 相關性信息矩陣數值含義

根據矩陣Ep,q在對應任務位置處的數值可確定兩個任務之間的相關關系。矩陣Ep,q和任務相關性描述圖一一對應。以圖1中的任務V1,1為例，該任務的相關性信息陣為：

矩陣E1,1說明了任務V1,2、V2,1和V3,1都與V1,1具有相關性，且V1,2、V2,1與V3,1是V1,1的后續任務。

在得到任務Vp,q的相關性信息矩陣后，可以計算該任務的增量因子。

由式（5）可知，任務的增量因子由該任務的后續任務的優先級因子和增量因子兩部分組成，如果任務處于一條相關任務流中，在進行任務的增量因子計算時，會將其后續任務的優先級因子疊加到該任務上，保證了前驅任務會獲得更高的優先級；如果該任務為孤立任務或該任務沒有后續任務，則求解的增量因子為0，不會改變優先級因子矩陣Φ中的數值。因為任務的增量因子與該任務的后續任務的增量因子有關，所以計算增量因子是一個從任務流末端向前遞歸的過程。

（2）根據任務相關性描述圖，求得各任務節點距離任務完成節點F所需要經過的最大節點數ε。例如將圖1中的任務分組并按ε大小排序后的任務相關性描述圖如圖3所示。

圖3 按ε 大小排序后的任務相關性描述圖

完成ε值的確定工作后，按ε從小到大的順序，利用式（5）遞歸求解各任務的增量因子。例如，對于圖3所示系統，首先求解ε=0 的任務V1,4、V2,3、V3,1、V3,2的增量因子，然后求解ε=1 的任務V1,3、V2,2、V2,4的增量因子，再求解ε=2 的任務V1,2、V2,1的增量因子，最后求解ε=3 的任務V1,1的增量因子。

求得各任務的增量因子后，將每個任務的增量因子按任務位置排列為矩陣形式就得到了系統優先級因子增量矩陣。

在任務的調度過程中，每次觸發任務切換時會從任務流末端開始計算就緒表中所有任務的增量因子進而形成優先級因子增量矩陣，然后將增量矩陣與優先級因子矩陣進行疊加，從而改變系統中各任務的優先級，讓前驅任務被優先調度，以保證后續任務的實時性，使一條任務流能更加高效地執行。增量矩陣ΔΦ的作用過程如圖4所示。

3.2 具有相關性的非周期任務優化處理

圖4 增量矩陣作用流程圖

在物聯網終端中各項任務按周期性可分為周期任務和非周期任務[15]。周期任務在系統啟動之后會按照規定的周期周而復始地運行下去，如環境數據周期采集、定時上傳監控數據等[16]。非周期任務則是不能提前預計到達時間的任務，這類任務對實時性的要求一般都更高，在任務到達時需要快速響應，否則可能造成難以預料的后果[17]。當非周期任務具有任務相關性時，影響其響應時間的不但與它達到的時刻有關，還與該非周期任務所依賴的前驅任務執行情況相關。針對非周期任務提出優化處理方案步驟如下：

（1）對于任意非周期任務Vp,q，根據其相關性矩陣信息Ep,q確定該任務的相關性。

（2）如果Ep,q=0，說明Vp,q是孤立任務，則以上文所述算法進行調度。否則找到Vp,q的前驅任務集是任務相關性描述圖中所有可以通過有向邊到達Vp,q的任務節點集合，如圖1中的任務a7的前驅任務集然后將Vp,q與一起組成一個臨時作業輪詢組。

（3）系統中斷正在執行的任務，對臨時作業輪詢組進行執行，執行完畢后臨時作業輪詢組解散，系統從被中斷處繼續執行。

某系統已經完成任務劃分工作，它的任務相關性如圖5 所示，其中V1,3為非周期任務。以該系統為例，對非周期任務優化處理方案進行描述。

圖5 示例系統任務相關性描述圖

如圖5所示，當具有相關性的非周期任務V1,3達到后，先計算增量矩陣用以更新優先級因子矩陣Φ，然后找到V1,3的前驅任務集{V1,1,V1,2,V2,1,V2,2,V2,3}，然后將前驅任務集與非周期任務V1,3一起建立一個臨時作業輪詢組。這個臨時作業輪詢組會中斷當前任務，獲得CPU使用權，在臨時作業輪詢組執行完畢之后再接著執行剛才被中斷的任務，與此同時，將V1*,3中所有任務狀態都置為失效。非周期任務處理過程如圖6所示。

圖6 非周期任務處理示意圖

特別地，如果當前因有多個非周期任務到達而產生多個臨時作業輪詢組，則利用式（4）來計算各個臨時作業輪詢組的優先級因子，判斷它們的執行順序，然后再以本節所述流程進行執行和返回。

3.3 算法復雜度分析

在本節中將對前文提出的調度算法進行復雜度分析。算法的偽代碼如下：

輸入：任務相關性描述圖D

輸出：當前需要調度的任務號

1.BEGIN：

2.Ini（tV，D）；//根據相關性描述圖進行任務劃分

3.WHILE（1）

4.IF（AperiodicTask）//判斷非周期任務是否到達

5.BuildTemGroup（）；//建立臨時作業輪詢組

6.RETURN TemGroupTaskNum；//返回調度的任務號

7.END IF

8.IF（TASKEND）//判斷當前任務執行是否完畢

9.UpdatePrio（r）；//任務執行完畢后更新增量矩陣

10.IF（GroupEnd）//判斷當前組是否完畢

11.IF（AllGroupEnd）//判斷一個輪詢周期是否完畢

12.FindGroupTask（）；//查找優先級最高的作業輪詢組和任務

13.RETURN TaskNum；

14.END IF

15.ELSE//當前組未執行完畢

16.FindTask（）；//查找當前組剩余優先級最高的任務

17.RETURN TaskNum；

18.END IF

19.ELSE//當前任務還未執行完畢

20.RETURN TaskNum；//直接返回當前任務

21.END IF

22.END WHILE

從偽代碼中易知：第2行任務劃分過程的時間復雜度為O(n×m)，由于任務劃分僅發生于系統初始化過程中，產生的時間影響可忽略；第9 行更新增量矩陣的時間復雜度為O(n×m)；第12 行查找優先級最高的作業輪詢組和任務的時間復雜度是O(n×m)；第16 行查找組內優先級最高的任務的時間復雜度是O(m)。綜合以上各部分復雜度，算法的總體時間復雜度為O(2 ×(n×m)+m)。

4 仿真驗證

本章中，通過仿真實驗來對本文所調度策略的有效性進行評估。為了體現一般性，實驗中使用的任務實例為實際應用中的數據采集終端，運行環境為32 位處理器，72 MHz 主頻。主要對比對象為典型動態調度最早時限優先調度（EDF）和應用在uCOS-Ⅲ、Linux2.6 中的時間片輪轉（RR）[18]。具體評價指標為任務集執行時間、任務調度失敗次數、非周期任務平均響應時間。

對任務集執行時間的評估方法為，將一個數據采集終端軟件任務進行任務劃分，然后執行5 000個周期，對比具有相關性任務數量不同的情況下任務集執行時間；對任務調度失敗次數的評估方法為，將任務集中具有相關性任務數量進行固定，對比執行任務數量不同的情況下調度失敗的次數。使用到的預配置任務集屬性如表4所示。

表4 預配置任務集屬性表

任務集執行時間仿真結果如圖7 所示，其中橫坐標表示任務相關性描述圖中與S、F節點無關的有向邊U數量的多少，該參數體現了系統中任務相關性的強弱。

圖7 任務集執行時間

由圖7 可以看出在任務圖中有向邊數量為0，即所有任務均為孤立任務時，EDF 調度和RR 調度均會優于本文所提策略。在本文所提策略中，任務間不存在相關性時，增量矩陣為0 矩陣，在調度階段仍然會花費時間去搜尋查找就緒任務的關聯關系，這會產生一定的時間浪費。而隨著任務圖中有向邊數量的增加，任務相關性逐漸加強，EDF 調度和RR 調度執行作業集的時間會逐漸增多，而本文所提策略的執行時間幾乎不變，在任務圖有向邊數量超過3時，本文所提策略已經優于EDF調度和RR調度。

任務調度失敗次數仿真結果如圖8 所示。橫坐標為任務完成數量，為了保證仿真結果的有效性，在本次仿真中所使用任務集的任務圖有向邊數量被固定為7?？v坐標為任務進行過程中調度失敗的次數，為因前驅任務尚未執行就對后繼任務進行調度引發調度失敗的次數，該指標顯示了調度在具有相關性的任務環境下的可靠性。

圖8 任務調度失敗次數

由圖8可以看出，在任務完成數量為1 000時，本文提出策略調度失敗次數少于EDF和RR調度，同時隨著任務完成數量的增加，本文所提策略的優勢更加明顯。這是因為本文所提策略在任務劃分階段就根據相關性對任務進行了處理，盡可能地保證了任務的后繼任務在其前驅任務全部完成之后才執行，有效地減少了任務調度失敗次數。而EDF僅以任務時限為調度依據，可能出現時限更短的后繼任務比時限稍長的前驅任務更優先調度而引起調度失敗。由于RR調度在每個時間片都可能引發調度，所以調度失敗的次數會更多。

對于非周期任務響應時間的仿真方案為，分別將表4中不同的任務設置為非周期任務，在任務集執行過程中對比不同調度下非周期任務的響應時間。為了保證隨機性，對于非周期任務，它們的到達時間將會在[100，1 000]之間隨機產生。三種調度非周期任務平均響應時間如圖9所示。

圖9 非周期任務平均響應時間

由圖9 可以看出，相較于其他兩種調度，本文所提出的調度策略能夠更及時地響應非周期任務，且隨著該非周期任務所需前驅任務的數量增加，本文所提策略優勢更加明顯。這是因為經過任務相關性處理，本文所提策略在非周期任務處于就緒表中的時候就提前將所需前驅任務優先級提高，同時列為單獨的一個作業輪詢組。這樣在非周期任務的前驅任務數量增加時，對響應時間的影響僅為增加前驅任務的執行時間。而對于其他兩種調度，根據執行時間或到達時間對非周期任務進行調度需要耗費一定時間，同時在前驅任務數量增加后，調度其所有前驅任務以確保非周期任務順利執行將會耗費更多的調度次數。

5 結束語

針對物聯網終端的應用場景多樣，任務之間存在相關性的情況，本文提出了一種基于任務相關性的調度策略。該策略在初始化過程中就對任務進行劃分，將相關性強的任務劃分為一個作業輪詢組。針對周期任務，通過增量矩陣動態改變任務優先級，讓任務總是能在其前驅任務完成之后再被調度，避免調度失敗產生額外的運行周期；針對時間敏感的非周期任務，通過建立臨時作業輪詢組，縮短其響應時間，提高系統實時性。該策略根據相關性動態地配置任務優先級，能夠在物聯網終端特別是應用場景復雜多變的可重構終端應用中發揮作用。