跨云环境下任务调度综述

唐续豪 刘发贵, 王 彬 李 超 蒋 俊 唐 泉 陈维明 何凤文

1 （华南理工大学计算机科学与工程学院 广州 510006）

2 （鹏城实验室 广东 深圳 518000）

3 （国家税务总局广东省税务局 广州 510627）

云计算作为国家“新基建”中重要的新技术基础设施，为5G、物联网、工业互联网等领域的发展提供了重要的支持.目前，云计算已经广泛应用于不同领域，为云服务使用者提供数据处理、大规模数据存储相关服务.云服务使用者可以根据自身需求选择不同的部署模式，如有可用资源多、按计算使用量付费的需求则可选择公有云作为部署模式；如有安全性高的需求则可选择私有云作为部署模式，这些彼此没有关联的单一公有云或私有云构成了单云环境.近年来由于云计算技术的快速发展，政府机关、企业、机构、个人用户等不同类别的云服务使用者在应用过程中形成了不同的技术路线，累积了大量不同架构、不同品牌的网络、计算、存储设备及多种应用和虚拟化环境[1]，这些不同种类的硬件资源、异构的虚拟化系统使得云环境日趋复杂，而单云环境已无法满足云服务使用者日益增长的计算需求和服务需求.同时，数据量的不断增加和云服务应用场景的多元化让单云环境还面临着3 个方面的挑战：

1）单云环境资源利用率有限，应对突发业务成本较高.云服务使用者在业务高峰时往往需要比平时高几倍甚至数十倍的资源，在单云环境中如按照峰值需求配置云资源，则会导致资源利用率低，为了保证服务质量，云服务提供者的成本会增加，而这部分成本最终将转嫁给云服务使用者，使得业务成本增加.同时，单云环境无法拥有云服务供应商的议价权，无法结合多个云服务供应商提供的资源价格来制定更加合理的经济策略，优化使用成本.

2）单云环境无法解决供应商锁定问题，阻碍业务发展.单一云服务供应商可能会因监管、法律、政治等因素中断服务，导致供应商锁定，这会使云服务使用者在业务发展中面临极大风险.

3）单云环境中云服务的可靠性无法得到保证.如果将所有数据都放在同一云平台上，出现宕机或数据丢失事故将对云服务，使用者的业务造成巨大损失，云服务的可靠性无法得到保证.

这些问题的存在都会导致云服务使用者无法统一管理云资源，制约了云服务使用者对于云资源的有效利用.为了集成云服务，统一管理云资源，有效地解决单云环境所面临的各种问题，跨云环境应运而生，跨云环境包括混合云（hybrid cloud）[2-3]、联盟云（federated cloud）[4]和多云（multi-cloud）[5].据全球著名市场研究公司IDC（international data corporation）预测，到2024 年，90%的全球1 000 强企业将建立跨云管理的战略，云计算环境正在经历从单云到跨云的转变[6].

云计算中的关键研究问题之一是任务调度，它根据任务的各种需求及资源的实际情况采用适当的策略将不同的任务分配到云内最佳的资源上执行[7].其中需要综合考虑任务的执行时间、完成时间、资源利用率、可靠性、成本、网络吞吐量、可伸缩性能、能耗等优化参数及相关评价指标[8].由于跨云环境中资源呈现复杂性、异构性，这使得统一管理并有效利用跨云资源的难度大大增加[9-10].因此，为了实现跨云资源的高效利用，如何合理调度用户任务并将其分配到最佳的跨云资源上执行，成为了跨云环境中需要解决的重要问题.同时，如何提高任务调度的效率，使其更好地适应跨云环境，满足日益增长的云计算能力与对各类云服务的需求，也成为目前云计算平台研究领域急需解决的瓶颈问题.

