基于Kriging代理模型的动态云任务调度方法

李召军 ，李 征 ，王希诚 ，李克秋

1.大连理工大学 计算机科学与技术学院，辽宁 大连 116023

2.大连理工大学 工业装备结构分析国家重点实验室，辽宁 大连 116023

1 引言

云计算提供了一种按需分配的服务模式，凭借云平台提供的高性能软硬件资源运行作业，可以在较大程度上为用户节约计算成本和运行时间。任务调度作为云计算环境下资源调度的一个重要子课题，其好坏程度直接影响了用户的使用体验。近年来，智能优化算法在云计算的任务调度领域发展迅速。如果能够使用有效的方法对复杂环境下的云任务进行性能分析和建模，优化计算后获取其最佳的资源分配方案，将对云平台本身的资源分配模式及用户的使用体验产生重要的影响。

本文发展了一种基于Kriging代理模型的动态云任务调度方法：该方法使用Kriging代理模型建立云任务一种有效的有限时间的资源分配方案与其计算性能之间存在的近似模型，从而方便地计算出最优的资源调度策略；而云平台所提供的API函数能够对云任务进行动态的资源配给，最终达到最合理和最高效的资源分配目的。为检验该方法在云计算任务调度中的效果，本文对OpenStack平台下两个工程计算应用的云任务进行调度测试；统计数据表明，本文提出的方法可有效应用在云计算环境下的类似任务调度问题中。

2 研究背景

2.1 云计算及任务调度问题

经过近十年左右的发展，云计算领域逐渐形成了以基础设施云（IaaS）、平台云（PaaS）和软件云（SaaS）等为代表的平台系统，按照虚拟化的不同层次对外提供服务[1]。商业云平台如Amazon EC2、Google App Engine、Microsoft Azure、阿里云、百度云等正为全世界范围内的用户提供各式服务；而如CloudStack、OpenStack等开源云平台的崛起也正在改变着云计算世界的版图[2-3]。

任务调度问题是云计算领域的资源调度问题之一，可简单描述为将用户的作业请求（CPU、内存、文件等资源的集合）映射到系统的虚拟资源（通常是虚拟机，VM）上并执行的过程。通常使用一种预计完成时间（ETC）矩阵对云任务调度问题进行分析：其长度为云任务的数量，宽度为VM数量，矩阵的元素为云任务在指定的VM上运行的时间。按任务之间的相互关系，云任务调度问题可分为元调度问题（任务之间无依赖关系）及存在依赖关系的调度问题[4-5]。本文仅分析元调度问题。

云任务调度问题的目标通常包括响应时间，资源负载，服务成本等。显然，云任务调度问题是典型的NP难问题，使用一个良好的调度算法可以极大增加用户的使用粘度，并提高云系统本身的资源使用效率。然而在复杂的云应用环境下，特别是对于大型工程应用数量众多的云平台而言，一个准确或有效的ETC通常是很难获取的，如何能够使用代理模型分析这类应用任务在不同资源组合下的计算特征，正在成为一个重要的新兴研究课题[6-7]。

2.2 任务调度算法

先来先服务（FCFS）算法、短作业优化算法、轮循（RR）算法等传统操作系统层面的算法是最先应用在云任务调度问题中的算法，其特点是简单易行[8-9]。而针对云任务调度问题的特殊性，许多新型算法也被广泛发展，如Huang提出了元节点的调度策略[10]，Lee设计了考虑云服务和其他服务的成本模型的算法[11]，Garg发展了以最小碳排放和最大经济效益为目标的多数据中心调度算法等[12]。

同时，诸如遗传算法、粒子群算法、蚁群算法等启发式智能算法也在云任务调度问题中得到广泛应用。例如Mezmaz提出基于遗传算法的混合式算法以获取最小能量损耗和最小响应时间[13]，Li发展了负载平衡的蚁群算法试图在获取最小响应的同时平衡整个系统的负载[14]，Pandey设计了基于粒子群算法的调度策略，用以同时考虑任务计算成本和数据传输成本[15]。

2.3 Kriging代理模型

假设样本组为X=[x1，x2，…，xn]，对应的响应值为y，Kriging模型可构建为[16-17]：

该模型包含线性回归部分和随机部分。β为回归系数，f(x)为确定性漂移，通常使用x的多项式形式对整个设计域进行全局近似，随机函数z(x)为波动，对整个设计域进行局部近似，其均值为0，方差可表示为σ2。

