文摘

云计算的一个重要问题面临的挑战是虚拟机调度任务,以满足成本和时间要求,同时保持服务质量(QoS)。分配任务到云资源是一个难题,由于消费者的不确定性的未来需求和供应商的多样性资源。先前的研究,在建模或调度方法,可以不再提供一个令人满意的解决方案。在本文中,我们建立一个资源分配框架,提出一种新颖的任务调度算法。提出了一种改进的珊瑚礁优化(ICRO)来处理这个任务调度问题。在ICRO,较好的后代和multicrossover策略提高收敛速度和提高解决方案的质量。此外,小说负载balance-aware突变提高虚拟机之间的负载平衡和调整资源提供给用户的数量。实验结果表明,与其他算法相比,ICRO可以显著降低调度的时间和成本,同时保持一个更好的系统中负载平衡。

1。介绍

云计算(1,2)近年来个人和企业带来了巨大的好处。它提供了大规模和灵活的效用计算服务消费者提供一个良好的硬件和软件的可伸缩性和减少成本。

云服务可以分为三个层次:基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)3,4]。IaaS是计算服务类型广泛用于云计算模式。在这个框架中,虚拟化技术应用于提供资源云用户通过创建虚拟机(vm)有限的硬件。云用户可以访问几乎无限的计算资源以较低的成本(5]。云计算服务提供商,比如IBM智能企业(1和Amazon EC26),负责保证的服务质量(QoS)运行虚拟机。这QoS可能被定义为不同的服务水平协议(sla),可以指定的QoS要求谈判资源,提供者和使用者之间的最低限制,和期望(7]。服务提供商可以提供不同类型的特点是机器配置vm, QoS和价格模型。在这个模型的服务,消费者可以轻松订阅vm来执行他们的任务;相反,有效地调度一个巨大数量的任务是一个关键关心云提供商。

在云计算环境中,资源管理IaaS层负责调度任务的执行。虚拟机调度任务是IaaS层上的关键问题,因为有效的任务映射到虚拟机需要保持活力和异构云计算环境的特点。这个问题有几个额外的因素使它更加难以处理(1)不同的QoS云用户的需求,如服务成本和响应时间,(2)不同类型的云服务任务执行的结合,和(3)大量的数据传输。由此产生的任务调度问题可以被看作是一个组合的问题,全球的最适条件无法轻易获得或由传统的近似算法。事实上,它已被证明是一个np完全问题[8)不能在多项式时间内解决。

云计算任务调度系统已被广泛研究的先前的研究[9- - - - - -13]。然而,在分析大量的任务调度策略,我们观察到的大多数研究都集中在只有少数QoS参数,如响应时间和考。此外,缺乏适当的成本模型(14,15)阻碍当前的调度算法从分析现实情况。此外,不能反映现实的场景调度策略;他们中的大多数认为云资源池的实验是一个固定的一个,和其中的一些优化成本和执行时间同时通过公共云定价模型。的成本和执行时间可以大大影响的任务,例如,能源消耗和可靠性可能直接影响执行时间,和云提供商的现收现付模式将通过成本。

在本文中,一种改进的珊瑚礁优化(ICRO)算法来解决这一任务调度问题。ICRO抢救配置不同数量的资源,同时最小化调度的成本,由Amazon EC2云定价模型(6),也考的调度。

这项工作的主要贡献如下:(我)我们建立一个资源调度模型在一个高度复杂的云环境。(2)我们提出一个方法来解决这个问题在ICRO算法的基础上,考虑到时间和成本的优化调度。(3)我们提出新的重组运营商提高虚拟机之间的负载平衡和调整所需的资源的用户数量。(iv)我们测试的有效性提出了调度方法在不同的场景,不同的性能和指标来证明该方法的鲁棒性和收敛性。我们还与替代现有策略通过实验仿真进行比较。

剩下的论文结构如下。部分2讨论了相关的文学作品。部分3描述了系统模型和问题公式化。节4,该调度方法的细节。进行了广泛的实验来评估我们的设计节的功效5。部分6总结了论文的最终结论和一些话。

