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

重慶郵電大學(xué) 工業(yè)物聯(lián)網(wǎng)與網(wǎng)絡(luò)化控制教育部重點實驗室，重慶 400065

1 引言

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

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

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

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

2 基于任務(wù)相關(guān)性的任務(wù)模型

2.1 任務(wù)模型

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

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

圖1 樣例系統(tǒng)任務(wù)相關(guān)性描述圖

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

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

2.2 作業(yè)輪詢組任務(wù)劃分

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

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

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

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

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

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

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

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

在進行任務(wù)劃分的過程中，作業(yè)輪詢組分配狀態(tài)與已被分配任務(wù)數(shù)量的關(guān)系如表1所示。

表1 作業(yè)輪詢組分配狀態(tài)

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

（1）當還存在作業(yè)輪詢組的分配狀態(tài)為未分配時，將待分配任務(wù)劃分到這個未分配任務(wù)的作業(yè)輪詢組中。

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

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

圖2 任務(wù)劃分示意圖

結(jié)合式（2），計算任務(wù)與各作業(yè)輪詢組的相關(guān)性強度，并根據(jù)計算結(jié)果進行作業(yè)輪詢組任務(wù)劃分，其統(tǒng)計結(jié)果如表2所示。

表2 任務(wù)劃分結(jié)果

2.3 作業(yè)輪詢組優(yōu)先級管理

作業(yè)輪詢組以優(yōu)先級機制進行調(diào)度，系統(tǒng)通過對作業(yè)輪詢組的調(diào)度來進行功能表達。在作業(yè)輪詢組內(nèi)，同樣也以優(yōu)先級為依據(jù)對組內(nèi)任務(wù)進行調(diào)度，為描述方便，以父優(yōu)先級因子表示作業(yè)輪詢組的優(yōu)先級因子，子優(yōu)先級因子表示組內(nèi)任務(wù)的優(yōu)先級因子。在作業(yè)輪詢組中的任務(wù)被劃分完畢后，包含最多m個任務(wù)的第x個作業(yè)輪詢組的父優(yōu)先級因子?x表示為：

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

3 基于任務(wù)相關(guān)性的調(diào)度策略

3.1 基于任務(wù)相關(guān)性的動態(tài)調(diào)度算法

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

系統(tǒng)的優(yōu)先級因子矩陣Φ是調(diào)度的唯一依據(jù)。通過式（4）可以發(fā)現(xiàn)，系統(tǒng)運行過程中父優(yōu)先級因子和子優(yōu)先級因子都是依賴于任務(wù)時限和任務(wù)等待時間。為了在運行過程中根據(jù)任務(wù)相關(guān)性動態(tài)改變優(yōu)先級，系統(tǒng)在每一個任務(wù)執(zhí)行完畢后輸出一個相關(guān)性增量矩陣ΔΦ，利用ΔΦ疊加到任務(wù)優(yōu)先級因子矩陣Φ上的方式進行優(yōu)先級修改。ΔΦ的產(chǎn)生步驟如下：

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

表3 相關(guān)性信息矩陣數(shù)值含義

根據(jù)矩陣Ep,q在對應(yīng)任務(wù)位置處的數(shù)值可確定兩個任務(wù)之間的相關(guān)關(guān)系。矩陣Ep,q和任務(wù)相關(guān)性描述圖一一對應(yīng)。以圖1中的任務(wù)V1,1為例，該任務(wù)的相關(guān)性信息陣為：

矩陣E1,1說明了任務(wù)V1,2、V2,1和V3,1都與V1,1具有相關(guān)性，且V1,2、V2,1與V3,1是V1,1的后續(xù)任務(wù)。

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

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

（2）根據(jù)任務(wù)相關(guān)性描述圖，求得各任務(wù)節(jié)點距離任務(wù)完成節(jié)點F所需要經(jīng)過的最大節(jié)點數(shù)ε。例如將圖1中的任務(wù)分組并按ε大小排序后的任務(wù)相關(guān)性描述圖如圖3所示。

圖3 按ε 大小排序后的任務(wù)相關(guān)性描述圖

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

求得各任務(wù)的增量因子后，將每個任務(wù)的增量因子按任務(wù)位置排列為矩陣形式就得到了系統(tǒng)優(yōu)先級因子增量矩陣。

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

3.2 具有相關(guān)性的非周期任務(wù)優(yōu)化處理

圖4 增量矩陣作用流程圖

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

（1）對于任意非周期任務(wù)Vp,q，根據(jù)其相關(guān)性矩陣信息Ep,q確定該任務(wù)的相關(guān)性。

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

