異構(gòu)系統(tǒng)雙關(guān)鍵級分布式功能的動態(tài)調(diào)度

劉樑驕　謝國琪　李仁發(fā)　楊　柳　劉　彥

1(湖南大學(xué)信息科學(xué)與工程學(xué)院　長沙　410082)2(嵌入式與網(wǎng)絡(luò)計算湖南省重點實驗室(湖南大學(xué))　長沙　410082)3　　　(湖南省發(fā)展和改革委員會　長沙　410004) (llj1984109@qq.com)

?

異構(gòu)系統(tǒng)雙關(guān)鍵級分布式功能的動態(tài)調(diào)度

劉樑驕1,2謝國琪1,2李仁發(fā)1,2楊柳3劉彥1,2

1(湖南大學(xué)信息科學(xué)與工程學(xué)院長沙410082)2(嵌入式與網(wǎng)絡(luò)計算湖南省重點實驗室(湖南大學(xué))長沙410082)3(湖南省發(fā)展和改革委員會長沙410004) (llj1984109@qq.com)

摘要異構(gòu)分布式嵌入式系統(tǒng)是由多種不同關(guān)鍵級功能組成的混合關(guān)鍵級系統(tǒng)，且每個功能又是由多個具有優(yōu)先級約束的任務(wù)組成的分布式功能.異構(gòu)分布式嵌入式系統(tǒng)的混合關(guān)鍵級調(diào)度在性能與時間約束上面臨嚴(yán)重的沖突.如何提高系統(tǒng)總體性能，并仍然確保高關(guān)鍵級功能的實時性，在性能與實時性上取得合理的權(quán)衡則成為研究的主要優(yōu)化問題.提出公平策略的動態(tài)雙關(guān)鍵級任務(wù)調(diào)度算法F_DDHEFT(fairness on dynamic dual-criticality heterogeneous earliest finish time)以提高系統(tǒng)的整體性能;提出關(guān)鍵級策略的動態(tài)雙關(guān)鍵級任務(wù)調(diào)度算法C_DDHEFT(criticality on dynamic dual-criticality heterogeneous earliest finish time) 以滿足高關(guān)鍵級功能的實時性;提出時限時距策略的動態(tài)雙關(guān)鍵級任務(wù)調(diào)度算法D_DDHEFT(deadline-span on dynamic dual-criticality heterogeneous earliest finish time)，在滿足高關(guān)鍵級功能實時性的基礎(chǔ)上，提高系統(tǒng)的整體性能，最終在性能與時間約束上取得合理的權(quán)衡.實例分析和實驗結(jié)果驗證了D_DDHEFT算法的優(yōu)越性.

關(guān)鍵詞異構(gòu)分布式嵌入式系統(tǒng);雙關(guān)鍵級；性能；實時；時限時距

新一代高端嵌入式系統(tǒng)是典型的異構(gòu)分布式嵌入式系統(tǒng).例如，汽車電子系統(tǒng)由100多個異構(gòu)ECU(electronic control unit)、各類傳感器、執(zhí)行器和網(wǎng)關(guān)等處理單元組成，并通過CAN(controller area network)，F(xiàn)lexRay，LIN(local interconnect network)，MOST(media oriented system transport)和以太網(wǎng)等多種異構(gòu)網(wǎng)絡(luò)總線互聯(lián)，系統(tǒng)體系結(jié)構(gòu)的異構(gòu)性日趨明顯[1-3].當(dāng)前，一輛豪華轎車至少包含70個ECU以及2 500個信號以完成各種復(fù)雜功能的執(zhí)行[4].與此同時，具有優(yōu)先級約束的分布式功能在任務(wù)數(shù)和復(fù)雜性上與日俱增.例如汽車電子系統(tǒng)中的線控剎車是典型的分布式主動安全功能，從感知數(shù)據(jù)開始到執(zhí)行剎車指令結(jié)束，該功能所包含的計算任務(wù)存在明顯的優(yōu)先級約束[5].整個過程需分配給5個ECU、1個傳感器和2個執(zhí)行器等處理單元.不同的任務(wù)之間產(chǎn)生不同的通信信號并被打包成消息在網(wǎng)絡(luò)總線上傳輸.

異構(gòu)分布式嵌入式系統(tǒng)體系結(jié)構(gòu)是一種典型的分布式集成體系結(jié)構(gòu)，這種結(jié)構(gòu)將多種安全與非安全關(guān)鍵功能集成到了同一個平臺，并由此在學(xué)術(shù)界和工業(yè)界引入了關(guān)鍵級與混合關(guān)鍵級系統(tǒng)的概念，并成為復(fù)雜嵌入式系統(tǒng)的主要研究熱點[6].“關(guān)鍵級”強(qiáng)調(diào)某個功能發(fā)生安全事故的嚴(yán)重性后果，以表示其重要程度，并經(jīng)過了第三方機(jī)構(gòu)的嚴(yán)格認(rèn)證.高關(guān)鍵級功能相比低關(guān)鍵級功能意味著前者在時間需求上要求更加嚴(yán)格苛刻，錯過高關(guān)鍵級功能的時隙將會造成嚴(yán)重的安全問題.關(guān)鍵級在汽車電子系統(tǒng)中用汽車安全完整性等級表示[7].道路車輛-功能安全標(biāo)準(zhǔn)規(guī)范“IS026262”對汽車電子系統(tǒng)中的功能從低到高劃分成A,B,C,D四個ASIL.其中，D為最高關(guān)鍵級，其安全性需求最為苛刻；A為最低等級，安全性需求最低.

任務(wù)調(diào)度是混合關(guān)鍵級系統(tǒng)的核心研究內(nèi)容.通過高效的任務(wù)調(diào)度算法，可充分利用異構(gòu)分布式嵌入式系統(tǒng)中的處理器和通信等資源以提高系統(tǒng)性能，但是面向具有不同關(guān)鍵級的分布式功能的調(diào)度卻面臨嚴(yán)峻的挑戰(zhàn).

首先，盡管混合關(guān)鍵級系統(tǒng)概念自誕生以來提出了眾多的調(diào)度理論與算法，但是大多方法都是基于周期任務(wù)模型或隨機(jī)任務(wù)模型，且都是從”任務(wù)級”的角度研究其調(diào)度問題[8-14].然而異構(gòu)分布式嵌入式系統(tǒng)中的分布式功能所包含的任務(wù)存在明顯的優(yōu)先級約束，傳統(tǒng)的”任務(wù)級”模型顯然無法精確描述任務(wù)之間的優(yōu)先級約束.如何從“功能級”的角度建立分布式的系統(tǒng)模型顯得至關(guān)重要.近年來相關(guān)學(xué)者針對汽車電子系統(tǒng)提出了時序鏈[15]、功能鏈[16]和任務(wù)鏈[17]等功能模型以適應(yīng)任務(wù)間的優(yōu)先級約束問題，但僅限于簡單的分布式功能.隨著功能的日益復(fù)雜化與并行化，迫切需要一種能夠更加精確反映功能特性的模型.在并行與分布式計算領(lǐng)域，有向無環(huán)圖(directed acyclic graph， DAG) 是一個能夠描述具有復(fù)雜的任務(wù)優(yōu)先級約束與蘊(yùn)含通信開銷的分布式功能的常用模型[18-19].

其次，異構(gòu)分布式嵌入式系統(tǒng)在性能與時間約束上面臨嚴(yán)重的沖突.若從系統(tǒng)的角度來看，降低整個系統(tǒng)的調(diào)度長度、提高系統(tǒng)性能是其主要目標(biāo).若從功能的角度來看，滿足其時間約束、確保實時性是其主要需求.然而，對于具有資源約束的大規(guī)模異構(gòu)分布式嵌入式系統(tǒng)，不可能滿足所有分布式功能的時間約束，因此滿足高關(guān)鍵級功能的時限、確保安全性則成為主要目標(biāo).在并行與分布式計算領(lǐng)域，通過公平調(diào)度多個分布式功能來降低系統(tǒng)的調(diào)度長度是一種可行的方法，但是應(yīng)用于異構(gòu)分布式嵌入式系統(tǒng)則會使得大量分布式功能(包括高關(guān)鍵級功能和低關(guān)鍵級功能)的時間約束無法滿足.

因此，如何提高系統(tǒng)的整體性能并確保高關(guān)鍵級功能的實時性則成為異構(gòu)分布式嵌入式系統(tǒng)的混合關(guān)鍵級任務(wù)調(diào)度需要優(yōu)化的主要問題.為此，本文旨在通過提出精確反映分布式功能的混合關(guān)鍵級系統(tǒng)模型，并在此基礎(chǔ)上提出優(yōu)化的任務(wù)調(diào)度算法，最小化系統(tǒng)性能與功能時限之間的沖突，在性能與實時性上取得合理的權(quán)衡.

