基于響應(yīng)時間的混合關(guān)鍵級系統(tǒng)弱約束調(diào)度策略研究

金永賢 胡心潔

(浙江師范大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院 浙江 金華 321004)

0 引 言

在傳統(tǒng)實時系統(tǒng)執(zhí)行過程中，所有任務(wù)的響應(yīng)時間小于其截止期限可以保證系統(tǒng)的順利運行。其中響應(yīng)時間可通過Joseph等[1]提出的方法進(jìn)行計算。然而現(xiàn)如今的實時系統(tǒng)日益呈現(xiàn)功能多樣性、計算密集性、時效敏感性的特點，相應(yīng)的物理平臺越來越小，因此傳統(tǒng)的實時系統(tǒng)不再適用，要求不同重要性的任務(wù)共享同一個平臺，混合關(guān)鍵級系統(tǒng)應(yīng)運而生。與傳統(tǒng)的實時系統(tǒng)不同，混合關(guān)鍵級系統(tǒng)的任務(wù)根據(jù)重要性分為不同的關(guān)鍵等級，外部環(huán)境的變化會引起系統(tǒng)關(guān)鍵等級的變化，對應(yīng)的任務(wù)執(zhí)行模式也會發(fā)生變化，從而影響任務(wù)的可調(diào)度性。因此傳統(tǒng)實時系統(tǒng)的任務(wù)可調(diào)度算法不再適用于混合關(guān)鍵級系統(tǒng)，Vestal[2]首先建立混合關(guān)鍵級系統(tǒng)模型，提出響應(yīng)時間計算方法，并結(jié)合Audsley[3]提出的OPA算法對任務(wù)進(jìn)行優(yōu)先級分配。

研究人員在文獻(xiàn)[2]模型的基礎(chǔ)上進(jìn)行研究，系統(tǒng)多以任務(wù)的最壞情況執(zhí)行時間(WCET)作為關(guān)鍵參數(shù)(關(guān)鍵參數(shù)是任務(wù)參數(shù)中因系統(tǒng)關(guān)鍵級改變而變化的參數(shù))，且保證高關(guān)鍵級任務(wù)的正確執(zhí)行，通常需要犧牲低關(guān)鍵級任務(wù)的執(zhí)行時間。但在實際應(yīng)用中，簡單地丟棄低關(guān)鍵級任務(wù)可能造成資源的浪費以及數(shù)據(jù)完整性的破壞[4]，且頻繁地丟棄任務(wù)也會增加開銷。對此，研究人員開始研究積極調(diào)度低關(guān)鍵級任務(wù)的方法：在關(guān)鍵級提升時，不采用簡單地丟棄低關(guān)鍵級任務(wù)的方法，而將其以較低的服務(wù)水平執(zhí)行，從而保證系統(tǒng)穩(wěn)定執(zhí)行，提高資源利用率。

Gettings等[5]在雙關(guān)鍵級任務(wù)模型下提出積極調(diào)度低關(guān)鍵級任務(wù)的方法：在系統(tǒng)進(jìn)入高關(guān)鍵級階段后，低關(guān)鍵級任務(wù)以弱約束的模式繼續(xù)執(zhí)行，即允許低關(guān)鍵級任務(wù)連續(xù)幾個工作業(yè)不執(zhí)行，并提出兩個調(diào)度策略，這兩個調(diào)度策略有一定局限性，在實際應(yīng)用中任務(wù)關(guān)鍵級通常多于2個，如：適用于商用飛行器的RTCA DO.178B航空電子軟件標(biāo)準(zhǔn)將任務(wù)劃分為成5個安全保證等級；ISO26262將任務(wù)劃分為4個安全等級。對此本文建立混合多關(guān)鍵級模型，改進(jìn)弱約束模式，并基于響應(yīng)時間分析提出調(diào)度策略。

1 相關(guān)研究