2。相关工作

资源和任务调度16- - - - - -19)异构云计算系统是一个非常重要的部分,因为它大大影响服务的质量,利润,在系统的操作过程和成本。有几个资源等云计算具有不同特点的处理器,存储、记忆,和软件等。反过来,大量的用户提交的任务需要处理这些资源。这使得资源和任务调度云计算提供商的严重挑战。

近年来,metaheuristic算法已经被用来处理这个资源调度问题的启发式算法,可以在多项式时间近似最优解。启发式算法在文献中提出这个问题主要有三种不同类型的方法:列表调度,集群,duplication-based调度(20.]。列表调度,主要有两个阶段在云计算资源调度过程:在第一阶段,重点应该分配给每个子任务顺序进行的。子任务将分配给处理器在第二阶段。优先级通常由通信和计算成本,如异构最早完成时间(影响力)15)或关键路径上的处理器(CPOP) [15]。在聚类算法,任务的集合命名集群将被分配到适当的处理器,如MLA (21]。一些duplication-based算法存在(22]。他们认为重复任务以最大完工时间最小化。注意,一般来说,确定性启发式不能产生高质量和一致的结果当问题的规模增长。

不同于heuristic-based算法,metaheuristic方法可以获得有竞争力的解决方案即使在非常困难的问题,通过与概率特征(包括不同的搜索过程23]。几个metaheuristic调度算法提出了有效地分配云资源提供者提供者的观点的效率,如负载平衡、利用率最大化和能源消耗。在[24),一只蜜蜂colony-based平衡算法,它可以平衡工作负载在vm通过考虑任务的优先级,从大量虚拟机加载。虽然这种方法可以减少响应时间和平衡负载,它不考虑过程的总成本。在[25),穆罕默德等人提出了一个离散的共生有机体搜索优化算法的任务调度问题。这种调度算法的目标是减少时间和最小化vm之间的不平衡度。然而,它不使用任何策略提高vm之间的平衡。此外,它没有考虑在调度过程中成本。在[26),温家宝等人提出了一种混合算法由算法和PSO改进云资源和利用收音机。在这个算法,算法过程帮助避免算法早熟。在[27),一个影子价格策略提出了指导遗传算法的进化方向,从而反映云资源的能源消耗。结果表明,该算法比传统的遗传调度算法。

除了云提供商的频谱资源调度,也存在众多工作的调度算法从用户的角度来看,如时间、用户成本,和应用程序的性能。在[28),作者提供一个成本高效的调度算法的并行任务调度。减少低成本竞争任务,这种方法使用加权随机安排政策将资源分配给的任务。尽管如此,他们引入了一个固定数量的资源算法没有考虑各种资源。在[29日),作者产生混合bicriteria调度算法调度工作流在云。这种方法旨在减少选择的标准,由用户指定。实验结果证明,这种方法超越了加入最短queue-scheduling算法。虽然这种方法使用资源的数量,这可以由用户指定,它不能保证最优利用云计算系统。左et al。30.]介绍了一种方法来解决任务调度问题。在他们的算法,建立了一个资源分配框架;服务提供者被允许将任务外包给外部云。自适应学习粒子群优化(PSO)调度算法来分配用户的任务来最大化利润的服务提供者。然而,这项工作在24)不提供一个合适的方法来设置虚拟机的数量或控制资源的数量。在[31日),一个沟通和storage-aware多目标调度策略是用来解决调度问题的大型集独立袋的任务。合作游戏theoretic-based任务调度算法被引入。虽然这个调度程序可以优化成本和时间,同时考虑带宽限制在不同的vm,它没有战略,选择合适的虚拟机的数量。此外,它没有考虑虚拟机之间的负载均衡。

在[32),Bahman等人提出了一种改进的遗传算法调度的方法来实现最佳的时间。在这种方法中,一个行为建模方法提出了基于模型检测技术分析的正确性,和一个标记转换系统(LTS)方法被用来获得最佳性能的验证算法。然而,这种方法没有考虑成本优化和不同数量的vm。

