異構(gòu)系統(tǒng)中帶可用性約束的性能優(yōu)化調(diào)度算法

孫健,張興軍,董小社

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

可用性是衡量復(fù)雜計(jì)算機(jī)系統(tǒng)的關(guān)鍵指標(biāo)之一,特別是近年來(lái)異構(gòu)系統(tǒng)的日益發(fā)展,伴隨系統(tǒng)規(guī)模以及實(shí)時(shí)應(yīng)用范圍的逐步擴(kuò)大,研究異構(gòu)系統(tǒng)中多實(shí)時(shí)任務(wù)的可用性需求問(wèn)題具有非常重要的理論與實(shí)際意義。該研究領(lǐng)域內(nèi)涌現(xiàn)出諸多以滿足實(shí)時(shí)任務(wù)的具體可用性需求,并通過(guò)帶可用性約束的調(diào)度策略來(lái)實(shí)現(xiàn)系統(tǒng)內(nèi)實(shí)時(shí)任務(wù)合理調(diào)度分配的實(shí)時(shí)任務(wù)調(diào)度算法[1-2]。

早期實(shí)時(shí)任務(wù)調(diào)度理論中對(duì)任務(wù)調(diào)度算法的最基本假設(shè)是系統(tǒng)內(nèi)所有用于任務(wù)分配執(zhí)行的處理機(jī)節(jié)點(diǎn)均可用[3]。該假設(shè)僅在理想狀態(tài)的多處理機(jī)系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度中是合理的,但在復(fù)雜計(jì)算機(jī)系統(tǒng)特別是異構(gòu)系統(tǒng)中,由于系統(tǒng)故障宕機(jī)、失效修復(fù)等情況時(shí)有發(fā)生常導(dǎo)致系統(tǒng)不可用,此時(shí)該假設(shè)便不再適用。另外,異構(gòu)系統(tǒng)內(nèi)各處理機(jī)節(jié)點(diǎn)的實(shí)時(shí)任務(wù)執(zhí)行時(shí)間即任務(wù)響應(yīng)時(shí)間也各不相同,為選取系統(tǒng)內(nèi)任務(wù)分配的處理機(jī)節(jié)點(diǎn)增添了難度。為此,在設(shè)計(jì)實(shí)時(shí)任務(wù)調(diào)度算法時(shí)應(yīng)充分考慮各實(shí)時(shí)任務(wù)的具體可用性需求即可用性約束,并在此基礎(chǔ)上權(quán)衡系統(tǒng)調(diào)度分配過(guò)程中的任務(wù)響應(yīng)時(shí)間,保證在任務(wù)可調(diào)度性以及可用性的前提下實(shí)現(xiàn)異構(gòu)系統(tǒng)中實(shí)時(shí)任務(wù)的合理調(diào)度。

針對(duì)上述問(wèn)題,本文提出一種異構(gòu)系統(tǒng)中帶可用性約束的性能優(yōu)化調(diào)度算法,構(gòu)建系統(tǒng)內(nèi)處理機(jī)節(jié)點(diǎn)、實(shí)時(shí)任務(wù)以及帶可用性約束的實(shí)時(shí)任務(wù)調(diào)度模型,通過(guò)引入可用性成本和系統(tǒng)綜合開(kāi)銷,考慮可用性成本與任務(wù)平均響應(yīng)時(shí)間的折中,為實(shí)時(shí)任務(wù)分配系統(tǒng)綜合開(kāi)銷最少的處理機(jī)節(jié)點(diǎn),合理利用異構(gòu)系統(tǒng)調(diào)度資源,在提升實(shí)時(shí)任務(wù)調(diào)度可用性的同時(shí)進(jìn)一步優(yōu)化異構(gòu)系統(tǒng)的調(diào)度性能。

1 相關(guān)工作

目前,異構(gòu)系統(tǒng)中可用性相關(guān)的實(shí)時(shí)任務(wù)調(diào)度算法大致可分為兩類:一類是可用性受限的實(shí)時(shí)任務(wù)調(diào)度算法,即在滿足實(shí)時(shí)任務(wù)可用性約束的前提下,對(duì)以往僅考慮任務(wù)執(zhí)行時(shí)間的調(diào)度算法進(jìn)行優(yōu)化改進(jìn),典型算法如QoS-SAC[4]、SSAC[5]等;另一類是實(shí)時(shí)任務(wù)本身無(wú)可用性約束,而在算法設(shè)計(jì)中考慮可用性因素調(diào)度策略,旨在提升系統(tǒng)整體以及實(shí)時(shí)任務(wù)分配執(zhí)行的可用性水平和性能,如HMSAS[6]、ADSS[7]等。

