云计算环境任务调度方法研究综述

2021-01-22田倬璟黄震春张益农

计算机工程与应用 2021年2期

关键词：多云任务调度调度

田倬璟，黄震春，张益农

1.北京联合大学北京市信息服务工程重点实验室，北京100101

2.清华大学计算机科学与技术系，北京100084

3.国家超级计算无锡中心，江苏无锡214072

4.北京信息科学与技术国家研究中心，北京100084

5.北京联合大学城市轨道交通与物流学院，北京100101

云计算利用互联网和虚拟机技术，通过少量管理工作，以虚拟化形式提供随时可用、可重新配置和无处不在的计算资源，在这种范例中，用户利用互联网和远程数据中心来运行应用程序和存储数据。云计算技术按使用服务付费的方式为用户提供了高效可扩展的计算能力，消除了用户硬件配置维护成本，目前已发展成为一种流行且高效的计算范例[1]。

云计算环境是一个典型的分布式计算环境，任务调度是指在IaaS 层，根据任务和资源的实际情况，将任务分配到最佳资源上进行执行的过程。在云计算环境中，任务的类型、状态、数量随时变化，资源具有异构性和扩展性，可自由组合为不同的任务提供服务。性能良好的任务调度算法可以优化服务质量参数（QoS），如最大完工时间、响应时间、吞吐量、资源利用率、任务拒绝率、可靠性、可伸缩性、能耗、执行成本等，并可以在不违反服务级别协议（SLA）的前提下，考虑各类约束，例如截止日期、优先级、经济成本等，实现用户的硬指标约束，同时可避免负载不均衡的发生，这是一个典型的NP 困难问题。目前，随着用户应用程序对云数据中心计算资源需求的逐渐增加，资源争用、服务中断、交互能力缺乏、QoS 性能降低、SLA 违反等问题日益严重；此外，传统单个云环境存在资源不足，服务部署易受故障影响，导致服务中断和低可用性，因此促使产生了跨云环境（inter-cloud）来解决此类问题。

任务调度算法的类型根据不同的分类方式具有不同的定义。根据任务的类型，可把任务调度分为独立任务调度和工作流调度，根据任务调度算法的特点，可将算法分为启发式、元启发式和混合式，根据任务运行的环境，可分为单云环境任务调度和跨云环境任务调度。

独立任务彼此之间没有关联关系，只需按照用户要求分配到指定虚拟机即可，而工作流的任务之间存在执行顺序，运行较为复杂。通常工作流由有向无环图（DAG）表示，节点表示任务所需的计算过程，边表示任务之间的数据通信，除了一般商业应用程序生成的业务工作流（business workflow）之外，天文学、生物信息学、地震科学和物理学等领域建立的科学应用程序构成了科学工作流（scientific workflow），典型科学工作流包括Montage、LIGO、CyberShake、SIPHT 和Epigenomics 等，独立任务和科学工作流都属于单次执行作业。

启发式算法是一类基于直观或经验构造的算法，其在可接受的计算时间和空间下给出待解决的组合优化问题的一个可行解，但无法保证结果最优，且调度周期较长。元启发式算法是随机算法和局部搜索算法结合的产物，这些算法独立于问题，寻找NP困难问题的近似最优解，针对大范围寻优问题提供搜索流程，一般需要至少一个初始可行解，在预定义的搜索空间高效迭代搜索以改进解，这类算法往往具有较高的时间复杂度，但由于具有较高的解的精度，整体调度周期缩短了。混合式算法是两种以上算法结合的算法统称，这类算法在一定程度上降低了局部最优解的发生率，但时间复杂度更高，且性能结果差异较大。

当一个云以即付即用的方法对公众开放使用时，它被称为公有云，当一个云属于企业或组织，不对公众开放使用时，被称为私有云，云环境包含大量独立、异构的私有云和公有云，这些彼此没有联系的云构成了单云环境。随着计算需求的逐渐增大，单云环境无法满足庞大的计算需求，为了集成聚合云服务以实现无缝的基础设施，提出了跨云环境，包括混合云（Hybrid Cloud）、联盟云（Federated Cloud）和多云（Multi Cloud）。

