混合關(guān)鍵級多任務調(diào)度中低關(guān)鍵級任務的積極處理＊

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

（1.湖南大學嵌入式與網(wǎng)絡計算湖南省重點實驗室，湖南 長沙410082；2.廈門理工學院計算機與信息工程學院，福建 廈門361024）

1 引言

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

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

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

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

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

2 任務模型與定義

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

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

（2）Di表示任務τi的相對截止時限，Di≤Ti，在之后的討論中，任務均視為具有默認截止時限，即Di＝Ti。

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

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

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

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

CPU利用率（后文簡稱為利用率）為：

是任務的WCET與其周期的比值，即一個job的有效計算時間比率。對于混合關(guān)鍵級系統(tǒng)而言，因為每個任務在不同關(guān)鍵級的WCET可能是不同的，那么就應當考慮不同關(guān)鍵級的利用率。對于任意任務τi在不同關(guān)鍵級其相應的利用率為：

Table1 A set of mixed－criticality tasks表1 一個簡單混合關(guān)鍵級任務集示例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟3－1 記此時L－Que上的任務集為Γlow，每一個Γi∈Γlow，均具有

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

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

4 仿真實驗

鑒于文獻［16］的任務集被多篇文獻［9，17］參照應用，仿照其生成測試任務集，對MC－DQ算法進行了仿真實驗。依據(jù)不同CPU利用率可接受任務集占總?cè)蝿占谋壤谔幚砥鱾€數(shù)為2、4、8的情況下，與MC－Partition進行了比較，參見圖1～圖3。可以看到本文所述算法將接受任務集比例平均提高了31%左右，所增加的可接受任務均為當前一般MC調(diào)度中被消極拋棄的低關(guān)鍵級任務，性能提升不受處理器個數(shù)和利用率限制的影響。

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

［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.