Zhang et al。13)提出了一种基于顺序优化调度方案(OO)方法。调度程序应用工作流的常数vm。为了减少调度时间,他们延长了OO方法最初开发的复杂动态系统来减少搜索空间。实验结果证明,该方法可以显著减少调度开销时间相比,基于重复的蒙特卡罗随机抽样。然而,这个计划缺乏指导用户选择资源的数量。

在[33),作者介绍了一种自适应调度算法科学工作流在云中。此外,调度工作流在三个目标,考,可靠性和顶尖成本,这种方法还可以向上和向下扩展的资源根据来源数据捕获并在运行时查询。实验结果表明,该方法优于MapReduce系统[34]。

2.1。珊瑚礁的优化

珊瑚礁优化(CRO)是一个metaheuristic算法,基于珊瑚繁殖和珊瑚礁的配方35在[],提出36),被应用到各种复杂优化问题(37- - - - - -39]。阴极射线示波器提出了全球最适条件很好的收敛性质。在[40],CRO一直使用到一个特定的问题的涡轮机的布局的海上风电场,显示优势对其他metaheuristic算法,如微分进化,和声搜索算法,和特殊的进化方法。在[41],CRO-SL算法已经成功地用来解决电池的问题安排在一个微型智能电网"可再生发电和电力价格变量,可以明显提高电池的确定性使用在所有的测试用例。在[42),阴极射线示波器已应用于最优参数的识别一个永磁同步电动机,优于粒子群优化算法与最小二乘法获得最佳的一组电机的参数。我们与改进提出ICRO multicrossover和负载balance-aware突变是更强大的比原来的CRO的版本,因为它包含了不同的程序进行搜索。

从现有文献的分析,我们可以发现,CRO已经成功地应用于不同的优化问题。相反,云资源调度领域的研究取得了一些成果,但仍存在一些缺点,例如,没有有效地保证用户的QoS和虚拟机之间的负载平衡不是同时充分考虑。为了解决这些问题,我们提出一种改进的版本的CRO, ICRO-based调度算法,不仅考虑如何有效地降低成本和时间还考虑虚拟机之间的负载平衡。

3所示。建模和配方

本节给出了系统框架和调度问题的模型。

3.1。系统框架

资源分配的系统框架如图1。在这个框架中,用户的请求提交到系统通过用户请求分析器,然后,在分析,这些请求转发到请求经理。请求经理负责收集和管理所有接受请求。全球和本地资源监视器共同管理云资源,即。vm。本地资源的本地监控工作节点。调度器是关键组件和时间表任务到云资源使用该调度方法。具体来说,首先,调度程序收集和资源信息的请求从请求经理和全球资源监控器,分别。然后,分析了需求的任务和资源的情况。最后,它的任务分配适当的资源。

3.2。问题建模

我们的工作集中在并行和独立的任务。每个任务可以大规模数据处理、科学计算、大规模图像呈现。数据挖掘等应用程序或传感器数据分析(43),这种类型的任务通常是应用。

让 是一组虚拟机,让 是一组任务。每个任务必须执行在一个VM。不能中断任务一旦开始运行。在本文中,我们针对云资源分配任务的集合的最大完工时间最小化成本和作业。作为主要约束的问题,注意,在任何时间段 ,所有任务使用的资源总量不得超过所提供的总资源提供者。

制定这个问题,说明表中给出的参数定义1和2。这个问题是制定如下模型。

最小化 这话题

方程(1)代表的时间由用户提交的任务。方程(2)显示的总成本在vm执行的所有任务。约束(3)和(4)保证供应商不能使用CPU和内存资源超出其能力。约束(5)和(6)确保每个任务必须执行,只有在一个虚拟机执行。

4所示。提出了调度方法