已存在一些相关的研究调度[2-6]，但并不完全针对任务调度，往往和资源调度合并阐述，而且着重点并不是任务调度自身的特点和环境适应性特征。本文针对独立任务和科学工作流对任务调度按照单云环境与跨云环境进行分类讨论，在单云环境中梳理了现有的不同种类的任务调度算法类型，并选取相关代表文献进行总结分析；在跨云环境中，结合跨云环境的特征，探讨任务调度算法在不同云环境下的适应性特征，并对部分跨云环境下的任务算法文献进行总结分析；最后，讨论任务调度算法研究中存在的不足和未来研究趋势，为云计算环境下任务调度的进一步研究提供参考。

1 单云任务调度

单云任务调度的主要流程为用户通过服务接口向云计算系统提交作业请求，任务管理器收到作业请求后，对其进行分类、排序等预处理，分为独立任务队列和工作流任务队列，并根据成本、执行时间、截止时间等参数对任务进行排序，任务调度器收到处理过的任务集后，通过考虑了各类QoS参数的算法按要求得出从任务到资源的分配方案，资源信息服务器（RIS）根据分配方案将任务分配到指定的虚拟机资源上执行，同时会监视和收集所有任务和资源的信息，并将其发送给任务调度器，以便任务调度器优化后续任务分配，负载均衡器负责对已经分配给资源上的任务进行二次分配，以防资源负载过重，流程如图1所示。而云内任务调度算法主要分为启发式、元启发式和混合式三大类。

图1 单云环境任务调度流程

1.1 启发式任务调度

启发式任务调度分为静态调度和动态调度两大类。在静态调度中，所有任务在调度之前都是已知的，并将它们静态分配给虚拟资源；在动态调度方法中，任务本质上是动态的，在这里，任务在不同的时间点到达，动态调度可分为在线模式和批处理模式，在线模式下，任务一经到达系统就会立即分配，批处理模式下，任务被作为一个组进行收集，并在预定义的时间进行调度。启发式算法包括min-min、max-min、先来先服务（FCFS）、最短作业优先（SJF）、时间片轮询（RR）、最小执行时间（MCT）、最小完成时间（MET）、机会负载均衡（OLB）[7]、爬山算法、sufferage算法[8]、异构最早完成时间（HEFT）[9-10]等。近年来，也出现了新的方法，如主成分分析[11]。

独立任务的静态调度算法包含一些基本简单策略，如FCFS、RR、SJF，而动态调度算法中，min-min、maxmin 和动态RR 是批处理模式的算法，MCT、MET、OLB属于在线模式。FCFS、min-min、max-min目前一般为云仿真平台的默认调度算法，由于云环境异构任务动态的特点，动态调度较为适应于云环境，此外，HEFT是适应于工作流调度的算法类型。

1.2 元启发式及混合式任务调度

云环境中存在着各式各样的元启发式算法，如粒子群优化（PSO）[12-13]、蚁群优化（ACO）[14]、差分进化算法（DE）[15]、遗传算法（GA）[16]、模拟退火（SA）、禁忌搜索（TSA）、人工蜂群（ABC）[17]、细菌觅食优化（BFO）[18]、联赛冠军算法（LCA）[19]、蝙蝠优化（BAT）[20]、猫群优化（CSO）[21-22]、共生生物搜索（SOS）[23]、萤火虫优化算法（FAO）[24]、布谷鸟搜索（CS）[25]、和声搜索（HS）、狮子优化（LOA）[26]、蛾类搜索（MSA）[27]、灰狼优化算法（GWO）[28]、引力搜索算法（GSA）[29]、智能水滴算法（IWD）[30]等。

目前元启发式算法研究的重点是如何平衡局部搜索与全局搜索，有效避免局部最优解，这些算法一般分为两大类：群体智能优化与随机搜索优化。群体智能优化算法主要模拟了昆虫、兽群、鸟群和鱼群等群体的行为，这些群体按照一种合作方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索方向，是一类很常用的分布式问题解决策略，在云环境中任务调度研究的有PSO、ACO、ABC、BFO、SOS、CSO、FAO、CS、LOA、MSA、GWO、GSA、BAT、IWD 等的各类优化。而随机搜索优化方向上，在传统的局部搜索与全局搜索的基础上，修改搜索方式的同时添加了随机算法，试图避免局部最优，在云环境中任务调度研究的有GA、SA、TSA、DE、LCA、HS 等算法的优化。元启发式算法针对独立任务和工作流任务都提出了性能较优的任务调度解决方案。