多處理機(jī)異構(gòu)環(huán)境下的實(shí)時(shí)任務(wù)最優(yōu)分配一直是一個(gè)難以解決的NP完全問(wèn)題[8]。考慮可用性受限的實(shí)時(shí)任務(wù)調(diào)度算法,Xie等首次提出了異構(gòu)系統(tǒng)中帶可用性約束的多任務(wù)組調(diào)度策略(SSAC)[9],該策略的核心思想是結(jié)合任務(wù)平均響應(yīng)時(shí)間和可用性約束對(duì)實(shí)時(shí)任務(wù)進(jìn)行數(shù)學(xué)建模,根據(jù)任務(wù)的具體可用性約束,為其選擇系統(tǒng)內(nèi)滿足該約束的候選處理機(jī)集合,并將任務(wù)分配至集合中任務(wù)平均響應(yīng)時(shí)間最短的處理機(jī)處理執(zhí)行,在提升調(diào)度性能的同時(shí)提高系統(tǒng)可用性。此外,Tong等考慮系統(tǒng)QoS以及可用性需求,在文獻(xiàn)[5,9]的基礎(chǔ)上,針對(duì)異構(gòu)分布式系統(tǒng)設(shè)計(jì)可用性受限的實(shí)時(shí)任務(wù)調(diào)度算法(QoS-SAC)[4],以縮短實(shí)時(shí)任務(wù)的完成時(shí)間同時(shí)提高系統(tǒng)可用性。

本文提出的異構(gòu)系統(tǒng)中帶可用性約束的性能優(yōu)化調(diào)度算法(PO-SSAC),在實(shí)時(shí)任務(wù)調(diào)度執(zhí)行時(shí)考慮任務(wù)平均響應(yīng)時(shí)間與可用性成本的折中,并為其分配系統(tǒng)綜合開(kāi)銷最少的處理機(jī)節(jié)點(diǎn),與SSAC以及其他現(xiàn)有算法相比,進(jìn)一步提升了異構(gòu)系統(tǒng)的實(shí)時(shí)任務(wù)調(diào)度可用性以及性能,實(shí)現(xiàn)了系統(tǒng)資源的合理利用。

2 實(shí)時(shí)任務(wù)調(diào)度模型

2.1 帶可用性約束的實(shí)時(shí)任務(wù)調(diào)度框架結(jié)構(gòu)

本文所需解決的具體問(wèn)題是如何在可用性受限的情況下對(duì)異構(gòu)系統(tǒng)中實(shí)時(shí)任務(wù)進(jìn)行合理調(diào)度分配,并在提升系統(tǒng)任務(wù)調(diào)度可用性的基礎(chǔ)上進(jìn)一步優(yōu)化調(diào)度性能。根據(jù)上述問(wèn)題描述,異構(gòu)系統(tǒng)中帶可用性約束的實(shí)時(shí)任務(wù)調(diào)度框架結(jié)構(gòu)如圖1所示。

圖1 帶可用性約束的實(shí)時(shí)任務(wù)調(diào)度框架結(jié)構(gòu)

調(diào)度器是實(shí)時(shí)任務(wù)調(diào)度框架結(jié)構(gòu)的核心,負(fù)責(zé)調(diào)度分配來(lái)自各不同用戶的任務(wù)組隊(duì)列,并實(shí)時(shí)監(jiān)測(cè)異構(gòu)系統(tǒng)內(nèi)所有處理機(jī)節(jié)點(diǎn)的運(yùn)行狀態(tài),及時(shí)獲取各處理機(jī)節(jié)點(diǎn)的運(yùn)行狀態(tài)信息。調(diào)度隊(duì)列負(fù)責(zé)接收來(lái)自各用戶的任務(wù)組,調(diào)度器按照先來(lái)先服務(wù)原則接收所有到達(dá)的實(shí)時(shí)任務(wù),分配其至各處理機(jī)節(jié)點(diǎn),并由處理機(jī)節(jié)點(diǎn)內(nèi)本地隊(duì)列實(shí)現(xiàn)對(duì)各實(shí)時(shí)任務(wù)的并行處理。