在本文中,我们提出一种改进的CRO-based调度方法来解决上述的调度问题。ICRO,每个珊瑚(潜在的解决问题)代表一组任务应该分配资源。它经历有性生殖的过程(广播产卵和沉思的),无性生殖(萌芽)和掠夺。最后,健康的珊瑚将生存下来,这意味着该算法获得的最好的解决方案将被保留和推广ICRO在接下来的步骤。提高性能的原始CRO调度问题,multicrossover,负载balance-aware突变和较好的后代策略应用。

4.1。原始的阴极射线示波器

在最初的CRO (35),每个珊瑚(代表候选人解决问题)可以分配在一个正方形的礁拥有MN的平方网格。CRO始于随机分配的一些广场被珊瑚礁石,但是其它的一些将是空的。礁的占领广场的比例是非常重要的算法的动态和演化,它通常设置为 。将评估每个珊瑚健康功能,也就是说,珊瑚是健康,最可能的,他们将为下一代生存的算法。

初始化后,阴极射线示波器进行第二阶段的珊瑚礁的形成。在此阶段,阴极射线示波器模拟珊瑚的繁殖通过一系列的操作:有性繁殖(广播产卵和沉思的),无性生殖(萌芽)[35)、息肉掠夺。性和无性繁殖后,形成一组幼虫(35),为了找到一个平方增长,他们将试图对抗其他珊瑚被分配在广场或者广场自由如果它是空的。如果幼虫不能分配一个成长的地方,他们会灭亡。这个过程会重复,直到满足给定的停止标准。原始CRO的步骤总结如下:步骤1:随机分配的一些广场被珊瑚礁石。步骤2:广播产卵(外部有性生殖)。这一步包含两个步骤:步骤2.1:随机选择的一小部分在礁珊瑚广播已成熟的雌鱼。步骤2.2:随机选择夫妇已成熟的雌鱼,每一个都将产生珊瑚幼虫的交叉操作,将被释放到水中。步骤3(沉思的有性生殖(内部):在这个步骤中,没有珊瑚将形成珊瑚幼虫通过随机变异brooding-reproductive珊瑚;然后,珊瑚幼虫将被释放到水中。步骤4(幼虫设置):健康(健康)将计算每个形成珊瑚幼虫的健康功能,然后,珊瑚幼虫拥有更好的健康功能将被分配到的广场被现有的珊瑚。第五步(无性繁殖):现有的珊瑚礁石将按健康,其中一小部分会重复自己,并试图解决在不同的地方的珊瑚礁遵循步骤4中描述的过程。步骤6(掠夺在息肉阶段):少量的珊瑚礁石将掠夺的繁殖以释放空间礁珊瑚的一代。第七步:停止条件是否满足,输出最好的珊瑚和健身;否则,转到第2步。

4.2。ICRO-Based调度方法

ICRO是将任务分配给云资源优化成本和执行时间。摘要CRO的运营商仔细调整在vm分配任务。首先,在步骤1中,珊瑚是随机初始化和分配给礁的广场。步骤2 - 11主循环发展。步骤3 - 6应用广播产卵(外部有性生殖)操作。multicrossover操作和较好的后代策略是用来帮助ICRO产生更好的后代。拟议中的变异操作窝珊瑚幼虫第7步中有性生殖(内部)。无性生殖是一样的原始阴极射线示波器。步骤8评估每一个珊瑚使用方程(7)。之后,一些珊瑚是毁坏珊瑚礁为下一代来释放空间。算法停止,直到满足停止准则,然后返回解决方案(步骤12)最好的健身价值。显示了ICRO算法的伪代码1。

4.2.1。准备珊瑚和适应度函数

珊瑚(个人)珊瑚人口代表一个完整的任务调度,每个维度的珊瑚代表一个任务和所需的虚拟机。珊瑚的长度大小的提交任务。表3显示了一个示例的珊瑚。的位置,尺寸1代表任务1和维度的位置2代表任务2。同样,第一个维度1和3的值表明任务1将分配给VM3执行。的价值维度2和4分配任务2 VM4等等。

珊瑚可以评估质量的适应度函数。函数(7每个珊瑚)分配一个健身价值基于其成本和时间每一代人。适应度函数如下所示: 在哪里的成本吗我珊瑚,和代表所有珊瑚的最大和最小成本,考的吗我珊瑚,和代表所有珊瑚的最大和最小极小化,分别和分别考和成本权重,让用户分配给定的优化目标和优先级 。在这篇文章中,他们都是设置为0.5。

4.2.2。广播产卵

ICRO利用的轮盘赌选择的珊瑚礁石播出已成熟的雌鱼,然后生产珊瑚幼虫通过应用multicrossover操作。为了提高性能和原始CRO的覆盖率,使用较好的后代的策略。

multicrossover操作如图2。三个父母的交叉操作中使用原来的作物。与原来的CRO, multicrossover操作旨在帮助CRO在更大范围的搜索,从而提高种群的多样性。multicrossover操作的细节提出了算法2。

较好的后代策略旨在加速收敛,因此提高阴极射线示波器的性能。这是描述的算法3。圆是改进应用这一策略的时候。随机突变中使用这一策略。

4.2.3。沉思的

ICRO,沉思的有性生殖(内部)类似于原始的CRO,除了负载balance-aware突变操作是用来减少虚拟机之间的不平衡。拟议中的变异操作的详细算法所示4。

无性生殖的操作和破坏仍然是一样的原始CRO,已在部分的细节4。

5。实验结果和分析

5.1。实验设计

几个问题实例展示在表4用于验证我们的特定的调度方法的有效性在这工作。VM实例类型和EC价格(6)根据设置(6),表中给出4。CPU和内存都选择这个工作,因为有两个典型的配置为用户和云服务提供商44]。vm的其他参数设置为4 GB内存,100 M / s绑定宽度,和10 GB存储。三种不同类型的任务实例设计;小型、中型和大型的任务都包含在这些类型的测试实例,分别。这些类型的测试实例表所示5- - - - - -7。