由于单独的调度算法通常无法很好地满足实际任务调度需求，因此目前混合了多种算法的任务调度已成为重要的研究方法。最新提出的混合任务调度算法有文献[31-34]。这些优化算法中有启发式算法与元启发式算法的混合，也有两种或两种以上元启发式算法的结合，经过实验验证，这些算法在不同程度上获得了较好的性能结果。

1.3 单云环境任务调度总结分析

表1对现有任务调度算法类型进行了梳理总结，分析了其优点和不足。由于任务调度是在网格计算、分布式计算任务调度基础上发展起来的，因此存在大量各式各样的算法类型优化方法，PSO是较为热门的一个算法类型，其又细分为标准PSO、多目标PSO、离散PSO、二进制PSO、混合PSO，而BAT、CSO是最近比较热门的研究方向，LOA、GWO 提出时间不久，具有较大的发展空间。通过列表可以看出，CS、LOA、IWD 目前没有针对云环境任务调度的具体性能评估，有待进一步验证，此外由于性能问题，SA、TSA、HS多用于混合算法。

表2 对上述所列云内任务调度算法部分典型研究文献进行分析总结。云内任务调度算法研究比较广泛，存在许多针对独立任务和工作流使用不同算法类型对QoS进行优化的方法，核心优化目标为最大完工时间和货币成本，此外，资源利用率、负载均衡、安全性、截止日期、能耗等指标也成为了重点优化目标。通过列表可以看出，文献[33]在减少最大完工时间和成本的同时实现了较好的负载均衡，文献[7-8，12，33]实现了资源利用率的提升，文献[15，33]考虑了能耗问题，文献[9]考虑了安全性问题和任务的截止日期；由于任务调度需要同时优化多个指标，因此多目标任务调度算法的研究目前已比较普遍，例如文献[7-9，12，31]均采用多目标函数进行优化；此外，对部分目标建立约束也是一种优化方法，例如文献[9，16]；绝大部分研究都是在仿真环境中进行测试的，但也有在真实环境中进行测试的研究，如文献[9，33]；同时，神经网络、强化学习等人工智能算法也开始应用于任务调度的研究，如文献[10，33]。自适应优化也被应用于任务调度优化，如文献[15]。目前云内任务调度的研究在继续关注基本QoS指标的情况下，重点关注优化负载均衡、能耗等性能指标，并且人工智能方法已逐步应用到任务调度排序、节点预测过程中，但在性能提高的同时，也提升了复杂性。

表1 云内任务调度算法类型总结

表2 云内任务调度算法研究文献总结

2 跨云任务调度

随着用户计算需求的逐渐增加，单一的云环境无法满足计算需求，因此出现了跨云计算环境。这类环境被定义为为了保证服务质量，例如服务的性能和可用性，通过不同云供应商的云系统之间的互操作，按需重新分配资源和转移负载，这种互操作基于用户对服务质量的需求和云供应商对SLA的协调，并且使用能够互相通信的标准接口[35]。跨云环境主要分为两大类，联盟云环境和多云环境。当一组云供应商彼此愿意互连它们的基础设施以实现共享资源时，就构成了联盟云环境，当用户可以使用多个独立的云，但这些云服务云供应商彼此之间并不互连和共享它们的基础设施，称为多云环境[36]。此外，混合云被定义为两个或多个私有云或公有云的组合，根据部署模型连接各类云，一般用于当本地资源不足时使用外部资源的云爆发情况，因此也属于多云类型。在跨云环境中，代理（broker）是安装在用户端专门进行资源分配管理和任务调度及部署的组件，由于跨云环境中每个云数据中心都有大量的物理资源，它们被虚拟化形成了一个虚拟资源池，为了实现跨云调度，使用代理与每个云供应商进行通信，屏蔽通信的异构性，生成统一的资源描述目录和通信接口提供给用户，当用户向代理发送请求执行任务时，代理首先查看资源目录，然后根据调度算法将任务分配给不同的虚拟机，接下来，根据用户的服务质量要求将虚拟机分配到合适的数据中心，这里的调度分为全局调度和局部调度，全局调度由代理进行，主要处理数据迁移，局部调度由云数据中心进行，主要处理具体的任务分配。