1相關(guān)研究

由于公平性是提高并行與分布式系統(tǒng)性能的重要方法，而滿足高關(guān)鍵級分布式功能的時間約束則是混合關(guān)鍵級的主要研究內(nèi)容，因此本節(jié)將公平性和混合關(guān)鍵級的相關(guān)研究分別論述.

1.1公平性研究

針對單個分布式功能的DAG任務(wù)調(diào)度是研究多個分布式功能DAG調(diào)度的重要基礎(chǔ).異構(gòu)系統(tǒng)單DAG任務(wù)調(diào)度一般包含2個步驟：1)根據(jù)優(yōu)先級進(jìn)行任務(wù)排序;2)將任務(wù)分配到合適的處理器上.異構(gòu)分布式系統(tǒng)的DAG任務(wù)調(diào)度算法是一個典型的NP難問題，比較有名的算法有CPOP[18]，HEFT[18]，HSV[19]等.同單DAG任務(wù)調(diào)度一樣，異構(gòu)系統(tǒng)多DAG調(diào)度也包含任務(wù)優(yōu)先級排序和處理器分配2個步驟.文獻(xiàn)[20]提出了將多個DAG合成一個復(fù)合DAG后， 再利用諸如HEFT等經(jīng)典的單DAG調(diào)度算法調(diào)度.很明顯，合成方法沒有考慮公平性問題.同樣，先來先服務(wù)(first come first serve， FCFS)和及時服務(wù)(serve on time， SOT)也都不能體現(xiàn)公平性.

Zhao等人[21]首次指出了在多DAG調(diào)度中的公平性問題，并提出了slowdown驅(qū)動的多DAG靜態(tài)公平任務(wù)調(diào)度算法Fairness.我們也提出了考慮通信開銷的靜態(tài)調(diào)度算法[1].多分布式功能DAG動態(tài)調(diào)度更加符合現(xiàn)實需求.動態(tài)調(diào)度即可在任意時刻提交新的功能到系統(tǒng)中，目前主要有RANK_HYBD[22],OWM[23],FDWS[24]等算法.動態(tài)調(diào)度算法與靜態(tài)調(diào)度算法的主要區(qū)別在于前者在有新功能提交時，要判斷當(dāng)前處理器是否空閑以及如何實現(xiàn)公平性等問題.如果當(dāng)前處理器忙，OWM會繼續(xù)將任務(wù)保留在系統(tǒng)的公共就緒隊列中等待處理器空閑，以等待下一輪的分配.OWM的等待方式過于被動，F(xiàn)DWS則通過為每個處理器提供一個處理器等待隊列來實現(xiàn)任務(wù)的分配時隙并等待處理器空閑，以減少多次的就緒調(diào)度.

1.2混合關(guān)鍵級研究

2007年Vestal[8]在嵌入式實時系統(tǒng)領(lǐng)域頂級國際會議RTSS上首次提出了混合關(guān)鍵級系統(tǒng)的概念以及相應(yīng)的固定優(yōu)先級任務(wù)調(diào)度策略.從此混合關(guān)鍵級系統(tǒng)相關(guān)的基礎(chǔ)理論和調(diào)度問題迅速成為實時系統(tǒng)領(lǐng)域的熱點問題.混合關(guān)鍵級系統(tǒng)包括周期任務(wù)模型和隨機(jī)任務(wù)模型2個主要模型，調(diào)度策略則包括固定優(yōu)先級搶占式策略、固定優(yōu)先級非搶占式策略、動態(tài)優(yōu)先級策略等.由此可見，混合關(guān)鍵級系統(tǒng)的調(diào)度問題實際上是傳統(tǒng)實時系統(tǒng)在面臨多種關(guān)鍵級任務(wù)時的擴(kuò)展，因此改進(jìn)和擴(kuò)展的RM和EDF算法也成為混合關(guān)鍵級系統(tǒng)的主要調(diào)度方法[8-14].

早期的研究主要集中在單處理器調(diào)度，由于成本、功耗和性能等需求，基于多處理器或多核架構(gòu)的混合關(guān)鍵級調(diào)度成為近年來的研究熱點[25-26].分區(qū)調(diào)度和全局調(diào)度是這類架構(gòu)的2種主要調(diào)度算法.分區(qū)調(diào)度即通過時間分區(qū)的方式將任務(wù)靜態(tài)地分配到處理器核上，在任務(wù)分配給具體的處理器核以后，該任務(wù)只能在該處理器核上調(diào)度執(zhí)行，被搶占或被掛起以后也不能再遷移到其他處理器核上調(diào)度執(zhí)行.而全局調(diào)度策略可以將任務(wù)分配到任何處理器核上，并可在處理器之間遷移.需要指出的是，目前的混合關(guān)鍵級系統(tǒng)主要考慮雙關(guān)鍵級系統(tǒng)，即包括高關(guān)鍵級和低關(guān)鍵級，或者安全關(guān)鍵級或非安全關(guān)鍵級2種級別.高關(guān)鍵體現(xiàn)為功能或任務(wù)的強(qiáng)實時性，低關(guān)鍵級體現(xiàn)為軟實時性；而對于非關(guān)鍵級功能或任務(wù)，則無需關(guān)注其實時性需求.盡管雙關(guān)鍵級僅考慮2個關(guān)鍵級問題，但是其調(diào)度問題仍然是一件非常復(fù)雜的工作，許多存在的問題需要綜合權(quán)衡考慮，主要包括確保高關(guān)鍵級功能或任務(wù)的實時性、提高系統(tǒng)性能或資源利用率、處理器空閑時隙、系統(tǒng)關(guān)鍵級切換等問題.因此，本文也將雙關(guān)鍵級系統(tǒng)作為研究對象，從“功能級”的角度研究異構(gòu)分布式嵌入式系統(tǒng)的混合關(guān)鍵級調(diào)度問題.

近年來，具有優(yōu)先級約束任務(wù)的混合關(guān)鍵級功能的調(diào)度研究也取得一定進(jìn)展.將每個分布式功能抽象成DAG模型，文獻(xiàn)[27-30]提出了一系列的異構(gòu)分布式系統(tǒng)的混合關(guān)鍵級調(diào)度算法.文獻(xiàn)[27]中通過采用時間與空間分區(qū)實現(xiàn)功能的隔離.每一個實時功能運(yùn)行在獨(dú)立的時間分區(qū)，其中高關(guān)鍵級功能使用靜態(tài)循環(huán)調(diào)度算法，低關(guān)鍵級功能則使用固定優(yōu)先級搶占策略以滿足所有功能的時限.文獻(xiàn)[28]對文獻(xiàn)[27]的工作進(jìn)行了擴(kuò)展，考慮了不同關(guān)鍵級功能的分區(qū)共享問題.上述2項工作的主要問題在于忽略了任務(wù)之間的通信開銷.因此在文獻(xiàn)[29]考慮在處理器之間通過TTEthernet協(xié)議實現(xiàn)通信，但仍對通信開銷缺乏定量的分析.文獻(xiàn)[30]則著重考慮滿足硬實時功能的可調(diào)度性，并最大化軟實時功能的服務(wù)質(zhì)量.上述工作都基于如下前提：當(dāng)且僅當(dāng)系統(tǒng)有足夠的時間和空間分區(qū)，混合關(guān)鍵級功能才能集成到同一個平臺上來；其次，上述工作所采用的方法都是基于傳統(tǒng)混合關(guān)鍵級系統(tǒng)的調(diào)度理論，包括使用改進(jìn)的RM，EDF調(diào)度算法和分區(qū)調(diào)度機(jī)制等.盡管采用了DAG模型抽象了分布式功能，但并未充分利用異構(gòu)分布式系統(tǒng)中DAG模型的經(jīng)典理論與方法，無法體現(xiàn)異構(gòu)分布式嵌入式系統(tǒng)的分布式與并行化特征.

本文的主要目標(biāo)就是解決上述研究中面臨的一些問題，提出面向異構(gòu)分布式嵌入式系統(tǒng)的混合關(guān)鍵級模型，從“功能級”以及“并行與分布式計算”的角度來研究性能與時間約束權(quán)衡下的動態(tài)調(diào)度優(yōu)化問題.

2系統(tǒng)模型

以異構(gòu)分布式汽車電子系統(tǒng)為例，它由多個異構(gòu) ECU(不同供應(yīng)商提供的ECU在設(shè)計方法或硬件實現(xiàn)上不同)、傳感器和執(zhí)行器等處理設(shè)備組成，本文將這些處理單元統(tǒng)稱為處理器，并用集合P={p1，p2，…} 來表示.用CL={LC,HC}表示系統(tǒng)中的關(guān)鍵級層次，當(dāng)前混合關(guān)鍵級系統(tǒng)的研究也主要集中在雙關(guān)鍵級系統(tǒng)[8-14]，因此本文也基于雙關(guān)鍵級系統(tǒng)，將功能劃分為低關(guān)鍵級(lower-criticality,LC) 和高關(guān)鍵級(higher-criticality,HC)兩種，且滿足高關(guān)鍵級功能的實時性是必需的目標(biāo)，否則會造成嚴(yán)重的安全問題.

