金永賢 胡心潔

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

0 引 言

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

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

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

1 相關(guān)研究

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

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

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

2.1 任務(wù)模型

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

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

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

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

2.2 相關(guān)概念

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

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

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

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

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

τ為待分配優(yōu)先級(jí)的任務(wù)集。結(jié)合OPA算法[3]對(duì)τ中的每個(gè)任務(wù)進(jìn)行優(yōu)先級(jí)分配，以此判斷任務(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)時(shí)間

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

Ri(l)=Ci(l)+ILj

(1)

4.1 干擾時(shí)間分析

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

(2)

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

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

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

4.2.1靜態(tài)部分

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

(3)

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

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

(4)

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

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

比較的調(diào)度策略有SMC、AMC-arb-x以及AMC-max-x。SMC由Baruah等[6]提出，規(guī)定所有任務(wù)執(zhí)行時(shí)間不超過自身關(guān)鍵級(jí)對(duì)應(yīng)的Ci(Li)，只在靜態(tài)條件下分析響應(yīng)時(shí)間，而AMC進(jìn)一步地考慮關(guān)鍵級(jí)的提升對(duì)響應(yīng)時(shí)間的影響，Li等[21]在Fleming等[7]的基礎(chǔ)上完善了混合多關(guān)鍵級(jí)系統(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ù)的幾個(gè)工作業(yè)必須連續(xù)“跳過”執(zhí)行[5]，而本文的執(zhí)行模式消除了這個(gè)限制，并擴(kuò)展至多關(guān)鍵級(jí)系統(tǒng)。假設(shè)系統(tǒng)當(dāng)前關(guān)鍵等級(jí)為L(zhǎng)，對(duì)于所有τi∈τ，LisLi+1(L)。例如系統(tǒng)關(guān)鍵等級(jí)由2提升到3，Li=2的任務(wù)以(m，s2(3))的約束模式執(zhí)行；系統(tǒng)關(guān)鍵等級(jí)由3提升到4時(shí)，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)時(shí)間計(jì)算重點(diǎn)有兩個(gè)方面：(1) 根據(jù)弱約束模式的分配規(guī)則計(jì)算干擾任務(wù)在執(zhí)行窗口內(nèi)實(shí)際執(zhí)行的工作業(yè)數(shù)量；(2) 確定干擾任務(wù)不同工作業(yè)的最壞情況執(zhí)行時(shí)間。區(qū)別在于兩個(gè)調(diào)度策略對(duì)子窗口的劃分方式不同，且干擾任務(wù)工作業(yè)的最壞情況執(zhí)行時(shí)間有不同的變化趨勢(shì)。

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

4.6 AMC-we-x

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

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

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

1)ILj

(5)

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

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

(6)

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

Cj(Lj)

(7)

(8)

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

Cj(Lj)

(9)

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

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

(10)

2)ILj

(11)

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

(12)

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

(13)

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

(14)

4.7 AMC-we-max-x

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

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

1) 計(jì)算ILj

(15)

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

(16)

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

(17)

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

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

(18)

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

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

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

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

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

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

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

(19)

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)六通過改變參數(shù)s，研究Li<3的任務(wù)丟棄比率變化趨勢(shì)，如圖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時(shí)，AMC-we-x與AMC-we-max-x的任務(wù)可調(diào)度比率接近，隨著cp3的增大兩者差距呈現(xiàn)增長(zhǎng)趨勢(shì)，說明AMC-we-max-x策略對(duì)有較多高關(guān)鍵級(jí)任務(wù)的任務(wù)集的調(diào)度有明顯優(yōu)勢(shì)。cp值在0.4左右時(shí)提升效果最明顯。同樣地，當(dāng)cf取值2.2左右時(shí)，AMC-we-max-x任務(wù)可調(diào)度優(yōu)勢(shì)比較明顯。

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

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

續(xù)表2

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

6 結(jié) 語(yǔ)

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