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

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

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

?

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

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

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

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

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

新一代高端嵌入式系統(tǒng)是典型的異構(gòu)分布式嵌入式系統(tǒng).例如，汽車電子系統(tǒng)由100多個(gè)異構(gòu)ECU(electronic control unit)、各類傳感器、執(zhí)行器和網(wǎng)關(guān)等處理單元組成，并通過(guò)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個(gè)ECU以及2 500個(gè)信號(hào)以完成各種復(fù)雜功能的執(zhí)行[4].與此同時(shí)，具有優(yōu)先級(jí)約束的分布式功能在任務(wù)數(shù)和復(fù)雜性上與日俱增.例如汽車電子系統(tǒng)中的線控剎車是典型的分布式主動(dòng)安全功能，從感知數(shù)據(jù)開(kāi)始到執(zhí)行剎車指令結(jié)束，該功能所包含的計(jì)算任務(wù)存在明顯的優(yōu)先級(jí)約束[5].整個(gè)過(guò)程需分配給5個(gè)ECU、1個(gè)傳感器和2個(gè)執(zhí)行器等處理單元.不同的任務(wù)之間產(chǎn)生不同的通信信號(hào)并被打包成消息在網(wǎng)絡(luò)總線上傳輸.

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

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

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

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

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

1相關(guān)研究

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

1.1公平性研究

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

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

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

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

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

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

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

2系統(tǒng)模型

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

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

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

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

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

FunctionalityCriticalityArrivalTimeTaskProcessorp1p2p3ranku(ni)FuncALC0FuncBHC20FuncC50LCA1141619109A213191878A311131981A41381781A512131070A61316964A77151143A85111436A918122045A102171615B145642B29101120B318171631B421151935B57656C181119110C21413891C39121663C418151431C518162039C651078

3調(diào)度策略

3.1認(rèn)證分析

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

(1)

使用最小最早完成時(shí)間作為處理器分配，計(jì)算為

(2)

其中，

(3)

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

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

(4)

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

(5)

因此，每個(gè)任務(wù)的絕對(duì)時(shí)限為

(6)

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

Table 2　Attributes of Higher CriticalityFuncB

Table 3　Attributes of Tasks ofFuncB

3.2公平策略

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

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

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

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

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

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

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

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

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

Step5. 新功能到達(dá).若當(dāng)前時(shí)刻有新的分布式功能到達(dá)，則取消所有task_allocation_queue中未開(kāi)始調(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)度框架和公平策略，提出公平策略的動(dòng)態(tài)雙關(guān)鍵級(jí)任務(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 (有一個(gè)功能Funcnew在時(shí)刻current_time到達(dá)) then

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

MS.add(Funcnew);

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

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

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

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

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

2) 如圖3(b)所示，高關(guān)鍵級(jí)功能FuncB在時(shí)刻20到達(dá)，從公平的角度出發(fā)，取消任務(wù)分配隊(duì)列中未開(kāi)始執(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)度順序?yàn)閧A2,B1,A5,B4,A6,B3,A9,B2,A7,B5,A8,A10}.需要指出的是，由于FuncB是高關(guān)鍵級(jí)功能，其調(diào)度長(zhǎng)度FuncB.makespan=67,超過(guò)了CA所認(rèn)證的絕對(duì)時(shí)限FuncB.deadline=66(如表2所示).因此FuncB會(huì)對(duì)系統(tǒng)造成嚴(yán)重的安全問(wèn)題.

4) 如圖3(d)所示，低關(guān)鍵級(jí)功能FuncC在時(shí)刻50到達(dá)，同樣從公平的角度出發(fā)，取消任務(wù)分配隊(duì)列中未開(kāi)始執(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}一起公平分配,分配順序?yàn)閧C1,A9,B5,C2,A8,C3,A10,C5,C4,C6}.此時(shí)，對(duì)于高關(guān)鍵級(jí)分布式功能FuncB，其調(diào)度長(zhǎng)度FuncB.makespan=71,仍然超過(guò)了CA所認(rèn)證的絕對(duì)時(shí)限FuncB.deadline=66(如表2所示).因此FuncB會(huì)持續(xù)對(duì)系統(tǒng)造成嚴(yán)重的安全問(wèn)題.需要指出的是，此時(shí)系統(tǒng)的調(diào)度長(zhǎng)度MS.makespan=102，該項(xiàng)指標(biāo)反映系統(tǒng)的整體性能，MS.makespan越低，則性能越好.