以汽車電子系統(tǒng)中的線控剎車功能為例，它的實現(xiàn)是由多個相互具有數(shù)據(jù)依賴的任務(wù)組成.當(dāng)駕駛者踩下剎車踏板時，首先同時對汽車當(dāng)前的運(yùn)行狀態(tài)和周圍的物理環(huán)境信息進(jìn)行采集，接著將接觸信號以電子形式傳輸至通過多種總線互連的ECU單元，ECU接收到信號并處理后，再傳送給其他ECU單元執(zhí)行并開啟楔軸承機(jī)械裝置，并以恰當(dāng)?shù)念l率對剎車執(zhí)行器發(fā)出指令啟動剎車信號，然后傳輸給執(zhí)行器執(zhí)行剎車動作.整個計算執(zhí)行和信號傳送需要在毫秒級內(nèi)完成[5].上述功能任務(wù)在不同處理器上執(zhí)行并產(chǎn)生大量的通信開銷，且這些功能任務(wù)又存在優(yōu)先級約束的依賴關(guān)系，它的實現(xiàn)需要通過總線網(wǎng)絡(luò)進(jìn)行交互和協(xié)作才能完成.因此可以用一個有向無環(huán)圖DAG來描述一個分布式功能[18-19]，這也是并行與分布式計算領(lǐng)域分布式功能的常用模型.在本文用Func={N,W,E,C,criticality,lower_bound,deadline,arrival_time,makespan}表示一個分布式功能.其中N={n1,n2,…}表示任務(wù)集合；由于處理器處理能力的異構(gòu)性，使得不同任務(wù)在不同的處理器計算時間不盡相同，因此定義W為一個|N|×|P|的矩陣，wi,k表示任務(wù)ni在處理器pk上的計算開銷；E={e1,2,e2,3,…,ei,j,…}描述為任務(wù)間的優(yōu)先級約束與數(shù)據(jù)依賴關(guān)系集合；本文假設(shè)處理器之間采用CAN總線型互聯(lián)，使用C={c1,2,c2,3,…,ci,j,…}描述具有數(shù)據(jù)依賴的任務(wù)之間的通信開銷集合，如果將這2個任務(wù)分配到同一個處理器上，則通信開銷為0.通信開銷的描述與經(jīng)典DAG模型一樣[18-19].由于處理器之間通過CAN，F(xiàn)lexRay，LIN，MOST等多種類型的網(wǎng)絡(luò)和網(wǎng)關(guān)實現(xiàn)互聯(lián)，不同總線的帶寬不盡相同，因此任務(wù)之間的通信開銷也不同，描述C={c1,2,c2,3,…,ci,j,…}為具有數(shù)據(jù)依賴的任務(wù)之間的通信開銷集合，如果將這2個任務(wù)分配到同一個處理器上，則通信開銷為0.pred(ni)表示任務(wù)ni的直接前驅(qū)任務(wù)集合；ind(ni)表示任務(wù)ni的入度，也就是其直接前驅(qū)任務(wù)集合的個數(shù)，當(dāng)前任務(wù)只有在它全部前驅(qū)任務(wù)的數(shù)據(jù)到達(dá)后才能執(zhí)行.succ(ni)表示任務(wù)ni的直接后繼任務(wù)集合；outd(ni)表示任務(wù)ni的出度，也就其直接后繼任務(wù)集合的個數(shù).沒有前驅(qū)任務(wù)的任務(wù)為入口任務(wù)，記為nentry；沒有后繼任務(wù)的任務(wù)為出口任務(wù)，記為nexit.criticality∈CL表示該功能的關(guān)鍵級；lower_bound表示該功能單獨(dú)占用所有處理器資源時的調(diào)度長度,本文稱之為下界；deadline表示該功能的時限.criticality，lower_bound，deadline這3個參數(shù)都由第三方認(rèn)證機(jī)構(gòu)給出.arrival_time表示功能的到達(dá)時間；makespan表示功能的最終調(diào)度長度.

混合關(guān)鍵級系統(tǒng)包括多種安全關(guān)鍵和非安全關(guān)鍵功能，我們用MS={{Func1,Func2,…},system_criticality,makespan}表示.其中system_criticality∈CL表示當(dāng)前系統(tǒng)所處的關(guān)鍵級，并且可以在LC和HC之間進(jìn)行切換；makespan表示系統(tǒng)的整體調(diào)度長度.由于一個任務(wù)分配到不同處理器會產(chǎn)生一定的通信開銷并使問題變得更加復(fù)雜.因此本文僅考慮非搶占式調(diào)度，而不包括搶占式調(diào)度和分區(qū)機(jī)制.

如圖1為由3個分布式功能組成的雙關(guān)鍵級系統(tǒng)，包含F(xiàn)uncA,FuncB，F(xiàn)uncC.表1為相應(yīng)的參數(shù)值，其中FuncB為高關(guān)鍵級功能，到達(dá)時刻為20;FuncA和FuncC為低關(guān)鍵級功能，到達(dá)時刻分別為0和50.圖1中，任務(wù)A1與任務(wù)A2之間的連線表示只有A1執(zhí)行完成后A2才有機(jī)會執(zhí)行，連接任務(wù)A1與A2邊的權(quán)值表示它們之間的通信開銷為18；若任務(wù)A1與A2在分配在同一處理器上，則通信開銷為0.表1中任務(wù)A1與處理器p1所結(jié)合處的數(shù)字14表示任務(wù)A1在處理器p1上的計算開銷為14.

Fig. 1　Dual-criticality systems with three distributed functionalities.圖1　包含3個分布式功能的雙關(guān)鍵級系統(tǒng)

FunctionalityCriticalityArrivalTimeTaskProcessorp1p2p3ranku(ni)FuncALC0FuncBHC20FuncC50LCA1141619109A213191878A311131981A41381781A512131070A61316964A77151143A85111436A918122045A102171615B145642B29101120B318171631B421151935B57656C181119110C21413891C39121663C418151431C518162039C651078

3調(diào)度策略

3.1認(rèn)證分析

HEFT算法是并行與分布式計算中眾所周知的具有低復(fù)雜度和高性能的DAG調(diào)度算法[18].該算法使用向上排序值(ranku)的降序排列作為任務(wù)優(yōu)先級排序標(biāo)準(zhǔn)，計算為

(1)

使用最小最早完成時間作為處理器分配，計算為

(2)

其中，

(3)

avail[pk]表示處理器pk的可用時間，AFT(ni)表示任務(wù)ni的實際完成時間.很明顯，對于分布式功能中的優(yōu)先級約束的任務(wù)，最早完成時間策略體現(xiàn)了一種典型的貪婪策略.

混合關(guān)鍵級系統(tǒng)中的高關(guān)鍵級功能具有嚴(yán)格的硬實時需求，且需通過第三方認(rèn)證機(jī)構(gòu)進(jìn)行嚴(yán)格的認(rèn)證.因此，第三方認(rèn)證機(jī)構(gòu)必須采用公認(rèn)有說服力的標(biāo)準(zhǔn)算法對該功能進(jìn)行嚴(yán)格的評估.作為低復(fù)雜度和高性能調(diào)度算法的著名算法，HEFT完全可以也應(yīng)該作為異構(gòu)分布式嵌入式系統(tǒng)中的功能認(rèn)證算法.第三方認(rèn)證機(jī)構(gòu)對高關(guān)鍵級功能進(jìn)行認(rèn)證時，會獨(dú)占所有處理器進(jìn)行調(diào)度，此時具有最小的調(diào)度長度，本文稱之為下界(lower_bound).根據(jù)下界值，第三方認(rèn)證機(jī)構(gòu)經(jīng)過安全分析和風(fēng)險評估后，會給出一個合理的時限時距(deadline_span).需要指出的是，本文的主要工作是假設(shè)功能的高低關(guān)鍵級級別已經(jīng)通過認(rèn)證獲得，并在此基礎(chǔ)上進(jìn)行調(diào)度.而不是具體的安全分析和風(fēng)險評估，也就是不對高低關(guān)鍵級關(guān)鍵進(jìn)行具體的度量.因此，本文的研究假設(shè)高低關(guān)鍵級級別已經(jīng)度量.綜合lower_bound，deadline_span，arrival_time可得出該功能的絕對時限:

(4)

對于分布式功能的每個任務(wù)，也存在相應(yīng)的下界為

