黃麗達(dá)，李 龍，李仁發(fā)，謝 勇

（1.湖南大學(xué)嵌入式與網(wǎng)絡(luò)計(jì)算湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙410082；2.廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，福建 廈門361024）

1 引言

當(dāng)前，在嵌入式系統(tǒng)領(lǐng)域，將多種功能整合在一個(gè)資源共享的平臺(tái)上是重要的研究?jī)?nèi)容。不同功能的計(jì)算任務(wù)其重要性是不同的，一般用不同關(guān)鍵級(jí)來表述，比如在航空和汽車等領(lǐng)域，均有多層次關(guān)鍵級(jí)的劃分?；旌详P(guān)鍵級(jí)多任務(wù)系統(tǒng)（后文簡(jiǎn)稱為混合關(guān)鍵級(jí)系統(tǒng)）正是致力于在盡量減少物理設(shè)備冗余的情況下，讓多個(gè)關(guān)鍵級(jí)的任務(wù)在同一個(gè)平臺(tái)上執(zhí)行，相對(duì)低關(guān)鍵級(jí)任務(wù)不會(huì)影響高關(guān)鍵級(jí)任務(wù)的時(shí)限要求。系統(tǒng)關(guān)鍵級(jí)與當(dāng)前正在運(yùn)行的任務(wù)的關(guān)鍵級(jí)一致，每個(gè)任務(wù)在各關(guān)鍵級(jí)都有相應(yīng)的執(zhí)行時(shí)間上限 WCET（Worst Cast Execution Time，最差情況下執(zhí)行時(shí)間），一旦具有更高關(guān)鍵級(jí)任務(wù)的執(zhí)行時(shí)間超出了當(dāng)前關(guān)鍵級(jí)的預(yù)期WCET，則立即提升系統(tǒng)關(guān)鍵級(jí)［1］。

一旦系統(tǒng)關(guān)鍵級(jí)提升，為了保證高關(guān)鍵級(jí)任務(wù)取得更多的CPU計(jì)算時(shí)間以滿足其截止時(shí)限，目前通常的處理辦法是立即拋棄或者無限期掛起低關(guān)鍵級(jí)任務(wù)。這種處理方法過于消極，武斷地將低關(guān)鍵級(jí)任務(wù)拋棄，可能會(huì)帶來負(fù)面影響，正在執(zhí)行的任務(wù)通常會(huì)訪存數(shù)據(jù)，那么數(shù)據(jù)的一致性和完整性可能會(huì)由于任務(wù)的無限期掛起受到影響［2］，尤其是在控制系統(tǒng)中。同時(shí)，任務(wù)的WCET是其計(jì)算時(shí)間的保守上限估值，即實(shí)際任務(wù)執(zhí)行時(shí)間并不會(huì)總能達(dá)到WCET，那么CPU很可能出現(xiàn)空閑；且不論采用哪一種調(diào)度方案，多處理器系統(tǒng)中總會(huì)有未被分配的空閑時(shí)段（以上兩種空閑時(shí)段后文中總稱為slack）。因此，在提升系統(tǒng)關(guān)鍵級(jí)時(shí)，消極地拋棄低關(guān)鍵級(jí)是不可取的，用更加謹(jǐn)慎積極的方式處理低關(guān)鍵級(jí)任務(wù)是可行的。

混合關(guān)鍵級(jí)多任務(wù)調(diào)度最早源于Vestals，他在文獻(xiàn)［1］中首先正式提出并定義了在多重認(rèn)證需求下的混合關(guān)鍵級(jí)多任務(wù)調(diào)度問題，并提出了一個(gè)適合混合關(guān)鍵級(jí)系統(tǒng)的固定優(yōu)先級(jí)調(diào)度算法。

