邱 遠(yuǎn), 虞慧群, 范貴生

(華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海 200237)

?

基于馬爾可夫決策過程的云平臺資源調(diào)度

邱 遠(yuǎn), 虞慧群, 范貴生

(華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海 200237)

云計(jì)算平臺可以動(dòng)態(tài)地配置資源,適合基于工作流的科學(xué)計(jì)算。當(dāng)前云平臺的資源調(diào)度研究更多考慮運(yùn)行時(shí)長和成本的最優(yōu)化,而較少提到魯棒性。本文提出了一種基于馬爾可夫決策過程理論的資源調(diào)度算法,對工作流任務(wù)進(jìn)行分組,按照任務(wù)的計(jì)算量和依賴關(guān)系將任務(wù)期限分配給各個(gè)任務(wù)組,在滿足工作流總期限的基礎(chǔ)上,將異構(gòu)環(huán)境中的云資源分配給工作流的各個(gè)任務(wù),通過最大化每個(gè)任務(wù)組的容忍時(shí)間使得整個(gè)工作流的魯棒性達(dá)到最優(yōu)。實(shí)驗(yàn)結(jié)果表明:該調(diào)度算法在異構(gòu)環(huán)境中可以在任務(wù)期限和開銷內(nèi)提高調(diào)度的魯棒性。

云計(jì)算; 資源調(diào)度; 馬爾可夫決策過程; 魯棒性

云計(jì)算[1]作為一種新興的大規(guī)模分布式計(jì)算范型,利用抽象、虛擬化、瞬時(shí)部署等關(guān)鍵技術(shù),通過網(wǎng)絡(luò)數(shù)據(jù)中心及動(dòng)態(tài)資源池,提供高效率、高可用性、低成本的硬件基礎(chǔ)設(shè)施和軟件應(yīng)用服務(wù),用戶可以根據(jù)服務(wù)水平協(xié)議(SLA)定制存儲和計(jì)算服務(wù),以“按需使用,按量付費(fèi)”的方式使用。隨著云計(jì)算技術(shù)的日益發(fā)展,云計(jì)算系統(tǒng)需要處理大規(guī)模的服務(wù)請求,資源調(diào)度技術(shù)作為該領(lǐng)域的核心內(nèi)容,其調(diào)度結(jié)果直接影響云計(jì)算的服務(wù)質(zhì)量及用戶體驗(yàn),是該領(lǐng)域中的重點(diǎn)和難點(diǎn)。由于云計(jì)算平臺的動(dòng)態(tài)性和靈活性,資源調(diào)度中的魯棒性是一個(gè)重要的考慮因素。魯棒性是指任務(wù)在執(zhí)行過程中,當(dāng)資源發(fā)生故障或者性能下降時(shí),系統(tǒng)在恢復(fù)故障后仍能夠在任務(wù)期限內(nèi)完成用戶交付的任務(wù),用容錯(cuò)時(shí)間來衡量一個(gè)系統(tǒng)的魯棒性。

云計(jì)算中,資源調(diào)度問題是一個(gè)NP-Hard問題,通常使用啟發(fā)式算法。當(dāng)前,云環(huán)境中的資源調(diào)度問題研究主要考慮相同云計(jì)算資源在運(yùn)行時(shí)長和成本方面的最優(yōu)化[2],而較少涉及到系統(tǒng)的魯棒性。Abrishami等[3]最早提出異構(gòu)系統(tǒng)資源調(diào)度的概念,但沒有考慮到系統(tǒng)的魯棒性。文獻(xiàn)[4]提出基于部分關(guān)鍵路徑的工作流云資源調(diào)度算法,該算法能夠在滿足用戶QoS需求的同時(shí)保證執(zhí)行工作流任務(wù)的成本最低,考慮滿足總的任務(wù)期限,而沒有涉及到非關(guān)鍵路徑上任務(wù)的魯棒性問題。文獻(xiàn)[5]以性能、服務(wù)質(zhì)量及服務(wù)成本這3個(gè)方面為目標(biāo),采用蟻群優(yōu)化算法和粒子群優(yōu)化算法混合的方法來調(diào)度云資源,能夠得到較好的結(jié)果,但是該算法整體性能有待提高。此外,網(wǎng)格計(jì)算、集群系統(tǒng)和分布式系統(tǒng)研究等領(lǐng)域中的分布式系統(tǒng)[6]、Job-shop調(diào)度[7]、供應(yīng)鏈系統(tǒng)[8]等研究,能夠?yàn)樵瀑Y源調(diào)度策略的研究提供借鑒。Shi等[9]提出的基于異構(gòu)平臺的資源調(diào)度策略,利用松弛時(shí)間提高系統(tǒng)的魯棒性,該策略嘗試在任務(wù)期限的約束下尋找最大的松弛時(shí)間,然而這個(gè)方法并沒有考慮云環(huán)境的靈活性以及成本模型。