對(duì)于每個(gè)來(lái)自用戶的實(shí)時(shí)任務(wù),處理機(jī)定位器為其篩選一個(gè)候選處理機(jī)集合,集合包含所有滿足該任務(wù)可用性需求即可用性約束的處理機(jī)節(jié)點(diǎn)。若集合非空,調(diào)度器從集合內(nèi)選擇系統(tǒng)綜合開(kāi)銷最少的處理機(jī)節(jié)點(diǎn),并分配任務(wù)至該處理機(jī)節(jié)點(diǎn)處理執(zhí)行;若集合為空,說(shuō)明沒(méi)有候選處理機(jī)節(jié)點(diǎn)滿足當(dāng)前任務(wù)的可用性約束,此時(shí)可用性成本計(jì)算器計(jì)算系統(tǒng)內(nèi)能夠滿足該任務(wù)可用性約束的處理機(jī)節(jié)點(diǎn),并將其添加至候選處理機(jī)集合。負(fù)載均衡檢測(cè)器檢測(cè)候選處理機(jī)節(jié)點(diǎn)是否超載,超載時(shí)實(shí)時(shí)任務(wù)將被分配至負(fù)載最輕的處理機(jī)節(jié)點(diǎn),否則分配至該處理機(jī)節(jié)點(diǎn)處理執(zhí)行。

2.2 處理機(jī)和實(shí)時(shí)任務(wù)模型

對(duì)異構(gòu)系統(tǒng)內(nèi)處理機(jī)和實(shí)時(shí)任務(wù)進(jìn)行如下的形式化數(shù)學(xué)描述。①處理機(jī)模型。異構(gòu)系統(tǒng)指由一定數(shù)量?jī)?nèi)部構(gòu)造不同且相互獨(dú)立的自治節(jié)點(diǎn),通過(guò)高速互聯(lián)網(wǎng)絡(luò)相互連接所共同組成的高性能、高可用計(jì)算機(jī)系統(tǒng),能夠作為一個(gè)整體為用戶提供所需的應(yīng)用服務(wù)。設(shè)異構(gòu)系統(tǒng)處理機(jī)集合H={N1,N2,…,Nj,…,Nn,j=1～n},n為處理機(jī)節(jié)點(diǎn)數(shù)。H中各處理機(jī)節(jié)點(diǎn)處理能力由每秒百萬(wàn)條指令(MIPS)來(lái)衡量,同時(shí)由于是異構(gòu)系統(tǒng),假設(shè)各處理機(jī)節(jié)點(diǎn)處理能力和可用性均不相同。②實(shí)時(shí)任務(wù)模型。設(shè)實(shí)時(shí)任務(wù)集合TG={t1,t2,…,ti,…,tm,i=1～m},m為來(lái)自用戶的實(shí)時(shí)任務(wù)數(shù)。系統(tǒng)根據(jù)用戶的可用性需求為實(shí)時(shí)任務(wù)設(shè)定可用性約束,范圍為0～1,實(shí)時(shí)任務(wù)必須分配至能夠滿足其可用性約束的處理機(jī)節(jié)點(diǎn)以確保得到成功處理。

定義實(shí)時(shí)任務(wù)ti在處理機(jī)節(jié)點(diǎn)Nj上執(zhí)行的平均響應(yīng)時(shí)間

φj))

(1)

式中:sj為實(shí)時(shí)任務(wù)集合TG在處理機(jī)節(jié)點(diǎn)Nj上的服務(wù)時(shí)間;sj2為sj的二階矩;E(sj)為服務(wù)時(shí)間均值;E(sj2)為服務(wù)時(shí)間均方。處理機(jī)節(jié)點(diǎn)Nj的任務(wù)到達(dá)率為Λj,服務(wù)率為φj,假設(shè)異構(gòu)系統(tǒng)內(nèi)任務(wù)到達(dá)模式和服務(wù)率是先驗(yàn)的,則Λj與φj均可通過(guò)代碼剖析和統(tǒng)計(jì)預(yù)測(cè)方法估算得出。

2.3 帶可用性約束的實(shí)時(shí)任務(wù)調(diào)度模型