針對經(jīng)典的混合關(guān)鍵級模型，研究人員已基于響應(yīng)時間計算提出了幾種調(diào)度策略。Baruah等[6]在Vestal基礎(chǔ)上進(jìn)行進(jìn)一步研究，以混合雙關(guān)鍵級系統(tǒng)為模型提出了SMC、AMC調(diào)度策略。文獻(xiàn)[7]將AMC調(diào)度策略擴(kuò)展到多關(guān)鍵級系統(tǒng)；文獻(xiàn)[8]以悲觀周期作為關(guān)鍵參數(shù)，基于響應(yīng)時間分析提出調(diào)度算法；文獻(xiàn)[9]提出一種新的計算響應(yīng)時間的方法，關(guān)注系統(tǒng)提升時任務(wù)自身的執(zhí)行時間，降低了響應(yīng)時間計算的復(fù)雜度。Burns等[10]進(jìn)一步改進(jìn)混合關(guān)鍵系統(tǒng)模型，加入可容錯的概念，保證系統(tǒng)魯棒性和可調(diào)度性之間的平衡。

在低關(guān)鍵級任務(wù)積極調(diào)度的研究方面，趙瑞姣等[11]針對異構(gòu)多處理器調(diào)度中存在的問題，引入回收隊列重新調(diào)度被丟棄的任務(wù)，從而提高低關(guān)鍵級任務(wù)的調(diào)度比率。Bernat等[12]提出弱實時系統(tǒng)的概念，允許任務(wù)在某幾個釋放周期錯過截止期限。文獻(xiàn)[5]將弱實時系統(tǒng)的概念引入到混合關(guān)鍵系統(tǒng)中，實現(xiàn)低關(guān)鍵級任務(wù)的弱約束模式執(zhí)行。此外，許多研究人員引入彈性模型對低關(guān)鍵級任務(wù)進(jìn)行積極調(diào)度，其中Su等[13]使用提前釋放策略,將高關(guān)鍵級任務(wù)執(zhí)行時產(chǎn)生的空閑時隙分配給低關(guān)鍵級任務(wù)執(zhí)行，低關(guān)鍵級任務(wù)釋放周期可以彈性調(diào)整，選擇合適的空閑時隙執(zhí)行。文獻(xiàn)[14]將該算法進(jìn)行改進(jìn)使其適用于多處理器平臺。黃麗達(dá)等[15]也使用了彈性調(diào)度模型的調(diào)度算法，積極地調(diào)度低關(guān)鍵級任務(wù)。文獻(xiàn)[16]根據(jù)系統(tǒng)負(fù)載的變化，實現(xiàn)任務(wù)周期的動態(tài)延伸或壓縮，從而保證更多任務(wù)執(zhí)行，提高了處理器利用率。Ren等[17]將任務(wù)進(jìn)行分組，高關(guān)鍵級任務(wù)只能影響與其同組的低關(guān)鍵級任務(wù)的執(zhí)行，從而提升低關(guān)鍵級任務(wù)的可調(diào)度性。文獻(xiàn)[18]引入重要性概念，對低關(guān)鍵級任務(wù)進(jìn)行重要性分配，低關(guān)鍵級任務(wù)按照其重要性的逆序被丟棄。Chen等[19]提出一種靈活的混合關(guān)鍵級模型，在關(guān)鍵級提升時，只有溢出任務(wù)本身被認(rèn)為表現(xiàn)出高關(guān)鍵級行為，而其他高關(guān)鍵級任務(wù)仍然保持以前相同的模式執(zhí)行，能夠在保證系統(tǒng)可調(diào)度的同時確定低關(guān)鍵性任務(wù)的最大可執(zhí)行時間。

2 任務(wù)模型及相關(guān)概念

2.1 任務(wù)模型

首先建立混合多關(guān)鍵級系統(tǒng)的任務(wù)模型：在單處理器可搶占平臺上，包含N個獨立任務(wù)的任務(wù)集τ(τ1，τ2，…，τn)等待運行，且不同關(guān)鍵級的任務(wù)共享一個平臺。下面定義任務(wù)參數(shù)和執(zhí)行模式。