為提高云計(jì)算資源調(diào)度的魯棒性,本文提出了一種基于云環(huán)境的資源調(diào)度算法。該算法根據(jù)預(yù)先設(shè)置的期限約束,將工作流任務(wù)進(jìn)行分組,利用馬爾可夫決策過程使任務(wù)組的錯(cuò)誤容忍時(shí)間最大化,將虛擬資源分配給工作流任務(wù)。最后使用WorkflowSim對提出的算法進(jìn)行性能評估。

1 資源調(diào)度模型

云計(jì)算的資源主要包括計(jì)算資源、網(wǎng)絡(luò)資源和存儲資源等,通過虛擬化提供給用戶使用。為簡化資源調(diào)度模型,本文僅考慮計(jì)算資源的調(diào)度,并有如下假設(shè):

(1) 虛擬資源的數(shù)量要小于工作流任務(wù)的數(shù)量。

(2) 每個(gè)任務(wù)在每個(gè)資源上的執(zhí)行時(shí)間已知。

(3) 任務(wù)之間存在依賴,需要傳遞數(shù)據(jù)。

本文的資源調(diào)度模型是將合適的資源分配給用戶提交的工作流任務(wù),建立資源與任務(wù)之間的有效映射關(guān)系,用S={T,VM,f}表示。其中,T為用戶提交的工作流任務(wù)集合,VM為虛擬資源集合,f表示任務(wù)集合到虛擬資源的映射。

用有向無環(huán)圖W=(T,E,D)表示工作流,其中T={t1,t2,…,tn}表示任務(wù)集合,tentry表示進(jìn)入結(jié)點(diǎn),texit表示退出結(jié)點(diǎn);E={e1,e2,…,en}表示任務(wù)之間的依賴關(guān)系;D表示工作流的任務(wù)期限約束。

VM={vm1,vm2,…,vmn}表示對應(yīng)虛擬云資源的集合。每個(gè)虛擬資源由vmk={vmIdk,vmDatak}(k∈[1,n])表示,其中vmIdk表示虛擬資源編號,vmDatak表示虛擬資源的基本參數(shù),如CPU個(gè)數(shù)、內(nèi)存容量、網(wǎng)絡(luò)帶寬等。

f:T→VM表示任務(wù)到虛擬資源的映射,是將虛擬資源分配給工作流任務(wù)的過程。

M=finishtn-tentry表示工作的運(yùn)行時(shí)長,M必須滿足M≤D。

容錯(cuò)時(shí)間Rt=D-finishtn是衡量一個(gè)調(diào)度魯棒性的標(biāo)準(zhǔn),表示調(diào)度能夠容忍的不確定性。

2 資源調(diào)度算法

2.1 工作流任務(wù)分組

執(zhí)行資源調(diào)度算法需要對工作流任務(wù)進(jìn)行分組。本文將工作流任務(wù)分為兩類:同步任務(wù)和簡單任務(wù)。前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的數(shù)量超過1個(gè)的任務(wù)是同步任務(wù),而前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的數(shù)量為1的節(jié)點(diǎn)是簡單任務(wù)。

先對任務(wù)的類型進(jìn)行標(biāo)記,再利用深度優(yōu)先算法遍歷工作流圖G,將兩個(gè)同步任務(wù)間連續(xù)的簡單任務(wù)劃分為分支組Bi(1≤i≤k),而兩端的同步任務(wù)劃分成同步任務(wù)組Yi(1≤i≤l),其中k和l分別是工作流總的分支組數(shù)和同步任務(wù)組數(shù)。

通過任務(wù)分組得到一個(gè)工作流分組圖G(V,E),其中V表示有向無環(huán)圖中的任務(wù)分組結(jié)點(diǎn)Vi(1≤i≤k+l),E表示任務(wù)組之間的依賴關(guān)系。任務(wù)分組Vi包含4個(gè)屬性:就緒時(shí)間rt[i],任務(wù)期限dl[i],期望執(zhí)行時(shí)間eet[i]和計(jì)算量c[i]。

2.2 任務(wù)期限分配