本文異構(gòu)系統(tǒng)中可用性均為穩(wěn)態(tài)可用性,是指在某個(gè)時(shí)間段內(nèi)系統(tǒng)維持正常運(yùn)行狀態(tài)的概率。定義異構(gòu)系統(tǒng)內(nèi)處理機(jī)節(jié)點(diǎn)Nj的可用性為ξj,表示任意時(shí)間段內(nèi)處理機(jī)節(jié)點(diǎn)Nj可提供持續(xù)運(yùn)算處理的概率,相應(yīng)的異構(gòu)系統(tǒng)內(nèi)處理機(jī)節(jié)點(diǎn)Nj的不可用性為θj。定義實(shí)時(shí)任務(wù)ti的可用性約束為ai,代表任務(wù)ti必須執(zhí)行成功的概率,例如,當(dāng)ai=0.85時(shí),任務(wù)ti執(zhí)行失敗的概率不得高于0.15。

進(jìn)一步定義aij為實(shí)時(shí)任務(wù)ti在處理機(jī)節(jié)點(diǎn)Nj上的可用性成本

aij=pijθj/μij

(2)

式中:pij為實(shí)時(shí)任務(wù)ti分配至處理機(jī)節(jié)點(diǎn)Nj的概率;μij為實(shí)時(shí)任務(wù)ti分配至處理機(jī)節(jié)點(diǎn)Nj的服務(wù)率。

本文引入綜合性能開(kāi)銷的概念,定義Cij為實(shí)時(shí)任務(wù)ti在處理機(jī)節(jié)點(diǎn)Nj上的系統(tǒng)綜合開(kāi)銷,結(jié)合式(1)和式(2),得到Cij的計(jì)算公式為

(3)

結(jié)合2.2小節(jié)對(duì)處理機(jī)和實(shí)時(shí)任務(wù)模型的相關(guān)分析,將帶可用性約束的性能優(yōu)化調(diào)度問(wèn)題抽象為異構(gòu)系統(tǒng)可用性與實(shí)時(shí)任務(wù)平均響應(yīng)時(shí)間兩者之間的折中,則本文調(diào)度算法的設(shè)計(jì)目標(biāo)可描述為:提高實(shí)時(shí)任務(wù)調(diào)度分配的可用性;合理利用資源減少系統(tǒng)綜合開(kāi)銷,即保證較短的實(shí)時(shí)任務(wù)平均響應(yīng)時(shí)間和較低的處理執(zhí)行可用性成本,得到如下數(shù)學(xué)模型

(4)

系統(tǒng)綜合開(kāi)銷約束條件為

?1≤i≤m,1≤j≤n,ai≤ξj:minCij

在該數(shù)學(xué)模型中,A為異構(gòu)系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度的系統(tǒng)可用性;λi為實(shí)時(shí)任務(wù)ti的到達(dá)率且符合泊松過(guò)程;λ為實(shí)時(shí)任務(wù)集合TG在異構(gòu)系統(tǒng)中的總平均到達(dá)率。

3 帶可用性約束的性能優(yōu)化調(diào)度算法

實(shí)時(shí)任務(wù)平均響應(yīng)時(shí)間在很大程度上依賴于異構(gòu)系統(tǒng)中各處理機(jī)節(jié)點(diǎn)所采用的具體排序策略,因此本文所提PO-SSAC算法采用文獻(xiàn)[10]中給出的最優(yōu)排序策略以最大程度減少異構(gòu)系統(tǒng)中實(shí)時(shí)任務(wù)集合的平均響應(yīng)時(shí)間,并作如下命題。

命題1 已知m組實(shí)時(shí)任務(wù)隊(duì)列和由n個(gè)處理機(jī)節(jié)點(diǎn)構(gòu)成的異構(gòu)系統(tǒng),根據(jù)最優(yōu)排序策略,在處理機(jī)節(jié)點(diǎn)Nj上,當(dāng)μij≥μkj時(shí),實(shí)時(shí)任務(wù)ti的優(yōu)先級(jí)高于tk。

上述命題說(shuō)明高服務(wù)率的實(shí)時(shí)任務(wù)在調(diào)度分配時(shí)必須擁有相對(duì)較高的優(yōu)先級(jí),以達(dá)到縮短任務(wù)平均響應(yīng)時(shí)間的目的。為簡(jiǎn)化描述進(jìn)一步作如下假設(shè)。

假設(shè)1 假設(shè)異構(gòu)系統(tǒng)內(nèi)實(shí)時(shí)任務(wù)集合TG按照服務(wù)率從高到低排序,即

