面向云计算的任务调度算法综述①

杨 戈,赵 鑫,黄 静,2

1(北京师范大学珠海分校 智能多媒体技术重点实验室,珠海 519087)

2(北京师范大学研究生院珠海分院,北京 100875)

3(北京大学深圳研究生院 深圳物联网智能感知技术工程实验室,深圳 518055)

1 引言

而随着云技术的发展和云平台的广泛部署,云中的工作流调度问题成为一个重要的研究课题[1],在云计算服务交付的过程中,由于用户直接面对的是虚拟机资源,而真正解决问题的是虚拟机映射的实际的物理资源,所以如何将任务合理分配到资源执行是我们所重点关注的.

(1)云计算

云计算通过多种部署方式,包括私有云、社区云、公有云、混合云4 种部署模型[2],通过基础设施即服务、平台即服务、软件即服务3 种服务模式用户提供服务.云计算有2 个显著的特征,快速弹性可扩展[3]、按需付费服务[4].

云计算关键技术[5]分别有:虚拟化技术[6]、分布式数据存储技术[7]、大规模数据管理技术[7]、调度技术[8].

(2)调度技术

云计算中的调度一般分为两个部分:① 资源调度:资源调度是指对物理资源进行合理有效的管理和使用等;② 任务调度:将任务合理分配到合适的计算资源执行.

简单点讲,一次正常的用户服务流程为:用户提交任务到云端,任务调度器将任务分配到合适的计算资源上执行,任务完成后再将结果反馈给用户.其中,任务分配这一环尤其重要,一个合理高效的调度策略能够极大的提升云计算系统的性能.下文重点关注的是任务调度.

随着云用户数量的不断增加,为用户提供优质的服务势在必行.因此,任务调度非常重要,因为它专注于在特定时间将任务分配给可用资源.为了获得良好的用户服务质量,需要高效的任务调度.现有的云计算任务调度技术已经被研究者们提出,但要实现高效的任务调度,还需要进一步的改进.所有算法的主要目标都是最大限度地利用资源,最大限度地减少制造时间和成本,提高性能.

(3)云环境中的服务交付模型

云计算中的服务交付模型分为4 部分,如图1 所示.

① 用户提交任务;

② 任务管理器将其拆分成多个子任务;

③ 任务调度器通过调度技术将子任务与物理资源建立映射关系;

④ 任务完成后进行汇总,反馈到用户.

由此看出,从任务出发到完成,在整个任务执行过程中,调度技术是重中之重,它影响到了整个系统的运行效率、用户服务质量、系统负载均衡、系统能耗.

因此一个适合云计算环境的调度技术十分重要.由于调度技术分为资源调度和任务调度,本文只关注任务调度.

图1 云计算服务交付模型图

2 任务调度

任务调度,在云计算环境下其本质是一个映射的过程,它在一定的约束条件下,根据云计算环境下任务、资源两者的预测信息和状态将用户提交的互相独立的任务映射到相应的虚拟机资源上执行,然后返回处理结果[9].简单点说,就是将x个任务分配到y个计算机资源上执行的过程.

根据工作流和资源的可用信息以及任务分配给资源的时间可以将任务调度分为静态调度和动态调度[1].

2.1 调度分类

2.1.1 静态调度

静态调度中分为4 类:列表调度启发式[10,11]、聚类调度启发式[11]、重复调度启发式、元启发式.

(1)列表启发式

基本思想是通过给任务分配一些优先级,并根据优先级对其进行排序,从而生成一个任务调度列表,然后从调度列表中选择第一个任务,再将任务分配给其对应的资源,直到对所有任务进行调度.

调度列表可以静态或动态构造.如果所有优先级都是在任务分配之前构造的,则为静态列表调度;如果在每个任务调度之后重新计算未调度任务的优先级,则为动态列表调度.但是无论是哪种列表调度,都必须要有一个优先级的判断属性和资源选择策略,并以此决定任务的优先级与其对应的最佳资源.