在進(jìn)行資源調(diào)度之前,利用廣度優(yōu)先算法與深度優(yōu)先算法結(jié)合的方式遍歷整個(gè)工作流分組圖G(V,E),根據(jù)從開始結(jié)點(diǎn)到結(jié)束結(jié)點(diǎn)每條路徑中任務(wù)分組的計(jì)算量按比例將任務(wù)期限D(zhuǎn)分配到G中的每個(gè)任務(wù)分組Vi中的dl[i]。任務(wù)組期限分配需要滿足以下3個(gè)約束:

(1) 兩個(gè)同步任務(wù)組之間的累計(jì)子任務(wù)期限必須相同。

(2) 從開始分組Vi(Tentry∈Vi)到結(jié)束分組Vi(Texit∈Vi)間的任何路徑的累計(jì)任務(wù)期限等于總的工作流任務(wù)期限D(zhuǎn)。

(3) 任何的子任務(wù)期限必須大于等于其對應(yīng)任務(wù)組最少處理時(shí)間。

2.3 馬爾可夫資源調(diào)度

本文將分支資源調(diào)度的問題建模成馬爾可夫決策過程MDP模型。馬爾可夫決策過程是基于馬爾可夫過程理論的隨機(jī)動(dòng)態(tài)系統(tǒng)的最優(yōu)決策過程,利用該模型可以有效地解決連續(xù)決策問題。一個(gè)馬爾可夫決策過程可以用四元組M=(S,A,T,R)表示,其中S是狀態(tài)集合,由當(dāng)前執(zhí)行的任務(wù)、就緒時(shí)間以及當(dāng)前任務(wù)在分支中的位置組成。對于每個(gè)狀態(tài)s,存在一個(gè)動(dòng)作集合A,使得MDP模型從一個(gè)狀態(tài)變遷成另一個(gè)狀態(tài)。A中包含的元素ai表示一個(gè)資源被分配到一個(gè)任務(wù)上,動(dòng)作包含任務(wù)輸入所需要傳輸時(shí)間加上任務(wù)在該資源上的執(zhí)行時(shí)間,以及執(zhí)行該動(dòng)作所需要的開銷c。T是一個(gè)轉(zhuǎn)移函數(shù),定義為T:S×A×S→[0,1],表示動(dòng)作變遷所產(chǎn)生的效用。R是回報(bào)函數(shù),定義為R:S×A×S→R,是從當(dāng)前狀態(tài)s采取動(dòng)作a之后,使得狀態(tài)變遷成s′而得到的收益,在本文中表示增加的容錯(cuò)時(shí)間。通過一個(gè)給定的MDP模型(S,A,T,R),可以計(jì)算得出一個(gè)策略π:S→A。

對于同步任務(wù)分組,目標(biāo)函數(shù)為

(1)

值函數(shù)是基于當(dāng)前狀態(tài)s及策略 π的期望收益即容錯(cuò)時(shí)間,見式(2)。

(2)

(3)

其中:γ是打折因子,表示未來狀態(tài)的收益會隨迭代次數(shù)的增加而下降;Qπ(s,a)函數(shù)表示基于狀態(tài)s采取行為a所獲得的期望收益。

在任意初始狀態(tài)條件下,一個(gè)MDP的最優(yōu)策略π*可以表示為

(4)

最優(yōu)調(diào)度表示在一個(gè)子任務(wù)期限的約束下,任務(wù)的執(zhí)行能夠匹配到的最優(yōu)資源,使得值函數(shù)的結(jié)果達(dá)到最大值,從而得到最優(yōu)調(diào)度f。

在狀態(tài)空間s中求解MDP問題最優(yōu)解即最優(yōu)調(diào)度是通過基于動(dòng)態(tài)規(guī)劃算法的值迭代算法實(shí)現(xiàn)的。值迭代算法基于當(dāng)前值的下一個(gè)狀態(tài)計(jì)算每個(gè)狀態(tài)的新值,以迭代方式處理并且能夠收斂于最優(yōu)值。值迭代算法將評價(jià)和改進(jìn)兩個(gè)階段混合起來,在評價(jià)階段計(jì)算值函數(shù)的極限,并且不用等其完全收斂,而是盡可能早地停止評價(jià)然后基于評價(jià)對結(jié)果進(jìn)行改進(jìn)。該方法在一次迭代后,把改進(jìn)步驟融合到迭代過程中,集中估算值函數(shù)的值,實(shí)時(shí)地計(jì)算必要更新。本質(zhì)上是將截?cái)喟姹镜脑u價(jià)階段和改進(jìn)階段結(jié)合起來。基于值迭代進(jìn)行改進(jìn)的值函數(shù)可以表示為

