云计算中的任务调度算法

一、云计算

1、云计算可以说是并行计算与分布式计算相结合的产物，利用互联网和虚拟机技术使得各种资源能够提供给用户使用。按需服务、弹性可扩展是其主要特征。

 一次正常的用户服务流程为: 用户提交任务到云端, 任务调度器将任务分配到合适的计算资源上执行, 任务完成后再将结果反馈给用户。

2、云计算的基本概念

●数据中心：云数据中心其中包括对服务器、存储、网络、应用等的虚拟化，使用户可以按需调用各种资源；其次还有对物理服务器、虚拟服务器以及相关业务的自动化流程管理。数据中心依据服务器性能等的不同分为单一数据中心、多同构数据中心、多异构数据中心。
●服务器：服务器是通过虚拟化、集群技术等进行资源整合，通过云端控制平台按需生成相关主机资源。服务器也可称之为物理主机，可以自行分配与实行多种网络功能服务。服务器也可以分为同构与异构。
●云计算任务（Task，t）：云计算任务就是云用户提交的需要用到云计算资源（服务器、网络设备、存储等）处理的任务，云计算任务根据任务的特点可以分为一般任务、计算型任务、存储型任务、内存型任务。
●虚拟机（VM）：虚拟机是服务器通过虚拟化技术虚拟表示形式的应用、服务器、存储和网络的的一种服务模式，以虚拟机的形式为用户提供云服务可以减少IT开销，同时提高效率和敏捷性。虚拟机根据运行内存、CPU核心数、存储的不同也可以分为同构虚拟机与异构虚拟机，虚拟机对应任务类型也分为通用型、计算型、内存型和存储型等，这些虚拟机在CPU、内存、操作系统等软硬件设施上都有所不同。
●云用户：通过云计算服务接口向云服务提供商请求云计算服务的大型企业、小型组织或个人。
云服务提供商：基于云平台、基础结构、应用程序、存储提供云服务服务的公司或者组织。
●指标体系：对云计算调度的一种量化评价方案。可以根据调度指标的多少分为单一目标优化和多目标优化指标体系。云计算调度中的典型指标有任务执行时间、系统能耗、系统可用性、系统经济、负载均衡、资源利用率、安全性等。
●指标权重：多目标优化的云计算调度中各各优化指标的的相对比重，权重不仅仅是某一指标所占的百分比，强调的是指标的相对重要程度，倾向于贡献度或重要性。
●目标函数：是云计算调度系统的性能标准，云计算在调度中所追求的目标，通常，这些目标通过量化的指标与权重设置为数学函数的形式。

3、关键技术

云计算的关键技术有：虚拟化技术、分布式数据存储技术、大规模数据管理技术、调度技术。

4、痛点

随着逐渐步入5g时代，以及元宇宙概念的提出，云用户、云任务、端设备数量不断增多，为了提高提供给用户的服务的质量，对于云资源、云任务的调度是必不可少的。

二、任务调度

1、任务调度的本质就是将任务分配到数据中心计算机资源的映射的过程。

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

3、静态调度主要是启发式和元启发式。其中启发式中有列表调度启发式、聚类调度启发式、重复调度启发式（任务复制）。

（1）列表调度启发式：通过给任务分配优先级。并进行排序，然后生成一个调度列表，依次执行。常见的算法有最早时间优先（ETF）、异类最早完成时间（PEFT）。

（2）聚类启发式：将任务聚类，然后映射到集群，排序、依次执行。

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

（4）元启发式：启发式的进化版，大多是在大量的解决方案中择优。

4、动态调度：动态调度算法的目标是在可用资源队列之间实现负载均衡。但是准确地评估每个队列的负载并不那么容易。单独使用动态工作流计划程序仍可能将任务分派到过量提交的队列，从而导致等待时间过长。
一种简单的方法是将队列等待时间预测技术与工作流调度相结合。Brevik等人首先提出了一种二项式批预测器（BMBP）方法来预测排队延迟的界，即单个作业在被启动执行之前在队列中等待的时间量。

三、任务调度算法

根据调度目标可以分为两类：针对单一目标优化的传统任务调度算法和针对多目标优化的启发式智能优化算法。传统的算法主要是寻求某个实例的最优解，智能算法则照顾到全局，寻求一个尽量满足多个实例的极优解。