用系統(tǒng)參數(shù)L={L1，L2，…，Lm}表示系統(tǒng)當(dāng)前關(guān)鍵等級，L1為系統(tǒng)的初始關(guān)鍵等級，Lm為系統(tǒng)可達(dá)到的最高關(guān)鍵等級。

任務(wù)參數(shù)可描述任務(wù)執(zhí)行模式。每個任務(wù)τi有6個參數(shù)(Ci，Ti，Di，Li，(m,sLi(L)),pi)，Ti為任務(wù)周期，Di為隱含式截止期限(Di=Ti)，pi代表任務(wù)的優(yōu)先級，Li為任務(wù)關(guān)鍵等級，任務(wù)最壞情況響應(yīng)時間向量Ci=(Ci(L1)，Ci(L2),…,Ci(Ln))，參數(shù)(m,sLi(L))規(guī)定任務(wù)的弱約束執(zhí)行模式。

任務(wù)的執(zhí)行模式。任務(wù)的最壞情況執(zhí)行時間在系統(tǒng)處于不同關(guān)鍵等級時有以下關(guān)系：當(dāng)L

2.2 相關(guān)概念

響應(yīng)時間：本文在線下對任務(wù)的工作業(yè)從釋放到執(zhí)行完畢經(jīng)歷的總時間做出估計，這個值為任務(wù)的響應(yīng)時間。

任務(wù)執(zhí)行窗口：已知τi首個工作業(yè)在0時刻釋放，響應(yīng)時間為Ri，(0，Ri)即為τi的執(zhí)行窗口。

任務(wù)可調(diào)度：若任務(wù)τi可被分配合適的優(yōu)先級，則判定τi為可調(diào)度。

可調(diào)度任務(wù)集：若所有τi∈τ都可被分配到合適的優(yōu)先級，則該任務(wù)集稱為可調(diào)度任務(wù)集。

3 優(yōu)先級分配策略

τ為待分配優(yōu)先級的任務(wù)集。結(jié)合OPA算法[3]對τ中的每個任務(wù)進(jìn)行優(yōu)先級分配，以此判斷任務(wù)集的可調(diào)度性，如算法1所示。

算法1WE-OPA

輸入：任務(wù)集τ。

輸出：任務(wù)集τ的優(yōu)先順序集P。

functionFLAG(τ)

fork=N→1do

flag←false

fori=1→length(τi)do

pi←ki

flag←true

τi←[]

break

end if

end for

if flag=flase then

return failure

end if

end for

return success

end function

4 響應(yīng)時間

任務(wù)模型基于可搶占處理器平臺，因此任務(wù)執(zhí)行時會受到高優(yōu)先級任務(wù)的搶占而產(chǎn)生干擾時間。由算法1可知，τi在待分配任務(wù)集中處于最低優(yōu)先級，除τi外的其他任務(wù)為干擾任務(wù)，生成一個集合hp(i)。現(xiàn)判斷τi是否可調(diào)度，根據(jù)文獻(xiàn)[20]，任務(wù)總響應(yīng)時間為本身執(zhí)行時間與hp(i)中的任務(wù)產(chǎn)生的干擾時間的總和，而本文為區(qū)分任務(wù)的關(guān)鍵級別，hp(i)集合又以系統(tǒng)當(dāng)前關(guān)鍵等級L為界限分成兩個子集，對應(yīng)的干擾時間表示為ILj

Ri(l)=Ci(l)+ILj

(1)

4.1 干擾時間分析

干擾任務(wù)τj∈hp(i)在τi的執(zhí)行窗口內(nèi)以固定周期Tj釋放多個工作業(yè)。傳統(tǒng)實時系統(tǒng)的干擾時間[20]：

(2)

首先求出干擾任務(wù)τj在τi執(zhí)行窗口內(nèi)釋放的工作業(yè)總數(shù)(Ri(l))/Tj，與任務(wù)i的最壞情況執(zhí)行時間相乘，類似地得出干擾時間總和。本文在該公式的基礎(chǔ)上進(jìn)行演變，分析系統(tǒng)在不同執(zhí)行模式下的干擾時間。