近年来，跨云环境的不断推广应用使得国内外出现了研究跨云环境下任务调度算法的高质量论文.由于跨云环境的分类界定较为模糊，相关研究的侧重不一，导致此类研究的综述性论文较为缺乏、研究较为滞后.目前，已有的综述论文大多只对单云环境下任务调度算法进行了总结分析，尚未针对跨云环境下任务调度算法研究展开综述.因此，本文根据国内外研究现状，结合跨云环境的相关资料和特点对其进行梳理，同时选取代表性论文对跨云环境下任务调度算法进行总结、分析，最后探讨了跨云环境下任务调度算法研究中的不足和未来的研究趋势，为跨云环境的分类、跨云环境下任务调度的进一步研究提供了参考.

1 跨云环境下任务调度概述

本节主要介绍跨云环境及任务调度算法的分类.由于跨云环境中部分概念及其场景无精确定义，本节重点梳理其中的关系，力求全面，以供读者理解.

1.1 跨云环境分类

跨云环境一般分为2 类：一类是联盟云环境，另一类是多云环境[11].如图1（a）所示，联盟云环境是指一组云服务供应商彼此愿意互连其基础设施以实现资源共享；多云环境是指云服务使用者可以使用多个独立的云，如图1（b）所示，其中云服务供应商彼此之间并不互连且不共享其基础设施[12].近年来，混合云作为新的云架构体系已成为云计算领域研究的热点，根据美国国家标准与技术（national institute of standards and technology，NIST）研究院的定义，混合云是由2 个或2 个以上的云（公有云、私有云或社区云）组成的，它们各自独立但通过标准化技术或专有技术绑定在一起，实现了跨云之间数据和应用程序的可移植性[13].因此，作为独立的云架构体系，混合云也属于多云环境.

Fig.1 Inter-cloud environment comparison diagram图1 跨云环境对比图

在跨云环境中，通常使用代理（broker）来实现任务的调度及部署.如图2 所示，代理作为独立的第三方，将跨云环境中所有的云资源虚拟化形成一个统一的虚拟资源池，在该资源池中代理分别与各个独立的云进行通信，但对于云服务使用者来说代理屏蔽了资源、通信等方面的异构性，只向云服务使用者提供统一资源池的资源目录及通信接口，并将任务分配给统一资源池中合适的资源执行，实现跨云资源的有效利用.

Fig.2 Schematic diagram of task scheduling in inter-cloud environment图2 跨云环境下任务调度示意图

联盟云环境大都以政府或学术组织为主发起，是政府内部用云或学术组织拥有的私有云之间的合作[14].联盟云环境更多地强调合作、共享的重要性，通常是通过部署和管理多个云计算服务来匹配云服务使用者的业务需求，通过聚合多个云平台来合作完成同一个目标任务[15].联盟云环境中代理会收集并不断更新环境中各个云的资源状态信息，之后根据云服务使用者的服务级别协议（service level agreement,SLA）将任务分配到联盟云环境中可用资源的虚拟机上，来实现资源利用率、可靠性、成本等相关性能的最优化.联盟云环境的提出，实现了多个云计算节点的互联，提出了互操作协议标准、共享资源、相关数据管理等一些基于联盟云环境下的云服务管理方法，解决了部分单云环境下所遇到的问题.但由于联盟云需要共享资源的特殊性，导致其应用范围较小，难以推广使用，其资源的异构性也会引起整个联盟云环境的不稳定.综合来看，联盟云为解决单云环境下所面临的部分问题提出了有参考价值的方案，但其中还存在一些尚待研究和解决的问题，同时联盟云需要共享资源的特殊性使其无法避免法律合规等相关问题，这也大大制约了联盟云的推广.

多云环境目前并无精确的定义，在学术界和工业界一般意义上的多云环境是指由多个不同的（infrastructure as a service, IaaS）基础设施即服务提供商组成的新环境，这些云服务供应商相互独立，同时向云服务使用者提供不同价格、不同性能的虚拟机以满足其需求[5].而混合云一般认为是公有云和私有云的混合，但云混合的形态有多种，根据NIST 的定义，混合云的形态应该包括公有云之间的混合、私有云之间的混合、公有云和私有云的混合.Gartner 公司曾经将混合云定义为混合的IT 架构，在现实应用中也存在大量传统IT 设施和公有云混合的情况，所以混合云的形态也应该包括传统IT 与公有云的混合.因此，如图3 所示混合云的形态可以总结为4 种：