3.3關(guān)鍵級(jí)策略

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

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

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

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

算法2.C_DDHEFT算法.

輸入：處理器集；

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

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

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

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

MS.add(Funcnew);

if (Funcnew).criticality=HC) then

MS.system_criticality=HC;

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

else

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

end if

if (MS.system_criticality=HC) then

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

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

從task_priority_queue(Funcm)中取出一個(gè)任務(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)中取出一個(gè)任務(wù)ni;

common_ready_queue.put(ni);

end for

while (!common_ready_queue.empty()) do

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

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

end while

end while

end if

end while

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

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

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

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

2) 如圖4(a)所示，高關(guān)鍵級(jí)功能FuncB在時(shí)刻20到達(dá)，系統(tǒng)關(guān)鍵級(jí)提升到HC,取消任務(wù)分配隊(duì)列中未開(kāi)始執(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)鍵級(jí)切換回LC，F(xiàn)uncA中取消的任務(wù){(diào)A2,A5,A6,A9,A7,A8,A10}再進(jìn)行分配,整個(gè)任務(wù)分配順序依次為{B1,B4,B3,B2,B5,A2,A5,A6,A9,A7,A8,A10}.FuncB是高關(guān)鍵級(jí)分布式功能，此時(shí)其調(diào)度長(zhǎng)度FuncB.makespan=56,滿足CA所認(rèn)證的絕對(duì)時(shí)限FuncB.deadline=66(如表2所示).因此FuncB不會(huì)對(duì)系統(tǒng)造成安全問(wèn)題.

4) 如圖4(c)所示，低關(guān)鍵級(jí)功能FuncC在時(shí)刻50到達(dá)，取消所有低關(guān)鍵級(jí)功能中未開(kāi)始執(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}一起公平分配,分配順序?yàn)閧C1,A9,C2,A8,C3,A10,C5,C4,C6}.此時(shí)，對(duì)于高關(guān)鍵級(jí)分布式功能FuncB，由于它并未受低關(guān)鍵級(jí)功能達(dá)到所造成的影響，因此它的調(diào)度長(zhǎng)度仍然為FuncB.makespan=56.特別需要指出的是，此時(shí)系統(tǒng)的調(diào)度長(zhǎng)度MS.makespan=123，明顯超過(guò)3.2節(jié)公平調(diào)度的調(diào)度長(zhǎng)度102.因此盡管關(guān)鍵級(jí)的調(diào)度策略滿足了FuncB的實(shí)時(shí)性，但造成了系統(tǒng)整體性能過(guò)低.

3.4時(shí)限時(shí)距策略

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

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

算法3. D_DDHEFT算法.

輸入：處理器集；

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

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

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

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

MS.add(Funcnew);

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

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

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

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

common_ready_queue.put(ni);

end for

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

while (!common_ready_queue.empty()) do

從common_ready_queue中取出一個(gè)任務(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)先級(jí)隊(duì)列;

清空common_ready_queue;

MS.system_criticality=HC;

end if

end while

if (MS.system_criticality=HC)

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

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

從task_priority_queue(Funcm)中取出一個(gè)任務(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算法的時(shí)間復(fù)雜度與F_DDHEFT和C_DDHEFT一樣都為O(m×n2×p).D_DDHEFT并沒(méi)有因?yàn)闄?quán)衡優(yōu)化而造成時(shí)間復(fù)雜度增長(zhǎng)，由此表明關(guān)鍵級(jí)提升的優(yōu)化不會(huì)造成時(shí)間復(fù)雜度的增長(zhǎng).圖5為D_DDHEFT算法的任務(wù)調(diào)度過(guò)程.

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

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