1、单目标优化：主要有最小完成时间 (MCT)、最小执行时间(MET)、交换算法 (SA)、贪心算法 (GRA)、先来先服务 (先进先出) 算法 (FCFS/FIFO)、最短作业优先算法 (SJF) 等。

 2、多目标智能优化主要分为基于生物启发（BI）的遗传算法 (GA)、模因算法(MA)、狮子算法 (LA)、帝国竞争算法 (ICA)

以及基于群体智能（SI）的蚁群 (ACO) 算法、粒子群优化 ( PSO) 算法、模拟退火 (SA) 算法、人工蜂群( ABC) 算法、猫群优化 (CSO) 算法、蝙蝠算法 (BA)、风驱动优化 (WDO) 算法等。

四、遗传算法

遗传算法以生物界中的基因遗传为灵感，将其抽象类比成对于问题的优化算法。

其中：

染色体：问题的解决方案

基因：解决方案中的一个参数。多个基因构成了染色体

交叉：在迭代过程中，把两个解决方案中的某参数进行交换重组。

变异：在迭代过程中，把解决方案中的某参数进行突变。（很小的概率）

在遗传算法中，初始生成大量的随机的染色体（种群），然后进行迭代。

如何进行迭代？

主要是两步：自然选择、繁殖

在遗传算法中用适应度来衡量染色体的表现好坏。其中适应度越高的个体，在自然选择中存活的几率越高，也就让更优秀的基因存留了下来；然后让这些染色体直接复制或杂交繁殖出下一代。这样，经过不断迭代，就能得到全局更优秀的染色体，也就是解决方案。

缺点：消耗大量时间进行迭代、评估，后期求解率低，如图是GA适应度曲线（来自网络）。

优点：全局搜索能力强（能找到全局最佳解），并行性强

 五、蚁群算法

在自然界中，蚂蚁群体在寻找食物的过程中，无论是蚂蚁与蚂蚁之间的协作还是蚂蚁与环境之间的交互均依赖于一种被称为信息素（Pheromone）的物质实现蚁群的间接通信，而蚂蚁会寻着信息素较高的路径爬行，从而通过不断迭代合作发现从蚁穴到食物源的最短路径。

优点：收敛速度快

缺点：容易陷入局部最优

在任务调度中：这种局部最优往往指的是，在某几个实例中达到了最优，而无法在大部分实例中达到更好。

六、粒子群算法

通过模拟了鸟群捕食，鸟群在整个搜寻的过程中，通过相互传递各自的信息，让其他的鸟知道自己的位置，通过这样的协作，来判断自己找到的是不是最优解，同时也将最优解的信息传递给整个鸟群，最终，整个鸟群都能聚集在食物源周围，即我们所说的找到了最优解，即问题收敛。

优点：收敛速度快

缺点：容易陷入局部最优

七、模拟退火算法

如图（来自网络），物体在降温的过程中，每个状态就是一种解决方案，这样循环直到内能最低。

某温度下物质状态：解决方案

内能最低：最优解

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

缺点：收敛速度慢，搜索速度慢

八、算法对比和总结

1、算法对比

对比这四种算法不难发现，粒子群算法和蚁群算法都是在信息交互后，向更优秀的个体看齐，是收敛速度加快，导致丧失多样性，可能陷入局部最优。

反之，遗传算法中会进行交叉、变异等，而模拟退火算法则由于Metropolis 准则使解更具有多样性，致使两者都将消耗大量时间，也加强了全局搜素能力，避免陷入局部最优。

 2、总结

在信息技术的不断发展下，云计算的两大难点也暴露了出来

其一，物联网设备、传感器中大量的数据传输带来了更高的功耗成本催生了调度技术，能较好的降低云计算的功耗。

其二，由于云是远离用户的，也导致了较高的网络延迟，因此催生了边缘计算。

边缘计算就是在网络的“边缘”进行服务交付, 执行的数据计算和存储在用户附近. 相比较云计算与用户的距离更近近,最直观导致的结果就是降低了网络延迟、网络的带宽需求、数据计算或存储期间的传输延迟, 并且有效地降低了物理设备损耗速度。

参考文献：

[1]杨戈,赵鑫,黄静.面向云计算的任务调度算法综述.计算机系统应用,2020,29(3):11–19. http://www.c-s-a.org.cn/1003-3254/7261.html