Fig.3 The whole classification of inter-cloud environment图3 跨云环境整体分类

1）公有云之间的混合

公有云之间的混合还存在同构公有云混合和异构公有云混合的情况，同构公有云的混合一般是指相同云服务提供商的云平台在不同地域之间的混合；异构公有云的混合是指不同云服务提供商的混合，也就是目前学术界和工业界一般意义上的多云，而在应用中则是将多个异构公有云统一纳管，实现云资源的统一管理，但此处的多云是为了区别混合云中公有云和私有云的混合类型.目前，异构公有云的混合是研究的热点，市场上也有很多工具来帮助云服务使用者同时部署管理多个异构公有云，如HashiCorp提供的Terraform 就是较为流行的一种部署工具，它通过抽象化基础架构模型来屏蔽各个云之间IaaS 的具体差别[16].

2）私有云之间的混合

私有云之间的混合一般是企业或组织内部的IT架构，为了降低运营成本通常都是采用同一种私有云进行连接，当然也会存在异构的私有云的混合，但这种混合并不是研究和应用的主流，如OpenStack 和VMware 可以进行混合，但并无太大意义甚至有可能增加运营成本.

3）公有云和私有云之间的混合

公有云与私有云的混合是一般意义上的混合云，它是目前工业界市场的主流选择，同时学术界对于跨云环境的研究也大多集中于此.这种形态的混合云能够同时兼顾公有云和私有云的优点，给云服务使用者带来更好的体验.公有云与私有云的混合依然存在同构和异构之分，同构是指2 个或多个云采用同一个技术架构（开源架构或同一厂家的平台）；异构是指公、私有云混合的技术架构不同.目前，研究和应用以同构混合云为主.

4）公有云和传统IT 的混合

这种混合一般需要尽可能地屏蔽公有云和传统IT 之间的差异，以公有云为主适配传统IT，进而达到对资源的有效利用.

综合来看，跨云环境的主体是多云环境，而多云环境又重点关注异构公有云的混合和公有云、私有云的混合.因此，多云环境可以理解为一种融合的IT架构，区别于单云环境，在这种环境下云服务使用者可以将独立的云资源尽可能地连接起来，实现应用的编排、管理，最终达到资源高效利用的目的，其中混合云的各种形态都属于多云环境.

学术界从很早之前就对多云环境展开相关研究，2014 年国际上出现了以研究多云环境下任务调度、资源管理等问题的研讨会，命名为Cross Cloud[17].2017 年国内的国防科技大学王怀民院士[18]首次提出云际计算概念，它以云服务提供者之间开放协作为基础，通过融合多方云资源，实现“服务无边界、云间有协作、资源易共享、价值可转换”的新一代云计算模式，其参考架构国家标准也已经进入批准阶段[19]，同时云际计算连续多年依托国内外知名会议在线下展开研讨，在2020 年由国防科技大学主导，正式成为IEEE 云际计算国际会议.

随着数据量的不断增大，对算力的需求会越来越高，对计算性能的要求会逐渐提升，计算成本会随之增加，云环境也会日趋复杂.这种趋势下跨云环境会成为越来越多云服务使用者的必然选择，而更加复杂的跨云环境将会不可避免地遇到新的问题.

1.2 主要任务调度算法

跨云环境下的任务调度算法是指根据当前任务具体情况并结合环境中的所有资源，将任务分配到跨云环境中最优资源上执行的过程，任务调度算法本质上是一个NP 难题[20].

跨云环境中的任务调度算法通常可以根据任务的类型将任务调度算法分为2 类：

1）独立任务调度.独立任务彼此之间没有关联关系，调度优化的目标通常是为了达到整个系统性能的最佳状态或根据用户的需求完成特定的调度优化，最终将任务分配到跨云环境中的指定虚拟机即可[21].