de Niz D等［3］從增加系統(tǒng)運(yùn)行的魯棒性出發(fā)，討論了在normal和critical雙模式下低關(guān)鍵級(jí)任務(wù)和高關(guān)鍵級(jí)任務(wù)不同的運(yùn)行模式，其核心在于高關(guān)鍵級(jí)任務(wù)竊取低關(guān)鍵級(jí)任務(wù)的CPU執(zhí)行時(shí)間以保證自己的截止時(shí)限；而Baruah S等［4］則從靜態(tài)驗(yàn)證的角度討論了混合關(guān)鍵級(jí)的多任務(wù)調(diào)度，在相對(duì)保守的認(rèn)證執(zhí)行標(biāo)準(zhǔn)和較開放的假設(shè)條件下，均能保證相對(duì)較高的資源利用率。近年，隨著多處理器在嵌入式系統(tǒng)中的廣泛應(yīng)用，一些研究開始轉(zhuǎn)向基于多處理器或多核平臺(tái)上的混合關(guān)鍵級(jí)多任務(wù)調(diào)度［5，6］。文獻(xiàn)［7］在分布式環(huán)境下討論混合關(guān)鍵級(jí)任務(wù)的局部調(diào)度，分析了在多處理器平臺(tái)上可能出現(xiàn)的關(guān)鍵級(jí)反轉(zhuǎn)問題，并著重討論了結(jié)合關(guān)鍵級(jí)和過載利用率進(jìn)行任務(wù)到處理器的分配。文獻(xiàn)［8］考慮的是以固定優(yōu)先級(jí)的全局調(diào)度來處理混合關(guān)鍵級(jí)調(diào)度問題。截止目前，在多處理器平臺(tái)上的混合關(guān)鍵級(jí)調(diào)度研究尚處于起步階段，審慎處理低關(guān)鍵級(jí)任務(wù)的研究還相當(dāng)少。Santy F等［9］首先關(guān)注到一般混合關(guān)鍵級(jí)調(diào)度中被拋棄的低關(guān)鍵級(jí)任務(wù)，并從多模式的角度討論了重啟低關(guān)鍵級(jí)任務(wù)的可行性。Su Han等［10］則依據(jù)可變周期的彈性調(diào)度理論，構(gòu)建了一個(gè)彈性混合關(guān)鍵級(jí)多任務(wù)模型，通過彈性化處理相對(duì)低關(guān)鍵集任務(wù)的周期使其獲得更頻繁的執(zhí)行。

本文基于同構(gòu)多處理器平臺(tái)，對(duì)混合關(guān)鍵級(jí)多任務(wù)調(diào)度中低關(guān)鍵級(jí)任務(wù)進(jìn)行積極處理。在保證高關(guān)鍵級(jí)任務(wù)滿足其截止時(shí)限的同時(shí)，盡可能充分利用多處理器的執(zhí)行能力。為此構(gòu)建了兩類隊(duì)列：任務(wù)隊(duì)列和空閑時(shí)隙隊(duì)列S＿Que（Slack Queue）。其中任務(wù)隊(duì)列包括兩個(gè)隊(duì)列：一個(gè)隊(duì)列是常規(guī)任務(wù)隊(duì)列R＿Que（Routine Queue），用于容納通?；旌详P(guān)鍵級(jí)系統(tǒng)中就緒待調(diào)度的任務(wù)集；另一個(gè)隊(duì)列是低關(guān)鍵級(jí)保留隊(duì)列L－Que（Low Criticality Reserving Queue），用于保留關(guān)鍵級(jí)提升時(shí)“被拋棄”的低關(guān)鍵級(jí)任務(wù)?？臻e時(shí)隙隊(duì)列S＿Que是一個(gè)全局性隊(duì)列，整個(gè)系統(tǒng)執(zhí)行過程中各處理器上的動(dòng)態(tài)空閑時(shí)隙都被回收到S＿Que。L－Que中的任務(wù)則從S＿Que中獲得可用的執(zhí)行時(shí)間。這樣就實(shí)現(xiàn)了不同關(guān)鍵級(jí)任務(wù)在不同時(shí)段不同場(chǎng)景下的“混合調(diào)度”，從而獲得更好的系統(tǒng)性能。

2 任務(wù)模型與定義