工程领域经常使用称为DACE的开源Matlab优化工具箱来建立样本与响应的Kriging替代函数模型。使用者可简单提供样本及响应值数据，并设定好一个用来定义模型建立精确度的θ函数值，用以创建最基本的Kriging代理模型。

2.4 OpenStack开源云平台

OpenStack是由Rackspace和NASA所发起的开源基础设施云平台项目，现在已经发展成为包括150多个商业公司及2 000多个研究组织所共同参与的云计算科研项目。OpenStack通常由负责租户及用户管理的keystone模块、镜像管理的glance模块、存储管理的cinder模块、网络管理的quantum模块和计算管理的nova模块等五个核心模块组成。OpenStack同时提供RESTful的编程接口（API），云服务提供商可根据自己的需求开发适合自己的云平台，从而为终端用户提供计算资源及定制化的服务[18-19]。如图1所示。

图1 OpenStack架构

3 基于Kriging代理模型的动态云任务调度方法

3.1 调度的目标函数确立

在某种资源分配下，考虑具有类似图2所示的资源和时间的计算特征的云应用：（1）应用中有若干近似平稳的计算期（SP），亦即平稳期内对资源的使用没有较大的变化，平稳期之间是过渡期（TP）；（2）平稳期的持续时间要远大于过渡期的时间。

图2 资源和时间的计算特征

通常情况下，以工程计算为代表的资源密集型应用具有上述特点：该类应用在某些特定计算阶段对资源的耗费相对集中，密集程度较高，可抽象为平稳期；相应的，不同计算时期之间的逻辑程序调整、分析和计算等过程，则可抽象为过渡期。通常情况下，类似应用的SP和TP的时间片设定可由应用开发人员自行完成，并由云平台开发者针对云环境下的特殊情况提供必要的调整和优化解决方案。同时，对于不同的资源分配方案，此类应用一般呈现如图3所示的资源和分配的计算特征：（1）随着资源分配不断增长，资源的实际使用量不断增加；（2）存在一个应用可最大利用的资源上限，亦即应用所最大需要的资源分配量。

图3 资源和分配的计算特征

例如，没有并行性的应用程序通常只能使用一个CPU物理核心，一个32位的应用程序通常不能使用超过4 GB的内存。假定对第i个资源Pi分配的资源数量为Pi(s)，而应用在该SP中实际需要的i资源数量为Pi(n)，Ui为资源的使用率，则该应用在第i个资源上消耗的时间可近似表示为：

考虑到所有可能的资源数i=1，2，…，k，k为资源种类的总数量，则式（2）可表示为：

而资源消耗总量则为：

若要获取最短的响应时间和最小资源消耗，则T应该尽可能的小，C也应该尽可能的小，表示为：

考虑到Pi(n)为未知的特定常数，并且使用加权求和方法将式（5）和式（6）转化为单目标优化问题，可得：

使用加权方式组合式（7）和式（8），可得

式（9）即本文所使用的调度目标函数，该式可理解为最大化应用所真正利用的计算资源的同时，减少因为应用可能达到如图3所示的峰值点后所造成的资源浪费。

3.2 基于应用的抽样

一般地，抽样是工程领域为对应用进行分析使用通用或特定抽样算法从设计变量的设计域内生成一系列样本点的过程。样本生成之后，作为输入由特定的分析软件计算后获得其响应值（特定的关键数据值）。样本和响应均得到之后，则可对该应用从整体层面分析、理解。

就云任务的调度问题而言，若要分析出应用对于不同资源分配的性能表现，则可定义样本组为不同的资源数量组合，即x=[P1(n)，P2(n)，…，Pk(n)]，对应的响应可定义为资源的使用率，即y=[U1，U2，…，Uk]。为从理论上对应用的资源使用率和分配值进行分析，本文采用如下所述的基于应用的抽样方式：

（1）在每个SP开始前，云任务暂停计算过程。

（2）保存计算的上下文到数据库中并上传到平台后端，如关键变量的值，重要的参数文件等。

（3）基于用户定义的资源分配数量上下限，随机生成m个（通常至少4倍或5倍于设计变量的维度，从而保证Kriging替代函数模型的有效性）样本组X=[x1，x2，…，xm]，作为资源分配的组合。

（4）平台后端通过API启动具有如上样本值（资源数量组合）的虚拟机样本实例。