(5)

因此，每個任務(wù)的絕對時限為

(6)

表2、表3分別列出了圖1所示的高關(guān)鍵級功能FuncB及其任務(wù)的下界值和絕對時限.

Table 2　Attributes of Higher CriticalityFuncB

Table 3　Attributes of Tasks ofFuncB

3.2公平策略

首先提出系統(tǒng)的調(diào)度框架，如圖2所示，該框架引入3個隊列，分別為任務(wù)優(yōu)先級隊列task_priority_queue、公共就緒隊列common_ready_queue以及任務(wù)分配隊列task_allocation_queue.

1) 每一個分布式功能都擁有一個task_priority_queue，用于對任務(wù)優(yōu)先級進(jìn)行排序；

2) 系統(tǒng)中僅有一個common_ready_queue，用于存儲待分配的就緒任務(wù)；

3) 每一個處理器都擁有一個task_allocation_queue，用于存儲分配到該處理器的相應(yīng)任務(wù).

公平策略的任務(wù)調(diào)度一共包括5個主要步驟：

Step1. 任務(wù)排序.對一個分布式功能排序，并按ranku式(1)的降序排列.

Step2. 任務(wù)就緒.基于輪轉(zhuǎn)的公平策略，從每一個分布式功能的task_priority_queue中取出一個ranku最大的就緒任務(wù)(只有該任務(wù)的所有前驅(qū)任務(wù)分配完成后，該任務(wù)才能成為就緒任務(wù))，放入到common_ready_queue中，同樣按ranku的降序排列.

Step3. 任務(wù)分配.依次從common_ready_queue中取出每個就緒任務(wù)，在插入法的基礎(chǔ)上將其分配到具有最小EFT的處理器task_allocation_queues上.

Step4. 任務(wù)執(zhí)行.若task_allocation_queue中任務(wù)的開始時間等于當(dāng)前時間，對該任務(wù)進(jìn)行調(diào)度.

Step5. 新功能到達(dá).若當(dāng)前時刻有新的分布式功能到達(dá)，則取消所有task_allocation_queue中未開始調(diào)度的任務(wù)，并將這些任務(wù)放回各自的task_priority_queue中.重復(fù)Step1，將新的分布式功能的任務(wù)與其他功能中未分配的任務(wù)一起進(jìn)行新一輪的公平分配.

Fig. 2　Scheduling framework of systems.圖2　系統(tǒng)調(diào)度框架

依據(jù)上述調(diào)度框架和公平策略，提出公平策略的動態(tài)雙關(guān)鍵級任務(wù)調(diào)度算法F_DDHEFT(fairness on dynamic dual-criticality heterogeneous earliest finish time),該算法步驟如算法1所示：

算法1.F_DDHEFT算法.

輸入：處理器集；

輸出：調(diào)度結(jié)果.

while (有功能需調(diào)度) do

if (有一個功能Funcnew在時刻current_time到達(dá)) then

計算Funcnew中所有任務(wù)的ranku值，并將這些任務(wù)放入到隊列task_priority_queue(Funcnew) 中;

MS.add(Funcnew);

將任務(wù)分配隊列中未執(zhí)行的任務(wù)放回到各功能的任務(wù)優(yōu)先級隊列;

while (有任務(wù)可以分配)

for (m=1;m≤|MS|;m++)

從task_priority_queue(Funcm)中取出任務(wù)ni;

common_ready_queue.put(ni);

end for

while (!common_ready_queue.empty()) do

從common_ready_queue中取出任務(wù)ni;

基于插入法將任務(wù)ni分配到具有最小EFT(ni,pk)的task_allocation_queue(pk)中;

end while

end while

end if

end while

F_DDHEFT算法的時間復(fù)雜度為O(m×n2×p).其中m代表功能數(shù)，n表示包含最多任務(wù)數(shù)的功能擁有的任務(wù)數(shù)，p為處理器數(shù).遍歷所有功能的時間復(fù)雜度應(yīng)為O(m)；遍歷任務(wù)次數(shù)的時間復(fù)雜度應(yīng)為O(n)；計算ni的EFT需遍歷其前驅(qū)和各處理器的時間復(fù)雜度應(yīng)為O(n×p).因此F_DDHEFT算法的時間復(fù)雜度為O(m×n2×p).

本文提出的公平策略的最大改進(jìn)在于當(dāng)有新功能到達(dá)時，不像OWM或者FDWS算法那樣會阻塞自己并等待其他任務(wù)完成.本文的策略會取消那些“已選擇處理器但未開始調(diào)度的任務(wù)”，并與新的DAG一起進(jìn)行公平分配.基于圖1提供的混合關(guān)鍵級實例，圖3所示為F_DDHEFT算法的執(zhí)行過程.

Fig. 3　Process of task scheduling based on the fairness policy.圖3　基于公平策略的任務(wù)調(diào)度過程

1) 如圖3(a)所示，低關(guān)鍵級功能FuncA在時刻0到達(dá)，根據(jù)向上排序值ranku分配所有任務(wù)到相應(yīng)的任務(wù)分配隊列.任務(wù)分配順序依次為{A1,A3,A4,A2,A5,A6,A9,A7,A8,A10}.

2) 如圖3(b)所示，高關(guān)鍵級功能FuncB在時刻20到達(dá)，從公平的角度出發(fā)，取消任務(wù)分配隊列中未開始執(zhí)行的任務(wù)，這些任務(wù)是{A2,A5,A6,A9,A7,A8,A10}.

3) 如圖3(c)所示，F(xiàn)uncB中的任務(wù){(diào)B1,B4,B3,B2,B5}與FuncA中取消的任務(wù){(diào)A2,A5,A6,A9,A7,A8,A10}一起公平調(diào)度,公平調(diào)度順序為{A2,B1,A5,B4,A6,B3,A9,B2,A7,B5,A8,A10}.需要指出的是，由于FuncB是高關(guān)鍵級功能，其調(diào)度長度FuncB.makespan=67,超過了CA所認(rèn)證的絕對時限FuncB.deadline=66(如表2所示).因此FuncB會對系統(tǒng)造成嚴(yán)重的安全問題.

4) 如圖3(d)所示，低關(guān)鍵級功能FuncC在時刻50到達(dá)，同樣從公平的角度出發(fā)，取消任務(wù)分配隊列中未開始執(zhí)行的任務(wù)，這些任務(wù)是{A9,A8,A10}與{B5}.

5) 如圖3(e)所示，F(xiàn)uncC中的任務(wù){(diào)C1,C2,C3,C5,C4,C6}與FuncA中取消的任務(wù){(diào)A9,A8,A10}和FuncB中取消的任務(wù){(diào)B5}一起公平分配,分配順序為{C1,A9,B5,C2,A8,C3,A10,C5,C4,C6}.此時，對于高關(guān)鍵級分布式功能FuncB，其調(diào)度長度FuncB.makespan=71,仍然超過了CA所認(rèn)證的絕對時限FuncB.deadline=66(如表2所示).因此FuncB會持續(xù)對系統(tǒng)造成嚴(yán)重的安全問題.需要指出的是，此時系統(tǒng)的調(diào)度長度MS.makespan=102，該項指標(biāo)反映系統(tǒng)的整體性能，MS.makespan越低，則性能越好.

3.3關(guān)鍵級策略

如引言所述，以及通過3.2節(jié)所展示的實例，公平任務(wù)調(diào)度易造成高關(guān)鍵級功能錯過其絕對時限，這對安全高度關(guān)鍵的分布式嵌入式系統(tǒng)來說無法容忍.因此，本節(jié)提出動態(tài)環(huán)境下滿足高關(guān)鍵級功能絕對時限的任務(wù)調(diào)度算法以解決上述問題.

系統(tǒng)關(guān)鍵級是混合關(guān)鍵級系統(tǒng)中的一個重要概念.系統(tǒng)關(guān)鍵級可以進(jìn)行切換，比如從低關(guān)鍵級提升到高關(guān)鍵級，也可以從高關(guān)鍵級降回低關(guān)鍵級.系統(tǒng)關(guān)鍵級的提升或下降實際上是系統(tǒng)的模式轉(zhuǎn)換.對于雙關(guān)鍵級系統(tǒng)，如果系統(tǒng)處于低關(guān)鍵級，那么所有關(guān)鍵級功能都可以在該模式下執(zhí)行；如果系統(tǒng)處于高關(guān)鍵級，那么僅有高關(guān)鍵級功能可以在該模式下執(zhí)行.因此，如圖3所示的公平任務(wù)調(diào)度實例，為保證所有功能都有公平執(zhí)行的機(jī)會，系統(tǒng)始終處于低關(guān)鍵級模式下.