2）工作流任务调度.工作流任务存在执行顺序，通常是所有前驱节点任务执行完毕后，当前任务才可以开始执行，常用有向无环图（directed acyclic graph,DAG）表示工作流任务，其中“节点”表示任务需要的计算过程，“边”表示任务间的数据通信[22-23].在跨云环境中，如何调度和分配多个具有依赖关系的任务，为每个具有依赖关系的任务在跨云环境中找到合适的云平台资源、降低资源使用成本、减少任务执行时间是工作流任务调度优化的重点目标.

对于跨云环境中的任务调度算法，目前已有的研究多数是以单云环境下任务调度算法为参考，根据特定目标对其进行改进和优化[24-25]，以满足跨云环境的需求.表1 总结了单云环境下常见的任务调度算法，传统调度算法包括先来先服务（first come first served, FCFS）、Min-Min[26]、Max-Min[27]、最小完成时间（minimum completion time, MCT）、最小执行时间（minimum execution time, MET）、循环调度（round robin, RR）等，这类算法的思想较为简单，通常是为了直接实现某种目标而制定，算法整体易于实现，复杂度较低同时具有较强的实用性，现在多为云仿真平台的默认任务调度算法.但这些算法大都存在较大的局限性，并且性能不高，往往在实际的云环境中无法直接运用.蚁群优化（ant colony optimization, ACO）[28-29]算法、粒子群优化（particle swarm optimization, PSO）算法[30-32]、遗传（genetic algorithm, GA）算法[33-35]、模拟退火（simulated annealing, SA）算法[36-37]、禁忌搜索（tabu search,TS）算法[38]等一般是模拟生物觅食方式或自然界中的物理现象，通过不断地迭代优化最终获得较好的调度结果，同时这类算法也已经在单云环境中获得了符合调度目标的较好的调度方案.但这类算法的参数及相关阈值的设定较为复杂，存在求解时间过长、算法复杂度较高等问题.

Table 1 Common Task Scheduling Algorithms in Single Cloud Environment表1 单云环境下常见的任务调度算法

在跨云环境中，由于资源具有异构性且资源池中其他用户的行为未知，任务会呈现较大的随机性，同时任务的类型、数量等方面也会不断地变化，更加复杂的环境下，任务调度会遇到新的问题和挑战.

2 联盟云环境下的任务调度算法

联盟云环境通常是指云服务供应商彼此愿意互连其基础设施以实现资源共享，通过管理多个云计算服务来满足云服务使用者的需求.联盟云支持若干个独立云平台合作完成同一个目标任务[39].

文献[40]设计了CometCloud 联盟云架构，该联盟云架构部署在3 所不同地域高校的服务器上，以成本最小化设计了调度策略并用2 个实际应用任务进行测试.同时，利用实验评估了处理相同任务量情况下单云环境及联盟云环境的性能，实验结果表明，在任务完成时间和成本优化方面，联盟云优势会更为明显.文献[41]针对联盟云环境构建了一种基于博弈论的调度方案，该方案以成本为导向，向纳什均衡[42]解靠拢，给代理赋予了系统组件所需的自治程度，并加入了自组织、弹性等全局属性.实验结果表明，这种调度方案在面对大量任务的情况下可提供更好的伸缩性.文献[43]提出了一种基于负载均衡的蚁群优化（load balancing ant colony optimization, LBACO）算法，也被称为ACOsched 算法，通过在联盟中寻找最优的云资源来执行任务，从而实现任务的高效分配.实验结果表明，ACOsched 算法在联盟云中的任务完成时间有了较为明显的缩减.由于联盟云需要共享资源的特殊性使其无法避免法律合规等相关问题，同时较为复杂的环境也制约了联盟云的推广，因此除了政府及学术组织外少有用户去使用联盟云，这也导致了相关研究论文较少.