2.1 混合云环境任务调度

在混合云环境中，公有云提供了一个公共接口，用于在其专用基础设施中创建和管理虚拟机实例，在私有云内部，用户接口组件用来接收用户应用程序任务请求，任务被发送给请求管理器进行管理，资源监控组件监视云资源池信息。任务调度算法分配任务给私有云或公有云，旨在实现利润最大化，在这个过程中，任务调度器从请求管理器、资源监视器和用户接口收集调度数据，然后决定每个任务分配给私有云还是公有云，如果任务需要分配给公有云，公有云的定价模型信息通过公共接口发送给任务调度器，以便决策选取具体的公有云[35]。由于该云环境不需要正式的跨云协议，实现难度较小，发展较为成熟，目前已成为企业用云的主要形式。

混合云任务调度研究虽不及传统单云环境任务调度研究广泛，但也有较多研究，如文献[37-41]。文献[37]针对混合云，提出了采用整数规划模型的自适应学习PSO 的任务调度算法，在该算法中，在速度更新阶段采用四种更新策略自适应地更新每个粒子的速度，以保证其多样性和鲁棒性，仿真实验表明，该算法与标准PSO相比，结果证明该算法可以提高云供应商的利润。

文献[38]针对混合云中时延约束的任务，在考虑私有云和公有云成本最小化的情况下，提出了一种时分任务调度算法TTSA，将任务有效地分配给公有云和私有云，在TTSA 的每次迭代中，将成本最小化问题建模为混合整数线性规划，并采用混合SA 和PSO 的调度算法进行求解，仿真实验结果表明，与现有的调度策略相比，TTSA产生的最优或近似最优调度策略可以在满足任务时延约束的同时，提高吞吐量，降低私有云成本。

文献[39]针对混合云中的科学工作流多目标调度问题，提出了一种基于NSGAII的非支配排序遗传算法，提出了两种执行模式：（1）在最大完工时间和成本之间做权衡，以提高帕累托前沿（pareto front）质量的累加法；（2）增量式执行，以成本为驱动在目标空间得到帕累托前沿解的多样性。此外设计了一种编码结构，对调度解决方案进行建模，并对其应用的遗传算子进行开发。在多个常见科学工作流中进行仿真实验表明，与经典的NSGAII 算法相比，该算法在成本和最大完工时间方面有显著改进。

文献[40]针对混合云提出了两种兼顾完工时间和货币成本的工作流调度算法，第一种是基于截止时间约束的成本优化的单目标混合云中工作流调度算法DCOH，在DCOH 的基础上，提出了一种以最大完工时间和货币成本为目标的混合云多目标工作流调度优化算法MOH，仿真结果表明，与现有算法相比，DCOH 可以很好地为用户减少货币成本，MOH 可以提供很好的成本与完工时间协调方案。

表3 对上述所列文献中研究的混合云任务调度算法进行了总结。混合云环境中的任务调度算法研究往往是结合混合云特征对云内经典算法进行修改优化，而其优化的QoS指标往往集中在最大完工时间和成本，但部分文献如文献[38]也考虑了任务延迟约束，文献[37]考虑了资源利用率，文献[40]考虑了截止日期约束，此外也出现了基于混合云的多目标任务调度算法研究，如文献[39]，以及结合混合云特点对吞吐量进行优化，以减少最大完工时间，如文献[38]。特别的，文献[40]将其算法在真实云环境中进行了测试。但也正如这些文献提到的那样，由于执行时间变化，执行延迟这些会影响最大完工时间的指标尚未得到很好的解决，目前负载均衡、能耗、安全性这些指标的优化在混合云中研究很不充分。

表3 混合云任务调度算法研究文献总结

2.2 多云环境任务调度

多云环境由多个不同的IaaS云服务供应商组成，这些供应商提供不同价格和性能的虚拟机，但彼此之间相互独立互不通信，为了将其整合以利用资源，需要针对每一个云供应商设计相应的API接口以实现通信，或者用户自行搭建工作负载管理程序以满足任务调度需求。虽然这种云环境导致了额外的开发成本，但可以防止数据丢失和减少局部组件故障而停机的风险，避免云供应商锁定，具有高可伸缩性，此外由于选择性的增加，任务执行成本减少了[42]。在多云环境中，每个云平台上都有一个资源管理器实时向用户发送当前的虚拟机资源情况，用户通过统一的API接口或外部代理获得不同云平台发送过来的资源信息，根据自身任务情况，将任务分段传输给不同的云进行处理计算。多云环境下任务调度研究不及混合云环境广泛，国际上存在部分质量较高的文献如文献[42-45]，国内研究的有文献[46]，它们从不同的角度进行了优化。