值迭代根據(jù)上式表示從所有狀態(tài)的值函數(shù)V0開始,一次迭代后更新每個(gè)狀態(tài)對應(yīng)的下一個(gè)值函數(shù)Vt,能夠產(chǎn)生如下一系列值函數(shù),使得值函數(shù)在極限情況下收斂于V*。

2.4 調(diào)度算法實(shí)現(xiàn)

MDP-Scheduling資源調(diào)度算法將調(diào)度問題建模成MDP模型利用值迭代的方法,主要包含3個(gè)階段:工作流任務(wù)分組、子任務(wù)期限分配以及任務(wù)組內(nèi)的資源調(diào)度。首先將工作流任務(wù)按同步任務(wù)和簡單任務(wù)兩種類型進(jìn)行分組,產(chǎn)生任務(wù)分組圖G,并且添加偽頭結(jié)點(diǎn)和偽尾結(jié)點(diǎn)。然后,根據(jù)任務(wù)組的類型和計(jì)算量將總的任務(wù)期限分配到每個(gè)任務(wù)分組。最后,根據(jù)工作流任務(wù)分組的類別,分別運(yùn)用STS-scheduling和BTS-scheduling進(jìn)行資源調(diào)度,產(chǎn)生一個(gè)局部最優(yōu)的資源調(diào)度,將計(jì)算資源分配給任務(wù)。偽代碼如下:

Algorithm1MDP-SchedulingAlgorithm

Input:

AworkflowgraphG(T,E)

DeadlineDforworkflow

VM={vm1,vm2,…,vmn}

convertG(T,E) to G’(V,E,D)

addpseudoheadandtailnodesforG′

distributedeadlineDover?T∈G′

repeat

s←unscheduled task partitions

foreachi∈S

computereadytimert[i]

findravailablebetweenrt[i]anddl[i]

ifiisabranchpartitionthen

callBTS-Schedulingfunction

else

callSTS-Schedulingfunction

endif

endfor

untilallpartitionshasbeenscheduled

STS-scheduling函數(shù)是基于同步任務(wù)組的資源調(diào)度。由于同步資源組中僅包含了一個(gè)任務(wù),因此可以將調(diào)度簡化為使得該任務(wù)組完成時(shí)間最快的資源調(diào)度。偽代碼如下:

FunctionSTS-Scheduling

Input:

aselectedtaskpartition

VM={vm1,vm2,…,vmn}

foreachvm∈VMdo

computeeet[i]foreacheachvm

endfor

findtheearliestfinishtimefort

scheduletonvm

BTS-scheduling函數(shù)是基于分支任務(wù)組的資源調(diào)度,通過計(jì)算每個(gè)任務(wù)在各個(gè)資源上的執(zhí)行時(shí)間,根據(jù)目標(biāo)函數(shù)及分組任務(wù)期限,選擇容忍時(shí)間最優(yōu)的資源調(diào)度。偽代碼如下:

FunctionBTS-Scheduling

Input:

aselectedtaskpartitionV

VM={vm1,vm2,…,vmn}

m←V.length,n←VM.length

letr[0…m,0…m]andeet[0,…,m,0,…,n]benewtables

fori←0tomdo

r[i,j]←0

endfor

computeeet[i,j]foreachtaskoneachvm

π*←0

foreachsinSdo

v←V(s)

foreachainA(s)do

endfor

V(s) ←maxQ(s,a)

π*←max(π*,|v-V(s)|)

assignvmjontaskireferbya

endfor

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用WorkFlowSim[10]仿真程序來仿真基于工作流云平臺的任務(wù)調(diào)度執(zhí)行。WorkFlowSim仿真程序是CloudSim仿真程序的擴(kuò)展,增加了對工作流任務(wù)的支持,可以定義、部署和調(diào)度執(zhí)行工作流任務(wù)。在WorkFlowSim中預(yù)先配置故障生成器,模擬云平臺發(fā)生故障的情況。

算法仿真使用5種工作流應(yīng)用模型[11],包括Montage、CyberShake、Epigenomics、LIGO和SIPHT,模擬流水線、數(shù)據(jù)聚集、數(shù)據(jù)分散和數(shù)據(jù)再分散的不同工作流類型。實(shí)驗(yàn)選擇3種工作流任務(wù)規(guī)模,包含小型(30個(gè)任務(wù)左右)、中型(100個(gè)任務(wù)左右)和大型(1 000個(gè)任務(wù)左右)。