常见的列表调度启发式算法,如最早时间优先(Earliest Time First,ETF),异类最早完成时间(Predict Earliest Finish Time,PEFT)[10]等.

(2)聚类启发式

基本思想是通过在同一个集群中对任务进行聚类,将任务映射到集群,在同一个群集中排序任务.尽量牺牲并行性来降低通信延迟,优化数据相关任务之间的传输时间.

如果同一个集群中有两个独立的邻居任务,则称为非线性集群;否则称为线性集群.对于非线性聚类,对独立任务进行排序.线性聚类保留了并行性,不会增加并行执行时间.非线性聚类通过对并行任务进行排序来减少并行性,从而增加并行执行时间.

(3)重复启发式

基本思想是在目标任务的同一资源上正确地复制任务,从而避免这两个任务之间的执行时间冲突,以及在不同的时间段内可能会发生一些资源闲置的情况.

因为在实际的调度中,有些任务可能正在等待分配给其他资源的任务的数据,只有接收到该数据之后,任务才能开始执行,如果在数据接收之前轮到该任务执行,就会发生阻塞,产生空闲时段,直到数据到来,影响到后面任务的执行.如果使用有效的调度算法,通过识别任务使得这些空闲时段可以有效地利用,那么就可以缩短总的执行时间.

基于重复的调度通常可以缩短生成时间.然而,这也使得调度问题更加困难.调度算法不仅需要观察任务之间的优先级约束,还需要识别哪些任务需要复制,以及如何将它们放入空闲时段.

(4)元启发式

元启发式是启发式的进化版,是对启发式局部搜索的改进,元启发式方法通常提供了一种快速朝着一个非常好的解决方案前进的有效方法.如遗传算法、蚁群算法、粒子群算法等.

与基于局部搜索的启发式方法相比,元启发式方法能够在更大的解空间中搜索到任务解决方案.因此,在大多数情况下,元启发式比基于局部搜索的启发式性能更好.

将以上局部的静态调度做了一个比较,比较结果如表1 所示.

列表启发式大部分都适用于资源数量有限的系统,比较关注如何在保证能完成调度的同时降低系统的开销.

聚类启发式通常假定资源数量无限,并将大量通信任务分配给同一类资源.虽然它减少了资源间的通信,但当任务在资源上按优先级约束排序时,也可能导致负载不平衡或空闲时隙.

重复启发式算法旨在降低任务的执行时间,避免大量的通信.重复启发式通常在牺牲计算时间复杂性的情况下具有更好的调度质量.

元启发式比以上基于局部的启发式性能更好.但是,随着工作流任务数的增加,元启发式算法的调度时间开销也会迅速增加.

表1 静态调度比较表

2.1.2 动态调度

动态调度[12]是为了解决调度信息的不可用性和资源与其他工作流或非工作流系统负载的争用而开发的,目标是在可用资源队列之间平衡负载.

任务执行和通信时间由资源和工作流信息共同决定.其中工作流信息包括工作流结构、任务执行工作量、通信数据量等,资源信息包括云环境下的可用性、处理能力、通信带宽等.在实际生产系统中它们都是不完整的、动态的.要准确地评估每个队列的负载并不容易,因此需要一个动态调度策略来处理这些不确定性.

总的来说,在静态中,所有关于任务的信息在执行之前都是调度程序已知的,可以事先获取到更多信息,对任务调度的方案进行优化,使得任务实际执行时开销更小;而在动态中,关于任务的信息在执行之前不知道,但运行时开销更大,但是能更好地处理负载平衡的问题.

通过对调度的分析发现,不管是静态还是动态调度,由理论到实际解决问题都是依靠具体的任务调度算法执行的.简单地说,一种任务调度算法就是一种调度方式,云计算中任务调度的优劣主要就体现在任务调度算法的优劣上.

合理的任务调度要从2 个出发点进行考虑:云计算提供商,用户.对提供商来说,最关心的就是成本,所以要能够有效协调和分配资源,降低成本;对用户来说,服务质量放在首位,所以需要在完成需求的同时,降低任务的总执行时间.