由于系統(tǒng)中可能有多個高關(guān)鍵級功能，并且可在任意時刻提交新的高關(guān)鍵級功能到系統(tǒng)中，此時系統(tǒng)也不可能滿足所有高關(guān)鍵級功能的實時性.因此根據(jù)實時調(diào)度理論的EDF(earliest deadline first)策略,在高關(guān)鍵級模式下，系統(tǒng)會對所有高關(guān)鍵級功能按照“絕對時限”的降序排列，并優(yōu)先分配EDF最小的高關(guān)鍵級功能中的所有任務(wù).

本文還提出關(guān)鍵級策略的動態(tài)雙關(guān)鍵級調(diào)度算法C_DDHEFT(criticality on dynamic dual-criticality heterogeneous earliest finish time),其核心思想就是通過犧牲低關(guān)鍵級的公平執(zhí)行機(jī)會，優(yōu)先執(zhí)行高關(guān)鍵級功能以滿足時限.C_DDHEFT算法的步驟如算法2所示：

算法2.C_DDHEFT算法.

輸入：處理器集；

輸出：調(diào)度結(jié)果.

while (有功能需調(diào)度) do

if (有一個功能Funcnew在時刻current_time到達(dá)) then

計算Funcnew中所有任務(wù)的ranku值，并將這些任務(wù)放入到隊列task_priority_queue(Funcnew) 中;

MS.add(Funcnew);

if (Funcnew).criticality=HC) then

MS.system_criticality=HC;

將任務(wù)分配隊列中未執(zhí)行的任務(wù)放回到各功能的任務(wù)優(yōu)先級隊列;

else

僅將低關(guān)鍵級功能中的任務(wù)分配隊列中未執(zhí)行的任務(wù)放回到各功能的任務(wù)優(yōu)先級隊列;

end if

if (MS.system_criticality=HC) then

將高關(guān)鍵級功能按照EDF的降序排列；

for (m=1;m≤|MS.higher_criticality.functionalities|;m++)

從task_priority_queue(Funcm)中取出一個任務(wù)ni;

基于插入法將任務(wù)ni分配到具有最小EFT(ni,pk)的task_allocation_queue(pk)中;

end for

end if

MS.system_criticality=LC;

while (有任務(wù)可以分配)

for (m=1;m≤|MS|;m++)

從task_priority_queue(Funcm)中取出一個任務(wù)ni;

common_ready_queue.put(ni);

end for

while (!common_ready_queue.empty()) do

從common_ready_queue中取出一個任務(wù)ni;

基于插入法將任務(wù)ni分配到具有最小EFT(ni,pk) 的task_allocation_queue(pk)中;

end while

end while

end if

end while

C_DDHEFT算法的時間復(fù)雜度與F_DDHEFT算法一樣，也為O(m×n2×p).

C_DDHEFT算法與F_DDHEFT算法的區(qū)別主要有2點:1)若新到達(dá)的功能是高關(guān)鍵級功能，那么系統(tǒng)會提升系統(tǒng)關(guān)鍵級，并取消所有任務(wù)分配隊列中未開始執(zhí)行的任務(wù).①依據(jù)EDF原則對高關(guān)鍵級功能進(jìn)行分配，待全部分配完成后將系統(tǒng)關(guān)鍵級降級為低關(guān)鍵級;②再與其他被取消分配的任務(wù)一起進(jìn)行公平分配.2)若新到達(dá)的功能是低關(guān)鍵級功能，那么系統(tǒng)只會取消所有任務(wù)分配隊列中未開始執(zhí)行的低關(guān)鍵級功能中的任務(wù)(不包括高關(guān)鍵級功能中的任務(wù))，新到達(dá)的功能只與這些被取消分配的任務(wù)一起進(jìn)行公平調(diào)度(換言之，低關(guān)鍵級功能不會影響高關(guān)鍵級功能中的任務(wù)分配).基于圖1提供的混合關(guān)鍵級實例，圖4為C_DDHEFT算法的任務(wù)調(diào)度過程.

Fig. 4　Process of task scheduling based on the criticality policy.圖4　基于關(guān)鍵級策略的任務(wù)調(diào)度過程

1) 低關(guān)鍵級功能FuncA在時刻0到達(dá)，系統(tǒng)關(guān)鍵級為LC,根據(jù)向上排序值ranku分配所有任務(wù)到相應(yīng)的任務(wù)分配隊列.任務(wù)分配順序依次為{A1,A3,A4,A2,A5,A6,A9,A7,A8,A10}.上述過程與圖3(a)完全相同，這里不再畫圖描述.

2) 如圖4(a)所示，高關(guān)鍵級功能FuncB在時刻20到達(dá)，系統(tǒng)關(guān)鍵級提升到HC,取消任務(wù)分配隊列中未開始執(zhí)行的任務(wù)，這些任務(wù)是{A2,A5,A6,A9,A7,A8,A10}.

3) 如圖4(b)所示，F(xiàn)uncB中的任務(wù){(diào)B1,B4,B3,B2,B5}優(yōu)先分配，分配完成后，系統(tǒng)關(guān)鍵級切換回LC，F(xiàn)uncA中取消的任務(wù){(diào)A2,A5,A6,A9,A7,A8,A10}再進(jìn)行分配,整個任務(wù)分配順序依次為{B1,B4,B3,B2,B5,A2,A5,A6,A9,A7,A8,A10}.FuncB是高關(guān)鍵級分布式功能，此時其調(diào)度長度FuncB.makespan=56,滿足CA所認(rèn)證的絕對時限FuncB.deadline=66(如表2所示).因此FuncB不會對系統(tǒng)造成安全問題.

4) 如圖4(c)所示，低關(guān)鍵級功能FuncC在時刻50到達(dá)，取消所有低關(guān)鍵級功能中未開始執(zhí)行的任務(wù)，這些任務(wù)是{A9,A8,A10}.

5) 如圖4(d)所示，F(xiàn)uncC中的任務(wù){(diào)C1,C2,C3,C5,C4,C6}與FuncA中取消的任務(wù){(diào)A9,A8,A10}一起公平分配,分配順序為{C1,A9,C2,A8,C3,A10,C5,C4,C6}.此時，對于高關(guān)鍵級分布式功能FuncB，由于它并未受低關(guān)鍵級功能達(dá)到所造成的影響，因此它的調(diào)度長度仍然為FuncB.makespan=56.特別需要指出的是，此時系統(tǒng)的調(diào)度長度MS.makespan=123，明顯超過3.2節(jié)公平調(diào)度的調(diào)度長度102.因此盡管關(guān)鍵級的調(diào)度策略滿足了FuncB的實時性，但造成了系統(tǒng)整體性能過低.

3.4時限時距策略

通過3.2節(jié)公平策略和3.3節(jié)關(guān)鍵級策略的實例分析可知：公平策略能夠提高性能，但造成高關(guān)鍵級功能實時性得不到滿足.關(guān)鍵級策略雖能夠滿足高關(guān)鍵級功能的實時性，但造成系統(tǒng)的整體性能急劇下降.異構(gòu)分布式嵌入式系統(tǒng)的混合關(guān)鍵級任務(wù)調(diào)度在性能與時間約束上面臨嚴(yán)重的沖突.如何在動態(tài)環(huán)境下提高系統(tǒng)整體性能，并仍然確保高關(guān)鍵級功能的實時性，在性能與實時性之間取得合理的權(quán)衡則成為主要的優(yōu)化問題.

提出時限時距的動態(tài)雙關(guān)鍵級調(diào)度算法D_DDHEFT(deadline-span on dynamic dual-criticality heterogeneous earliest finish time),其核心思想就是通過判斷每個任務(wù)的時限是否滿足來決定進(jìn)一步的任務(wù)分配.D_DDHEFT算法的步驟如算法3所示：

算法3. D_DDHEFT算法.

輸入：處理器集；

輸出：調(diào)度結(jié)果.

while (有功能需調(diào)度) do

if (有一個功能Funcnew在時刻current_time到達(dá)) then

計算Funcnew中所有任務(wù)的ranku值，并將這些任務(wù)放入到隊列task_priority_queue(Funcnew) 中;

MS.add(Funcnew);

將任務(wù)分配隊列中未執(zhí)行的任務(wù)放回到各功能的任務(wù)優(yōu)先級隊列;

while (有任務(wù)可以分配)

for (m=1;m≤|MS|;m++)

從task_priority_queue(Funcm)中取出一個任務(wù)ni;

common_ready_queue.put(ni);

end for

Fig. 5　Process of task scheduling based on the deadline-span policy.圖5　基于時限時距策略的任務(wù)調(diào)度過程

while (!common_ready_queue.empty()) do

從common_ready_queue中取出一個任務(wù)ni;

基于插入法將任務(wù)ni分配到具有最小EFT(ni,pk) 的task_allocation_queue(pk)中;