（3）系統(tǒng)中斷正在執(zhí)行的任務(wù)，對臨時作業(yè)輪詢組進行執(zhí)行，執(zhí)行完畢后臨時作業(yè)輪詢組解散，系統(tǒng)從被中斷處繼續(xù)執(zhí)行。

某系統(tǒng)已經(jīng)完成任務(wù)劃分工作，它的任務(wù)相關(guān)性如圖5 所示，其中V1,3為非周期任務(wù)。以該系統(tǒng)為例，對非周期任務(wù)優(yōu)化處理方案進行描述。

圖5 示例系統(tǒng)任務(wù)相關(guān)性描述圖

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

圖6 非周期任務(wù)處理示意圖

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

3.3 算法復(fù)雜度分析

在本節(jié)中將對前文提出的調(diào)度算法進行復(fù)雜度分析。算法的偽代碼如下：

輸入：任務(wù)相關(guān)性描述圖D

輸出：當前需要調(diào)度的任務(wù)號

1.BEGIN：

2.Ini（tV，D）；//根據(jù)相關(guān)性描述圖進行任務(wù)劃分

3.WHILE（1）

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

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

6.RETURN TemGroupTaskNum；//返回調(diào)度的任務(wù)號

7.END IF

8.IF（TASKEND）//判斷當前任務(wù)執(zhí)行是否完畢

9.UpdatePrio（r）；//任務(wù)執(zhí)行完畢后更新增量矩陣

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

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

12.FindGroupTask（）；//查找優(yōu)先級最高的作業(yè)輪詢組和任務(wù)

13.RETURN TaskNum；

14.END IF

15.ELSE//當前組未執(zhí)行完畢

16.FindTask（）；//查找當前組剩余優(yōu)先級最高的任務(wù)

17.RETURN TaskNum；

18.END IF

19.ELSE//當前任務(wù)還未執(zhí)行完畢

20.RETURN TaskNum；//直接返回當前任務(wù)

21.END IF

22.END WHILE

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

4 仿真驗證

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

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

表4 預(yù)配置任務(wù)集屬性表

任務(wù)集執(zhí)行時間仿真結(jié)果如圖7 所示，其中橫坐標表示任務(wù)相關(guān)性描述圖中與S、F節(jié)點無關(guān)的有向邊U數(shù)量的多少，該參數(shù)體現(xiàn)了系統(tǒng)中任務(wù)相關(guān)性的強弱。

圖7 任務(wù)集執(zhí)行時間

由圖7 可以看出在任務(wù)圖中有向邊數(shù)量為0，即所有任務(wù)均為孤立任務(wù)時，EDF 調(diào)度和RR 調(diào)度均會優(yōu)于本文所提策略。在本文所提策略中，任務(wù)間不存在相關(guān)性時，增量矩陣為0 矩陣，在調(diào)度階段仍然會花費時間去搜尋查找就緒任務(wù)的關(guān)聯(lián)關(guān)系，這會產(chǎn)生一定的時間浪費。而隨著任務(wù)圖中有向邊數(shù)量的增加，任務(wù)相關(guān)性逐漸加強，EDF 調(diào)度和RR 調(diào)度執(zhí)行作業(yè)集的時間會逐漸增多，而本文所提策略的執(zhí)行時間幾乎不變，在任務(wù)圖有向邊數(shù)量超過3時，本文所提策略已經(jīng)優(yōu)于EDF調(diào)度和RR調(diào)度。

任務(wù)調(diào)度失敗次數(shù)仿真結(jié)果如圖8 所示。橫坐標為任務(wù)完成數(shù)量，為了保證仿真結(jié)果的有效性，在本次仿真中所使用任務(wù)集的任務(wù)圖有向邊數(shù)量被固定為7?？v坐標為任務(wù)進行過程中調(diào)度失敗的次數(shù)，為因前驅(qū)任務(wù)尚未執(zhí)行就對后繼任務(wù)進行調(diào)度引發(fā)調(diào)度失敗的次數(shù)，該指標顯示了調(diào)度在具有相關(guān)性的任務(wù)環(huán)境下的可靠性。

圖8 任務(wù)調(diào)度失敗次數(shù)

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

對于非周期任務(wù)響應(yīng)時間的仿真方案為，分別將表4中不同的任務(wù)設(shè)置為非周期任務(wù)，在任務(wù)集執(zhí)行過程中對比不同調(diào)度下非周期任務(wù)的響應(yīng)時間。為了保證隨機性，對于非周期任務(wù)，它們的到達時間將會在[100，1 000]之間隨機產(chǎn)生。三種調(diào)度非周期任務(wù)平均響應(yīng)時間如圖9所示。

圖9 非周期任務(wù)平均響應(yīng)時間

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

5 結(jié)束語

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