所以一个既可以对虚拟资源进行有效的协调和分配,降低提供商的成本;又能快速、准确地完成任务,给用户一个好的用户体验;能让提供商和用户都满意的任务调度算法是云计算所迫切需要的.

而任务调度的约束条件就是依靠具体的任务调度算法来执行的,所以选择合适的任务调度算法对策略的执行具有很重大的意义.

2.2 任务调度算法

任务调度算法根据调度目标的数量可以分为2 类:针对单一目标优化的传统任务调度算法,针对多目标优化的启发式思想的智能化算法.

2.2.1 单目标优化的任务调度算法

单目标优化的任务调度算法主要包括最小完成时间(Minimum Completion Time,MCT)、最小执行时间(Minimum Execution Time,MET)、交换算法(Switching Algorithm,SA)、贪心算法(GReedy Algorithm,GRA)、先来先服务(先进先出)算法(First Come First Server,FCFS/First In First Out,FIFO)、短作业优先算法(Shortest Job First,SJF)等.

其中MET 算法考虑到任务的最短执行时间,忽略了负载是否平衡的问题;MCT 算法考量到任务最早的完成时间,但是可能导致工作时间变长;SJF 算法考虑选择用时较短的任务优先执行,而忽略了任务的优先级.

从以上不难看出:单目标优化的任务调度算法重点在于单一目标的最优解,即某个实例的最优,体现在“最”字上,这样的话其他实例没在考虑的范围内,就会不可避免的舍弃掉很多东西,比较局限于某个目标最优,而无法考虑到全局,都是比较极端的算法,为了达到目标,可以不惜牺牲一切.导致的后果是:虽然该实例取得的效果最好,但是因为要最大化的满足它而舍弃掉太多东西,导致其他实例的效果就不是很理想甚至很糟糕,使得结果具有很大的局限性而无法推广.

2.2.2 多目标优化的任务调度算法

在优化设计中,要求多个目标达到最优的问题被称为多目标优化或者多约束问题.在这种情况下,基于启发式思想的智能化算法应运而生.

启发式思想的智能化算法思想在于:解决多约束问题时,在可以接受的花费的前提下,得到一个解决方案,给出尽量满足多个目标优化的一个可行解.其核心点在于“多目标优化”,即对于每一个实例来说,也许当下解并不是它的最优解,但却是多个实例在尽量满足需求条件下的极优解.

常用的启发式思想的智能化算法包括2 类[13]:

(1)基于生物启发(Biological Inspiration,BI)

遗传算法(Genetic Algorithm,GA)、模因算法(Memetic Algorithm,MA)、狮子算法(Lion Algorithm,LA)、帝国竞争算法(Imperialist Competitive Algorithm,ICA),是在云计算中与任务调度相关的少数生物启发算法.

(2)基于群体智能(Swarm Intelligence,SI)

蚁群(Ant Colony Optimization,ACO)算法、粒子群优化(Particle Swarm Optimization,PSO)算法、模拟退火(Simulated Annealing,SA)算法、人工蜂群(Artificial Bee Colony,ABC)算法、猫群优化(Cat Swarm Optimization,CSO)算法、蝙蝠算法(Bat Algorithm,BA)、风驱动优化(Wind Driven Optimization,WDO)算法等[13].

3 任务调度算法

3.1 遗传算法

GA 的创造思路来源于达尔文著名的生物进化论中“优胜劣汰”的自然选择原则,将自然生物的进化类比应用到实际问题中,是通过模拟自然进化的过程来解决组合优化问题的一种搜索最优解的方法.

GA 对于给定问题的任何解决方案都由一组称为基因的元素组成的染色体代表,即每一条染色体代表一个解决方案.算法终止后,最出色的染色体就是给定问题的最优解.

算法的优点:进行选择、交叉、变异等操作的目标是选择区域中所有的染色体,初期全局搜索能力强,并行性强;