（5）样本实例下载已经保存好的计算上下文到本地，开启SP计算较短时间过程（可因应用和SP的持续时间而异，本文采用60秒）。

（6）样本实例收集该应用在该SP内的计算特征，如CPU和内存使用率等，集中发送到云任务所在的主机上作为响应组Y=[y1，y2，…，ym]，以供下述资源优化过程所用。

（7）平台后端关闭所有的样本实例，并发送唤醒信号给暂停的云任务。

（8）云任务接收到唤醒信号，进行资源的优化过程。

3.3 云任务资源的优化

通过抽样过程所得到的相关样本和响应数据，云任务可以使用预先在其主机镜像中内置的DACE模块开启优化过程，描述为：

（1）基于样本点（资源的数量组合X=[x1，x2，…，xm]）和响应值（资源的使用率Y=[y1，y2，…，ym]），使用DACE工具箱建立k个Kriging代理模型，从而获得所有k种资源对该应用任务的影响情况模型。

（2）使用优化算法计算（本文使用基于梯度的序列二次规划方法）对应于应用任务，该SP的最优值xopt，优化的目标函数按3.1节的式（9）进行定义。

（3）上述最优值即为云任务该SP下最佳的资源调度组合，该组合将作为后续云任务资源重新调度时的输入值，因此作为数据上传到平台后端保存。

优化过程包含三个子任务过程：建立Kriging替代函数过程、优化计算过程、结果上传过程。DACE模块具有强大的矩阵运算处理功能，因此前两者的时间消耗非常低；平台提供的强大API支持可以保证最后一个子任务在较短的时间内完成。因此，资源优化过程一般只需要20～30 s的计算时间，远小于云任务本身所持续的时间，可以忽略不计。

3.4 云任务的资源重新调度

xopt获取之后，平台后端即可相应地做出云任务资源的重新分配，从技术层面上讲，即是对运行着的云任务主机重新分配计算资源的过程。一般地，这种动态的主机资源分配过程需要虚拟机管理软件的支持，从而保证主机在短暂夯机（或挂起）后重新启动时，数据的正确和一致性。比较流行的开源云平台通常已经将常用虚拟机管理软件的类似API进行了功能包装、增强，并提供给云服务商方便地使用。借助云平台的特定API函数，可以对云任务的资源分配进行动态的调整，亦即“resize”的过程。本文建立的是基于OpenStack开源云平台的测试环境，OpenStack平台对主机动态资源配置的API函数是nova的resize命令，其主要参数是主机的编号和其重新调度后的资源组合编号（flavor id），而调整结束后需要手动（或者由系统定义一个时间阀）确认调整的完成，整个过程需要事先使用验证信息（租户名称tenant name、用户名user name等）获得keystone模块的操作令牌（token）。基于这些条件，该过程可简单表述如下：

（1）使用诸如tenant name，user name等的身份信息与keystone模块通信，获取操作所需要的令牌（token）。

（2）检测是否有如优化解xopt的资源组合存在（flavor）；如果不存在，则使用nova模块的flavor添加命令增加该组合，并最终获得该资源组合编号（id）。

（3）使用nova模块API的resize指令，对该云任务所在主机的资源按得到的资源组合编号进行重新分派。

（4）当resize操作结束后（OpenStack平台下主机将呈现“VERIFY_RESIZE”状态），使用nova模块的对应于resize指令的确定（confirm）命令完成该重新调度操作。

（5）平台后端唤醒主机上的云任务，云任务继续计算任务，使用其新配给的资源方案xopt，开启接下来的SP过程。

重新调度（resize）操作的执行时间可因云平台硬件及软件（虚拟机管理软件等）性能的不同而有所差异，通常来说可从30秒到几分钟不等。就所建立的测试平台而言，在使用了NFS文件系统和高性能的固态硬盘运行应用实例后，该过程可在30秒左右，与云任务本身而言，这个过程的时间消耗也同样可以忽略不计。

3.5 运行机制

为更好地描述本文所提出的动态调度方法，本节对包含用户、平台后端和任务主机（由虚拟机生成的云任务计算载体）三个实体的运行机制进行分析和描述，如图4所示。

关键步骤说明：

（1）用户通过平台门户申请要运行某个应用的任务并提交相关的作业信息，诸如初始资源方案、调度模式（初始分配、动态配置）等，并定义其任务计算资源的上下限。

（2）平台后端按要求完成对应任务的初始化工作（数据库操作、日志记录、权限检测等），返回该任务运行的任务主机编号给用户。