表2 总结对比了联盟云环境下的任务调度算法.现有的联盟云环境下任务调度算法，大部分会优先根据实际应用场景自定义联盟云架构，如文献[40]中针对不同地域的服务器设计了联盟云架构，将该场景下的任务调度形式化为成本和最大完成时间的多目标优化问题，同时将多个云计算节点互联，并通过成本决策函数的计算结果，确定何时将任务分配至联盟云中不同的节点，优化了任务调度的求解过程.文献[40-43]等大都以成本、最大完成时间为首要优化目标，将不同场景中的调度形式化为单目标或多目标优化问题，以单云环境下任务调度算法为参考，根据特定目标需求对算法进行改进和优化[43]，实现在联盟云环境下任务的高效分配.但这些研究并不会只考虑单一的任务调度问题，同时会提出联盟云环境下相关资源管理、数据安全、隐私保护、互操作协议标准等服务管理方法，最终实现跨云资源的高效利用[44-45].综合来看，目前联盟云环境下的任务调度研究还不充分，对于共享资源的接口标准、异构资源的统一管理等问题还需要深入探讨和解决.

Table 2 Comparison of Task Scheduling Algorithms in Federated Cloud Environment表2 联盟云环境下任务调度算法对比

3 多云环境下的任务调度算法

3.1 异构公有云环境下的任务调度算法

异构公有云环境是由多个不同的IaaS 云服务供应商组成，该环境下各个云服务供应商相互独立且互不通信，云服务使用者需要通过不同的API 将云资源整合或者根据需求构建新的架构统一管理云资源.异构公有云环境主要有4 个方面的优势：

1）避免供应商锁定.统一管理多个不同的IaaS云服务供应商使得云服务使用者拥有多个选择，避免因某一个供应商锁定而中断服务.

2）多元化的地理位置.目前，业界较为领先的云服务供应商已在全球不同，范围内部署建立了数据中心.但由于不同国家、地域的法律规定要求不同，使得云服务供应商无法在所有区域建立相同的数据中心，因此异构公有云环境可以融合多个地域的云服务提供商，为云服务使用者提供性能良好且合规的服务.

3）受外界影响因素较小.近年来，云服务中断事件频发，单云环境易受到此类影响，而使用不同云服务提供商的资源能够很好地规避此类情况，同时可以防止因监管或法律因素引起的服务停止，也能在不同地域备份数据保证数据的完整性和安全性.

4）成本降低.云服务使用者可以根据自身需求，结合各个云服务供应商提供的资源价格来制定更加灵活的经济策略，在满足自身需求的同时降低使用成本.