設(shè)定多處理器平臺(tái)由m個(gè)同構(gòu)處理器組成，記為π＝｛π1，π2，…，πm｝。混合關(guān)鍵級(jí)多任務(wù)集由n個(gè)具有周期性的任務(wù)組成，記為Γ＝｛τ1，τ2，…，τn｝。任務(wù)之間相互獨(dú)立，不存在依賴關(guān)系。任務(wù)之間允許搶占。每個(gè)任務(wù)都有其相應(yīng)的最高關(guān)鍵級(jí)。系統(tǒng)關(guān)鍵級(jí)與正在運(yùn)行的任務(wù)的關(guān)鍵級(jí)一致，即當(dāng)前同時(shí)執(zhí)行的任務(wù)集具有相同關(guān)鍵級(jí)。一個(gè)任務(wù)τi由一個(gè)四元組〈Ti，Di，Li，Ci〉表示，其中：

（1）Ti表示任務(wù)τi連續(xù)兩次作業(yè)（job）之間的最小時(shí)間間隔，即周期。

（2）Di表示任務(wù)τi的相對(duì)截止時(shí)限，Di≤Ti，在之后的討論中，任務(wù)均視為具有默認(rèn)截止時(shí)限，即Di＝Ti。

（3）Li∈｛L1，L2，…，Lk｝，其中L1表示最低關(guān)鍵級(jí)LO，Lk表示最高關(guān)鍵級(jí)LH，即L的下標(biāo)越大表示關(guān)鍵級(jí)越高。

（4）Ci表示最差情況下的執(zhí)行時(shí)間（WCET），Ci實(shí)際上是一個(gè)大小為k的向量，Ci（l）表示任務(wù)τi處于 關(guān) 鍵 級(jí)l 時(shí) 的 WCET，l∈ ［L1，Lk］，且Ci（L1）≤Ci（L2）≤…≤Ci（Li）＝Ci（Li＋1）＝…＝Ci（Lk），即任務(wù)在低關(guān)鍵級(jí)的WCET總是小于或等于高關(guān)鍵級(jí)的WCET，而一旦當(dāng)前系統(tǒng)到達(dá)任務(wù)既定最高關(guān)鍵級(jí)，那么相應(yīng)任務(wù)不能再提升關(guān)鍵級(jí)，即在之后的系統(tǒng)關(guān)鍵級(jí)提升時(shí)其WCET不再變化。

WCET實(shí)際是任務(wù)占用CPU的保守上限時(shí)間，對(duì)于任意任務(wù)，其實(shí)際所需的執(zhí)行時(shí)間總是滿足≤Ci（Li）。擁有較高關(guān)鍵級(jí)的任務(wù)若是超過其在較低關(guān)鍵級(jí)的預(yù)期 W CET，那么提升系統(tǒng)關(guān)鍵級(jí)l，高關(guān)鍵級(jí)任務(wù)繼續(xù)執(zhí)行，低關(guān)鍵級(jí)被掛起不再繼續(xù)執(zhí)行，此時(shí)無論對(duì)于高關(guān)鍵級(jí)任務(wù)還是低關(guān)鍵級(jí)任務(wù)，將已經(jīng)執(zhí)行的部分記為，未執(zhí)行完畢的部分記為，且滿足＋＝。

在上述任務(wù)模型中，將任務(wù)τi的一次執(zhí)行稱之為作業(yè)（job），記為Ji1，Ji2，Ji3，……，每一個(gè)任務(wù)的job序列是無限的。為了討論分析簡(jiǎn)便起見，視所有任務(wù)的每一個(gè)job均是在其周期一開始就釋放。任務(wù)τi釋放時(shí)間記為ri。那么，任務(wù)的絕對(duì)截止時(shí)限記為di＝ri＋Di。

CPU利用率（后文簡(jiǎn)稱為利用率）為：

