邱 遠, 虞慧群, 范貴生

(華東理工大學計算機科學與工程系,上海 200237)

?

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

邱 遠, 虞慧群, 范貴生

(華東理工大學計算機科學與工程系,上海 200237)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

M=finishtn-tentry表示工作的運行時長,M必須滿足M≤D。

容錯時間Rt=D-finishtn是衡量一個調(diào)度魯棒性的標準,表示調(diào)度能夠容忍的不確定性。

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

2.1 工作流任務分組

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

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

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

2.2 任務期限分配

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

(1) 兩個同步任務組之間的累計子任務期限必須相同。

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

(3) 任何的子任務期限必須大于等于其對應任務組最少處理時間。

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

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

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

(1)

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

(2)

(3)

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

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

(4)

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

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

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

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

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

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ù)是基于同步任務組的資源調(diào)度。由于同步資源組中僅包含了一個任務,因此可以將調(diào)度簡化為使得該任務組完成時間最快的資源調(diào)度。偽代碼如下:

FunctionSTS-Scheduling

Input:

aselectedtaskpartition

VM={vm1,vm2,…,vmn}

foreachvm∈VMdo

computeeet[i]foreacheachvm

endfor

findtheearliestfinishtimefort

scheduletonvm

BTS-scheduling函數(shù)是基于分支任務組的資源調(diào)度,通過計算每個任務在各個資源上的執(zhí)行時間,根據(jù)目標函數(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 仿真實驗

3.1 實驗設置

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

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

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

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

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

3.2 實驗分析

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

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

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

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

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

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

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

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

圖4 LIGO工作流基于FT模型的平均容忍時間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 結束語

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

在利用MDP-Scheduling進行云資源調(diào)度時,假設所有虛擬結點都以相同的概率發(fā)生故障。然而在實際情況下,可以參考虛擬結點歷史考慮按照歷史資源節(jié)點的故障狀況來選擇調(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)化算法的云計算資源調(diào)度[J].電腦開發(fā)與應用,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

邱 遠(1984-),碩士生,主要研究方向為云計算。E-mail:adidast@163.com

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

TP391

A