ρ1≥ρ2≥…≥ρi…≥ρm

式中:ρi為實(shí)時(shí)任務(wù)ti分配至H的總服務(wù)率。根據(jù)該假設(shè),調(diào)度策略可以在執(zhí)行最初對(duì)所有實(shí)時(shí)任務(wù)按照服務(wù)率從高到低順序進(jìn)行重新排列,以方便之后的調(diào)度分配。

在PO-SSAC算法中,執(zhí)行程序首先按照命題1和假設(shè)1為高服務(wù)率的實(shí)時(shí)任務(wù)分配高優(yōu)先級(jí)并按照優(yōu)先級(jí)進(jìn)行排序,之后進(jìn)入對(duì)實(shí)時(shí)任務(wù)集合的循環(huán)處理。循環(huán)處理是PO-SSAC算法的核心部分,首先判斷候選處理機(jī)子集是否為空,若子集非空,說(shuō)明子集內(nèi)至少包含1個(gè)處理機(jī)節(jié)點(diǎn)能夠滿足實(shí)時(shí)任務(wù)ti的可用性約束,進(jìn)而循環(huán)計(jì)算候選處理機(jī)子集中各候選處理機(jī)節(jié)點(diǎn)的系統(tǒng)綜合開(kāi)銷Cij,選取子集中系統(tǒng)綜合開(kāi)銷最少的處理機(jī)節(jié)點(diǎn),并將該處理機(jī)節(jié)點(diǎn)選為任務(wù)調(diào)度的執(zhí)行節(jié)點(diǎn)。

討論調(diào)度的特殊情況,若候選處理機(jī)子集為空,說(shuō)明此時(shí)異構(gòu)系統(tǒng)中所有處理機(jī)節(jié)點(diǎn)均無(wú)法滿足實(shí)時(shí)任務(wù)ti的可用性約束。在該情況下PO-SSAC算法將采取相應(yīng)的措施盡可能對(duì)ti的調(diào)度執(zhí)行可用性進(jìn)行提升。循環(huán)計(jì)算ti在異構(gòu)系統(tǒng)內(nèi)處理機(jī)節(jié)點(diǎn)的可用性成本aij,并為ti分配系統(tǒng)內(nèi)可用性成本最低的處理機(jī)節(jié)點(diǎn)。另外,如果系統(tǒng)內(nèi)存在2個(gè)或2個(gè)以上可用性成本取值相同且最低的處理機(jī)節(jié)點(diǎn),則ti將分配至其中平均響應(yīng)時(shí)間相對(duì)較短的處理機(jī)節(jié)點(diǎn)上。

當(dāng)某候選處理機(jī)節(jié)點(diǎn)Ns選定以后,PO-SSAC主函數(shù)將調(diào)用loadBalance()函數(shù)進(jìn)行負(fù)載均衡檢測(cè)并最終分配實(shí)時(shí)任務(wù)ti至相應(yīng)的處理機(jī)節(jié)點(diǎn)處理執(zhí)行。loadBalance()函數(shù)首先估算H內(nèi)所有處理機(jī)節(jié)點(diǎn)的負(fù)載指標(biāo)并找到其中負(fù)載最輕的處理機(jī)節(jié)點(diǎn)Nnmin,令該節(jié)點(diǎn)負(fù)載指標(biāo)為L(zhǎng)min。對(duì)于所選取的處理機(jī)節(jié)點(diǎn)Ns,如果Ns沒(méi)有超載,系統(tǒng)將分配ti至該節(jié)點(diǎn)處理執(zhí)行;如果Ns超載,系統(tǒng)將分配ti至H內(nèi)負(fù)載最輕的處理機(jī)節(jié)點(diǎn)Nnmin處理執(zhí)行,負(fù)載閾值為L(zhǎng)T。