是任務(wù)的WCET與其周期的比值，即一個(gè)job的有效計(jì)算時(shí)間比率。對(duì)于混合關(guān)鍵級(jí)系統(tǒng)而言，因?yàn)槊總€(gè)任務(wù)在不同關(guān)鍵級(jí)的WCET可能是不同的，那么就應(yīng)當(dāng)考慮不同關(guān)鍵級(jí)的利用率。對(duì)于任意任務(wù)τi在不同關(guān)鍵級(jí)其相應(yīng)的利用率為：

Table1 A set of mixed－criticality tasks表1 一個(gè)簡(jiǎn)單混合關(guān)鍵級(jí)任務(wù)集示例

表1所示的是一個(gè)簡(jiǎn)單的任務(wù)集，若是在單處理器平臺(tái)上，系統(tǒng)關(guān)鍵級(jí)l＝L1時(shí)，利用率為：

系統(tǒng)關(guān)鍵級(jí)升到L2時(shí)，由于相對(duì)的低關(guān)鍵級(jí)任務(wù)τ1被無限期掛起，此時(shí)利用率為：

類似地，當(dāng)系統(tǒng)關(guān)鍵級(jí)升到L3時(shí)，相對(duì)的低關(guān)鍵級(jí)任務(wù)τ2被無限期掛起，此時(shí)利用率為：

即由于不同關(guān)鍵級(jí)下執(zhí)行的任務(wù)集不同，不同關(guān)鍵級(jí)下的利用率也會(huì)不同：

下面定義：若一個(gè)混合關(guān)鍵多任務(wù)調(diào)度算法是正確的，那么對(duì)于任務(wù)集的所有實(shí)例均要滿足：

（1）當(dāng)系統(tǒng)關(guān)鍵級(jí)不高于任務(wù)既定關(guān)鍵級(jí)時(shí)，任務(wù)的每個(gè)實(shí)例在其周期T內(nèi)均有足夠的運(yùn)行時(shí)間執(zhí)行完畢，滿足其截止時(shí)限；

（2）當(dāng)系統(tǒng)關(guān)鍵級(jí)比任務(wù)既定關(guān)鍵級(jí)高時(shí)，所有比該任務(wù)關(guān)鍵級(jí)高的任務(wù)集在其周期T內(nèi)可獲得足夠的運(yùn)行時(shí)間執(zhí)行完畢，并保證截止時(shí)限。

在之前幾乎所有的混合關(guān)鍵級(jí)多任務(wù)調(diào)度研究中，為了保證前述定義中的（2），一旦系統(tǒng)關(guān)鍵級(jí)提升，低關(guān)鍵級(jí)任務(wù)不論是否已經(jīng)被釋放均立即終止，所以不會(huì)考慮低關(guān)鍵級(jí)任務(wù)在系統(tǒng)處于高關(guān)鍵級(jí)狀態(tài)時(shí)的 WCET。但是，本文對(duì)低關(guān)鍵級(jí)任務(wù)進(jìn)行保留處理，促使其盡可能地執(zhí)行完畢，所以如表1所示，低關(guān)鍵級(jí)任務(wù)在高關(guān)鍵級(jí)下的行為不發(fā)生變化，即其WCET保持不變。

在實(shí)時(shí)調(diào)度理論中，可接受任務(wù)是指若系統(tǒng)使用某種調(diào)度算法能夠被正確調(diào)度，即滿足截止時(shí)限的任務(wù)?？山邮苋蝿?wù)數(shù)目，或可接受任務(wù)占總釋放任務(wù)的比率，是衡量系統(tǒng)性能的重要指標(biāo)之一［11］。

3 調(diào)度算法描述

按照如何將任務(wù)分配給處理器的方式，多處理器平臺(tái)上的實(shí)時(shí)調(diào)度大致上可以劃分為全局調(diào)度和局部調(diào)度兩種。所謂全局調(diào)度，是指待調(diào)度任務(wù)可以在任意一個(gè)處理器上執(zhí)行，任務(wù)隨時(shí)可以在不同處理器之間遷移；所謂局部調(diào)度，是指待調(diào)度任務(wù)只能按照某種預(yù)先分配規(guī)則，固定在某一個(gè)處理器上執(zhí)行，不可遷移。文獻(xiàn)［12］指出，局部調(diào)度更加適合硬實(shí)時(shí)任務(wù)集，而全局調(diào)度更適合軟實(shí)時(shí)任務(wù)調(diào)度需求。對(duì)混合關(guān)鍵級(jí)多任務(wù)集而言，文獻(xiàn)［13］指出，以可接受任務(wù)數(shù)目為性能指標(biāo)，局部調(diào)度要優(yōu)于全局調(diào)度。

