面向物聯(lián)網(wǎng)終端的任務(wù)相關(guān)性調(diào)度策略

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

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

1 引言

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

對于考慮任務(wù)相關(guān)性的任務(wù)調(diào)度，目前已經(jīng)有一些研究成果。Geng提出了一種結(jié)合任務(wù)之間相關(guān)性和依賴性的調(diào)度方案，以相關(guān)約束和依賴約束為條件設(shè)計(jì)了禁忌搜索擴(kuò)展算法來縮短任務(wù)完成時(shí)間[7]。Wu 等人提出一種在多媒體云計(jì)算平臺(tái)中的數(shù)據(jù)動(dòng)態(tài)調(diào)度方法，利用動(dòng)態(tài)任務(wù)之間存在的數(shù)據(jù)依賴性確定優(yōu)先級來提高調(diào)度性能[8]。Boyer等人提出應(yīng)用在分布式系統(tǒng)中任務(wù)調(diào)度算法，該調(diào)度利用隨機(jī)排序技術(shù)搜索最佳時(shí)間表用以估計(jì)遷移任務(wù)執(zhí)行時(shí)間，同時(shí)考慮了任務(wù)間的相關(guān)性進(jìn)行平衡負(fù)載的任務(wù)遷移，減小了時(shí)間估計(jì)中的不確定性[9]。Zotkiewicz等人提出一種在數(shù)據(jù)中心使用的調(diào)度方法，利用任務(wù)間相互依賴性動(dòng)態(tài)調(diào)度工作流，達(dá)成了降低服務(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ū)動(dòng)的調(diào)度方案，通過盡可能將具有相關(guān)性的任務(wù)數(shù)據(jù)放在同個(gè)計(jì)算節(jié)點(diǎn)來解決在大數(shù)據(jù)處理過程中產(chǎn)生過多數(shù)據(jù)遷移的問題[12]。丁男等人提出了一種多核系統(tǒng)中基于數(shù)據(jù)依賴性的調(diào)度算法，文中主要思路是將所有計(jì)算型任務(wù)通過評價(jià)函數(shù)量化它們相關(guān)性的大小，然后通過將相關(guān)性強(qiáng)的任務(wù)分配到同一個(gè)核內(nèi)，避免了過多核間通信造成的時(shí)間開銷，達(dá)到降低任務(wù)調(diào)度長度，提高實(shí)時(shí)性的目的[13]。這兩篇文獻(xiàn)的主要成果是根據(jù)任務(wù)的相關(guān)性，在空間上進(jìn)行處理，將相關(guān)性強(qiáng)的任務(wù)放在同個(gè)計(jì)算區(qū)域，減少任務(wù)處理過程中不同計(jì)算區(qū)域間的可能產(chǎn)生的通信開銷，但并沒有在同個(gè)節(jié)點(diǎn)中利用相關(guān)性從時(shí)間上進(jìn)行任務(wù)執(zhí)行順序的處理。黃姝娟等人針對有相關(guān)關(guān)系的周期任務(wù)提出了基于ST（Simple-Tree）的調(diào)度模型和可延遲時(shí)間越短越優(yōu)先調(diào)度方法，提高了核利用率[14]，但缺少對具有相關(guān)性的非周期任務(wù)的處理。

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

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

2.1 任務(wù)模型

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

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

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

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

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

在進(jìn)行任務(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é)點(diǎn)到F節(jié)點(diǎn)擁有最多任務(wù)節(jié)點(diǎn)數(shù)的路徑Dmax，如果有多條最長路徑則選取其中節(jié)點(diǎn)度數(shù)最少的路徑。m的值為找到的第一個(gè)Dmax中包含任務(wù)節(jié)點(diǎn)數(shù)。

（2）從圖D中刪除Dmax所包含節(jié)點(diǎn)及邊，然后按照步驟（1）的規(guī)則繼續(xù)尋找擁有最多任務(wù)節(jié)點(diǎn)的路徑Dmax，重復(fù)本步驟直到Dmax中只包含孤立任務(wù)。此時(shí)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)性強(qiáng)度的任務(wù)劃分函數(shù)如式（2）所示：

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

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

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

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

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

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