對(duì)于PO-SSAC主函數(shù),TG按照服務(wù)率從高到低排序的時(shí)間復(fù)雜度為O(mlbm),處理機(jī)節(jié)點(diǎn)選取的時(shí)間復(fù)雜度為O(n),則對(duì)于實(shí)時(shí)任務(wù)集合TG,PO-SSAC主函數(shù)在最差執(zhí)行情況下的時(shí)間復(fù)雜度為O(mn)。進(jìn)一步分析loadBalance()函數(shù),循環(huán)計(jì)算異構(gòu)系統(tǒng)內(nèi)所有處理機(jī)節(jié)點(diǎn)負(fù)載指標(biāo)的時(shí)間復(fù)雜度為O(n),假設(shè)單次任務(wù)調(diào)度分配中,PO-SSAC主函數(shù)和loadBalance()函數(shù)中其他步驟執(zhí)行時(shí)間復(fù)雜度為O(1),則對(duì)于實(shí)時(shí)任務(wù)集合TG,PO-SSAC算法任務(wù)分配的時(shí)間復(fù)雜度為O(m(n+1))。綜合上述分析,PO-SSAC算法在最差執(zhí)行情況下的整體時(shí)間復(fù)雜度為O(mlbm)+O(mn)+O(m(n+1))≈O(2mn)。

圖2給出了PO-SSAC調(diào)度策略的一個(gè)抽象實(shí)例,假設(shè)異構(gòu)系統(tǒng)由8個(gè)處理機(jī)節(jié)點(diǎn)(N1～N8)組成,其中各處理機(jī)節(jié)點(diǎn)可用性取值范圍為0.68～0.97,任務(wù)平均響應(yīng)時(shí)間取值范圍為42～204 s,可用性成本取值范圍為0.031～0.297。假設(shè)實(shí)時(shí)任務(wù)可用性約束為0.80,則符合該可用性約束的候選處理機(jī)集合為N3、N4、N6、N7和N8,各候選處理機(jī)的系統(tǒng)綜合開(kāi)銷取值范圍為2.94～21.42。按照PO-SSAC調(diào)度策略,調(diào)度器將最終分配實(shí)時(shí)任務(wù)至系統(tǒng)綜合開(kāi)銷最少的處理機(jī)節(jié)點(diǎn)N3處理執(zhí)行。

圖2 PO-SSAC調(diào)度策略實(shí)例

4 實(shí)驗(yàn)分析

本文面向異構(gòu)系統(tǒng)設(shè)計(jì)了帶可用性約束的性能優(yōu)化調(diào)度算法PO-SSAC,并通過(guò)隨機(jī)實(shí)時(shí)任務(wù)集在異構(gòu)系統(tǒng)內(nèi)的調(diào)度分配對(duì)現(xiàn)有實(shí)時(shí)任務(wù)調(diào)度算法SSAC、MinMin、Sufferage以及PO-SSAC進(jìn)行對(duì)比仿真實(shí)驗(yàn)。異構(gòu)系統(tǒng)選用GridSim仿真工具進(jìn)行構(gòu)建,代碼用Java通過(guò)eclipse編譯實(shí)現(xiàn),仿真環(huán)境為Red Hat Enterprise Linux 7.0操作系統(tǒng),CPU為Inter Core i7-6700k@4.00 GHz四核,內(nèi)存為16 GB,硬盤(pán)為希捷ST3000DM001-1ER166(3 TB)。

4.1 實(shí)驗(yàn)用例

實(shí)驗(yàn)主要從任務(wù)總平均到達(dá)率和處理機(jī)節(jié)點(diǎn)數(shù)的變化情況對(duì)異構(gòu)系統(tǒng)內(nèi)PO-SSAC算法以及對(duì)比算法的調(diào)度執(zhí)行情況進(jìn)行分析。實(shí)驗(yàn)運(yùn)行200次并記錄實(shí)驗(yàn)結(jié)果,去掉其中5次最大和最小結(jié)果,取剩余結(jié)果均值作為最終實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)參數(shù)和取值情況見(jiàn)表1,參數(shù)或者參照文獻(xiàn)[5,9]中實(shí)驗(yàn)部分的參數(shù)取值,或者取自異構(gòu)系統(tǒng)的實(shí)際評(píng)測(cè)經(jīng)驗(yàn)值。

異構(gòu)系統(tǒng)處理機(jī)節(jié)點(diǎn)數(shù)為n,實(shí)時(shí)任務(wù)集合TG通過(guò)GridSim仿真工具隨機(jī)生成,任務(wù)平均響應(yīng)時(shí)間Tij為1～500 s內(nèi)隨機(jī)整數(shù)。根據(jù)對(duì)實(shí)時(shí)任務(wù)調(diào)度模型的分析可知,任務(wù)總平均到達(dá)率λ服從泊松分布,任務(wù)平均響應(yīng)時(shí)間Tij、處理機(jī)節(jié)點(diǎn)可用性ξj以及任務(wù)可用性約束ai均服從均勻分布,負(fù)載閾值LT取固定經(jīng)驗(yàn)值。

