一種多特征參數(shù)的多級表設(shè)計(jì)方法

一種多特征參數(shù)的多級表設(shè)計(jì)方法

優(yōu)先級交付算法廣泛應(yīng)用于實(shí)時(shí)系統(tǒng)。這些算法主要包括單調(diào)率算法（rv）、最短的阻塞時(shí)間（idf）、最短的休息時(shí)間（lsf）、最高的價(jià)值（hvf）、價(jià)值密度最高的排名（hvf）等。在這些算法中，任務(wù)的優(yōu)先性是基于任務(wù)的幾個(gè)資源參數(shù)，例如初始阻塞時(shí)間和初始阻塞時(shí)間。對于hvf來說，初始阻塞時(shí)間和最重要的任務(wù)（即任務(wù)的價(jià)值或價(jià)值）。然而，對于基于特定資源的優(yōu)先性，例如，edf戰(zhàn)略是將最高優(yōu)先權(quán)限設(shè)置為具有最短的休息時(shí)間的任務(wù)，lsf戰(zhàn)略是將最高優(yōu)先權(quán)限指定給具有最短的休閑時(shí)間的任務(wù)。對于基于傳統(tǒng)系統(tǒng)負(fù)荷的算法，它們通常是最好的，但在加載期間，系統(tǒng)無法確保所有任務(wù)都可以滿足加載期間的要求。在這種情況下，基于價(jià)值的hvf算法可以優(yōu)先考慮具有最重要價(jià)值的任務(wù)，并進(jìn)行更高級的服務(wù)?；趦r(jià)值的分布模式，如hvf，可以優(yōu)先考慮具有最重要價(jià)值的任務(wù)，例如，在段或段的情況下，最重要的任務(wù)不會等待完成，但即使在加載期間，系統(tǒng)也必須確保完成重要任務(wù)，并確保網(wǎng)絡(luò)系統(tǒng)的性能優(yōu)雅，不會出現(xiàn)系統(tǒng)崩潰。基于價(jià)值的分布模式的算法，如hvf，可以優(yōu)先考慮具有最重要價(jià)值的任務(wù)，在過載情況下提供系統(tǒng)的性能降級?；趦r(jià)值分配算法的相關(guān)性指標(biāo)通常基于系統(tǒng)執(zhí)行的累積價(jià)值來衡量。因此，hvmf算法是一種貪婪的算法，總是假設(shè)具有高價(jià)值密度和最小空閑時(shí)間的任務(wù)很快完成。因此，執(zhí)行最高價(jià)值密度的任務(wù)需要大量的積累價(jià)值，并且往往會導(dǎo)致許多任務(wù)不相交。許多研究表明,優(yōu)先級驅(qū)動的調(diào)度算法應(yīng)該綜合任務(wù)的關(guān)鍵性與截止期兩個(gè)獨(dú)立的特征參數(shù).例如,最大努力(besteffort,簡稱BE)算法基于任務(wù)的價(jià)值密度來接納任務(wù),但是按照EDF策略調(diào)度這些任務(wù),盡管這種算法在不考慮算法復(fù)雜性與調(diào)度開銷的情況下優(yōu)于基于單特征參數(shù)的調(diào)度算法,如EDF或LSF,但是文獻(xiàn)所進(jìn)行的實(shí)驗(yàn)結(jié)果表明,BE算法在系統(tǒng)過載的情況下會有非常大的系統(tǒng)開銷.文獻(xiàn)提出了關(guān)鍵性-截止期優(yōu)先(criticalness-deadlinefirst,簡稱CDF)算法,每個(gè)任務(wù)在到達(dá)時(shí)基于(相對截止期÷關(guān)鍵性)分配優(yōu)先級,實(shí)驗(yàn)表明基于CDF的CPU調(diào)度,相對于單獨(dú)使用截止期或者關(guān)鍵性作為特征參數(shù)的算法,能夠很大地改進(jìn)系統(tǒng)的綜合性能.文獻(xiàn)對4種調(diào)度策略:EDF,HVF,HVDF與MIX進(jìn)行了綜合仿真研究,其中MIX算法的優(yōu)先級pi=(α)Vi-(1-α)di,pi,Vi與di分別表示任務(wù)i的優(yōu)先級、價(jià)值與截止期,這4種策略被進(jìn)一步擴(kuò)展,以兩種方式管理過載,或者簡單地拒絕到來的任務(wù)或者移去最小價(jià)值的任務(wù),直到排除過載為止.研究的結(jié)論是,在過載前按截止期調(diào)度,在過載期間按價(jià)值調(diào)度,這樣,在大多數(shù)實(shí)際情況下表現(xiàn)最好.文獻(xiàn)描述了一個(gè)綜合離線調(diào)度與基于價(jià)值的動態(tài)調(diào)度的運(yùn)行時(shí)調(diào)度方法,要求所有定期任務(wù)必須離線地調(diào)度,而通過過載檢測方法來防止動態(tài)到達(dá)的非定期任務(wù)導(dǎo)致系統(tǒng)過載,并把過載處理問題形式化為二元最優(yōu)化問題.這個(gè)算法與BE算法類似,會有較大的運(yùn)行時(shí)開銷.總的來說,上述算法存在以下不足之處:(1)由于任務(wù)的截止期與價(jià)值是兩個(gè)完全不同的概念,其取值范圍也不同,因此不能簡單地將它們進(jìn)行加權(quán)運(yùn)算;(2)由于操作系統(tǒng)或者調(diào)度系統(tǒng)通常只支持有限的優(yōu)先級,CDF與MIX算法所計(jì)算的優(yōu)先級必須轉(zhuǎn)換到系統(tǒng)所支持的優(yōu)先級層次上,因此會導(dǎo)致不同的任務(wù)具有相同的優(yōu)先級;(3)BE之類的啟發(fā)式算法具有較大的系統(tǒng)開銷,特別是在系統(tǒng)過載的情況下,較高的過載處理開銷會更加嚴(yán)重地影響系統(tǒng)性能.為了克服這些問題,本文提出了基于優(yōu)先級表的實(shí)時(shí)調(diào)度算法,其中任務(wù)的優(yōu)先級不再通過對其特征參數(shù)進(jìn)行算術(shù)運(yùn)算來分配,而是通過排序充分體現(xiàn)任務(wù)的特征參數(shù)之間的序列關(guān)系.這種算法不僅能夠用來綜合任務(wù)的價(jià)值與截止期兩個(gè)特征參數(shù),而且同樣適用于在調(diào)度中綜合考慮任務(wù)的其他任何兩個(gè)特征參數(shù),甚至綜合任務(wù)的3個(gè)不同的特征參數(shù).本文重點(diǎn)討論了綜合任務(wù)的截止期與價(jià)值的優(yōu)先級表設(shè)計(jì)方法,提出了EDV(earliestdeadlinevalue)與VED(valueearliestdeadline)兩種調(diào)度算法,給出了基于多重鏈表的算法實(shí)現(xiàn),并進(jìn)行了仿真實(shí)驗(yàn)與分析.1調(diào)度執(zhí)行的任務(wù)具有絕對截止期在描述具體的調(diào)度算法之前,首先給出任務(wù)及其參數(shù)的定義與表示.假設(shè)存在任務(wù)Ji,具有下面的參數(shù):·ai表示任務(wù)的到達(dá)時(shí)間,即任務(wù)被啟動并準(zhǔn)備執(zhí)行的時(shí)間;·Ci表示任務(wù)的最壞情形執(zhí)行時(shí)間,即任務(wù)在最壞情況下無中斷執(zhí)行所需的處理器時(shí)間;·ci表示任務(wù)的剩余執(zhí)行時(shí)間,即任務(wù)的最壞情況執(zhí)行時(shí)間與任務(wù)已經(jīng)執(zhí)行時(shí)間之差;·di表示任務(wù)的絕對截止期,即任務(wù)在這個(gè)時(shí)間應(yīng)該完成執(zhí)行并產(chǎn)生一個(gè)有價(jià)值的結(jié)果(在后面的討論中,如果沒有特別說明,我們所說的截止期都是指任務(wù)的絕對截止期);·Di表示任務(wù)的相對截止期,有Di=di-ai;·Vi表示任務(wù)的價(jià)值,即任務(wù)的關(guān)鍵性,該任務(wù)相對于任務(wù)集中其他任務(wù)的重要程度;·fi表示任務(wù)的完成時(shí)間.假設(shè)當(dāng)任務(wù)到達(dá)時(shí),任務(wù)表示為Ji=(Ci,Di,Vi),其到達(dá)時(shí)間是預(yù)先未知的.本文后面的討論只考慮任務(wù)具有固定截止期的情況,即任務(wù)一旦到達(dá)截止期,其價(jià)值立即降低為0,并且任務(wù)的執(zhí)行也將立即終止.調(diào)度算法的性能從3個(gè)方面被考察:(1)實(shí)現(xiàn)價(jià)值率(hitvalueratio,簡稱HVR)是調(diào)度算法調(diào)度執(zhí)行任務(wù)滿足截止期所實(shí)現(xiàn)的累積價(jià)值與所有提交的任務(wù)價(jià)值總和的比率;(2)加權(quán)截止期保證率(weightedguaranteeratio,簡稱WGR)是指不同關(guān)鍵程度的任務(wù)的被滿足截止期的情況,它體現(xiàn)了一個(gè)調(diào)度算法的健壯性;(3)差分截止期保證率(differentiatedguaranteeratio,簡稱DGR),即使在系統(tǒng)嚴(yán)重過載的情況下,調(diào)度算法也必須盡量保證較高價(jià)值(即較重要)的任務(wù)滿足截止期,因此,使用DGR來評估調(diào)度算法在系統(tǒng)過載時(shí)對于不同價(jià)值的任務(wù)所產(chǎn)生的差分服務(wù)能力.2確定相對截止期和外包層優(yōu)先級分派策略可看成是一個(gè)函數(shù),它可以針對兩類不同情況:單個(gè)任務(wù)或一個(gè)任務(wù)集.當(dāng)用于單個(gè)任務(wù)時(shí),函數(shù)的結(jié)果就是對應(yīng)分派策略所確定的該任務(wù)的優(yōu)先級;當(dāng)用于任務(wù)集時(shí),函數(shù)的結(jié)果是任務(wù)集中任務(wù)的一個(gè)排序表,在實(shí)施調(diào)度時(shí),優(yōu)先級最高者排第1,最低者排最后.文獻(xiàn)在設(shè)計(jì)優(yōu)先級表時(shí),考慮的是任務(wù)的相對截止期和空閑時(shí)間兩個(gè)特征參數(shù),將任務(wù)的相對截止期和空閑時(shí)間這兩個(gè)參數(shù)的取值范圍劃分成若干個(gè)不同的取值區(qū)間,每個(gè)區(qū)間選擇一個(gè)典型值來代表這個(gè)區(qū)間.對具有不同的典型相對截止期Di和典型空閑時(shí)間sj的任務(wù)Jij,賦予其特定的優(yōu)先級值Pij(di,sj),從而得到事先能夠確定的優(yōu)先級表P=(Pij).對于具有任一相對截止期D和空閑時(shí)間s的任務(wù),當(dāng)D和s是典型截止期之一和典型空閑時(shí)間值之一時(shí),則查表可獲得該任務(wù)的優(yōu)先級;當(dāng)D和s中至少有一個(gè)不是典型值時(shí),則通過對優(yōu)先級表進(jìn)行插值,以便獲得該任務(wù)的優(yōu)先級,文獻(xiàn)中給出了二元三點(diǎn)插值公式.文獻(xiàn)中基于優(yōu)先級表設(shè)計(jì)與插值方法的優(yōu)先級分派策略通過綜合任務(wù)的截止期與空閑時(shí)間這兩個(gè)特征參數(shù),有效地提高了任務(wù)調(diào)度的成功率.但是,算法要求必須事先明確特征參數(shù)的典型值并計(jì)算優(yōu)先級表,而典型值的設(shè)置又會影響插值的效果.針對動態(tài)實(shí)時(shí)系統(tǒng)中的任務(wù)調(diào)度與過載處理問題,下面給出一種綜合任務(wù)的截止期與價(jià)值的優(yōu)先級表設(shè)計(jì)方法,不需要預(yù)先確定任務(wù)參數(shù)的典型值并計(jì)算優(yōu)先級表,而是在線地為任務(wù)分配優(yōu)先級,并按照優(yōu)先級調(diào)度這些任務(wù).2.1分級編碼.截止期/價(jià)值優(yōu)先級表設(shè)計(jì)方法的目標(biāo)是在任務(wù)調(diào)度時(shí)綜合考慮任務(wù)的截止期與價(jià)值,從而保證系統(tǒng)在過載情況下能夠優(yōu)雅地降級,不會出現(xiàn)EDF之類調(diào)度算法中存在的多米諾現(xiàn)象.首先我們來明確算法調(diào)度的原則:·任務(wù)的截止期越早且價(jià)值越大,則任務(wù)的優(yōu)先級越高;·對于截止期與價(jià)值完全相同的任務(wù),先到達(dá)者具有更高的優(yōu)先級.圖1給出了基于截止期/價(jià)值的一種優(yōu)先級方案表,其中箭頭表示了任務(wù)的優(yōu)先級順序.在這種優(yōu)先級分派方法中,任務(wù)的截止期序列按照升序排列,即截止期越早,任務(wù)越靠前;而任務(wù)的價(jià)值序列則是采用降序排列,即任務(wù)價(jià)值越大越靠前.對于具有同樣截止期的任務(wù),價(jià)值越大,任務(wù)的優(yōu)先級越高;而對于具有同樣價(jià)值的任務(wù),截止期越早,任務(wù)的優(yōu)先級越高.在如圖1所示的優(yōu)先級表中,每個(gè)任務(wù)具有一個(gè)優(yōu)先級等級:P=i+j,其中i與j分別表示任務(wù)的截止期與價(jià)值在各自序列中的位置.圖中每條斜線上標(biāo)識的任務(wù)具有相同的優(yōu)先級等級P,但是同樣優(yōu)先級等級的任務(wù),其調(diào)度執(zhí)行的順序必須按照箭頭所指的方向,表現(xiàn)為不同的優(yōu)先級.任務(wù)的優(yōu)先級p可以按照下式計(jì)算:p值越小,任務(wù)的優(yōu)先級越高.對于具有相同優(yōu)先級等級的任務(wù),調(diào)度算法更加傾向于截止期較早的任務(wù),即同一優(yōu)先級等級中的任務(wù),截止期較早的任務(wù)具有更高的優(yōu)先級.這種優(yōu)先級表設(shè)計(jì)模式給出了一種綜合任務(wù)的截止期與價(jià)值的調(diào)度算法,我們稱為EDV算法.類似地,我們給出任務(wù)優(yōu)先級表的另一種設(shè)計(jì)模式,如圖2所示.對于具有相同優(yōu)先級等級的任務(wù),調(diào)度算法更加傾向于價(jià)值較大的任務(wù).這種模式下,任務(wù)的優(yōu)先級可以按照下式計(jì)算:基于這種模式的調(diào)度算法稱為VED算法.盡管任務(wù)的優(yōu)先級是按照優(yōu)先級表來分配,但是我們的方法并不事先計(jì)算優(yōu)先級表,而是通過運(yùn)行時(shí)動態(tài)組織任務(wù)的優(yōu)先級表來達(dá)到基于優(yōu)先級的任務(wù)調(diào)度.2.2edv和ved算法上面提出的EDV與VED算法分別傾向于截止期較早與價(jià)值較大的任務(wù),下面我們討論如何通過加權(quán)方法加強(qiáng)這種傾向性.優(yōu)先級表加權(quán)方法引入了一個(gè)權(quán)重參數(shù)?,?為正整數(shù).同樣,優(yōu)先級表加權(quán)方法也分為兩種傾向截止期的加權(quán)方法(weighted-EDV,簡稱WEDV)和傾向價(jià)值的加權(quán)方法(Weighted-VED,簡稱WVED).在傾向截止期的加權(quán)方法中,任務(wù)優(yōu)先等級P和優(yōu)先級p的計(jì)算公式為其中u=[(j-2)/γ].當(dāng)γ=1時(shí),該算法就是EDV算法.當(dāng)γ=2時(shí),任務(wù)的優(yōu)先級表如圖3所示.當(dāng)γ取值足夠大時(shí),該算法相當(dāng)于EDF算法.在傾向價(jià)值的加權(quán)方法中,任務(wù)優(yōu)先等級P和優(yōu)先級p的計(jì)算公式如下:其中u=[(i-2)/γ].當(dāng)γ=1時(shí),該算法就是VED算法.當(dāng)γ=2時(shí),任務(wù)的優(yōu)先級表如圖4所示.當(dāng)γ取值足夠大時(shí),該算法相當(dāng)于HVF算法.2.3關(guān)鍵等級的確定假設(shè)任務(wù)的價(jià)值根據(jù)其取值范圍被劃分為N個(gè)區(qū)間或者任務(wù)具有N個(gè)不同關(guān)鍵等級,則優(yōu)先級表的價(jià)值維是固定的,因此優(yōu)先級表為非方陣結(jié)構(gòu).在非方陣優(yōu)先級表中,任務(wù)優(yōu)先級等級P和優(yōu)先級p的計(jì)算公式如下其中n為任務(wù)所在的區(qū)間號.圖5給出了N=5時(shí)EDV-N算法的優(yōu)先級表.2.4個(gè)任務(wù)的等級分配優(yōu)先級表方法能夠被進(jìn)一步擴(kuò)展,在調(diào)度中集成任務(wù)的3個(gè)不同的特征參數(shù).圖6給出了一種綜合任務(wù)的截止期、松弛時(shí)間與價(jià)值的三維優(yōu)先級表設(shè)計(jì)模式,其中,截止期序列按照升序排列,松弛時(shí)間序列也按照升序排列,而價(jià)值序列按照降序排列.處于同一斜剖面上的任務(wù)屬于同一優(yōu)先級等級:其中,i,j與k分別表示任務(wù)在截止期、松弛時(shí)間與價(jià)值序列中的位置.同一優(yōu)先級等級上的任務(wù),由于每個(gè)特征參數(shù)在任務(wù)優(yōu)先級分配中比重不同,仍然使得每個(gè)任務(wù)具有不同的優(yōu)先級:在上面的三維優(yōu)先級表設(shè)計(jì)模式中,任務(wù)的3個(gè)特征參數(shù)的重要程度由高到低依次為:截止期、松弛時(shí)間與價(jià)值.這種優(yōu)先級表設(shè)計(jì)模式,不僅可以通過偏重于不同的特征參數(shù)來實(shí)現(xiàn)不同的調(diào)度算法,而且能夠用于綜合任務(wù)的其他任何3個(gè)特征參數(shù).3任務(wù)完成/發(fā)揮本節(jié)以EDV算法為例,給出基于優(yōu)先級表的調(diào)度算法的一種實(shí)現(xiàn).基于優(yōu)先級表的特點(diǎn),任務(wù)的截止期序列與價(jià)值序列分別實(shí)現(xiàn)為基于截止期的任務(wù)鏈表Qd與基于價(jià)值的任務(wù)鏈表Qv,Qd與Qv都是帶空閑頭結(jié)點(diǎn)的雙向循環(huán)鏈表,交錯(cuò)形成一個(gè)邏輯上的優(yōu)先級表.之所以使用雙向鏈表,是為了便于任務(wù)結(jié)點(diǎn)的插入與移除.任務(wù)結(jié)點(diǎn)TaskNode的結(jié)構(gòu)與鏈表的定義如下:其中,dhead與vhead分別是Qd與Qv的表頭結(jié)點(diǎn),pactive指向當(dāng)前正在執(zhí)行的任務(wù)結(jié)點(diǎn).在系統(tǒng)運(yùn)行過程中,當(dāng)新的任務(wù)到達(dá)、任務(wù)完成或者任務(wù)夭折時(shí),需要調(diào)整優(yōu)先級表,并且確定當(dāng)前最高優(yōu)先級的任務(wù)去執(zhí)行.基于這樣的優(yōu)先級表組織結(jié)構(gòu),我們給出了線性時(shí)間復(fù)雜性的任務(wù)接收策略與任務(wù)完成/夭折策略來進(jìn)行新任務(wù)的接收與任務(wù)的完成/夭折處理.3.1接收策略的實(shí)現(xiàn)當(dāng)新的任務(wù)到達(dá)時(shí),系統(tǒng)調(diào)用任務(wù)接收策略,把任務(wù)插入Qd與Qv,并計(jì)算出任務(wù)的優(yōu)先級,判斷是否需要搶占當(dāng)前正在執(zhí)行的任務(wù).任務(wù)接收策略的算法描述如下:1)設(shè)pnew指向新任務(wù),其中指針域初始為Null;2)把任務(wù)pnew插入Qd3)把任務(wù)pnew插入Qv4)計(jì)算任務(wù)的優(yōu)先級并判斷是否需要搶占當(dāng)前正在執(zhí)行的任務(wù)這個(gè)算法分別從兩個(gè)鏈表的尾結(jié)點(diǎn)開始逆向查找,以確定新的任務(wù)結(jié)點(diǎn)在優(yōu)先級表中的位置與其優(yōu)先級在最壞情況下,需要對Qd與Qv各掃描一遍,因此算法的復(fù)雜度為O(2n),其中n為當(dāng)前優(yōu)先級表中的任務(wù)數(shù).3.2任務(wù)完成/發(fā)揮算法當(dāng)一個(gè)任務(wù)完成執(zhí)行或者超過截止期而夭折時(shí),系統(tǒng)需要調(diào)用任務(wù)完成/夭折策略,把完成執(zhí)行或者夭折的任務(wù)結(jié)點(diǎn)從優(yōu)先級表中移除,并且相應(yīng)地調(diào)整后續(xù)任務(wù)的行與列下標(biāo)以重新計(jì)算任務(wù)的優(yōu)先級,并且選擇優(yōu)先級最高的任務(wù)去執(zhí)行.任務(wù)完成/夭折策略的算法描述如下:1)從優(yōu)先級表中移除當(dāng)前完成的任務(wù)2)Qd鏈表中所有后續(xù)任務(wù)的行下標(biāo)減13)Qv鏈表中所有后續(xù)任務(wù)的列下標(biāo)減14)從Qd鏈表頭結(jié)點(diǎn)開始掃描確定優(yōu)先級最高的任務(wù)去執(zhí)行這個(gè)算法首先從鏈表Qd與Qv中移除給定的任務(wù)結(jié)點(diǎn),并且從被移除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始更新任務(wù)的行與列下標(biāo)并重新計(jì)算任務(wù)的優(yōu)先級,這在最壞情況下需要對Qd與Qv各掃描一遍.確定最高優(yōu)先級任務(wù)的過程是掃描Qd鏈表(當(dāng)然也可以掃描Qv鏈表),時(shí)間復(fù)雜度為O(n).因此算法總的復(fù)雜度為O(3n),其中n為當(dāng)前優(yōu)先級表中的任務(wù)數(shù).4任務(wù)的最壞情形執(zhí)行時(shí)間ci的計(jì)算為了評估EDV算法與VED算法在不同負(fù)載下的性能,我們以EDF算法與HVF算法作為基線,從實(shí)現(xiàn)價(jià)值率HVR、加權(quán)截止期保證率WGR與差分截止期保證率DGR這3個(gè)方面比較EDV算法、VED算法相對于EDF算法與HVF算法在性能方面所具有的優(yōu)越性,以及這些算法的優(yōu)缺點(diǎn).在我們做的所有仿真實(shí)驗(yàn)中,任務(wù)集由100個(gè)任務(wù)Ji(i=1,2,3,…,100)組成,任務(wù)的參數(shù)根據(jù)下面的方法產(chǎn)生(1)任務(wù)的最壞情形執(zhí)行時(shí)間Ci在5~105個(gè)時(shí)間單元之間隨機(jī)選擇,服從均勻分布;(2)任務(wù)的每個(gè)實(shí)例Jij到達(dá)的時(shí)間服從均值為Ti的指數(shù)分布,Ti按照下面的公式計(jì)算:Ti=N*Ci/ρ,其中N表示任務(wù)集中的總?cè)蝿?wù)數(shù)(此處為100),ρ表示期望產(chǎn)生的工作負(fù)載,稱為標(biāo)稱負(fù)載;(3)設(shè)fs表示任務(wù)的松弛時(shí)間與最壞情形執(zhí)行時(shí)間的比率,并且fs服從均值2.0的指數(shù)分布,使得任務(wù)實(shí)例Jij的相對截止期Dij=Ci+fjs*Ci;(4)由于任務(wù)的實(shí)際執(zhí)行時(shí)間通常小于任務(wù)的最壞情形執(zhí)行時(shí)間,因此定義fe表示任務(wù)的實(shí)際執(zhí)行時(shí)間與最壞情形執(zhí)行時(shí)間的比率,并且fe服從0.4~1.0之間的均勻分布,則任務(wù)實(shí)例的平均實(shí)際執(zhí)行時(shí)間為0.7*Ci;(5)任務(wù)的價(jià)值Vi服從1~100之間的均勻分布,并且所有任務(wù)被劃分到關(guān)鍵程度不同的k(0≤k≤9)個(gè)類別中,其中k越大表示該類別任務(wù)的關(guān)鍵程度越高,任務(wù)Ji屬于第k類當(dāng)且僅當(dāng)k*10<Vi≤(k+1)*10.本文所有的實(shí)驗(yàn)結(jié)果都是采用100次獨(dú)立實(shí)驗(yàn)結(jié)果的平均值,每次實(shí)驗(yàn)運(yùn)行的持續(xù)時(shí)間為30000個(gè)時(shí)間單元.標(biāo)稱負(fù)載ρ是基于任務(wù)的最壞情形執(zhí)行時(shí)間,為了比較算法在不同負(fù)載情形下的性能,實(shí)驗(yàn)中,ρ的取值范圍為0.5~3.5.4.1負(fù)載優(yōu)化下的edv、ved算法性能圖7給出了EDF算法、HVF算法、EDV算法與VED算法在不同負(fù)載下的HVR變化趨勢,其中x軸是標(biāo)稱負(fù)載ρ,y軸表示不同調(diào)度算法的實(shí)現(xiàn)價(jià)值率HVR.從圖中我們不難發(fā)現(xiàn),EDF算法在負(fù)載較低的情形下,表現(xiàn)出了其最優(yōu)性,如ρ=0.5時(shí),HVR接近100%.但是,隨著負(fù)載的不斷增加,EDF的性能急劇下降,相對而言,其他算法能夠更加優(yōu)雅地降級.HVF算法傾向于優(yōu)先執(zhí)行價(jià)值最大的任務(wù),但是調(diào)度中沒有考慮任務(wù)的截止期,因此易于導(dǎo)致任務(wù)錯(cuò)失截止期,即使在較低的負(fù)載下,HVR也是所有算法中最低的.但是隨著負(fù)載的增加,特別是在ρ>2.0以后,這種算法表現(xiàn)出比EDF更好的性能.無論如何,綜合考慮任務(wù)的截止期與價(jià)值的EDV與VED算法在幾乎所有的負(fù)載情況下都表現(xiàn)出了比EDF算法和HVF算法更好的性能.EDV算法與VED算法相比,在較低的負(fù)載下EDV算法優(yōu)于VED算法,但是當(dāng)標(biāo)稱負(fù)載達(dá)到2.0以后,VED算法表現(xiàn)出更好的性能,其原因在于VED算法更加偏重于考慮任務(wù)的價(jià)值,因此能夠在較高的負(fù)載下實(shí)現(xiàn)更高的累積價(jià)值.4.2edv算法性能分析加權(quán)截止期保證率(weigtedguaranteeratio,簡稱WGR)是指不同關(guān)鍵程度的任務(wù)的被滿足截止期的情況,它體現(xiàn)了一個(gè)調(diào)度算法的健壯性.當(dāng)然,這個(gè)值也與使用的加權(quán)系數(shù)有關(guān),具體的加權(quán)值應(yīng)該根據(jù)應(yīng)用環(huán)境決定,這里我們利用公式其中i表示任務(wù)的關(guān)鍵程度,wi=2i表示不同類別任務(wù)的權(quán)重,GTi表示滿足截止期的第i類任務(wù)的總數(shù),CTi表示提交的第i類任務(wù)的總數(shù).圖8給出了EDF算法、HVF算法、EDV算法與VED算法在不同負(fù)載下的WGR變化趨勢,其中x軸是標(biāo)稱負(fù)載ρ,y軸表示調(diào)度算法在不同負(fù)載下的加權(quán)截止期保證率WGR.從圖中我們不難發(fā)現(xiàn),EDF算法隨著系統(tǒng)負(fù)載的增加其性能急劇下降,而其他算法能夠較優(yōu)雅地降級.由EDV算法與VED算法的比較,我們發(fā)現(xiàn):在較低的負(fù)載下,EDV算法表現(xiàn)出最好的性能;隨著負(fù)載的增加,VED算法逐漸表現(xiàn)出其優(yōu)越性,當(dāng)標(biāo)稱負(fù)載達(dá)到2.5以后,VED算法明顯優(yōu)于其他算法.4.3任務(wù)的截止期保證率由于價(jià)值較大的任務(wù)相對重要,因此調(diào)度算法應(yīng)該優(yōu)先保證價(jià)值較大的任務(wù)滿足截止期.這里,我們采用差分截止期保證率比較不同算法在系統(tǒng)過載時(shí)對于不同關(guān)鍵程度的任務(wù)所能夠提供的差分服務(wù)能力.在我們的實(shí)驗(yàn)中取標(biāo)稱負(fù)載ρ=2.0與ρ=3.0兩種情況,分別代表了算法在一般過載與嚴(yán)重過載兩種情況下所表現(xiàn)的性能.圖9(a)與圖9(b)分別給出了算法在這兩種負(fù)載下對不同類別任務(wù)所提供的截止期保證率.由圖9不難發(fā)現(xiàn),EDF算法不加區(qū)別地調(diào)度執(zhí)行任務(wù),因此所有任務(wù)在不同負(fù)載下具有差不多相同的截止期保證率,而