文献[46]提出了一种基于成本最优的二进制整数规划算法（binary integer program, BIP），该算法以最小化公有云的成本为基础，通过二进制整数规划选取成本最优的资源进行分配，为异构公有云环境中的任务调度提供了易于实现的方案.实验结果表明，该算法在成本最小化、可行性和可伸缩性方面都表现得非常好.文献[47]针对异构公有云环境下的任务调度问题，提出了一种基于遗传算法的任务调度算法，该算法采用适应度函数求导和变异的思想，最终以任务完成时间来评估算法的整体性能.文献[48]提出了一种基于异构公有云环境的局部关键路径算法，该算法在异构公有云环境下为任务调度过程中部分关键路径分配子截止时间，从而最大限度地降低工作流任务的总执行成本.文献[49]提出了一种改进的遗传算法，其目的是为当前任务在异构公有云环境下找到合适的云资源配置.通过考虑各个云服务提供商在价格和功能上的不同，以满足云服务使用者和应用程序的需求.文献[50]构建了一种基于地理位置分布的异构公有云环境服务组合模型，同时提出了一种具有改进交叉和变异算子的遗传算法，用于QoS 服务组合（响应时间、成本、可靠性），允许用户根据自己的偏好选择最优组合方案.文献[51]提出了一种新的云代理方法，该方法基于调度预测模型，该模型能预测异构公有云环境中的最低价格，最终为云服务使用者提供资源的最佳部署建议.文献[52]提出了一种基于异构云环境下的资源优化机制，在此机制上又提出了2 种在线动态资源分配算法，算法根据实际任务执行的更新信息来动态调整资源分配.实验结果表明，所提算法的任务完成时间和能耗都有了明显的减少.文献[53]提出了一种异构公有云环境下的多目标任务调度算法.实验结果表明，该算法在最大完成时间、总成本和云资源平均利用率等性能指标上表现较好，同时也实现了最大完成时间和成本之间的平衡.文献[54]提出了一种基于异构公有云环境下多目标科学工作流调度算法，该算法在满足可靠性约束的前提下，使工作流的最大完成时间和成本最小化.该算法基于粒子群优化算法（PSO），考虑了任务执行位置和数据传输顺序.文献[55]设计了一种基于异构公有云环境的工作流调度架构，该架构包括了应用队列、可靠性分析、任务执行成本估算、计划与调度、多云系统互联等模块，并设计了工作流调度算法，目的是为了提高应用程序的执行可靠性并降低其成本.实验表明，在该架构下的工作流调度算法在成本和可靠性方面优于现有算法.文献[56]构建了一个多目标分布式调度模型，该模型包括总时间、成本、云吞吐量、能耗、资源利用率和负载均衡6 个目标.在该模型中又提出了一种基于正弦函数的多目标智能算法来解决任务调度问题，该算法考虑了种群多样性策略在种群中的变化趋势与正弦函数相似.实验结果表明，该算法具有良好的调度效率，提高了系统的安全性，同时该工作为解决物联网中数据处理的难题提供了一种新的思路.文献[57]设计了一种新的基于软件定义的工作流代理，该代理能够用于跨多个软件定义的异构数据中心部署工业工作流任务，同时自动化任务发放、数据发放和资源发放.同时提出了一种基于遗传算法的自适应工业工作流调度算法，该算法能够利用多种软件定义的云数据中心资源.实验结果表明，该算法既提高了绿色能源利用率，又降低了成本.文献[58]提出了一种基于预算约束的异构多云环境动态任务调度算法，该算法分别提出了2 个版本，第2 版在第1 版的基础上对算法进行了优化和改进.实验结果表明，算法的第2 版优于第1 版，同时也从最大完工时间的角度证明了算法的有效性.

表3 对异构公有云环境中的任务调度算法进行了总结，可以看出大部分的算法都是依托代理或自行设计的架构，以最大完成时间和成本为主要优化目标，将不同场景中的调度建模为单目标或多目标优化问题来进行求解.由于异构公有云的特殊性，成本会成为任务调度过程中首要考虑的因素，因此存在部分研究将成本优化作为算法的重点，通过改进单云环境下任务调度算法来适配异构公有云环境，虽然此方法解决了部分特定场景下的任务调度问题，但忽略了任务调度的其他评价指标，未能实现任务的高效分配.近年来的研究如文献[55]为异构公有云环境下的任务调度提供了更有价值的参考，文献[55]中提出的架构已经最大限度地接近了实际的云环境，为解决异构公有云环境下的任务调度问题提供了较为新颖的解决思路；文献[56]中基本囊括了异构公有云环境下任务调度的主要性能评价指标，优化目标全面，整个系统可靠性强，为该问题的研究提供了更加全面的参考；文献[59-62]研究了异构公有云环境下的资源调度等相关问题，通过文献[55-56, 59-62]可以发现资源调度和任务调度密不可分，在新环境下资源调度问题的有效解决也会给任务调度研究提供新的思路.

Table 3 Comparison of Task Scheduling Algorithms in Heterogeneous Public Cloud Environment表3 异构公有云环境下任务调度算法对比

由于异构公有云的表述过于复杂，一般研究中都不会刻意区分，只是将其称作“多云”环境.而“多云”的界定较为模糊，且相关研究的侧重不一导致此类研究与实际环境差距较大.近年来公有云的快速发展使得异构公有云环境正在不断成为云服务使用者的最新选择，但不难发现目前在该环境下的调度问题研究还存在不少困难有待解决.

3.2 公有云、私有云混合环境下的任务调度算法

公有云、私有云混合环境是目前市场的主流选择，学术界的诸多跨云任务调度研究都以此环境为主，该环境能同时兼顾公有云和私有云的优点，实现难度相对较小.公有云、私有云混合环境主要有3 个方面的优势：