現(xiàn)有的混合關(guān)鍵級(jí)系統(tǒng)中，除了少量具有最高關(guān)鍵級(jí)的、與生命和重大財(cái)產(chǎn)安全休戚相關(guān)的任務(wù)以外，大部分任務(wù)之間的“硬”與“軟”的界定具有相對(duì)性［14］。比如，在從相對(duì)低關(guān)鍵級(jí)提升到相對(duì)高關(guān)鍵級(jí)時(shí)，低關(guān)鍵級(jí)任務(wù)呈現(xiàn)出某些軟實(shí)時(shí)任務(wù)的特性，而高關(guān)鍵級(jí)任務(wù)則被視為硬實(shí)時(shí)任務(wù)來確保執(zhí)行，系統(tǒng)的每一次關(guān)鍵級(jí)提升，實(shí)際都是這種模式的一次切換。

基于前述結(jié)論，我們對(duì)處于某關(guān)鍵級(jí)下的多任務(wù)集進(jìn)行局部調(diào)度，而將在關(guān)鍵級(jí)提升時(shí)掛起的低關(guān)鍵級(jí)任務(wù)序列進(jìn)行“全局性”調(diào)度。

這里的全局性是指低關(guān)鍵級(jí)要全局分配的是多關(guān)鍵級(jí)任務(wù)在多處理器上執(zhí)行時(shí)產(chǎn)生的動(dòng)態(tài)空閑（Dynamic Slack）。修改文獻(xiàn)［15］中的動(dòng)態(tài)空閑回收規(guī)則，描述如下：

（1）系統(tǒng)一旦開始執(zhí)行，就開始回收各處理器上的空閑時(shí)隙（slack，記為sp），為簡(jiǎn)單起見，不限定最小可回收空閑時(shí)隙的時(shí)長(zhǎng)。

（2）每一片回收的空閑時(shí)隙使用二元組（q，d）來描述，其中q表示空閑時(shí)隙時(shí)長(zhǎng)；d表示其絕對(duì)截止時(shí)限，若超過d時(shí)刻則這片空閑時(shí)隙失效。

（3）若任務(wù)τi在時(shí)刻t＜di執(zhí)行完畢，且其＜Ci，那么產(chǎn)生空閑時(shí)隙（min（Ci－，di－t），di）。

（4）未失效的空閑時(shí)隙按照d的時(shí)間順序保存在空閑時(shí)隙隊(duì)列S＿Que中，待分配給L＿Que中的任務(wù)使用。

（5）若該片空閑時(shí)隙失效，或者被使用完畢，則從S＿Que上出列；否則，未使用完的空閑時(shí)隙（q－（L），d）重新入列S＿Que，并重復(fù)（4）中的分配，j其中，（Lj）表示L＿Que上的某個(gè)任務(wù)πj的未執(zhí)行完畢的部分，且0≤（Lj）＜（Lj）≤Cj（Lj）。

同時(shí)，引入雙任務(wù)隊(duì)列：一個(gè)稱之為常規(guī)任務(wù)隊(duì)列R－Que，用于容納待調(diào)度任務(wù)，對(duì)該隊(duì)列上的任務(wù)進(jìn)行局部調(diào)度；另一個(gè)稱之為低關(guān)鍵級(jí)保留隊(duì)列L－Que，用于容納關(guān)鍵級(jí)提升時(shí)被掛起的相對(duì)低關(guān)鍵級(jí)任務(wù)，對(duì)L－Que中的任務(wù)集面向全局隊(duì)列S＿Que進(jìn)行調(diào)度。