（3）用户向任务主机提交运算任务请求。

（4）平台后端按初始资源对任务主机进行调度，启动相应的虚拟机主机。

（5）任务主机按应用要求配置其计算环境和完成相应的初始化工作（主机名定义、IP地址分配等）。

（6）在新SP即将到来之前，使用3.2节的方法对该应用进行抽样。

（7）抽样结束后，利用3.3节的方法对应用任务该SP下的计算资源配置进行优化计算。

（8）优化计算完成后，平台后端按照优化后的资源配比使用3.4节的方法对任务主机重新调度。

（9）主机上的云任务按应用的要求完成任务的该SP阶段计算。

（10）没有新的SP且所有计算结束后，平台后端将对该任务主机进行销毁，回收其占用的计算资源。

图4 运行机制

4 测试算例

我们开发了包括汽轮机基础优化和模具分析的两个工程计算应用，用来测试本文所提出的动态任务调度方法。两个应用均具有第三章所描述的计算特征，并分别有2个和4个SP，且它们的任务主机初始化时间均约为12分钟。鉴于过渡期的时间较短，因此在时间耗费统计时与相邻的上一个SP合并，方便分析数据。简单起见，这里仅对包括虚拟CPU和虚拟MEM的两类计算资源进行调度测试。

两个测试应用均采用[1，2]和[6，12]的资源分配上下限（分别为虚拟CPU和虚拟MEM），且应用任务的初始资源使用方案均定义为[3，6]。任务执行时的抽样样本点数量设定为8个。

4.1 测试算例一

测试算例一具有2个SP，并有约12分钟的初始化期。该算例调度情况如图5和图6所示，每单位时间片代表3分钟（180 s）。

图5 算例一的虚拟CPU调度

算例中云任务的SP时间片始终范围分别为#1 SP（5～54），（5～46）和#2 SP（55～126），（47，112）（初始分配在前）。对比于初始分配的资源组合[3，6]，采取3.1节所描述的目标函数进行动态调度后，该应用任务优化后的两个SP资源组合分别为[3，7]和[4，7]，在大幅度减少任务的响应时间的同时（14个时间片），并未增加过多的资源消耗。

图6 算例一的虚拟MEM调度

4.2 测试算例二

测试算例二具有4个SP，并同样具有约12分钟的初始化期。该算例的调度情况如图7和图8所示，每个单位时间片的长度也为3分钟（180 s）。

图7 算例二的虚拟CPU调度

图8 算例二的虚拟MEM调度

算例中云任务的SP时间片始终范围分别为#1 SP（5～26），（5～27）、#2 SP（27～62），（28，65）、#3 SP（63，92），（66，90）和#4 SP（93，161），（91，154）（初始分配在前）。从图7和图8中可以看出，使用第3章的方法进行动态任务调度后，该任务优化后的SP资源配给分别为[2，7]，[3，5]，[1，8]和[4，6]。从某些 SP上看，初始分配方案具有更高的资源数组合，会有一些响应时间上的优势（如#1 SP）；不过从整体上看，优化过后的调度方案，整体资源的分配更合理：在耗费了[453，959]计算资源的前提下，仅使用了154个时间片即完成了整个任务；相应的，初始分配策略使用了共计[483，966]计算资源，却使用了更多的161个时间片完成该任务。

4.3 结果分析与讨论

一般的，云应用任务的响应时间和资源耗费是两个矛盾的因素：较快的响应时间通常意味着更多的计算资源投入（如算例一）。然而，如果能够合理地分析出云应用的计算特征，获取出其在不同资源配比下的性能表现，就能够作出合理的资源调度：在投入了较少的资源时，反而能够得到较快的响应时间（如算例二）。工程算例复杂多样，对不同资源的需求也不尽相同，若能使用Kriging替代函数模型获取这些应用的特定计算特征并优化计算得到其最优资源分配，将在加快这些应用任务的执行速度的同时，降低任务消耗的资源总量。

本文第3章所发展的调度目标函数，忽略了云应用不同阶段（SP和TP等）有可能出现的不同资源消耗权重问题，而选择相同的加权因子整合它们；同时对于响应时间和资源消耗，也采取了相同的加权系数进行整合。在未来的生产环境中，通过云应用开发人员和用户共同设计符合特定要求的调度函数，并使用类似本文第3章的方法调度，将有望得到一种“所付即所需”的云服务体验。