此時(shí)，系統(tǒng)關(guān)鍵級(jí)提升到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)鍵級(jí)切回LC，F(xiàn)uncA中取消的任務(wù){(diào)A5,A6,A9,A7,A8,A10}再分配,整個(gè)任務(wù)分配順序?yàn)閧B4,B3,B2,B5,A5,A6,A9,A7,A8,A10}.FuncB是高關(guān)鍵級(jí)分布式功能，此時(shí)其調(diào)度長(zhǎng)度FuncB.makespan=61,滿足CA所認(rèn)證的絕對(duì)時(shí)限deadline=66(如表2所示).因此FuncB不會(huì)對(duì)系統(tǒng)造成安全問(wèn)題.

4) 如圖5(e)所示，低關(guān)鍵級(jí)功能FuncC在時(shí)刻50到達(dá)，取消所有低關(guān)鍵級(jí)功能中未開(kāi)始執(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}.此時(shí)，對(duì)于高關(guān)鍵級(jí)分布式功能FuncB，盡管其與其他功能中的任務(wù)一起分配，但其調(diào)度長(zhǎng)度仍然為FuncB.makespan=61.特別需要指出的是，此時(shí)系統(tǒng)的調(diào)度長(zhǎng)度MS.makespan=104，明顯低于3.3節(jié)關(guān)鍵級(jí)策略調(diào)度的調(diào)度長(zhǎng)度123.不難發(fā)現(xiàn)，時(shí)限時(shí)距策略調(diào)度在滿足FuncB實(shí)時(shí)性的前提下，有效地提高了系統(tǒng)的整體性能.

4實(shí)驗(yàn)

4.1評(píng)價(jià)指標(biāo)

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

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

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

(7)

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

4.2公平性算法比較

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

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

圖6所示為采用4種算法的SLR和Unfairness隨功能到達(dá)時(shí)距變化情況.實(shí)驗(yàn)結(jié)果顯示，到達(dá)間距越大，平均SLR和平均Unfairness越低.表明動(dòng)態(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ù)分析可知，通過(guò)公平調(diào)度可以盡可能地提高調(diào)度性能，且F_DDHEFT相比同類算法性能更好.

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

4.3本文提出的算法比較

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

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

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

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

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

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

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

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

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

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

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

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

5結(jié)論

本文面向異構(gòu)分布式嵌入式系統(tǒng)，開(kāi)展雙關(guān)鍵級(jí)分布式功能的動(dòng)態(tài)任務(wù)調(diào)度研究.以多DAG雙關(guān)鍵級(jí)動(dòng)態(tài)模型為基礎(chǔ)，從“功能級(jí)”以及“并行與分布式計(jì)算”的角度，通過(guò)分析現(xiàn)有公平調(diào)度和混合關(guān)鍵級(jí)調(diào)度的研究進(jìn)展，提出了面向不同目標(biāo)的動(dòng)態(tài)任務(wù)調(diào)度算法.包括以提高系統(tǒng)性能為目標(biāo)的公平策略算法F_DDHEFT，以滿足更多高關(guān)鍵級(jí)功能實(shí)時(shí)性的關(guān)鍵級(jí)策略算法C_DDHEFT，和在滿足更多高關(guān)鍵級(jí)功能實(shí)時(shí)性的基礎(chǔ)上提高系統(tǒng)性能的時(shí)限時(shí)距策略算法D_DDHEFT，使得在系統(tǒng)整體性能和高關(guān)鍵級(jí)功能實(shí)時(shí)之間能夠達(dá)到一種合理的權(quán)衡.最后通過(guò)實(shí)驗(yàn)將本文提出的3種算法進(jìn)行全方位比較，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出的D_DDHEFT算法在滿足更多高關(guān)鍵級(jí)功能實(shí)時(shí)性的條件下，能夠有效地提高系統(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)(謝國(guó)琪, 李仁發(fā), 楊帆, 等. 異構(gòu)網(wǎng)絡(luò)化汽車電子系統(tǒng)中多DAG離線任務(wù)調(diào)度[J]. 通信學(xué)報(bào), 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)(謝國(guó)琪, 李仁發(fā), 劉琳, 等. 異構(gòu)分布式系統(tǒng)DAG可靠性模型與容錯(cuò)算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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

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

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

中圖法分類號(hào)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).