缺点:要花费大量时间对染色体进行评估、选择、交叉、变异等操作,后期求解效率低.

遗传算法的优点主要在于其强力的全局搜索,但是在算法的搜索效率以及算法解的多样性方面还是需要改进,所以以下文献主要对算法的这2 个部分进行优化,如表2 所示.

表2 遗传算法优化表

3.2 蚁群算法

ACO 最早是于20 世纪90 年代,Dorigo M 等[19]通过观察蚂蚁觅食行为,并从中获得设计灵感而提出的,常用于求解复杂组合优化问题的一种元启发式智能优化技术[20].

信息素的管理主要包括信息素的局部更新和信息素的全局更新2 个部分[21].

算法的优点:在后期确定了目标点和最优路径之后,所有成员每次都会按照最优路径进行计算,节省大量时间,速度快.

缺点:在初期确定目标点和最优路径时,因为信息匮乏需要花费大量的时间做大量的摸索尝试,速度慢.

蚁群个体之间通过信息素交流,信息素积累起来之后,搜索效率、解的精度极高,但同时,其缺点在于前期信息素的积累花费了太多时间,由于收敛速度快,也容易陷入局部最优,所以以下文献主要在算法的解的多样性和算法前期的搜索效率方面进行优化,如表3所示.

表3 蚁群算法优化表

3.3 粒子群算法

粒子群算法,也称为鸟群、鱼群觅食算法,是模拟鸟群、鱼群的觅食行为规律在搜索空间进行搜索最优解的方法.最早由Kennedy J 和Eberhart R[26],该算法最初是对一个简化的社会环境的模拟,主要应用于求解连续搜索范围问题[27].

与遗传算法这种进化算法不同,遗传算法会舍弃适应度较低的染色体,而粒子群不使用选择,不会舍弃任何一个解,尽管这个解的质量很差,算法会利用粒子间的信息交流对差解不断地优化,所有的种群成员从试验开始一直存活到最后.

算法的优点:搜索速度快、收敛速度快、参数少等.

缺点:局部搜索能力差、初始化粒子随机性强.

粒子群和蚁群算法在某些方面比较相似,搜索速度快,但是容易陷入极值,所以以下文献主要在算法多样性和精度方面进行优化,如表4 所示.

表4 粒子群算法多样性优化表

3.4 模拟退火算法

模拟退火算法是一种随机搜索算法,是对热力学中固体物质退火过程的模拟.文献[34]中介绍模拟退火算法最早的思想是由Metropolis 等提出.Kirkpatrick 等成功地将退火思想引入到组合优化领域.

固体物质退火过程与一般组合优化问题之间的相似性如表5 所示.

表5 模拟退火算法与组合优化问题的相似性

SA 对于给定问题的任何解决方案都由退火过程中物质的状态代表,即每个温度下物质的状态代表一个解决方案,当内能到达最低时,物质的状态就代表最优解[35].

算法的优点:稳定性好,在局部最优时容易有概率跳出并趋于全局最优;

缺点:对参数依赖性强,收敛速度慢,搜索时间长.如果冷却过程足够慢,模拟运行时间足够长,模拟退火几乎可以保证找到最优的解决方案.

与其它智能算法不同的是,SA 在迭代过程中会以一定的概率接受与当前解相比较差的解,接受概率随着温度的降低减小.由于在搜索过程中接受差解,所以有可能导致遗失掉最优解;另一方面,这种处理可以在一定程度上避免算法陷入局部最优解.

以下文献主要在使用Metropolis 准则对新解进行一个概率接受的部分进行优化,减小陷入局部最优的可能性.如表6 所示.

3.5 算法对比

由以上第4 章对各算法的阐述,发现各个算法都有其自身的优点和不足,这里对其能力的各个方面进行比较,如表7 所示.

算法搜索过程中会进行信息交互的算法ACO,PSO 都会面临一个问题:信息交互后,每个个体都会受到优秀个体搜索结果的影响,都会向着优秀的个体“看齐”,这样就会导致算法收敛速度大大加快.算法收敛速度快会产生2 种结果:

① 算法整体的进程节奏加快,更早地达到终止条件;

② 算法丧失多样性,容易陷入局部最优.

与之相反,GA,SA 的收敛速度都相对比较慢,其原因是GA 会对种群中的大量个体执行操作,SA 则会对温度变化过程中产生的每一个新解都进行操作,花费了大量的时间,收敛速度自然就快不起来.算法收敛速度慢会产生2 种结果:

③ 算法整体的进程节奏过慢,算法搜索效率低;

④ 加强了算法的全局搜索能力,有效降低陷入局部最优的可能性.

所以如何将算法的收敛性利用好,在加速算法进程的同时增加算法解决方案的多样性是值得进行研究的.

启发式思想的智能化算法相比较于传统的算法优化更全面,适用性更广,虽然各自有各自的特点,但同时也有自身的不足,要想使其具有更强的生命力,就需要不断自我提升;同时也需要借鉴其他算法的优势,彼此相互学习,优劣互补来弥补自身的不足,同时达到更优的效果.

表6 模拟退火算法优化表

表7 算法对比

4 结束语

对云计算作了一个概述,阐述了云计算环境下的任务调度模型,并对其进行了分析,再由任务调度引出4 个比较完善、具有代表性的任务调度算法ACO、GA、PSO、SA,分别对它们做了详细分析,包括基本思想、算法特点以及可改进的方式,针对各个算法的特点,归纳了一些各个算法两两之间可以进行改进以及融合方法;再对相比前面4 种算法,比较新颖的ACO、ICA、BA、CSO 做了分析,包括算法的基本思想、特点和可改进的方式;由于从理论想要应用到实践,就必须要经过实验对其进行验证,而直接投入实际环境中进行实验会花费大量的时间、资源等.

随着信息技术的不断进步,物联网在我们的日常生活中发挥着越加重要的作用,人们生活水平的提高,对各种物联网应用的要求也越来越高,对云计算的挑战也随之到来.在传统的云计算中,每一次服务交付都要将计算过程上传到云,有限的带宽和网络资源被大量数据传输所占用,然而云是远离用户的,这就直接造成了云计算所面临的第一大难点:网络延迟.此外,物联网设备和传感器的功率是有限的,大量的数据传输也给物理设备带来了压力,这也是云计算所面临的第二大难点:功耗成本.

为了延长设备的使用寿命,就很有必要通过将计算调度到具有更高功率和计算能力的设备来平衡功耗,即通过改善任务调度可以有效地降低云计算的功耗成本.因此,任务的调度和处理分配就成为了云计算需要解决的关键问题.

虽然通过调度方案的优化可以减少云计算的功耗,但是由于云计算服务中,每一次服务交付都要将计算过程上传到云端,即使改进了调度方案,还是无法有效地解决网络延迟的问题.

为了解决云计算网络延迟的问题,边缘计算[40]出现了.边缘计算不同于云计算,很直观地,边缘计算就是在网络的“边缘”进行服务交付,执行的数据计算和存储在用户附近.相比较云计算与用户的距离更近近,最直观导致的结果就是降低了网络延迟、网络的带宽需求、数据计算或存储期间的传输延迟,并且有效地降低了物理设备损耗速度.此外,与云计算相比,边缘计算可以将计算和通信开销从具有有限电池或电源的节点迁移到具有大量功率资源的边缘节点.

2016 年5 月,美国自然科学基金委(National Science Foundation,NSF)在计算机系统研究中将边缘计算替换云计算,列为突出领域[41].虽然其发展和技术还不太成熟,但是由于其自身的特点,边缘计算将会成为继云计算之后的又一大热点领域.7 个关键技术包括:网络、隔离技术、体系结构、边缘操作系统、算法执行框架、数据处理平台以及安全和隐私;未来几年迫切需要解决的6 个方向问题:编程模型、软硬件选型、基准程序与标准、动态调度、与垂直行业的紧密结合以及边缘节点的落地[41].