5.2。方法相比

ICRO-based调度算法比较与原CRO-based调度算法(OCRO-SA)和标准遗传调度算法(GA-SA) [45),先到先得(先)46调度算法。

的参数ICRO-SA和OCRO-SA保持不变的36),除了单点交叉和随机变异操作用于OCRO-SA。这两个操作也在GA-SA就业。人口大小设置为100;max一代被设置为10000。测试实例,OCRO-SA的终止判据,ICRO-SA, GA-SA是几代人的最大数量。

5.3。实验结果

该调度方法的性能评估使用云模拟器基于CloudSim [47- - - - - -49]。CloudSim是一个广义模拟框架,该框架允许建模、模拟和试验的云计算基础设施和应用程序服务(47]。所有模拟运行在PC机与64位英特尔酷睿i5处理器10和12 GB内存使用windows操作系统。每个算法执行30独立运行每个测试实例。一个双边Mann-WhitneyU测试是对每个实验结果统计是否和明显不同(95%的置信区间内)从相应的ICRO-SA结果。结果以粗体并不显著。

5.3.1。性能在不同类型的任务

时间和成本的常用指标是评估一个调度方法。在本节中,三个不同的测试实例的平均成本和考了30分的所有调度方法与100年,300年、500年和1000年的任务和100年vm给出了表8- - - - - -10和数字3和4。

我们可以观察到ICRO-SA比获得的平均时间和成本的方法相比,在几乎所有的测试用例。例如,ICRO-SA最大完工时间提高了77.08%,90.25%,和636.12%的大型任务实例(1000任务)与其他三种方法相比,分别和改善成本的中型任务实例任务(300)6.58%,9.28%,和40.99%,分别。这是因为ICRO有更好的搜索能力由于其multicrossover操作和较好的后代策略,它可以保持多样性,在调度过程中加快算法的收敛。