4.2 響應(yīng)時間的靜態(tài)部分和關(guān)鍵等級切換部分

系統(tǒng)運行時需經(jīng)歷穩(wěn)定運行和關(guān)鍵等級切換兩個階段，干擾任務(wù)在這兩個階段對τi產(chǎn)生的干擾時間也不一致。因此τi的響應(yīng)時間分為兩部分：靜態(tài)部分和關(guān)鍵級切換部分。

4.2.1靜態(tài)部分

假設(shè)當(dāng)前系統(tǒng)穩(wěn)定在關(guān)鍵等級k運行，干擾任務(wù)在τi的執(zhí)行窗口內(nèi)有穩(wěn)定的執(zhí)行模式，對于每個τj∈hp(i)，可在整個執(zhí)行窗口內(nèi)確定實際執(zhí)行的工作業(yè)個數(shù)，修改式(2)為：

(3)

4.2.2關(guān)鍵級切換部分

干擾任務(wù)的最壞情況執(zhí)行時間和實際執(zhí)行工作業(yè)數(shù)量隨著系統(tǒng)關(guān)鍵等級動態(tài)變化。假設(shè)系統(tǒng)關(guān)鍵等級已提升至L，可對執(zhí)行窗口進(jìn)行劃分，以關(guān)鍵等級提升經(jīng)歷的時間段作為一個子窗口，如系統(tǒng)關(guān)鍵等級從k提升至k+1對應(yīng)的子窗口為(Ri(k)，Ri(k+1))，Ri(k)是系統(tǒng)關(guān)鍵等級在k穩(wěn)定運行時τi的靜態(tài)響應(yīng)時間。分別計算每個子窗口的干擾時間，并求出總干擾時間：

(4)

特別地，ε取值為L-1時，對應(yīng)的子窗口為(Ri(L-1)，Ri(L))，Ri(L)作為響應(yīng)時間值參與迭代計算。

4.3 基于響應(yīng)時間分析的傳統(tǒng)調(diào)度策略

比較的調(diào)度策略有SMC、AMC-arb-x以及AMC-max-x。SMC由Baruah等[6]提出，規(guī)定所有任務(wù)執(zhí)行時間不超過自身關(guān)鍵級對應(yīng)的Ci(Li)，只在靜態(tài)條件下分析響應(yīng)時間，而AMC進(jìn)一步地考慮關(guān)鍵級的提升對響應(yīng)時間的影響，Li等[21]在Fleming等[7]的基礎(chǔ)上完善了混合多關(guān)鍵級系統(tǒng)的調(diào)度策略：包括SMC和AMC-arb-x和AMC-max-x。

4.4 弱約束執(zhí)行模式參數(shù)分配規(guī)則

現(xiàn)有的弱約束執(zhí)行模式只適用于雙關(guān)鍵系系統(tǒng)，且規(guī)定任務(wù)的幾個工作業(yè)必須連續(xù)“跳過”執(zhí)行[5]，而本文的執(zhí)行模式消除了這個限制，并擴(kuò)展至多關(guān)鍵級系統(tǒng)。假設(shè)系統(tǒng)當(dāng)前關(guān)鍵等級為L，對于所有τi∈τ，LisLi+1(L)。例如系統(tǒng)關(guān)鍵等級由2提升到3，Li=2的任務(wù)以(m，s2(3))的約束模式執(zhí)行；系統(tǒng)關(guān)鍵等級由3提升到4時，Li=3的任務(wù)以(m，s3(4))約束模式執(zhí)行，Li=2的任務(wù)以(m，s2(4))的約束模式執(zhí)行，有s2(3)=s3(4)，s2(4)>s3(4)。

4.5 兩種調(diào)度策略的主要區(qū)別