1）数据安全.公有云、私有云混合环境可以利用公有云多地域的特点，为数据提供跨多地域的数据备份，同时可以利用私有云独有的数据安全性为数据提供最为可靠的保障.

2）弹性扩展.公有云环境的算力较高，可以有效解决私有云在特殊情况下瞬时算力不足的情况，给云服务使用者提供了更好的服务保障.

3）成本降低.公有云的接入降低了云服务使用者购买IT 的成本，同时云服务使用者可以根据需求和公有云的资源价格将任务选择分配到公有云还是私有云上，实现了成本的有效降低.

文献[63]提出了一种混合云环境下截止时间约束的任务调度算法，该算法将最早截止时间优先算法进行改进优化，算法考虑了计算和数据传输成本，以及网络带宽限制.实验结果表明，该算法能够很好地适合于规模较大的混合云环境.文献[64]提出了一种混合云优化成本调度算法，该算法先将工作流调度到私有云上，估算工作流完成时间，之后从公有云租用合适的资源并将其聚合到私有云，以便在截止时间内提供足够的处理能力来执行工作流.如果超过截止时间，则选择优先级最高的任务调度到能够确保工作流在截止时间之前完成的、且价格最低的公有云上.文献[65]提出了一种基于任务级别的调度算法，该算法能够按级别在公有云上寻找最佳资源以节省成本，并在截止时间内能完成工作流任务的执行.算法中还提出了一种工作流的子截止时间的概念，即工作流中单个任务的截止时间.文献[66]提出了2 种兼顾最大完成时间和成本的混合云工作流调度算法.首先提出了一种单目标工作流调度算法，解决在截止时间约束下最小化执行成本的单目标优化问题.然后又提出了一种多目标工作流调度算法，同时解决最小化执行成本和最大完成时间的多目标优化问题.实验结果表明，该算法可以更好地实现成本和完成时间的权衡.文献[67]提出了一种启发式的任务调度算法，该算法以任务调度的安全性和截止时间作为约束，优化了任务完成数量和成本.该算法一方面优先分配消耗公共云资源最大的任务，将其分配给本地集群中处理能力最强的服务器；另一方面如果在本地资源不足的情况时，租用性价比较高的新虚拟机来解决该问题.实验结果表明，在未到达截止时间前，该算法的性能较好.文献[68]提出了一种时间任务调度算法，该算法基于绿色数据中心和公有云构成的混合云环境，在延迟约束下对任务进行调度.绿色数据中心的电能是由太阳能、风能等绿色能源提供，随着时间的变化，数据中心会产生收益.实验结果表明，对比已有的多种算法，该算法能够获得更大的利润，同时也能很好地适应绿色数据中心和公有云构成的混合云环境.文献[69]提出了一种基于遗传算法的单目标任务调度算法，该算法在交叉、选择和控制调节参数方面进行了改进.文献[69]在单目标任务调度算法的基础上又提出了一种改进的多目标调度算法，该算法结合了NSGA-Ⅱ算法中基于帕累托最优的快速排序的方法.实验结果表明，这2 种算法都能在混合云环境下有效提升任务调度的性能.

表4 对文献[63-69]中公有云、私有云混合环境下的任务调度算法进行了对比总结，可以看出与联盟云环境及异构公有云环境下的任务调度算法相同，公有云、私有云混合环境下大部分的算法都是以单云环境下任务调度算法为参考，根据应用场景中的不同需求将调度问题抽象成为单目标或多目标优化问题并结合实际环境对参考算法进行改进和优化.公有云、私有云混合环境在实际应用中较为广泛，成本是该环境下任务调度需要考虑的首要因素，现有的研究中大部分算法都以成本作为优化目标对任务调度进行求解.但在实际应用中，私有云上的资源大都是安全性需求较高的内部资源，任务调度过程中更应该关注云服务使用者对于安全性的需求，同时环境中的其他影响因素如能耗、资源利用率、可靠性、负载均衡等性能指标也应当考虑在内并进行深入的研究和讨论.