文献[42]针对多云环境，提出了三种调度算法，分别是最小完成云（MCC）、中位数最大（MEMAX）和云min-max 归一化（CMMN），MCC 是单阶段调度算法，MEMAX和CMMN是两阶段调度算法，实验结果表明，MCC 适用于在线调度，CMMN 的最大完工时间较短，MEMAX的平均资源利用率较高，这些算法在最大完工时间和资源利用率方面整体优于已有的多云环境任务调度算法RR、CMMS。

文献[43]提出了一种新的多云系统架构，并设计了一种动态调度策略，该策略结合了可分负载理论和节点可用性预测技术，包括使用预测方法来估计虚拟机的准备时间，以及使用以前关于处理时间的数据来估计工作负载的处理时间，并允许计算节点估计它们接受和处理负载的准备时间，将这些时间应用于策略，以保证负载平衡和系统的高性能，仿真实验结果表明，该调度策略优于基准策略，有效地减少了任务执行最大完工时间。

文献[44]针对多云环境提出了一种多目标科学工作流调度算法，该算法在满足可靠性约束的情况下，使工作流最大完工时间和成本同时最小化，该算法基于PSO，求解帕累托前沿，同时考虑了任务的执行位置和传输顺序，仿真结果表明，该算法与CMOHEFT 和随机算法相比，性能得到明显改进。

文献[45]针对多云环境中的多目标科学工作流调度问题，提出了同时减少最大完工时间和成本的调度算法，该方法在不同场景中采用了不同的数值方法，例如加权和法、本森数值法和加权min-max，此外，研究了所得解的稳定性，提出了一种方法来分析加权和法及加权min-max 的最优稳定解，实验结果表明，本文提出的加权和法在超体积（hypervolume）方面优于已有的算法。

表4 对上述所列多云环境中的任务调度算法进行了总结。由于多云环境整体的结构发生了很大的改变，基于多云环境的任务调度算法结合了该环境任务特点进行优化，如文献[42]考虑了任务的执行位置和传输顺序，文献[43]采用可用性预测技术和自适应方法提高多云环境的负载均衡，文献[45]采用整数规划来进行计算。此外，由于多云环境中信息发送比较频繁，耗时较长，因此任务调度算法大多数选择时间复杂度较低的算法类型，如文献[42-43，45]皆为启发式调度，多云环境下也存在多目标任务调度研究，如文献[44-45]，而该环境下主要优化目标依然是最大完工时间和成本，部分文献如文献[49]考虑了可靠性约束，文献[47]考虑了资源利用率。目前在多云环境任务调度的研究中，主要集中在使用不同的方法降低算法时间复杂度，增加求解多样性和精度，而不是增加优化目标。

2.3 联盟云环境任务调度

当一组云供应商彼此合作交换资源时，就构成了联盟云。这类云环境往往由政府或学术组织发起，是政府云或私有云之间的合作。这种云环境可以使用分布式实体进行代理，或者集中使用一个中心实体进行资源注册、共享和代理[2]。联盟云的代理收集各个云服务供应商发来的资源状态，同时根据用户指定的SLA将用户应用程序任务分配到可用资源的不同虚拟机上，以实现完工时间，成本，资源利用率等性能的最大化。

文献[47]提出了一种使用统计多路复用技术在联盟云中进行请求分配的方法，该方法结合统计多路复用和服务器整合，检查使用的变异系数和其他相关统计指标作为目标函数，用于决定请求分配，并比较了使用随机算法、爬山算法、最大提升爬山算法、模拟退火算法、后期验收爬山算法等启发式算法应用该目标函数的结果，实验结果表示后期验收爬山算法具有更好的性能。

表4 多云任务调度算法研究文献总结