整個(gè)調(diào)度過程大略可以分為三個(gè)階段：

第一階段：釋放的任務(wù)序列依次入列R－Que，對(duì)于R－Que上的任務(wù)進(jìn)行局部調(diào)度。我們修改了文獻(xiàn)［13］中的局部調(diào)度算法：將任務(wù)映射到處理器的方法以Best－First替換了原來的First－Fit——每次選取當(dāng)前利用率最低的處理器優(yōu)先分配，故均衡了各個(gè)處理器的負(fù)載，并提高了調(diào)度成功率。

第二階段：一旦發(fā)生關(guān)鍵級(jí)提升，從各個(gè)處理器對(duì)應(yīng)的待處理隊(duì)列中，出列未執(zhí)行完畢的低關(guān)鍵級(jí)任務(wù)，并按照如下準(zhǔn)則入/出列L－Que：

（1）關(guān)鍵級(jí)高的任務(wù)優(yōu)先—當(dāng)系統(tǒng)中存在兩個(gè)以上的關(guān)鍵級(jí)時(shí)，關(guān)鍵級(jí)的提升可能會(huì)發(fā)生不止一次，那么被掛起的相對(duì)低關(guān)鍵級(jí)任務(wù)之間的關(guān)鍵級(jí)也不是一致的；

（2）若關(guān)鍵級(jí)相同則未執(zhí)行時(shí)間較少的任務(wù)優(yōu)先。

第三階段：將S＿Que上的時(shí)隙依據(jù)前述第二階段的規(guī)則和前文的動(dòng)態(tài)空閑回收規(guī)則（4）分配給L＿Que上的任務(wù)。

之后每次關(guān)鍵級(jí)提升都將重復(fù)第二和第三階段的工作。

第一階段局部調(diào)度算法描述如下：

步驟1－1 m個(gè)同構(gòu)處理器，R－Que中是就緒的任務(wù)集Γ＝｛τ1，τ2，…，τn｝，當(dāng)前系統(tǒng)關(guān)鍵級(jí)為l∈｛L1，L2，…，Lk｝，其中初始關(guān)鍵級(jí)是L1，且初始階段L－Que為空；

步驟1－2 若?τi∈Γ，l＝Li，那么對(duì)于?τj∈Γ，其Lj＞l，那么將任務(wù)τj分配給當(dāng)前U（l）最小的處理器；

步驟1－3 若?/τj∈R－Que，那么將任務(wù)τi再分配給當(dāng)前U（l）最小的處理器，直至R－Que上的任務(wù)分配完畢。

第二階段相對(duì)低關(guān)鍵級(jí)任務(wù)入列L-Que的算法描述如下：

步驟2－1 當(dāng)前關(guān)鍵級(jí)為l時(shí)，若有?τj∈Γ，其Lj＞l，if＞Cj（l），then l＝Li＋1；

步驟2－2 若?τi∈Γ，且其Li＜l，無論其是否已經(jīng)分配到各個(gè)處理器開始執(zhí)行，還是在R－Que尚未開始執(zhí)行，均立刻將τi進(jìn)行出列處理；

步驟2－3 將步驟2－2中的所有低關(guān)鍵級(jí)任務(wù)τi入列L－Que：若此時(shí)L＿Que不止一個(gè)任務(wù)，即?τs，τt∈LQue，

第三階段L－Que上的低關(guān)鍵級(jí)任務(wù)全局性調(diào)度描述如下：

步驟3－1 記此時(shí)L－Que上的任務(wù)集為Γlow，每一個(gè)Γi∈Γlow，均具有

步驟3－2 按照步驟2－3中的規(guī)則出列任務(wù)τ′i，同時(shí)選取S＿Que中q最小的動(dòng)態(tài)時(shí)隙sp，

鑒于上述調(diào)度方法涉及兩類隊(duì)列——任務(wù)隊(duì)列和空閑時(shí)隙隊(duì)列，在下文描述中，將本文調(diào)度算法簡(jiǎn)稱為MC－DQ。

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