Table 4 Comparison of Task Scheduling Algorithms in Public Cloud and Private Cloud Hybrid Environment表4 公有云、私有云混合环境下任务调度算法对比

4 总结与展望

目前，针对单云环境下的任务调度算法研究较为充分，不少国内外学者已经提出了性能较好的调度算法并在真实的云环境中得到了验证.但由于单云环境存在架构瓶颈、资源上限、易被供应商锁定等问题，现已无法满足庞大的数据量及日益增长的服务需求.跨云环境的提出有效地解决了这些问题，目前国内外学者针对跨云环境从跨云资源管理架构、跨云资源调度、跨云任务调度等方面已经开展了多年的讨论研究并取得了一定的进展，但跨云环境是对云计算资源的重组和聚合，资源在跨云环境中呈现了异构性、分散性、复杂性和多样性的特点，这使得任务调度的难度大大增加，部分特定场景的需求仍然得不到满足，跨云环境下的任务调度算法还需要不断进行深入地研究.

本文以跨云环境为出发点介绍了跨云环境的不同分类，在此分类下对任务调度算法进行了整理分析，通过梳理观察得出3 个方面的建议：

1）现有任务调度算法未能有效考虑跨云架构的特点，普适性不强.跨云环境下的任务调度算法研究目前主要集中于异构公有云环境及公有云、私有云混合的环境，其中公有云、私有云混合的环境是目前市场的主流选择.由于跨云环境较为复杂，现有的研究大部分是根据具体需求将多种云资源合并，在此基础上考虑任务调度，而从构建跨云架构角度出发考虑任务调度问题的研究很少，这导致任务调度算法仅能在特定的环境中运行，虽有一定的参考价值但普适性不强.

未来研究中，可以从构建普适性较强的跨云架构角度出发，以更好的扩展性将更多的云资源甚至边缘资源整合[70-71]，以统一的API 屏蔽底层基础设施的差异，并在此基础上提出更为有效的任务调度算法.

2）现有任务调度算法以改进单云环境下任务调度算法为主，创新性不足.跨云环境下任务调度算法研究正在不断深入，现有的研究多数是以单云环境下任务调度算法作为参考，再结合跨云环境中新的需求进行改进、优化，虽然能够解决部分问题但这些算法在跨云环境中并不能全部适用，无法与其他算法进行对比，缺少一定的针对性和创新性.

未来研究中，可以针对跨云环境的特点，结合未在跨云环境中使用过的强化学习、模糊排序等算法，提出更新颖、更高效、更实用的跨云环境下任务调度算法.

3）现有任务调度算法优化目标较少且评价指标不完善，无法准确评估算法性能.现有的跨云环境下任务调度算法多是以成本及最大完成时间作为优化目标，虽然在跨云环境中取得了一定的效果，但未考虑环境中诸如可靠性、能耗等其他因素，优化目标过于单一且缺少多维度评价指标.

未来研究中，可结合实际应用环境，将任务的执行时间、完成时间、资源利用率、可靠性、成本、网络吞吐量、可伸缩性能、能耗等优化参数考虑在内，增加对应优化目标，更加全面地考虑环境中影响算法性能的因素，提出跨云环境下任务调度算法的多维度评价指标，更加全面地验证算法的性能，保证任务调度算法的高效性.

随着国家新基建政策的实施，云计算基础设施将得到更加有力地发展和支持，云计算与边缘计算、物联网等新兴技术的深度融合，将使跨云环境成为更多云服务使用者的选择，研究和提出更具实用性的跨云环境下任务调度算法更贴近解决现实问题.未来跨云环境会愈加复杂，跨云环境下任务调度算法将会迎来更多的挑战.

作者贡献声明：唐续豪撰写论文；刘发贵提出了撰写方面的建议；王彬对论文进行了修改，并负责部分文献的整理分类；李超对论文进行了修改及审阅校对；蒋俊对论文的总体架构提出了意见，并对论文进行了审阅校对；唐泉对论文进行了修改及审阅校对；陈维明和何凤文对论文进行了审阅校对并提供了实际参考案例.