調(diào)度策略AMCwe-x和AMCwemax-x響應(yīng)時間計算重點有兩個方面：(1) 根據(jù)弱約束模式的分配規(guī)則計算干擾任務(wù)在執(zhí)行窗口內(nèi)實際執(zhí)行的工作業(yè)數(shù)量；(2) 確定干擾任務(wù)不同工作業(yè)的最壞情況執(zhí)行時間。區(qū)別在于兩個調(diào)度策略對子窗口的劃分方式不同，且干擾任務(wù)工作業(yè)的最壞情況執(zhí)行時間有不同的變化趨勢。

關(guān)鍵等級提升至L需經(jīng)歷L-1次提升階段，AMC-we-x調(diào)度策略沒有精準(zhǔn)確定系統(tǒng)關(guān)鍵等級提升的時間點，將干擾任務(wù)在τi的整個執(zhí)行窗口(0，Ri(L))釋放的工作業(yè)的最壞情況執(zhí)行時間都估計為Cj(L)，而忽略系統(tǒng)關(guān)鍵級提升過程中Cj值的變化。AMC-we-max-x策略設(shè)定L-1個提升的時間點，并以提升點調(diào)整子窗口，每個子窗口內(nèi)釋放的工作業(yè)最壞情況有不同的估值。因此AMC-we-x策略悲觀估計了干擾任務(wù)工作業(yè)的最壞情況執(zhí)行時間，在響應(yīng)時間計算的精確方面低于AMC-we-max-x，但AMC-we-max-x調(diào)度策略需枚舉所有提升序列對應(yīng)的響應(yīng)時間，算法復(fù)雜程度較高。

4.6 AMC-we-x

假設(shè)在系統(tǒng)關(guān)鍵等級為L時對任務(wù)進(jìn)行調(diào)度，由分配算法可知需計算τi響應(yīng)時間以判斷該任務(wù)是否可調(diào)度。

4.6.1靜態(tài)部分響應(yīng)時間

系統(tǒng)需經(jīng)歷L個穩(wěn)定運行階段。現(xiàn)討論系統(tǒng)穩(wěn)定在關(guān)鍵等級k(k∈(1，L-1))時任務(wù)的響應(yīng)時間。可根據(jù)弱約束執(zhí)行模式計算兩部分干擾時間，從而求得響應(yīng)時間Ri(k)，過程如下：

1)ILj

(5)

第一部分為τi執(zhí)行窗口(0，Ri(k))內(nèi)τj釋放的工作業(yè)總數(shù)，第二部分為應(yīng)“跳過”的工作業(yè)個數(shù)。

2)Lj≥k的干擾任務(wù)在τi的執(zhí)行窗口內(nèi)以正常模式執(zhí)行，即sLj(k)=0,τj釋放的總工作業(yè)即為實際執(zhí)行的工作業(yè)：

(6)

另一方面，干擾任務(wù)τj在τi執(zhí)行窗口內(nèi)有固定的最壞情況執(zhí)行時間Ci(k)，Lj

Cj(Lj)

(7)

(8)

將式(7)和式(8)代入式(1)，可求出靜態(tài)部分總響應(yīng)時間：

Cj(Lj)

(9)

4.6.2關(guān)鍵級切換部分響應(yīng)時間計算

1)ILj≥l(l)部分，干擾任務(wù)τj在整個執(zhí)行窗口內(nèi)沒有工作業(yè)丟失，且τj所有工作業(yè)的最壞情況執(zhí)行時間為Cj(L)，干擾時間計算如下：

(10)

2)ILj

(11)

τj在τi的執(zhí)行窗口內(nèi)應(yīng)跳過的工作業(yè)總數(shù)如下：

(12)

由此可得出總響應(yīng)時間為：

(13)

若待分配任務(wù)τi的關(guān)鍵等級小于L，由于具體的關(guān)鍵級提升點未知，可假設(shè)任務(wù)τi首個工作業(yè)沒有被丟棄，且干擾任務(wù)在τi窗口內(nèi)沒有工作業(yè)跳過。響應(yīng)時間為：

(14)

4.7 AMC-we-max-x