鑒于文獻(xiàn)［16］的任務(wù)集被多篇文獻(xiàn)［9，17］參照應(yīng)用，仿照其生成測(cè)試任務(wù)集，對(duì)MC－DQ算法進(jìn)行了仿真實(shí)驗(yàn)。依據(jù)不同CPU利用率可接受任務(wù)集占總?cè)蝿?wù)集的比例，在處理器個(gè)數(shù)為2、4、8的情況下，與MC－Partition進(jìn)行了比較，參見圖1～圖3?？梢钥吹奖疚乃鏊惴▽⒔邮苋蝿?wù)集比例平均提高了31%左右，所增加的可接受任務(wù)均為當(dāng)前一般MC調(diào)度中被消極拋棄的低關(guān)鍵級(jí)任務(wù)，性能提升不受處理器個(gè)數(shù)和利用率限制的影響。

Figure 1 Comparison between MC－DG and MC－Partition on double－processor platform圖1 雙處理器時(shí) MC－DQ與MC－Partition比較

Figure 2 Comparison between MC－DG and MC－Partition on four－processor platform圖2 四處理器時(shí) MC－DQ與MC－Partition比較

Figure 3 Comparison between MC－DG and MC－Partition on eight－processor platform圖3 八處理器時(shí)MC－DQ與MC－Partition比較

參照同樣考慮多處理器平臺(tái)上低關(guān)鍵級(jí)任務(wù)處理的文獻(xiàn)［9］，本文比較了算法 MC－DQ與文獻(xiàn)［9］中所提及的如下三種多關(guān)鍵級(jí)任務(wù)調(diào)度算法：

（1）TA：即通常的多關(guān)鍵級(jí)任務(wù)調(diào)度處理，一旦任務(wù)執(zhí)行時(shí)間超過其關(guān)鍵級(jí)的 WCET，那么系統(tǒng)關(guān)鍵級(jí)提升，而所有的任務(wù)均被拋棄；

（2）CD：在TA的基礎(chǔ)上，關(guān)鍵級(jí)提升后，一旦出現(xiàn)l級(jí)的空閑時(shí)間，則將系統(tǒng)關(guān)鍵級(jí)降至最低；

（3）CD－A：在 CD 基礎(chǔ)上，考慮容差（Allowance），進(jìn)一步約束系統(tǒng)關(guān)鍵級(jí)提升條件。

如圖4和圖5所示，本文算法在相同利用率情況下能獲得更大的可接受任務(wù)集，拋棄的任務(wù)比例比CD－A還要低14%左右，性能不受處理器個(gè)數(shù)的影響。

Figure 4 Tasks acceptable ratio of different scheduling algorithms with different utilizations圖4 不同調(diào)度算法在不同利用率下可接受任務(wù)集比例

5 結(jié)束語(yǔ)

Figure 5 Discarded tasks ration camparison of different scheduling algorigthms圖5 比較不同調(diào)度算法的拋棄任務(wù)集比例

盡管低關(guān)鍵級(jí)任務(wù)在安全性和重要性上要讓位于高關(guān)鍵級(jí)任務(wù)，但是其數(shù)據(jù)完整性和一致性對(duì)系統(tǒng)的正確執(zhí)行還是相當(dāng)有意義的。而實(shí)際任務(wù)執(zhí)行過程中，處理器上總是存在可觀的空閑時(shí)隙。因此，本文基于同構(gòu)多處理器平臺(tái)，一反目前混合關(guān)鍵級(jí)多任務(wù)調(diào)度中在高關(guān)鍵級(jí)運(yùn)行階段消極地對(duì)低關(guān)鍵級(jí)任務(wù)進(jìn)行拋棄的處理，動(dòng)態(tài)回收所有處理器的空閑時(shí)隙專供被拋棄的低關(guān)鍵級(jí)任務(wù)調(diào)度，并結(jié)合關(guān)鍵級(jí)提升前后的局部調(diào)度，以CPU利用率和系統(tǒng)可接受任務(wù)比例等作為性能衡量的主要指標(biāo)。本文的調(diào)度算法在確保高關(guān)鍵級(jí)任務(wù)滿足截止時(shí)限的同時(shí)，獲取了更好的整體性能。