實(shí)驗(yàn)選取與PO-SSAC算法相近似的另外3個(gè)調(diào)度算法進(jìn)行對(duì)比,包括SSAC、MinMin[11]以及Sufferage算法[12],上述算法均適用于異構(gòu)系統(tǒng)中的實(shí)時(shí)任務(wù)調(diào)度分配,同時(shí)也適用于分布式或同構(gòu)系統(tǒng)的任務(wù)調(diào)度情況。

實(shí)驗(yàn)主要評(píng)價(jià)指標(biāo)包括異構(gòu)系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度系統(tǒng)可用性、系統(tǒng)總平均響應(yīng)時(shí)間以及系統(tǒng)綜合開(kāi)銷。

4.2 實(shí)驗(yàn)結(jié)果分析

首先分析任務(wù)總平均到達(dá)率λ變化情況下異構(gòu)系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度的各評(píng)價(jià)指標(biāo)。λ取值范圍為0.2～1.0,增量為0.2,處理機(jī)節(jié)點(diǎn)數(shù)n=16。實(shí)時(shí)任務(wù)調(diào)度分配實(shí)驗(yàn)結(jié)果如圖3所示。

(a)系統(tǒng)可用性

(b)系統(tǒng)平均響應(yīng)時(shí)間

(c)系統(tǒng)綜合性能開(kāi)銷圖3 任務(wù)總平均到達(dá)率不同時(shí)系統(tǒng)的各項(xiàng)性能實(shí)驗(yàn)結(jié)果

由圖3a可以看出,采用可用性約束調(diào)度策略的PO-SSAC與SSAC可用性提升明顯,與MinMin算法相比,可用性提升約76.9%,與Sufferage算法相比,可用性提升約76.5%,同時(shí)PO-SSAC更優(yōu)于SSAC,可用性提升約3.4%,原因在于PO-SSAC在實(shí)時(shí)任務(wù)處理機(jī)節(jié)點(diǎn)選取時(shí)考慮了實(shí)時(shí)任務(wù)可用性成本與平均響應(yīng)時(shí)間的折中,為其分配系統(tǒng)綜合開(kāi)銷最少的處理機(jī)節(jié)點(diǎn)調(diào)度執(zhí)行,該策略使實(shí)時(shí)任務(wù)調(diào)度分配的可用性能夠得到進(jìn)一步的提升。圖3b、圖3c中實(shí)驗(yàn)結(jié)果表明,PO-SSAC在獲取較高系統(tǒng)可用性的同時(shí)增加了異構(gòu)系統(tǒng)內(nèi)實(shí)時(shí)任務(wù)的調(diào)度執(zhí)行時(shí)間,有效降低了系統(tǒng)綜合開(kāi)銷,與系統(tǒng)綜合開(kāi)銷最多的Sufferage算法相比,減少近30%,優(yōu)化了異構(gòu)系統(tǒng)的性能。

進(jìn)一步分析處理機(jī)節(jié)點(diǎn)數(shù)n變化時(shí)異構(gòu)系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度的各評(píng)價(jià)指標(biāo)。n取值為16、32、64、128時(shí),任務(wù)總平均到達(dá)率λ=1。實(shí)時(shí)任務(wù)調(diào)度分配實(shí)驗(yàn)結(jié)果如圖4所示。

(a)系統(tǒng)可用性

(b)系統(tǒng)平均響應(yīng)時(shí)間

(c)系統(tǒng)綜合開(kāi)銷圖4 處理機(jī)節(jié)點(diǎn)數(shù)不同時(shí)系統(tǒng)的各項(xiàng)性能實(shí)驗(yàn)結(jié)果