if (Func(ni).criticality=HC&&makespan(ni)>deadline(ni)) then

取消本輪與前一輪的任務(wù)分配結(jié)果;

將這些取消的任務(wù)放回到各功能的任務(wù)優(yōu)先級隊列;

清空common_ready_queue;

MS.system_criticality=HC;

end if

end while

if (MS.system_criticality=HC)

將高關(guān)鍵級功能按照EDF的降序排列；

for (m=1;m≤|MS.higher_criticality.functionalities|;m++)

從task_priority_queue(Funcm)中取出一個任務(wù)ni;

基于插入法將任務(wù)ni分配到具有最小EFT(ni,pk) 的task_allocation_queue(pk)中;

end for

MS.system_criticality=LC;

end if

end while

end if

end while

D_DDHEFT算法的時間復(fù)雜度與F_DDHEFT和C_DDHEFT一樣都為O(m×n2×p).D_DDHEFT并沒有因為權(quán)衡優(yōu)化而造成時間復(fù)雜度增長，由此表明關(guān)鍵級提升的優(yōu)化不會造成時間復(fù)雜度的增長.圖5為D_DDHEFT算法的任務(wù)調(diào)度過程.

1) 低關(guān)鍵級功能FuncA在時刻0到達(dá)，系統(tǒng)關(guān)鍵級為LC,根據(jù)向上排序值ranku分配所有任務(wù)到相應(yīng)的任務(wù)分配隊列.任務(wù)分配順序依次為{A1,A3,A4,A2,A5,A6,A9,A7,A8,A10}.上述過程與圖4(a)完全相同，這里不再贅述.

2) 如圖5(a)所示，高關(guān)鍵級功能FuncB在時刻20到達(dá)，此時系統(tǒng)關(guān)鍵級并不急于提升到HC,而是FuncB中的任務(wù)與FuncA中的任務(wù)一起公平分配，直到B3錯過其時隙(makespan(B3)=58,大于deadline(B3)=52)(如表2所示)，如圖5(b)所示.

此時，系統(tǒng)關(guān)鍵級提升到HC,如圖5(c)所示,取消本輪與前一輪的公平任務(wù)分配(由于本輪分配尚未分配完成，若只取消本輪，繼續(xù)分配還是本輪的分配結(jié)果，因此需要取消到前一輪)，這些任務(wù)是{A5,B4,A6,B3}.

3) 如圖5(d)所示，F(xiàn)uncB中的任務(wù){(diào)B4,B3,B2,B5}優(yōu)先分配，分配完成后，系統(tǒng)關(guān)鍵級切回LC，F(xiàn)uncA中取消的任務(wù){(diào)A5,A6,A9,A7,A8,A10}再分配,整個任務(wù)分配順序為{B4,B3,B2,B5,A5,A6,A9,A7,A8,A10}.FuncB是高關(guān)鍵級分布式功能，此時其調(diào)度長度FuncB.makespan=61,滿足CA所認(rèn)證的絕對時限deadline=66(如表2所示).因此FuncB不會對系統(tǒng)造成安全問題.

4) 如圖5(e)所示，低關(guān)鍵級功能FuncC在時刻50到達(dá)，取消所有低關(guān)鍵級功能中未開始執(zhí)行的任務(wù)，他們是FuncA中的{A9,A7,A8,A10}和FuncB中的{B5}.

5) 如圖5(f)所示，F(xiàn)uncC中的任務(wù){(diào)C1,C2,C3,C5,C4,C6}與FuncA中的{A9,A7,A8,A10},以及FuncB中任務(wù){(diào)B5}一起公平分配,分配順序依次為{C1,A9,B5,C2,A7,C3,A8,C5,A10,C4,C6}.此時，對于高關(guān)鍵級分布式功能FuncB，盡管其與其他功能中的任務(wù)一起分配，但其調(diào)度長度仍然為FuncB.makespan=61.特別需要指出的是，此時系統(tǒng)的調(diào)度長度MS.makespan=104，明顯低于3.3節(jié)關(guān)鍵級策略調(diào)度的調(diào)度長度123.不難發(fā)現(xiàn)，時限時距策略調(diào)度在滿足FuncB實時性的前提下，有效地提高了系統(tǒng)的整體性能.

4實驗

4.1評價指標(biāo)

本文采用系統(tǒng)的調(diào)度長度比(schedule length ratio, SLR)[18]、功能之間的不公平性(unfairness)[19]以及高關(guān)鍵級功能的時隙錯失率(deadlines missed radio, DMR)[31]作為評價指標(biāo).

實驗的硬件環(huán)境為1臺配置了奔騰雙核處理器(3.2 GHz2.0 GB RAM)的Windows XP機(jī)器，使用 Java語言，根據(jù)不同參數(shù)生成各種不同特性的DAG功能樣本.主要包括任務(wù)個數(shù)n={30,40,50,60,70,80,90,100}.產(chǎn)生隨機(jī)DAG的參數(shù)設(shè)置為：任務(wù)個數(shù)n={30,40,50,60,70,80,90,100}，形狀參數(shù)α={0.5,1.0,2.0,4.0}，最大出度β={1,2,3,4,5}，最大入度γ={1,2,3,4,5}，通信開銷與計算開銷的比值CCR={0.1,0.5,1.0,5.0,10.0}，任務(wù)在不同處理器上執(zhí)行時間的差異度η={0.1,0.5,1.0,2.0,4.0}.假設(shè)wi表示任務(wù)ni的平均計算開銷，那么任務(wù)ni在處理器pk上的計算開銷為

wi(1-η4)≤wi,k≤wi(1+η4).

(7)

以上參數(shù)主要針對單個功能，整個系統(tǒng)中的功能數(shù)為MSN={10,20,30,40,50}， 不同功能的到達(dá)時距(arrival interval) 為{0,50,100,150,200}，每個高關(guān)鍵級功能的相對時限定為其下界的110%.

4.2公平性算法比較

本節(jié)的實驗主要驗證本文提出的算法與同類算法(RANK_HYBD[22],OWM[23],FDWS[24])采用的公平策略在性能上的比較.

實驗1.探究SLR和Unfairness隨功能到達(dá)時距變化的情況.功能樣本從樣本空間取出.每個功能的到達(dá)時距的變化范圍是0～200，并以50個時距遞增.到達(dá)時距的大小反映了系統(tǒng)中功能的動態(tài)負(fù)載情況，總到達(dá)的功能數(shù)固定為50.所有功能具有同樣的關(guān)鍵級.本文提出的F_DDHEFT與同類算法進(jìn)行比較.

圖6所示為采用4種算法的SLR和Unfairness隨功能到達(dá)時距變化情況.實驗結(jié)果顯示，到達(dá)間距越大，平均SLR和平均Unfairness越低.表明動態(tài)提交功能的間距越大，任務(wù)需要重新調(diào)度的幾率減少，性能結(jié)果更好.F_DDHEFT的平均SLR優(yōu)于RANK_HYBD，OWN，F(xiàn)DWS的平均百分比分別達(dá)30%，10%，5%以上；平均Unfairness優(yōu)于RANK_HYBD，OWN，F(xiàn)DWS的平均百分比分別為30%，30%，15%.從數(shù)據(jù)分析可知，通過公平調(diào)度可以盡可能地提高調(diào)度性能，且F_DDHEFT相比同類算法性能更好.

Fig. 6　SLR and Unfairness for varying deadline-spans.圖6　SLR和Unfairness隨功能到達(dá)時距變化的情況

4.3本文提出的算法比較

據(jù)我們所知，這是第1次針對性能與實時權(quán)衡的異構(gòu)分布式嵌入式系統(tǒng)雙關(guān)鍵級的動態(tài)研究，因此本節(jié)的實驗主要探究和驗證本文提出的3種算法在性能、實時及其權(quán)衡的優(yōu)化.

實驗2. 探究SLR，Unfairness，DMR隨系統(tǒng)中功能數(shù)變化的情況.基于雙關(guān)鍵級系統(tǒng)，系統(tǒng)總的到達(dá)時距固定為0，即所有功能都在時刻0同時到達(dá).高關(guān)鍵級功能數(shù)的變化范圍為10～50，并以10遞增.功能數(shù)目反映了系統(tǒng)的工作負(fù)載情況.通過對本文所提出的3種算法(F_DDHEFT,C_DDHEFT,D_DDHEFT)進(jìn)行實驗并比較相應(yīng)結(jié)果.