現(xiàn)確定關(guān)鍵級提升的時間點，從k提升至k+1的提升點tk在(Ri(k-1),Ri(k))之間，τj在tk前釋放的工作業(yè)最壞情況執(zhí)行時間仍為k-1關(guān)鍵等級對應(yīng)的Cj(k-1)，tk后釋放的工作業(yè)最壞情況執(zhí)行時間為Ci(k)。如圖1所示，以提升點為分界調(diào)整子窗口，將(tk，tk+1)作為系統(tǒng)關(guān)鍵等級處于k+1階段的子窗口。

圖1 調(diào)整任務(wù)子窗口

1) 計算ILj

(15)

已知系統(tǒng)關(guān)鍵等級k

(16)

2)ILj≥l部分的干擾時間如下：

(17)

干擾任務(wù)在(tk,tk+1)子窗口對應(yīng)的最壞情況執(zhí)行時間為Cj(k+1)。

綜上，得到總響應(yīng)時間計算公式：

(18)

5 實 驗

實驗參數(shù)：任務(wù)集包含的任務(wù)數(shù)量N，任務(wù)周期Ti：在10 ns～1 s范圍內(nèi)按均勻分布生成。任務(wù)集利用率u采用UUnifast算法生成[22]，可以通過任務(wù)集總利用率和任務(wù)個數(shù)生成每個任務(wù)的利用率。系統(tǒng)最大關(guān)鍵等級Lm。任務(wù)執(zhí)行時間Ci(L)：L1關(guān)鍵等級下τi的最壞情況執(zhí)行時間Ci(L)=u×T。不同關(guān)鍵級的最壞情況執(zhí)行時間有如下關(guān)系：Ci(L+1)=cf×Ci(L)。cf為Ci的關(guān)鍵級擴(kuò)展參數(shù)。不同關(guān)鍵級的任務(wù)所占比率cp=(cp0,cp1,…,cpm)。cpk代表關(guān)鍵級為k的任務(wù)所占比率。弱約束執(zhí)行模式參數(shù)(m，sLi(L))。

通過六組實驗對比相同任務(wù)集在AMC-arb-x、AMC-max-x、SMC、AMC-we-x、AMC-we-max-x 5個調(diào)度策略下估計所得的可調(diào)度比率以及低關(guān)鍵級任務(wù)丟棄比率。

除實驗四和實驗六外，弱約束模式中的參數(shù)值取為s2(3)=s1(2)=1,s1(3)=2，N取固定值20，可調(diào)度比率f(p)=可調(diào)度任務(wù)集個數(shù)/總?cè)蝿?wù)集個數(shù)。

實驗一分析利用率變化對任務(wù)集可調(diào)度比率的影響，u在(0.025，0.975)之間變化，步長為0.025，每個利用率下生成1 000個任務(wù)集，結(jié)果如圖2所示。

圖2 任務(wù)可調(diào)度比率隨u變化曲線

實驗二至實驗五分析cp、cf、弱約束模式參數(shù)變化與可調(diào)度比率的關(guān)系，使用加權(quán)可調(diào)度比率公式[20]：

(19)

式中：Wy(p)代表參數(shù)p下由算法y計算得到的加權(quán)任務(wù)可調(diào)度比率；sy(τ,p)表示任務(wù)τ集在參數(shù)p下用算法y計算得到的可調(diào)度比率；u(τ)表示總利用率，在每個參數(shù)p下計算在利用率(0.025,0.975)之間任務(wù)的可調(diào)度比率，且每個利用率生成100個任務(wù)集。

實驗二觀察cp值變化對任務(wù)可調(diào)度比率的影響，如圖3所示。

圖3 任務(wù)可調(diào)度比率隨cp3變化曲線

實驗三觀察cf變化時任務(wù)可調(diào)度比率的變化趨勢，如圖4所示。

圖4 任務(wù)可調(diào)度比率隨cf變化曲線

實驗四通過改變參數(shù)s，觀測任務(wù)集可調(diào)度比率的變化趨勢，如圖5所示。