文献[48]基于欧洲学术组织建立的Contrail[49]联盟云环境建立了基于遗传算法的代理组件，该遗传算法根据多个QoS建立了本地适应度函数和全局适应度函数，将任务与虚拟机一一对应，将虚拟机分配到相应的不同的云服务供应商中。实验结果表明，此方法充分利用了本地资源和全局资源，资源利用率较高，但处理大量数据，最大完工时间并没有降低。

文献[50]为了在云环境中执行霜冻预测应用程序，使最大完工时间和成本最小化，在联盟云中两个级别设计了调度策略。在代理级别，实现了基于ACO 的调度和基于PSO 的调度，其目标是在考虑网络延迟、货币成本和数据中心计算资源可用性的前提下选择数据中心，在基础设施级别，虚拟机通过基于ACO 和PSO 的调度分配给数据中心的物理主机。实验结果表明，与GA相比，这两种调度可以极大降低最大完工时间和货币成本。

文献[51]针对联盟云提出了一种基于多目标列表的工作流调度算法MOHEFT，该算法扩展了HEFT工作流调度算法，通过拥挤距离实现了近似最优帕累托前沿，降低了成本和最大完工时间，并使用实际工作流和合成工作流评估了MOHEFT，与HEFT 和SPEA2 相比，该算法能获得较好的完工时间和成本，此外，还用GoGrid和Amazon EC2进行实际测试，结果表明当数据传输支配时间的情况下，工作流不会从联盟云中获益，反而在单个供应商的配置中表现更好。

表5 对上述所列联盟云环境中的任务调度算法进行了总结。联盟云作为学术云的常见形式，存在许多结合不同科学应用程序进行优化的调度研究，如文献[50]；针对任务分配的优化问题，也出现了许多适应联盟云的新方法，如文献[47]使用的统计多路复用技术；此外，结合实际的联盟云环境，设计符合要求的仿真环境和相匹配的任务调度算法也是联盟云任务调度研究的一大类型，如文献[48]，多目标优化也是联盟云任务调度建立目标函数常用的方法，如文献[51]。目前，联盟云任务调度研究是以优化最大完工时间和成本为目标，充分考虑联盟云特征，尽可能多地考虑影响指标，如跨云带宽、网络延迟、成本等来达到优化的目的。用户对联盟云拥有海量的计算需求，但目前联盟云任务调度研究尚不充分，对数据密集且计算密集型的应用程序并没有充分研究。

3 任务调度优化方法分析

通过对云计算各类环境下任务调度算法研究文献进行总结分析可以看出，目前任务调度算法的优化方法是在已有的启发式、元启发式以及混合式算法类型的基础上结合单/多目标函数及QoS 约束，进行诸如任务排序、解集筛选、节点预测策略，对已有的各类标准调度算法进行改进，如模糊排序方法[7，33]、整数规划[37-38，45]、帕累托权衡[39，45，51]、节点预测技术[11，33，43]、统计多路复用[47]、人工智能[10，33]、多目标优化[39，44，51]、自适应优化[37，43]。表6对文献中使用的优化策略进行分析，并给出了相应的部分文献研究类型。可以看到这些方法使用建模、任务排序、节点预测、请求合并、方案排序等对任务调度算法进行优化，从而简化模型，方便分配，整理需求，减少可分配计算节点，寻找可行解，从各个角度实现提高分配效率与精度的目标。未来可以在不同云环境任务调度的研究中充分应用这些方法来达到性能优化目的。

4 总结与展望

本文根据环境类型对云计算任务调度算法进行了总结分析，讨论了云内、混合云、多云、联盟云的环境特点和任务调度特征，归纳出27 种不同算法类型的任务调度方法、结合启发式、元启发式及混合式调度类型对独立任务和工作流最新及代表性研究文献的具体实现过程、优化指标、仿真环境及优缺点进行分析探讨，并对相关优化方法进行描述分析，呈现了云任务调度领域的最新重要研究进展。

云内任务调度研究充分，存在大量优化性能较好的调度算法，为了应对逐渐增加的用户计算任务，提供安全稳定的计算环境，跨云环境任务调度研究逐步发展，由于跨云环境具有一些独特且复杂的特征，使得任务调度研究在传统任务调度算法类型的基础上进行了许多环境针对性优化，出现了使得独立任务和科学工作流在各类环境下能够有效调度的算法和框架。