實(shí)際上，對(duì)低關(guān)鍵級(jí)任務(wù)的處理可以借鑒（m，k）弱硬實(shí)時(shí)調(diào)度的相關(guān)調(diào)度方法，并充分考慮其偏離截止時(shí)限后價(jià)值函數(shù)的下降情況，整體系統(tǒng)可執(zhí)行任務(wù)數(shù)量可能尚會(huì)有進(jìn)一步的提升空間。

［1］ Vestal S.Preemptive scheduling of multi－criticality systems with varying degrees of execution time assurance［C］∥Proc of the 28th IEEE Real－Time Systems Symposium，2007：239－243.

［2］ Kumar C，Vyas S，Cytron R K，et al.Scheduling challenges in mixed－critical real－time heterogeneous computing platforms［C］∥Proc of International Conference on Computational Science，2013：1891－1898.

［3］ de Niz D，Lakshmanan K，Rajkumar R R.On the scheduling of mixed－criticality real－time task sets［C］∥Proc of the Real－Time Systems Symposium，2009：291－300.

［4］ Baruah S，Vestal S.Schedulability analysis of sporadic tasks with multiple criticality specifications［C］∥Proc of the 20th Euromicro Conference on Real－Time Systems，2008：147－155.

［5］ Baker T P，Baruah S K.Schedulability analysis of multiprocessor sporadic task systems［K］.Handbook of Real－Time and Embedded System，NC：Chapman Hall/CRC，2007.

［6］ Herman J，Kenna C，Mollison M，et al.RTOS support for multicore mixed－criticality systems［C］∥Proc of the 18th Real－Time and Embedded Technology and Applications Symposium，2012：197－208.

［7］ Lakshmanan K，de Niz D，Rajkumar R R，et al.Resource allocation in distributed mixed－criticality cyber－physical systems［C］∥Proc of the 30th International Conference of Distributed Computing Systems，2010：169－178.

［8］ Pathan R.Schedulability analysis of mixed－criticality systems on multiprocessors［C］∥Proc of the 24th Euromicro Conference on Real－Time Systems，2012：309－320.

［9］ Santy F，George L，Thierry P，et al.Relaxing mixed－criticality scheduling strictness for task sets scheduled with fp［C］∥Proc of the 24th Euromicro Conference on Real－Time Systems，2012：155－165.

［10］ Su Hang，Zhu Da－kai.An elastic mixed－criticality task model and its scheduling algorithm［C］∥Proc of IEEE/ACM Design，Automation，and Test in Europe，2013：147－152.

［11］ Liu J W S W.Real－time systems［M］.NJ：Prentice Hall PTR Upper Saddle River，2000.

［12］ Lauzac S，Melkem R，Mosse D.Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor［C］∥Proc of the 10th Euromicro Workshop on Real－Time Systems，1998：188－195.

［13］ Baruah S，Chattopadhyay B，Li H，et al.Mixed－criticality scheduling on multiprocessors［J］.Real－Time System，2013（49）：1－36.

［14］ Mixed Criticality Systems.Report from the Workshop on Mixed Criticality Systems Held on 03rd［R］.Belgium，2012.

［15］ Brandenburg B B，Anderson J H.Integrating hard/soft real－time tasks and best－effort jobs on multiprocessors［C］∥Proc of the 19th Euromicro Conference on Real－Time Systems，2007：61－70.

［16］ Baruah S K，Burns A，Davis R I.Response－time analysis for mixed criticality systems［C］∥Proc of 2011 IEEE Real－Time Systems Symposium，2011：34－43.

［17］ Ekberg P，Yi W.Outstanding paper award：Bounding and shaping the demand of mixed－criticality sporadic tasks［C］∥Proc of the 24th Euromicro Conference on Real－Time Systems，2012：135－144.