基于马尔可夫决策过程的云平台资源调度

邱 远, 虞慧群, 范贵生

(华东理工大学计算机科学与工程系,上海 200237)



基于马尔可夫决策过程的云平台资源调度

邱 远, 虞慧群, 范贵生

(华东理工大学计算机科学与工程系,上海 200237)

云计算平台可以动态地配置资源,适合基于工作流的科学计算。当前云平台的资源调度研究更多考虑运行时长和成本的最优化,而较少提到鲁棒性。本文提出了一种基于马尔可夫决策过程理论的资源调度算法,对工作流任务进行分组,按照任务的计算量和依赖关系将任务期限分配给各个任务组,在满足工作流总期限的基础上,将异构环境中的云资源分配给工作流的各个任务,通过最大化每个任务组的容忍时间使得整个工作流的鲁棒性达到最优。实验结果表明:该调度算法在异构环境中可以在任务期限和开销内提高调度的鲁棒性。

云计算; 资源调度; 马尔可夫决策过程; 鲁棒性

云计算[1]作为一种新兴的大规模分布式计算范型,利用抽象、虚拟化、瞬时部署等关键技术,通过网络数据中心及动态资源池,提供高效率、高可用性、低成本的硬件基础设施和软件应用服务,用户可以根据服务水平协议(SLA)定制存储和计算服务,以“按需使用,按量付费”的方式使用。随着云计算技术的日益发展,云计算系统需要处理大规模的服务请求,资源调度技术作为该领域的核心内容,其调度结果直接影响云计算的服务质量及用户体验,是该领域中的重点和难点。由于云计算平台的动态性和灵活性,资源调度中的鲁棒性是一个重要的考虑因素。鲁棒性是指任务在执行过程中,当资源发生故障或者性能下降时,系统在恢复故障后仍能够在任务期限内完成用户交付的任务,用容错时间来衡量一个系统的鲁棒性。

云计算中,资源调度问题是一个NP-Hard问题,通常使用启发式算法。当前,云环境中的资源调度问题研究主要考虑相同云计算资源在运行时长和成本方面的最优化[2],而较少涉及到系统的鲁棒性。Abrishami等[3]最早提出异构系统资源调度的概念,但没有考虑到系统的鲁棒性。文献[4]提出基于部分关键路径的工作流云资源调度算法,该算法能够在满足用户QoS需求的同时保证执行工作流任务的成本最低,考虑满足总的任务期限,而没有涉及到非关键路径上任务的鲁棒性问题。文献[5]以性能、服务质量及服务成本这3个方面为目标,采用蚁群优化算法和粒子群优化算法混合的方法来调度云资源,能够得到较好的结果,但是该算法整体性能有待提高。此外,网格计算、集群系统和分布式系统研究等领域中的分布式系统[6]、Job-shop调度[7]、供应链系统[8]等研究,能够为云资源调度策略的研究提供借鉴。Shi等[9]提出的基于异构平台的资源调度策略,利用松弛时间提高系统的鲁棒性,该策略尝试在任务期限的约束下寻找最大的松弛时间,然而这个方法并没有考虑云环境的灵活性以及成本模型。

为提高云计算资源调度的鲁棒性,本文提出了一种基于云环境的资源调度算法。该算法根据预先设置的期限约束,将工作流任务进行分组,利用马尔可夫决策过程使任务组的错误容忍时间最大化,将虚拟资源分配给工作流任务。最后使用WorkflowSim对提出的算法进行性能评估。

1 资源调度模型

云计算的资源主要包括计算资源、网络资源和存储资源等,通过虚拟化提供给用户使用。为简化资源调度模型,本文仅考虑计算资源的调度,并有如下假设:

(1) 虚拟资源的数量要小于工作流任务的数量。

(2) 每个任务在每个资源上的执行时间已知。

(3) 任务之间存在依赖,需要传递数据。

本文的资源调度模型是将合适的资源分配给用户提交的工作流任务,建立资源与任务之间的有效映射关系,用S={T,VM,f}表示。其中,T为用户提交的工作流任务集合,VM为虚拟资源集合,f表示任务集合到虚拟资源的映射。

用有向无环图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表示虚拟资源的基本参数,如CPU个数、内存容量、网络带宽等。

f:T→VM表示任务到虚拟资源的映射,是将虚拟资源分配给工作流任务的过程。

M=finishtn-tentry表示工作的运行时长,M必须满足M≤D。

容错时间Rt=D-finishtn是衡量一个调度鲁棒性的标准,表示调度能够容忍的不确定性。

2 资源调度算法

2.1 工作流任务分组