圖5 任務(wù)可調(diào)度比率隨s變化曲線

實驗五通過改變參數(shù)m，觀測任務(wù)集可調(diào)度比率的變化趨勢，如圖6所示。

圖6 任務(wù)可調(diào)度比率隨m變化曲線

實驗六通過改變參數(shù)s，研究Li<3的任務(wù)丟棄比率變化趨勢，如圖7所示。

圖7 丟棄工作業(yè)數(shù)量隨s變化曲線

可得出以下結(jié)論：在所有調(diào)度策略下任務(wù)集的可調(diào)度比率隨著u、cf、cp的增加而下降，AMC-we-max-x以及AMC-max-x的整體調(diào)度性能分別優(yōu)于AMC-we-x以及AMC-arb-x。

表1和表2分別為AMC-we-max-x提升比率隨cp3和cf的變化情況。可以看出，當(dāng)Li=3的任務(wù)所占比例為0.1時，AMC-we-x與AMC-we-max-x的任務(wù)可調(diào)度比率接近，隨著cp3的增大兩者差距呈現(xiàn)增長趨勢，說明AMC-we-max-x策略對有較多高關(guān)鍵級任務(wù)的任務(wù)集的調(diào)度有明顯優(yōu)勢。cp值在0.4左右時提升效果最明顯。同樣地，當(dāng)cf取值2.2左右時，AMC-we-max-x任務(wù)可調(diào)度優(yōu)勢比較明顯。

表1 AMC-we-max-x提升比率隨cp3變化情況

表2 AMC-we-max-x提升比率隨cf變化情況

續(xù)表2

對比實驗四到實驗六數(shù)據(jù)，分析弱約束執(zhí)行模式參數(shù)的變化對任務(wù)可調(diào)度比率的影響，當(dāng)m=sLi(L)時，AMC-we-x與AMC-we-max-x的執(zhí)行模式與AMC-arb-x與AMC-max相同，因此任務(wù)可調(diào)度比率也一致(見圖5-圖6)。當(dāng)固定sLi(L)值，改變m，因為隨著m增加，Li<3任務(wù)工作業(yè)的丟棄比率減少，導(dǎo)致整體調(diào)度比率下降；同理，隨著s增加，Li<3任務(wù)丟棄的工作業(yè)增加(見圖7)，整體調(diào)度比率隨之增加。

6 結(jié) 語

本文建立了一種新的混合多關(guān)鍵級任務(wù)模型，并基于響應(yīng)時間分析提出兩種調(diào)度策略，在系統(tǒng)未實際運行前對任務(wù)集進(jìn)行優(yōu)先級分配，并在悲觀條件下分析可調(diào)度比率。修改了原有的弱約束執(zhí)行模式并擴(kuò)展至多關(guān)鍵級，給任務(wù)在不同系統(tǒng)關(guān)鍵級下設(shè)置對應(yīng)的弱約束執(zhí)行模式參數(shù)，通過實驗得出結(jié)論：由于AMC-we-x和AMC-we-max-x沒有簡單地丟棄所有低關(guān)鍵級任務(wù)工作業(yè)，因此線下估計的整體調(diào)度比率較AMC-arb-x和AMC-max-x有所下降，而任務(wù)實際運行時的執(zhí)行時間往往小于Ci值，低關(guān)鍵級任務(wù)的弱約束執(zhí)行對高關(guān)鍵級任務(wù)的實際影響小于估計值，因此本文提出調(diào)度策略能夠在保證高關(guān)鍵級任務(wù)正確執(zhí)行的情況下提升低關(guān)鍵級任務(wù)的調(diào)度比率，從而減少丟棄任務(wù)的開銷，提高資源利用率。此外，AMC-we-max-x策略的響應(yīng)時間計算精確度較高，估計所得的任務(wù)集可調(diào)度比率整體高于AMC-we-x。在實際應(yīng)用中，可以根據(jù)任務(wù)的性能分配弱約束模式中的參數(shù)值，為任務(wù)的服務(wù)水平提供多種選擇。