圖7(a)和圖7(b)所示為3種算法的SLR和Unfairness隨系統(tǒng)功能數(shù)目變化情況.隨著功能數(shù)目增加，SLR都增大，不公平性都越來越高，這表明了系統(tǒng)中任務(wù)調(diào)度的公平性越來越低，系統(tǒng)的總體性能在逐漸下降.可以發(fā)現(xiàn)F_DDHEFT擁有最好的性能，并且隨著功能數(shù)目的增多，系統(tǒng)的SLR并未顯著增長，始終控制在1.9～2.6范圍內(nèi)，不公平性也最低；C_DDHEFT表現(xiàn)最差，而且隨著系統(tǒng)負(fù)載不斷加大，性能越低.圖7(c)所示為采用3種算法的DMR隨系統(tǒng)功能數(shù)目變化情況，隨著功能數(shù)增加，DMR都越來越高.F_DDHEFT在DMR表現(xiàn)最差，DMR始終控制在90%以上；C_DDHEFT在DMR表現(xiàn)最好.

Fig. 7　SLR,Unfairness and DMR for varying numbers of functionalities.圖7　SLR，Unfairness，DMR隨系統(tǒng)中功能數(shù)變化的情況

上述實驗可以發(fā)現(xiàn)，無論SLR和Unfairness，還是DMR， D_DDHEFT處于F_DDHEFT和C_DDHEFT之間,并且在DMR上與C_DDHEFT較為接近， DMR整體控制在20%～65%.DDHEFT在性能和實時性上體現(xiàn)了合理的權(quán)衡.

實驗3. 探究SLR，Unfairness，DMR隨功能到達(dá)時距變化的情況.功能樣本從樣本空間取出.每個功能的到達(dá)時距的變化范圍是0～200，并以50個時距遞增.到達(dá)時距的大小反映了系統(tǒng)中功能的動態(tài)負(fù)載情況，總到達(dá)的功能數(shù)固定為50.基于雙關(guān)鍵級系統(tǒng)，每個功能被認(rèn)證為高關(guān)鍵級功能或低關(guān)鍵級功能,2種功能數(shù)目各占一半.通過對本文所提出的3種算法(F_DDHEFT,C_DDHEFT,D_DDHEFT)進(jìn)行實驗并比較相應(yīng)結(jié)果.

圖8所示為采用3種算法的SLR，Unfairness，DMR隨功能到達(dá)時距變化情況.隨著到達(dá)時距的增大，SLR都減少，不公平性降低，DMR降低，體現(xiàn)系統(tǒng)的各項指標(biāo)都在提升.當(dāng)?shù)竭_(dá)時距較小時，3種算法的差距較為明顯，一定程度上反映了3種算法的特點.隨著到達(dá)時距不斷增長，3種算法的差距逐漸減少，這實際上體現(xiàn)了3種算法最終趨近一種各自采用HEFT獨(dú)立調(diào)度時的表現(xiàn).

Fig. 8　SLR,Unfairness and DMR for varying deadline-spans.圖8　SLR，Unfairness，DMR隨功能到達(dá)時距變化的情況

實驗4. 探究DMR隨高關(guān)鍵級功能數(shù)變化的情況.功能樣本同樣從樣本空間取出.基于雙關(guān)鍵級系統(tǒng)，系統(tǒng)總的功能數(shù)固定為50，高關(guān)鍵級功能數(shù)的變化范圍是0～50，并以10遞增.系統(tǒng)總的到達(dá)時距固定為0.高關(guān)鍵級功能數(shù)的多少反映了系統(tǒng)的實時需求情況.通過對本文所提出的3種算法(F_DDHEFT,C_DDHEFT,D_DDHEFT)進(jìn)行實驗并比較相應(yīng)結(jié)果.

圖9所示為采用3種算法的DMR隨高關(guān)鍵級功能數(shù)變化的情況.F_DDHEFT仍然表現(xiàn)最差，C_DDHEFT表現(xiàn)最好,D_DDHEFT與C_DDHEFT較為接近.在高關(guān)鍵級功能數(shù)為50的時候，3種算法的表現(xiàn)差距很小.這是因為此時不存在低關(guān)鍵級功能，而C_DDHEFT和D_DDHEFT只能通過EDF來滿足少量高關(guān)鍵級功能的實時性.

Fig. 9　DMR for varying numbers of functionalities.圖9　DMR隨高關(guān)鍵級功能數(shù)目變化

Fig. 10　DMR and WCRT for varying deadline spans.圖10　DMR，WCRT隨功能到達(dá)時距變化

實驗5. 汽車電子系統(tǒng)是典型的異構(gòu)分布式嵌入式系統(tǒng).我們基于實際汽車電子環(huán)境，探討端到端的響應(yīng)時間與DMR隨到達(dá)時距變化的情況.系統(tǒng)使用的功能為線控剎車功能和安全氣囊功能.線控剎車功能為高關(guān)鍵級功能，它包括10個優(yōu)先級約束的任務(wù).安全氣囊為低關(guān)鍵級功能，它包括8個優(yōu)先級約束的任務(wù).這2個功能共享5個ECU.所有的ECU有不同的計算能力.實驗環(huán)境下，到達(dá)時距的變化范圍是0～40 ms并以10 ms的增量遞增，到達(dá)功能數(shù)一共為10個，高關(guān)鍵級功能與低關(guān)鍵級功能各占一半.圖10所示為采用3種算法的DMR和WCRT隨到達(dá)時距的變化情況.可以發(fā)現(xiàn)實際環(huán)境下的實驗結(jié)果與隨機(jī)樣本結(jié)果的整體趨勢一樣.在滿足實時性上，F(xiàn)_DDHEFT仍然表現(xiàn)最差，C_DDHEFT表現(xiàn)最好,D_DDHEFT與C_DDHEFT較為接近.在總體性能上，F(xiàn)_DDHEFT仍然表現(xiàn)最好，C_DDHEFT表現(xiàn)最差,D_DDHEFT與F_DDHEFT較為接近.再次驗證了D_DDHEFT在整體性能和實時性上的合理權(quán)衡.

5結(jié)論

本文面向異構(gòu)分布式嵌入式系統(tǒng)，開展雙關(guān)鍵級分布式功能的動態(tài)任務(wù)調(diào)度研究.以多DAG雙關(guān)鍵級動態(tài)模型為基礎(chǔ)，從“功能級”以及“并行與分布式計算”的角度，通過分析現(xiàn)有公平調(diào)度和混合關(guān)鍵級調(diào)度的研究進(jìn)展，提出了面向不同目標(biāo)的動態(tài)任務(wù)調(diào)度算法.包括以提高系統(tǒng)性能為目標(biāo)的公平策略算法F_DDHEFT，以滿足更多高關(guān)鍵級功能實時性的關(guān)鍵級策略算法C_DDHEFT，和在滿足更多高關(guān)鍵級功能實時性的基礎(chǔ)上提高系統(tǒng)性能的時限時距策略算法D_DDHEFT，使得在系統(tǒng)整體性能和高關(guān)鍵級功能實時之間能夠達(dá)到一種合理的權(quán)衡.最后通過實驗將本文提出的3種算法進(jìn)行全方位比較，實驗結(jié)果驗證了本文所提出的D_DDHEFT算法在滿足更多高關(guān)鍵級功能實時性的條件下，能夠有效地提高系統(tǒng)整體性能，且在汽車電子系統(tǒng)這一典型的異構(gòu)分布式嵌入式系統(tǒng)中也有較好表現(xiàn).

參考文獻(xiàn)

[1]Xie Guoqi, Li Renfa, Yang Fan, et al. Multiple-DAG off-line task scheduling for heterogeneous networked automobile electronic system[J]. Journal on Communications, 2013, 34(12): 20-32 (in Chinese)(謝國琪, 李仁發(fā), 楊帆, 等. 異構(gòu)網(wǎng)絡(luò)化汽車電子系統(tǒng)中多DAG離線任務(wù)調(diào)度[J]. 通信學(xué)報, 2013, 34(12): 20-32)

[2]Xie Guoqi, Li Renfa, Liu Lin, et al. DAG Reliability model and fault-tolerant algorithm for heterogeneous distributed system[J]. Chinese Journal of Computers, 2013, 36(10): 2019-2032 (in Chinese)(謝國琪, 李仁發(fā), 劉琳, 等. 異構(gòu)分布式系統(tǒng)DAG可靠性模型與容錯算法[J]. 計算機(jī)學(xué)報, 2013, 36(10): 2019-2032)

[3] Seo S H, Kim J H, Hwang S H, et al. A reliable gateway for in-vehicle networks based on lin, can, and flexray[J]. ACM Trans on Embedded Computing Systems, 2012, 11(1): 1-24

[4]Buckl C, Camek A, Kainz G, et al. The software car: Building ICT architectures for future electric vehicles[C] //Proc of Electric Vehicle Conf. Piscataway, NJ: IEEE, 2012: 1-8

[5]Fürst S. Challenges in the design of automotive software[C] //Proc of the Conf on Design, Automation and Test in Europe. Piscataway, NJ: IEEE, 2010: 256-258