與任務(wù)到達(dá)率變化實(shí)驗(yàn)結(jié)果類似,與其他3個(gè)算法相比,PO-SSAC系統(tǒng)可用性有所提升,但由于考慮可用性約束,增加了異構(gòu)系統(tǒng)的實(shí)時(shí)任務(wù)調(diào)度執(zhí)行時(shí)間。由圖4c中實(shí)驗(yàn)結(jié)果可以看出,與其他3個(gè)算法相比,PO-SSAC系統(tǒng)綜合開(kāi)銷最少。另外,本實(shí)驗(yàn)結(jié)果也說(shuō)明當(dāng)異構(gòu)系統(tǒng)規(guī)模擴(kuò)大,即處理機(jī)節(jié)點(diǎn)數(shù)增多時(shí),系統(tǒng)綜合開(kāi)銷會(huì)減少,實(shí)時(shí)任務(wù)調(diào)度可用性和系統(tǒng)性能將得到提升。

5 結(jié) 論

本文提出了一種異構(gòu)系統(tǒng)中帶可用性約束的性能優(yōu)化調(diào)度算法,該算法對(duì)異構(gòu)系統(tǒng)內(nèi)處理機(jī)節(jié)點(diǎn)、實(shí)時(shí)任務(wù)以及帶可用性約束的實(shí)時(shí)任務(wù)調(diào)度進(jìn)行數(shù)學(xué)建模,引入系統(tǒng)綜合開(kāi)銷概念并考慮可用性成本與任務(wù)平均響應(yīng)時(shí)間的折中,將實(shí)時(shí)任務(wù)分配給系統(tǒng)綜合開(kāi)銷最少的處理機(jī)節(jié)點(diǎn),以達(dá)到系統(tǒng)調(diào)度資源合理利用的目的。實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有算法相比,PO-SSAC算法提升了異構(gòu)系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度的系統(tǒng)可用性,系統(tǒng)調(diào)度性能也得到了進(jìn)一步優(yōu)化。

[1] FAN J, LU X W, LIU P H. Integrated scheduling of production and delivery on a single machine with availability constraint [J]. Theoretical Computer Science, 2015, 562: 581-589.

[2] BELMABROUK M, MARRAKCHI M. Optimal parallel scheduling for resolution a triangular system with availability constraints [C]∥Proceedings of the International Conference on Computer Systems and Applications. Piscataway, NJ, USA: IEEE, 2015: 1-7.

[3] SALFNER F, WOLTER K. A Petri net model for service availability in redundant computing systems [C]∥Proceedings of the 2009 Winter Simulation Conference. Piscataway, NJ, USA: IEEE, 2009: 819-826.

[4] TONG Z, LI K L, XIAO Z, et al. A Qos scheduling scheme with availability constraint in distributed systems [C]∥Proceedings of the 13th International Conference on Parallel and Distributed Computing, Applications and Technologies. Piscataway, NJ, USA: IEEE, 2012: 481-486.

[5] QIN X, XIE T. An availability-aware task scheduling for heterogeneous systems [J]. IEEE Transactions on Computers, 2008, 57(2): 188-199.

[6] KHOUDI A, BERRICHI A, YALAOUI F. Heuristics to maximize system availability on parallel machine scheduling problem [C]∥Proceedings of the International Symposium on Programming and Systems. Piscataway, NJ, USA: IEEE, 2015: 1-6.

[7] ZHU M, GUO W, XIAO S L, et al. Availability-driven scheduling for real-time directed acyclic graph applications in optical grids [J]. Journal of Optical Communications and Networking, 2010, 2(7): 469-480.

[8] 李智勇, 陳少淼, 楊波, 等. 異構(gòu)云環(huán)境多目標(biāo)Memetic優(yōu)化任務(wù)調(diào)度方法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2016, 39(2): 377-390. LI Zhiyong, CHEN Shaomiao, YANG Bo, et al. Multi-object memetic algorithm for task scheduling on heterogeneous cloud [J]. Chinese Journal of Computers, 2016, 39(2): 377-390.

[9] XIE T, QIN X. Stochastic scheduling with availability constraints in heterogeneous clusters [C]∥Proceedings of the International Conference on Cluster Computing. Piscataway, NJ, USA: IEEE, 2006: 1-10.

[10]SETHURAMAN J, SQUILLANTE M S. Optimal stochastic scheduling in multiclass parallel queues [J]. ACM Sigmetrics Performance Evaluation Review, 1999, 27(1): 93-102.

[11]TAN M, SIEGEL H J, ANTONIO J K, et al. Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system [J]. IEEE Transactions on Parallel and Distributed Systems, 1997, 8(8): 857-871.

[12]SONG S S, HWANG K, KWOK Y K. Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling [J]. IEEE Transactions on Computers, 2006, 55(6): 703-719.