以圖1所示任務(wù)相關(guān)性描述圖為例，演示任務(wù)劃分過程。圖1 中任務(wù)節(jié)點(diǎn)數(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é)點(diǎn)數(shù)最多路徑(a5,a6,a7)=Dmax。接著從圖2（b）中刪除(a5,a6,a7)，余下的圖如圖2（c）所示，由于其中僅包含孤立任務(wù)，結(jié)束尋找Dmax的步驟，此時(shí)n=2 。由于輸入任務(wù)數(shù)量Ntask=10，根據(jù)式（1）可知，當(dāng)n×m=8

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

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

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

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

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

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

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

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

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

系統(tǒng)的優(yōu)先級因子矩陣Φ是調(diào)度的唯一依據(jù)。通過式（4）可以發(fā)現(xiàn)，系統(tǒng)運(yùn)行過程中父優(yōu)先級因子和子優(yōu)先級因子都是依賴于任務(wù)時(shí)限和任務(wù)等待時(shí)間。為了在運(yùn)行過程中根據(jù)任務(wù)相關(guān)性動(dòng)態(tài)改變優(yōu)先級，系統(tǒng)在每一個(gè)任務(wù)執(zhí)行完畢后輸出一個(gè)相關(guān)性增量矩陣ΔΦ，利用ΔΦ疊加到任務(wù)優(yōu)先級因子矩陣Φ上的方式進(jìn)行優(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ù)值可確定兩個(gè)任務(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)性信息矩陣后，可以計(jì)算該任務(wù)的增量因子。

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

（2）根據(jù)任務(wù)相關(guān)性描述圖，求得各任務(wù)節(jié)點(diǎn)距離任務(wù)完成節(jié)點(diǎn)F所需要經(jīng)過的最大節(jié)點(diǎn)數(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ù)的增量因子后，將每個(gè)任務(wù)的增量因子按任務(wù)位置排列為矩陣形式就得到了系統(tǒng)優(yōu)先級因子增量矩陣。

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

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

圖4 增量矩陣作用流程圖

在物聯(lián)網(wǎng)終端中各項(xiàng)任務(wù)按周期性可分為周期任務(wù)和非周期任務(wù)[15]。周期任務(wù)在系統(tǒng)啟動(dòng)之后會(huì)按照規(guī)定的周期周而復(fù)始地運(yùn)行下去，如環(huán)境數(shù)據(jù)周期采集、定時(shí)上傳監(jiān)控?cái)?shù)據(jù)等[16]。非周期任務(wù)則是不能提前預(yù)計(jì)到達(dá)時(shí)間的任務(wù)，這類任務(wù)對實(shí)時(shí)性的要求一般都更高，在任務(wù)到達(dá)時(shí)需要快速響應(yīng)，否則可能造成難以預(yù)料的后果[17]。當(dāng)非周期任務(wù)具有任務(wù)相關(guān)性時(shí)，影響其響應(yīng)時(shí)間的不但與它達(dá)到的時(shí)刻有關(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ù)，則以上文所述算法進(jìn)行調(diào)度。否則找到Vp,q的前驅(qū)任務(wù)集是任務(wù)相關(guān)性描述圖中所有可以通過有向邊到達(dá)Vp,q的任務(wù)節(jié)點(diǎn)集合，如圖1中的任務(wù)a7的前驅(qū)任務(wù)集然后將Vp,q與一起組成一個(gè)臨時(shí)作業(yè)輪詢組。

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

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

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

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

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

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

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

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

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

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

1.BEGIN：

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

3.WHILE（1）

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

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

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

7.END IF

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

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

10.IF（GroupEnd）//判斷當(dāng)前組是否完畢

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

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

13.RETURN TaskNum；

14.END IF

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

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

17.RETURN TaskNum；

18.END IF

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

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

21.END IF

22.END WHILE

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

4 仿真驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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