[6]Kelly O R, Aydin H, Zhao B. On partitioned scheduling of fixed-priority mixed-criticality task sets[C] //Proc of the 10th IEEE Int Conf on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ: IEEE, 2011: 1051-1059

[7]Sinha P. Architectural design and reliability analysis of a fail-operational brake-by-wire system from ISO 26262 perspectives[J]. Reliability Engineering & System Safety, 2011, 96(10): 1349-1359

[8]Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2007). Piscataway, NJ: IEEE, 2007: 239-243

[9]De Niz D, Lakshmanan K, Rajkumar R. On the scheduling of mixed-criticality real-time task sets[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2009). Piscataway, NJ: IEEE, 2009: 291-300

[10]Lakshmanan K, De Niz D, Rajkumar R. Mixed-criticality task synchronization in zero-slack scheduling[C] //Proc of IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2011: 47-56

[11]Baruah S, Vestal S. Schedulability analysis of sporadic tasks with multiple criticality specifications[C] //Proc of Euromicro Conf on Real-Time Systems. Piscataway, NJ: IEEE, 2008: 147-155

[12]Petters S M, Lawitzky M, Heffernan R, et al. Towards real multi-criticality scheduling[C] //Proc of IEEE Int Conf on Embedded and Real-Time Computing Systems and Applications. Piscataway, NJ: IEEE, 2009: 155-164

[13]Dorin F, Richard P, Richard M, et al. Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities[J]. Real-Time Systems, 2010, 46(3): 305-331

[14]Li H, Baruah S. An algorithm for scheduling certifiable mixed-criticality sporadic task systems[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2010). Piscataway, NJ: IEEE, 2010: 183-192

[15]Zeller M, Prehofer C, Weiss G, et al. Towards self-adaptation in real-time, networked systems: Efficient solving of system constraints for automotive embedded systems[C] //Proc of Int Conf Self-Adaptive and Self-Organizing Systems. Piscataway, NJ: IEEE, 2010: 79-88

[16]Katoen J P, Noll T, Wu H, et al. Model-based energy optimization of automotive control systems[C] //Proc of the Conf on Design, Automation and Test in Europe. Piscataway, NJ: IEEE, 2013: 761-766

[17]Heinrich P, Prehofer C. Network-wide energy optimization for adaptive embedded systems[J]. ACM SIGBED Review, 2013, 10(1): 33-36

[18]Topcuoglu H, Hariri S, Wu M. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Trans on Parallel and Distributed Systems, 2002, 13(3): 260-274

[19]Xie G, Li R, Xiao X, et al. A high-performance dag task scheduling algorithm for heterogeneous networked embedded systems[C] //Proc of IEEE Int Conf on Advanced Information Networking and Applications. Piscataway, NJ: IEEE, 2014: 1011-1016

[20]H?nig U, Schiffmann W. A meta-algorithm for scheduling multiple DAGs in homogeneous system environments[C] //Proc of the Parallel and Distributed Computing and Systems. Piscataway, NJ: IEEE, 2006: 147-152

[21]Zhao Henan, Sakellariou R. Scheduling multiple DAGs onto heterogeneous systems[C] //Proc of the IEEE Int Conf on Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2006: 189-194

[22]Yu Z F, Shi W S. A planner-guided scheduling strategy for multiple workflow applications[C] //Proc of the Int Parallel Processing Workshops. Piscataway, NJ: IEEE, 2008: 1-8

[23]Hsu C C, Huang K C, Wang F J. On line scheduling of workflow applications in grid environments[J]. Future Generation Computer Systems, 2011, 27(6): 860-870

[24]Arabnejad H, Barbosa J. Fairness resource sharing for dynamic workflow scheduling on heterogeneous systems[C] //Proc of the 10th IEEE Int Symp on Parallel and Distributed Processing with Applications. Piscataway, NJ: IEEE, 2012: 633-639

[25]Anderson J, Baruah S, Brandenburg B. Multicore operating-system support for mixed criticality[C] //Proc of the Workshop on Mixed Criticality: Roadmap to Evolving UAV Certification. Piscataway, NJ: IEEE, 2009: 1-11

[26]Mollison M S, Erickso J P, Anderson J H, et al. Mixed-criticality real-time scheduling for multicore systems[C] //Proc of IEEE Int Conf on Computer and Information Technology. Piscataway, NJ: IEEE, 2010: 1864-1871

[27]Tamas-Selicean D, Pop P. Optimization of time-partitions for mixed-criticality real-time distributed embedded systems[C] //Proc of Object/Component/Service-Oriented Real-Time Distributed Computing Workshops(ISORCW). Piscataway, NJ: IEEE, 2011: 1-10

[28]Tamas-Selicean D, Pop P. Design optimization of mixed-criticality real-time applications on cost-constrained partitioned architectures[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2011). Piscataway, NJ: IEEE, 2011: 24-33

[29]Tamas-Selicean D, Marinescu S, Pop P. Analysis and optimization of mixed-criticality applications on partitioned distributed architectures[C] //Proc of System Safety, incorporating the Cyber Security Conf. Piscataway, NJ: IEEE, 2012: 1-6

[30]Tamas-Selicean D, Pop P. Optimization of partitioned architectures to support soft real-time applications[C] //Proc of the 20th IEEE Pacific Rim Int Symp on Dependable Computing(PRDC 2014). Piscataway, NJ: IEEE, 2014: 24-33

[31]Kang W, Son S H, Stankovic J A, et al. I/O-aware deadline miss ratio management in real-time embedded databases[C] //Proc of IEEE Real-Time Systems Symp (RTSS 2007). Piscataway, NJ: IEEE, 2007: 277-287

Liu Liangjiao, born in 1984. PhD candidate. Student member of China Computer Federation. His main research interests include embedded computing, distributed computing, and automobile electronic systems.

Xie Guoqi, born in 1983. PhD, assistant professor. Member of China Computer Federation. His main research interests include embedded systems, distributed systems, real-time systems, in-vehicle networks, and cyber-physical systems.

Li Renfa, born in 1957. Professor, PhD, and PhD supervisor. Distinguished member of China Computer Federation. His main research interests include embedded computing, distributed computing, automobile electronic systems, and cyber-physical systems(CPS).

Yang Liu, born in 1983. PhD. His main research interests include embedded computing, cloud computing, and software engineering.

Liu Yan, born in 1979. PhD, assistant professor. Member of China Computer Federation. His main research interests include computer architecture, multicore scheduling, distributed computing systems.

Dynamic Scheduling of Dual-Criticality Distributed Functionalities on Heterogeneous Systems

Liu Liangjiao1,2, Xie Guoqi1,2, Li Renfa1,2, Yang Liu3, and Liu Yan1,2

1(CollegeofComputerScienceandElectronicEngineering,HunanUniversity,Changsha410082)2(KeyLaboratoryforEmbeddedandNetworkComputingofHunanProvince(HunanUniversity),Changsha410082)3(DevelopmentandReformCommissionofHunanProvince,Changsha410004)

AbstractHeterogeneous distributed systems are mixed-criticality systems consisting of multiple functionalities with different criticality levels. A distributed functionality contains multiple precedence-constrained tasks. Mixed-criticality scheduling of heterogeneous distributed systems faces severe conflicts between performance and time constraints. Improving the overall performance of systems while still meeting the deadlines of higher-criticality functionalities, and making a reasonable tradeoff between performance and timing are major optimization problems. The F_DDHEFT(fairness of dynamic dual-criticality heterogeneous earliest finish time) algorithm is to improve the performance of systems. The C_DDHEFT (criticality of dynamic dual-criticality heterogeneous earliest finish time) algorithm is to meet the deadlines of higher-criticality functionalities. The D_DDHEFT (deadline-span of dynamic dual-criticality heterogeneous earliest finish time) algorithm is to allow the lower-criticality functionalities to be processed positively for better overall performance while still meeting the deadlines of higher-criticality functionalities, such that a reasonable tradeoff between performance and timing is made. Both example and extensive experimental evaluation demonstrate significant improvement of the D_DDHEFT algorithm.

Key wordsheterogeneous distributed embedded systems; dual-criticality; performance; real-time; deadline-span

收稿日期：2015-02-27；修回日期：2015-09-06

基金項目：國家自然科學(xué)基金項目(61173036,61202102,61300039,61300037,61402170);國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2012AA01A301-01);中國博士后科學(xué)基金項目(2016M592422)

通信作者：謝國琪(xgqman@hnu.edu.cn)

中圖法分類號TP316

This work was supported by the National Natural Science Foundation of China (61173036,61202102,61300039,61300037,61402170) and the National High Technology Research and Development Program of China (863 Program) (2012AA01A301-01), and the China Postdoctoral Science Foundation (2016M592422).