云计算中的使命调度算法
一、云计算1、云计算可以说是并行计算与分布式计算相联合的产物，利用互联网和虚拟机技能使得各种资源能够提供给用户使用。按需服务、弹性可扩展是其紧张特性。
一次正常的用户服务流程为: 用户提交使命到云端, 使命调度器将使命分配到符合的计算资源上执行, 使命完成后再将效果反馈给用户。
https://img-blog.csdnimg.cn/0c866791fa754bc998f30434e1216f27.png
2、云计算的根本概念
●数据中心：云数据中心此中包罗对服务器、存储、网络、应用等的虚拟化，使用户可以按需调用各种资源；其次尚有对物理服务器、虚拟服务器以及相关业务的自动化流程管理。数据中心依据服务器性能等的差别分为单一数据中心、多同构数据中心、多异构数据中心。
●服务器：服务器是通过虚拟化、集群技能等进行资源整合，通过云端控制平台按需天生相关主机资源。服务器也可称之为物理主机，可以自行分配与实行多种网络功能服务。服务器也可以分为同构与异构。
●云计算使命（Task，t）：云计算使命就是云用户提交的需要用到云计算资源（服务器、网络装备、存储等）处置处罚的使命，云计算使命根据使命的特点可以分为一般使命、计算型使命、存储型使命、内存型使命。
●虚拟机（VM）：虚拟机是服务器通过虚拟化技能虚拟表现形式的应用、服务器、存储和网络的的一种服务模式，以虚拟机的形式为用户提供云服务可以减少IT开销，同时提高效率和灵敏性。虚拟机根据运行内存、CPU焦点数、存储的差别也可以分为同构虚拟机与异构虚拟机，虚拟机对应使命范例也分为通用型、计算型、内存型和存储型等，这些虚拟机在CPU、内存、操纵体系等软硬件办法上都有所差别。
●云用户：通过云计算服务接口向云服务提供商请求云计算服务的大型企业、小型构造或个人。
云服务提供商：基于云平台、基础布局、应用程序、存储提供云服务服务的公司或者构造。
●指标体系：对云计算调度的一种量化评价方案。可以根据调度指标的多少分为单一目的优化和多目的优化指标体系。云计算调度中的典范指标有使命执行时间、体系能耗、体系可用性、体系经济、负载平衡、资源利用率、安全性等。
●指标权重：多目的优化的云计算调度中各各优化指标的的相对比重，权重不但仅是某一指标所占的百分比，夸大的是指标的相对紧张水平，倾向于贡献度或紧张性。
●目的函数：是云计算调度体系的性能标准，云计算在调度中所追求的目的，通常，这些目的通过量化的指标与权重设置为数学函数的形式。
3、关键技能
云计算的关键技能有：虚拟化技能、分布式数据存储技能、大规模数据管理技能、调度技能。
4、痛点
随着逐渐步入5g时代，以及元宇宙概念的提出，云用户、云使命、端装备数目不断增多，为了提高提供给用户的服务的质量，对于云资源、云使命的调度是必不可少的。
二、使命调度
1、使命调度的本质就是将使命分配到数据中心计算机资源的映射的过程。
2、根据工作流和资源的可用信息以及使命分配给资源的时间可以将使命调度分为静态调度和动态调度。
3、静态调度紧张是开导式和元开导式。此中开导式中有列表调度开导式、聚类调度开导式、重复调度开导式（使命复制）。
（1）列表调度开导式：通过给使命分配优先级。并进行排序，然后天生一个调度列表，依次执行。常见的算法有最早时间优先（ETF）、异类最早完成时间（PEFT）。
（2）聚类开导式：将使命聚类，然后映射到集群，排序、依次执行。
（3）重复开导式（使命复制）：根本头脑是在目的使命的同一资源上精确地复制使命, 从而避免这两个使命之间的执行时间冲突, 以及在差别的时间段内大概会发生一些资源闲置的情况.
https://img-blog.csdnimg.cn/d95d162f17ed493ea2bdf1191369d3a0.png
（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适应度曲线（来自网络）。
优点：全局搜索能力强（能找到全局最佳解），并行性强
https://img-blog.csdnimg.cn/74822c7348744eb0a690b63c0744a6bf.png
五、蚁群算法
在天然界中，蚂蚁群体在寻找食物的过程中，无论是蚂蚁与蚂蚁之间的协作还是蚂蚁与情况之间的交互均依赖于一种被称为信息素（Pheromone）的物质实现蚁群的间接通信，而蚂蚁会寻着信息素较高的路径爬行，从而通过不断迭代合作发现从蚁穴到食物源的最短路径。
优点：收敛速度快
缺点：容易陷入局部最优
在使命调度中：这种局部最优通常指的是，在某几个实例中达到了最优，而无法在大部分实例中达到更好。
六、粒子群算法
通过模拟了鸟群捕食，鸟群在整个征采的过程中，通过相互转达各自的信息，让其他的鸟知道自己的位置，通过这样的协作，来判断自己找到的是不是最优解，同时也将最优解的信息转达给整个鸟群，最终，整个鸟群都能聚集在食物源四周，即我们所说的找到了最优解，即问题收敛。
优点：收敛速度快
缺点：容易陷入局部最优
七、模拟退火算法
https://img-blog.csdnimg.cn/10a4712c269549d8b95a392d48b32726.png
如图（来自网络），物体在降温的过程中，每个状态就是一种办理方案，这样循环直到内能最低。
某温度下物质状态：办理方案
内能最低：最优解
https://img-blog.csdnimg.cn/7ea5daf68e3142f8b641da8a7827beb4.png
与别的智能算法差别的是, SA 在迭代过程中会以一定的概率担当与当前解相比较差的解, 担当概率随着温度的降低减小. 由于在搜索过程中担当差解, 所以有大概导致遗失掉最优解; 另一方面, 这种处置处罚可以在一定水平上避免算法陷入局部最优解。
缺点：收敛速度慢，搜索速度慢
八、算法对比和总结
1、算法对比
对比这四种算法不难发现，粒子群算法和蚁群算法都是在信息交互后，向更良好的个体看齐，是收敛速度加快，导致丧失多样性，大概陷入局部最优。
反之，遗传算法中会进行交叉、变异等，而模拟退火算法则由于Metropolis 准则使解更具有多样性，致使两者都将消耗大量时间，也加强了全局搜素能力，避免陷入局部最优。
https://img-blog.csdnimg.cn/0a6eaa271b254d0ebf45a192578b258c.png
2、总结
在信息技能的不断发展下，云计算的两大难点也暴露了出来
其一，物联网装备、传感器中大量的数据传输带来了更高的功耗成本催生了调度技能，能较好的降低云计算的功耗。
其二，由于云是远离用户的，也导致了较高的网络延迟，因此催生了边沿计算。
边沿计算就是在网络的“边沿”进行服务交付, 执行的数据计算和存储在用户附近. 相比较云计算与用户的距离更近近,最直观导致的效果就是降低了网络延迟、网络的带宽需求、数据计算或存储期间的传输延迟, 而且有用地降低了物理装备消耗速度。
参考文献：
杨戈,赵鑫,黄静.面向云计算的使命调度算法综述.计算机体系应用,2020,29(3):11–19. http://www.c-s-a.org.cn/1003-3254/7261.html
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]