5 结束语

云计算为用户提供了一种以服务作为形式使用计算机软硬件资源的新型途径。而数据中心作为云平台的核心结构，必须能够及时和高效地对用户提交的任务进行调度执行。本文发展了一种基于Kriging代理模型的方法，可应用在云任务的动态调度问题中。该方法将Kriging代理函数模型建立在云任务的资源配给和其对应的计算性能特征之上，并按照设定好的目标函数进一步计算得到其最佳的优化资源分配方案。通过对汽轮机基础优化和模具设计两个工程计算应用组成的测试算例分析可知，本文所发展的方法可有效应用在云任务的动态调度问题中：在尽可能得到较快的响应时间的同时，减少任务所消耗的计算资源总量。

Kriging代理模型方案仅是众多的替代函数模型中使用较为广泛的一种，其他的如神经网络也可以类比地迁移到该问题当中；本文所设计的优化目标函数，是基于云任务特别是资源密集型的工程应用的共性，并按照若干假设而提出的，可在实际使用时作出必要的修正；适应于求解代理模型的优化算法也有很多，序列二次规划只是常用的基于梯度的一种，使用不同的优化算法，最终的优化解也不尽相同。同时，本文所提出的动态调度方法，是从云任务相对微观的资源层面进行分析和优化，从而得出其有针对性的资源解决方案。类似的解决思路也可以应用在宏观层面：从全局的高度去分析云任务，势必也将对云任务的资源调度产生同样积极的影响。

[1]张建勋，古志民，郑超.云计算研究进展综述[J].计算机应用研究，2010，27（2）：429-433.

[2]Bist M，Wariya M，Agarwal A.Comparing delta，open stack and Xen Cloud Platforms：A survey on open source IaaS[C].Ghaziabad，2013.

[3]von Laszewski G，Diaz J，Fugang W，et al.Comparison of multiple cloud frameworks[C].Honolulu，HI，2012.

[4]T Ograph B，Morgens Y R.Cloud computing[J].Communications of the ACM，2008，51（7）.

[5]Zhong H，Tao K，Zhang X.An approach to optimized resource scheduling algorithm for open-source cloud systems[C].2010.

[6]朱宗斌，杜中军.基于改进GA的云计算任务调度算法[J].计算机工程与应用，2013，49（5）：77-80.

[7]史恒亮.云计算任务调度研究[D].南京：南京理工大学，2012.

[8]Singh A，Malhotra M.A comparative analysis of resource scheduling algorithms in cloud computing[J].American Journal of Computer Science and Engineering Survey，2013，1（1）：14-32.

[9]Bhattacharya A A，Culler D，Friedman E，et al.Hierarchical scheduling for diverse datacenter workloads[C].ACM，2013.

[10]Huang Y，Bessis N，Norrington P，et al.Exploring decentralized dynamic scheduling for grids and clouds using the community-aware scheduling algorithm[J].Future Generation Computer Systems，2013，29（1）：402-415.

[11]Lee Y C，Wang C，Zomaya A Y，et al.Profit-driven scheduling for cloud services with data access awareness[J].Journal of Parallel and Distributed Computing，2012，72（4）：591-602.

[12]Garg S K，Yeo C S，Anandasivam A，et al.Environmentconscious scheduling of HPC applications on distributed cloud-oriented data centers[J].Journal of Parallel and Distributed Computing，2011，71（6）：732-749.

[13]Mezmaz M，Melab N，Kessaci Y，et al.A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[J].Journal of Parallel and Distributed Computing，2011，71（11）：1497-1508.

[14]Li K，Xu G，Zhao G，et al.Cloud task scheduling based on load balancing ant colony optimization[J].IEEE，2011.

[15]Pandey S，Wu L，Guru S M，et al.A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[J].IEEE，2010.

[16]Ryu J，Kim M，Cha K，et al.Kriging interpolation methods in geostatistics and DACE model[J].KSME International Journal，2002，16（5）：619-632.

[17]高月华，张崎，王希诚.基于Kriging模型的汽轮机基础动力优化设计[J].计算力学学报，2008，25（5）：610-615.

[18]Bist M，Wariya M，Agarwal A.Comparing delta，open stack and Xen cloud platforms：A survey on open source IaaS[C].Ghaziabad，2013.

[19]Schmidberger M，Schmidberger M.Software engineering as a service for HPC[C].Munich：2012.