實(shí)驗(yàn)的云平臺使用一個(gè)數(shù)據(jù)中心,提供9種虛擬資源結(jié)點(diǎn)類型用來執(zhí)行工作流任務(wù)。虛擬資源結(jié)點(diǎn)的配置形式參照AmazonEC2實(shí)例(t2.micro,m3.medium,m3.large,m3.xlarge,m4.xlarge,m4.2xlarge,m4.4xlarge,c4.large,c4.xlarge),按小時(shí)計(jì)費(fèi)。

實(shí)驗(yàn)選擇兩種故障模型:第1種是從失敗記錄Condor-cae中模擬仿真平臺中發(fā)生故障的情況;第2種是服從均勻分布、故障率為10%的仿真環(huán)境。

本文實(shí)驗(yàn)選擇的參考算法是IaaS云部分關(guān)鍵路徑算法(ICPCP)和雙目標(biāo)遺傳算法(GA)。ICPCP算法將工作流任務(wù)劃分成局部關(guān)鍵路徑,然后計(jì)算最優(yōu)調(diào)度。然而ICPCP算法不是魯棒的調(diào)度算法,不考慮任務(wù)期限的因素。GA算法考慮在異構(gòu)資源情況下通過提高各個(gè)任務(wù)間的松弛時(shí)間使得平臺的魯棒性達(dá)到最大。GA算法參數(shù)設(shè)置如下:種群大小為2 000,組合交叉率為0.9,變異率為0.1,最大迭代數(shù)為800,適應(yīng)度函數(shù)和文獻(xiàn)中描述的一致。

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

本文對MDP-Scheduling資源調(diào)度算法和ICPCP及GA基于平均容忍時(shí)間和平均開銷進(jìn)行對比分析,給出了3種算法在Epigenomics和LIGO工作流模型基于2種故障模型情況下執(zhí)行20次的平均結(jié)果。

圖1和圖2分別示出了根據(jù)Condor-cae中的失敗記錄(FT)模型及失敗概率(FP)模型得到Epigenomics工作流模型的平均容忍時(shí)間與任務(wù)期限的關(guān)系。從圖中可以發(fā)現(xiàn),平均容忍時(shí)間隨著任務(wù)期限因子的提高而增加,而圖中的負(fù)值表示調(diào)度算法違反了任務(wù)期限的約束,其中MDP-Scheduling資源調(diào)度的平均容忍時(shí)間最高,而ICPCP算法由于不是魯棒的工作流調(diào)度算法,結(jié)果較差。

圖1 Epigenomics工作流基于FT模型的平均容忍時(shí)間Fig.1 Tolerance time of Epigenomics with FT model

圖2 Epigenomics工作流基于FP模型的平均容忍時(shí)間Fig.2 Tolerance time of Epigenomics with FP model

圖3和圖4則示出了LIGO工作流的平均容忍時(shí)間與任務(wù)期限的關(guān)系。由于LIGO工作流較Epigenomics工作流并行度稍低,所以平均容忍時(shí)間總體較低,而MDP-Scheduling資源調(diào)度與其他兩種算法相比仍能提供較高的平均容忍時(shí)間。

圖5和圖6示出了平均開銷和任務(wù)期限的關(guān)系。結(jié)果表明,MDP-Scheduling資源調(diào)度并不能完全有效地控制開銷。針對LIGO工作流模型,MDP-Scheduling資源調(diào)度的平均開銷比ICPCP高23%,而比GA算法低9%。當(dāng)MDP-Scheduling選擇一個(gè)較好的容錯(cuò)策略時(shí),其相應(yīng)的開銷也會增大。

以上仿真結(jié)果表明,MDP-Scheduling資源調(diào)度算法能夠在一定任務(wù)期限的約束下,提高工作流任務(wù)的平均容錯(cuò)時(shí)間,并且在開銷方面,較GA算法有所提升。面對故障的不確定性和虛擬資源性能變化,MDP-Scheduling資源調(diào)度算法能夠勝任基于工作流的科學(xué)計(jì)算任務(wù)。

圖3 LIGO工作流基于FP模型的平均容忍時(shí)間Fig.3 Tolerance time of LIGO with FP model

圖4 LIGO工作流基于FT模型的平均容忍時(shí)間Fig.4 Tolerance time of LIGO with FT model

圖5 Epigenomics基于FP模型的平均開銷Fig.5 Cost of Epigenomics with FP model