GA-SA获得的结果,也比OCRO-SA,这意味着,通过改善原来的阴极射线示波器的操作,该调度方法ICRO-SA可以更好地处理云调度问题。它还可以看到,该方法实现相对复杂的测试实例的性能改进(大型任务实例)比小型任务实例,这意味着ICRO-SA更有能力处理更复杂的任务调度问题比approaches.where相比任务的执行时间是我虚拟机,所有虚拟机之间的平均执行时间,米是虚拟机的数量。

5.3.2。算法收敛性和负载平衡

本节分析了ICRO-SA的全局探索能力。的收敛曲线OCRO-SA、ICRO-SA GA-SA三测试实例如图5- - - - - -7,分别。它可以观察到,搜索阶段,初原比ICRO CRO-SA可以更快地收敛,但不能做任何改进在以后的演进(在图5之后,1600年的演进,而ICRO连续探索找到一个更好的解决方案的能力,这可以解释为较好的后代策略可以产生更好的后代在每个迭代中加快搜索过程。GA-SA最低收敛速度较其他方法。我们也可以观察到,在图5,OCRO-SA ICRO-SA几乎具有相同的收敛性能由于任务的数量是100,和虚拟机的数量也是100;因此,将这些任务分配给虚拟机就更容易了。

负载平衡是非常重要的在某些情况下,大量的任务需要分配有限的云资源。它也反映了在云计算调度算法的性能。我们使用不平衡的程度的度量(DI)说明了负载平衡,计算如下。

DI四的调度算法结果的测试实例给出了表11。它可以观察到,DI结果ICRO-SA比几乎所有其他调度方法相比在三个测试实例。这意味着,一方面,该算法可以获得更短的时间比其他方法相比与一个可以接受的平衡工作负载;与此同时,它有一个更低的成本。另一方面,为了达到一个更好的时间和成本,负载平衡将被牺牲掉。任务的执行时间在每个虚拟机数据所示8- - - - - -10。22日,48和69 VM,类似CPU的人物8然而,22日和48 VM比69便宜VM;该交易安排不是第69 VM分配更多的任务。事实上,ICRO-SA不分配任务的69 VM,但将任务分配给其他更便宜的VM。类似于12日,第37,第57 VM,类似CPU的人物9,ICRO-SA只分配任务的101 VM,的价格低于33th和55 VM。

5.3.3。虚拟机的数量的影响

在本节中,ICRO-SA的行为与其他算法进行了分析和比较。四种调度方法将为所有可能的VM和生产调度计划将开始安排从一个虚拟机,然后,增加虚拟机的数量,直到满足停止条件。这些结果提出了数字11和12。

从这些结果,我们可以观察到调度方法不适用更多的云资源超越一个特定的vm。例如,ICRO-SA达到一个值(4.85)150 vm,如图11;然而,它不能改善当增加虚拟机的数量。它也可以观察到ICRO-SA可以获得非常相似的执行时间,而采用较低数量的vm。考时是150,vm受雇于ICRO-SA, OCRO-SA, GA-SA是60,80年和80年,分别。一般来说,所有四个本文方法不需要大量的虚拟机的最大完工时间最小和成本。

6。结论

在本文中,我们提出了一个资源调度系统在云计算环境下资源分配问题。一种改进的珊瑚礁文中针对(ICRO)调度方法已经提出了这个问题。ICRO增强原CRO通过有目的的修改在其内部和外部的有性繁殖操作。拟议中的ICRO实现multicrossover和较好的后代策略产生更多健康的后代,而不是原始的复制操作。它还使用了一个balance-aware突变增强虚拟机之间的负载平衡。这些改进可以减少算法的随机性,专注搜索,比原来的作物。实验结果表明,该方法是有效的和高效的调度问题。ICRO结果比原CRO也优于标准遗传算法和先获得的对于不同类型的任务,在一个合理的运行时。

数据可用性

没有数据被用来支持本研究。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作的部分支持由英国工程和物理科学研究委员会,在格兰特EP / K001310/1,湖北省重点实验室智能视觉监控为基础的水电工程,中国三峡大学,中国,在批准号2017 sdsj06,中国国家自然科学基金批准号下U1703261。