执行资源调度算法需要对工作流任务进行分组。本文将工作流任务分为两类:同步任务和简单任务。前驱结点或后继结点的数量超过1个的任务是同步任务,而前驱结点和后继结点的数量为1的节点是简单任务。

先对任务的类型进行标记,再利用深度优先算法遍历工作流图G,将两个同步任务间连续的简单任务划分为分支组Bi(1≤i≤k),而两端的同步任务划分成同步任务组Yi(1≤i≤l),其中k和l分别是工作流总的分支组数和同步任务组数。

通过任务分组得到一个工作流分组图G(V,E),其中V表示有向无环图中的任务分组结点Vi(1≤i≤k+l),E表示任务组之间的依赖关系。任务分组Vi包含4个属性:就绪时间rt[i],任务期限dl[i],期望执行时间eet[i]和计算量c[i]。

2.2 任务期限分配

在进行资源调度之前,利用广度优先算法与深度优先算法结合的方式遍历整个工作流分组图G(V,E),根据从开始结点到结束结点每条路径中任务分组的计算量按比例将任务期限D分配到G中的每个任务分组Vi中的dl[i]。任务组期限分配需要满足以下3个约束:

(1) 两个同步任务组之间的累计子任务期限必须相同。

(2) 从开始分组Vi(Tentry∈Vi)到结束分组Vi(Texit∈Vi)间的任何路径的累计任务期限等于总的工作流任务期限D。

(3) 任何的子任务期限必须大于等于其对应任务组最少处理时间。

2.3 马尔可夫资源调度

本文将分支资源调度的问题建模成马尔可夫决策过程MDP模型。马尔可夫决策过程是基于马尔可夫过程理论的随机动态系统的最优决策过程,利用该模型可以有效地解决连续决策问题。一个马尔可夫决策过程可以用四元组M=(S,A,T,R)表示,其中S是状态集合,由当前执行的任务、就绪时间以及当前任务在分支中的位置组成。对于每个状态s,存在一个动作集合A,使得MDP模型从一个状态变迁成另一个状态。A中包含的元素ai表示一个资源被分配到一个任务上,动作包含任务输入所需要传输时间加上任务在该资源上的执行时间,以及执行该动作所需要的开销c。T是一个转移函数,定义为T:S×A×S→[0,1],表示动作变迁所产生的效用。R是回报函数,定义为R:S×A×S→R,是从当前状态s采取动作a之后,使得状态变迁成s′而得到的收益,在本文中表示增加的容错时间。通过一个给定的MDP模型(S,A,T,R),可以计算得出一个策略π:S→A。

对于同步任务分组,目标函数为

(1)

值函数是基于当前状态s及策略 π的期望收益即容错时间,见式(2)。

(2)

(3)

其中:γ是打折因子,表示未来状态的收益会随迭代次数的增加而下降;Qπ(s,a)函数表示基于状态s采取行为a所获得的期望收益。

在任意初始状态条件下,一个MDP的最优策略π*可以表示为

(4)

最优调度表示在一个子任务期限的约束下,任务的执行能够匹配到的最优资源,使得值函数的结果达到最大值,从而得到最优调度f。

在状态空间s中求解MDP问题最优解即最优调度是通过基于动态规划算法的值迭代算法实现的。值迭代算法基于当前值的下一个状态计算每个状态的新值,以迭代方式处理并且能够收敛于最优值。值迭代算法将评价和改进两个阶段混合起来,在评价阶段计算值函数的极限,并且不用等其完全收敛,而是尽可能早地停止评价然后基于评价对结果进行改进。该方法在一次迭代后,把改进步骤融合到迭代过程中,集中估算值函数的值,实时地计算必要更新。本质上是将截断版本的评价阶段和改进阶段结合起来。基于值迭代进行改进的值函数可以表示为

值迭代根据上式表示从所有状态的值函数V0开始,一次迭代后更新每个状态对应的下一个值函数Vt,能够产生如下一系列值函数,使得值函数在极限情况下收敛于V*。

2.4 调度算法实现

MDP-Scheduling资源调度算法将调度问题建模成MDP模型利用值迭代的方法,主要包含3个阶段:工作流任务分组、子任务期限分配以及任务组内的资源调度。首先将工作流任务按同步任务和简单任务两种类型进行分组,产生任务分组图G,并且添加伪头结点和伪尾结点。然后,根据任务组的类型和计算量将总的任务期限分配到每个任务分组。最后,根据工作流任务分组的类别,分别运用STS-scheduling和BTS-scheduling进行资源调度,产生一个局部最优的资源调度,将计算资源分配给任务。伪代码如下:

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函数是基于同步任务组的资源调度。由于同步资源组中仅包含了一个任务,因此可以将调度简化为使得该任务组完成时间最快的资源调度。伪代码如下:

FunctionSTS-Scheduling

Input:

aselectedtaskpartition

VM={vm1,vm2,…,vmn}

foreachvm∈VMdo

computeeet[i]foreacheachvm

endfor

findtheearliestfinishtimefort

scheduletonvm

BTS-scheduling函数是基于分支任务组的资源调度,通过计算每个任务在各个资源上的执行时间,根据目标函数及分组任务期限,选择容忍时间最优的资源调度。伪代码如下:

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]仿真程序来仿真基于工作流云平台的任务调度执行。WorkFlowSim仿真程序是CloudSim仿真程序的扩展,增加了对工作流任务的支持,可以定义、部署和调度执行工作流任务。在WorkFlowSim中预先配置故障生成器,模拟云平台发生故障的情况。

算法仿真使用5种工作流应用模型[11],包括Montage、CyberShake、Epigenomics、LIGO和SIPHT,模拟流水线、数据聚集、数据分散和数据再分散的不同工作流类型。实验选择3种工作流任务规模,包含小型(30个任务左右)、中型(100个任务左右)和大型(1 000个任务左右)。

实验的云平台使用一个数据中心,提供9种虚拟资源结点类型用来执行工作流任务。虚拟资源结点的配置形式参照AmazonEC2实例(t2.micro,m3.medium,m3.large,m3.xlarge,m4.xlarge,m4.2xlarge,m4.4xlarge,c4.large,c4.xlarge),按小时计费。

实验选择两种故障模型:第1种是从失败记录Condor-cae中模拟仿真平台中发生故障的情况;第2种是服从均匀分布、故障率为10%的仿真环境。

本文实验选择的参考算法是IaaS云部分关键路径算法(ICPCP)和双目标遗传算法(GA)。ICPCP算法将工作流任务划分成局部关键路径,然后计算最优调度。然而ICPCP算法不是鲁棒的调度算法,不考虑任务期限的因素。GA算法考虑在异构资源情况下通过提高各个任务间的松弛时间使得平台的鲁棒性达到最大。GA算法参数设置如下:种群大小为2 000,组合交叉率为0.9,变异率为0.1,最大迭代数为800,适应度函数和文献中描述的一致。

3.2 实验分析

本文对MDP-Scheduling资源调度算法和ICPCP及GA基于平均容忍时间和平均开销进行对比分析,给出了3种算法在Epigenomics和LIGO工作流模型基于2种故障模型情况下执行20次的平均结果。

图1和图2分别示出了根据Condor-cae中的失败记录(FT)模型及失败概率(FP)模型得到Epigenomics工作流模型的平均容忍时间与任务期限的关系。从图中可以发现,平均容忍时间随着任务期限因子的提高而增加,而图中的负值表示调度算法违反了任务期限的约束,其中MDP-Scheduling资源调度的平均容忍时间最高,而ICPCP算法由于不是鲁棒的工作流调度算法,结果较差。

图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资源调度与其他两种算法相比仍能提供较高的平均容忍时间。

图5和图6示出了平均开销和任务期限的关系。结果表明,MDP-Scheduling资源调度并不能完全有效地控制开销。针对LIGO工作流模型,MDP-Scheduling资源调度的平均开销比ICPCP高23%,而比GA算法低9%。当MDP-Scheduling选择一个较好的容错策略时,其相应的开销也会增大。

以上仿真结果表明,MDP-Scheduling资源调度算法能够在一定任务期限的约束下,提高工作流任务的平均容错时间,并且在开销方面,较GA算法有所提升。面对故障的不确定性和虚拟资源性能变化,MDP-Scheduling资源调度算法能够胜任基于工作流的科学计算任务。

图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 结束语

本文通过对云平台中基于工作流资源调度问题的研究,针对在根据给定任务期情况下考虑云平台的鲁棒性,提出了基于马尔可夫决策过程的工作流资源调度算法MDP-Scheduling。该算法根据分治策略将工作流任务分成同步任务组和分支任务组,利用马尔可夫决策模型,通过迭代求得,从而得到松弛时间最优的资源分配。

在利用MDP-Scheduling进行云资源调度时,假设所有虚拟结点都以相同的概率发生故障。然而在实际情况下,可以参考虚拟结点历史考虑按照历史资源节点的故障状况来选择调度。后续研究将会考虑这方面因素。

[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] 任小金,郭培.基于混合优化算法的云计算资源调度[J].电脑开发与应用,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