圖6 LIGO基于FT模型的平均開銷Fig.6 Cost of LIGO with FT model

4 結(jié)束語

本文通過對云平臺中基于工作流資源調(diào)度問題的研究,針對在根據(jù)給定任務(wù)期情況下考慮云平臺的魯棒性,提出了基于馬爾可夫決策過程的工作流資源調(diào)度算法MDP-Scheduling。該算法根據(jù)分治策略將工作流任務(wù)分成同步任務(wù)組和分支任務(wù)組,利用馬爾可夫決策模型,通過迭代求得,從而得到松弛時(shí)間最優(yōu)的資源分配。

在利用MDP-Scheduling進(jìn)行云資源調(diào)度時(shí),假設(shè)所有虛擬結(jié)點(diǎn)都以相同的概率發(fā)生故障。然而在實(shí)際情況下,可以參考虛擬結(jié)點(diǎn)歷史考慮按照歷史資源節(jié)點(diǎn)的故障狀況來選擇調(diào)度。后續(xù)研究將會考慮這方面因素。

[1] BUYYA R,YEA C S,VENUGOPAL S,etal.Cloud computing and emerging IT platforms:Vision,hype,and reality for delivering computing as the 5th utility[J].Future Generation Computer Systems,2009,25(6):599-616.

[2] PANDEY S,KARUNAMOORTHY D,BUYYA R.Workflow Engine for Clouds[M]// Cloud Computing:Principles and Paradigms.USA:John Wiley& Sons Inc,2011:321-344.

[3] ABRISHAMI S,NAGHIBZADEH M,EPEMA D H J.Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[J].Future Generation Computer Systems,2013,29(1):158-169.

[4] ABRISHAMI S,NAGHIBZADEH M,EPEMA D H J.Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[J].Future Generation Computer Systems,2013,29(1):158-169.

[5] 任小金,郭培.基于混合優(yōu)化算法的云計(jì)算資源調(diào)度[J].電腦開發(fā)與應(yīng)用,2014 (11):1-6.

[6] SHESTAK V,SMITH J,SIEGEL H J,etal.A stochastic approach to measuring the robustness of resource allocations in distributed systems[C]//Proceedings of the 2006 International Conference on Parallel Processing.Columbus,Ohio,USA:IEEE,2006:459-470.

[7] JORGE L V,WU S D,ROBRT S.Robustness measures and robust scheduling for job shops[J].IIE Transactions,1994,26(5):32-43.

[8] HERROLEN W,LEUS R.Project scheduling under uncertainty:Survey and research potentials[J].European Journal of Operational Research,2005,165(2):289-306.

[9] SHI Zhiao,JEANNOT E,DONGARRA J J.Robust task scheduling in non-deterministic heterogeneous computing systems[C]// 2006 IEEE International Conference on Cluster Computing.Barcelona:IEEE,2006:1-10.

[10] CHEN Weiwei,DEELMAN E.WorkflowSim:A toolkit for simulating scientific workflows in distributed environments[C]// 2012 IEEE 8th International Conference on E-Science (e-Science).USA:IEEE,2012:1-8.

[11] BHARATHI S,CHERVENAK A,DEELMAN E,etal.Characterization of scientific workflows[C]//Third Workshop on Workflows in Support of Large-Scale Science.USA:IEEE,2008:1-10.

Markov Decision Processes Based Resource Scheduling in Cloud Environment

QIU Yuan, YU Hui-qun, FAN Gui-sheng

(Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

The characteristic of provisioning resource dynamically in cloud platform is suitable for the scientific computation of workflows.The existing works on workflow scheduling mainly consider the factors of makespan and cost optimization,and have little involving in robustness.In this paper,a resource scheduling algorithm based on Markov decision process theory is proposed,in which the tasks of the whole workflow are partitioned and the deadline on task partitions based on calculation time of task is distributed.Under the requirement that the deadline of whole workflow is not violated,the proposed algorithm makes the tolerance time maximum,and finally allocates resources on workflow tasks in heterogeneous cloud environment.The experimental results show that the proposed algorithm could effectively improve the robustness of the schedule within a given deadline and budget.

cloud computing; resource scheduling; Markov decision processes; robustness

1006-3080(2016)05-0702-06

10.14135/j.cnki.1006-3080.2016.05.018

2015-11-20

邱 遠(yuǎn)(1984-),碩士生,主要研究方向?yàn)樵朴?jì)算。E-mail:adidast@163.com

虞慧群,E-mail:yhq@ecust.edu.cn

TP391

A