文丨五年宝

编辑丨五年宝

前言

云计算是一种，彻底改变了通过互联网以虚拟化方式动态交付计算资源和服务的方式，计算是使用基于实用程序的商业模式来提供的。

其中一些，比如像电力、水、天然气和电话等传统服务，按照即用即付的方式按需提供计算能力，云服务提供商使访问云服务变得更加容易，也被称为超级缩放器。

客户从云服务提供商处获得副级别协议(SLA)的云服务，云计算具有多租户、可扩展性、弹性、资源池和虚拟化等独特功能。

在此基础上，云服务提供商部署IaaS（基础设施即服务）、SaaS（软件即服务）和PaaS（平台即服务）等云服务，这些服务模型的部署以及云资源的高效利用。

在提供商依赖于调度算法的部署后，这些算法保证了资源可以轻松按需获取，在高或低负载条件下高效利用资源，降低资源使用成本。

虚拟化技术理论上可以为云提供无限的资源，即使使云服务提供商实际上控制着无数的资源，消费者在尝试访问资源和服务时也可能会遇到问题。

造成这种情况的主要原因是物理资源对虚拟机的映射不正确，从而影响了云用户的性能，通过调度解决虚拟资源到物理基础设施映射不均匀的问题。

相关工作

在过去的十年里，一些研究人员已经着眼于解决分布式环境中的任务调度问题，在之前他们已经探索过分布式云平台上大规模工作负载的调度 。

而在过去几年中，即将到来的研究人员，还探索了分布式云环境中的其他几个关键特征以及调度。

在他们一些提出的研究方法中，除了调度之外，还包括身份验证、安全性和负载平衡等功能，都是为了实现更高吞吐量的存储架构。

Donghyun提供了一种雾辅助云存储的存储数据审计方案，无需修改现有的最终用户物联网终端设备，而这项方案在最近提出的云计算平台中，作为调度工作负载的算法。

多根调度应用程序的算法，其最终目标是最少的执行时间、最少的完成时间和机会负载平衡，研究人员表示所提出的算法还降低了失败概率。

史密斯研究员提出了启发式方法，包括拍卖、最小到最小和最大到最小，他们提出了两种方法来实施启发式基础设施分配的有力指标。

萨姆拉特·纳特提出了一种基于深度强化学习（DRL）和深度确定性策略梯度（DDPG）方法的动态调度策略，以解决移动边缘计算服务器中的移动用户任务卸载问题。

布亚研究员提出了一种基于预算、截止日期和服务质量的新模型，其最终目标是为基于任务调度的问题找到优化的解决方案。

这种基于遗传的算法旨，在通过解决异构和基于预订的面向服务，其中分布式环境来解决基于期限和成本限制的优化问题。

还有一些研究人员基于多种因素，提出了一种具有更好的虚拟机容错放置方案的启发式蚁群算法来调度提供服务的虚拟机，而传统的启发式算法则用于调度冗余虚拟机。

伯努瓦提出了一种，根据任何特定时间点可用资源的知识来分配工作负载的方法，为了调度集群，传统的抢占式调度机制用于将不同的虚拟机映射到单个主机上。

以此来为算法添加新的近似和启发式方法，直到加瓦利使用基于标准差的改进的布谷鸟优化算法，用来提高系统的性能后，该两阶段算法在第一阶段选择适当的总体样本以获得最佳结果。

之后在第二阶段将所提出的算法应用于该样本总体，Li和Buyya设计了一个基于模拟的模型来调度网格计算环境中的工作负载。

为了计算工作负载相关性的准确性，实验是在模型驱动的模拟中进行的，本地和电网层面的仿真结果表明性能下降，并且表明该模型中负荷的自相关性并不理想。

卢和佐玛亚提出了一种集成的工作负载调度机制，用于在网格的异构环境中执行任务，以减少工作负载的平均响应时间。

该策略适用于广泛的计算网格网络，是分布式网络的优点，比如说工作负载平衡、容错和集中式环境的优点之间的权衡。

而线性规划是最常用的优化技术之一，这种机制用于在给定最小完工时间和最大吞吐量的约束下获得任务调度的最优解决方案。

博什为基础设施即服务平台提出了一种基于时间和成本限制的任务调度算法后，贝尔托又回顾了云模拟增强的蒙特卡罗方法。

他们的工作表明，通过生成随机调度，人们可以获得高精度的最优调度，但对于波动的调度周期，该方法提供了较高的系统吞吐量，同时显示出内存需求的下降。

对于调度周期较大的任务波动，蒙特卡罗会导致系统整体性能下降，但是盲选可以应用于缩小的搜索空间，该搜索空间可以随着工作负载的快速波动而演变。

而这种具有中等精度和不太理想的集合选择的方法会导致整体系统性能下降，Gawali使用基于抢占的分而治之方法，它在云中分配资源，并改善周转时间和响应时间。

在基于遗传的方法中，研究人员通常旨在提高系统吞吐量，而不关心整体系统性能，最终导致重点是在定义的执行模式下正确使用基础设施来正确执行任务。

遗传算法遵循适当的候选程序选择、适应度评估、突变和变异，直到顾描述了一种基于遗传算法的云计算平台基础设施调度策略。

其他研究员又提出了一种基于遗传学的调度程序，其主要目标是通过使用基于染色体的编码方案并在基于数值的模拟器上实现它们来减少完工时间。

随后，他们提出了一种更加基于稳定性的进化调度算法，基础设施即服务模型受益于这种多目标遗传算法。

工作负载的快速变化，需要一种算法来调度高吞吐量的任务并降低多任务环境中调度工作负载的内存需求。

这可以以较低的开销适应工作环境的变化，以获得最佳的调度。

最后在介绍了与云计算环境中的任务调度相关的各种研究后，研究人员发现，蒙特卡罗模拟可能需要数月的时间才能产生最佳调度，并且会承受高波动的负担，从而导致整体性能下降。

如果盲选模拟在较小的搜索空间下给出更好的结果，在增加搜索空间的大小时，性能会下降，减少这些调度开销对于实时云计算是必要的。

提议的方法

现实世界的问题需要现实世界的解决方案，理想的解决方案只是一个理论概念，因为它是不可实现的，而且也不具有成本效益。

而找到问题的准确解决方案似乎是一项不切实际且耗时的任务，云环境中缺乏结构、广泛的不确定性以及巨大的搜索空间，导致需要快速缩小可用的足够好的调度方法。

而不是坚持使用耗时的更准确的调度方法，这让研究人员们首先想到了比较订单，然后评估其价值的概念，也就是它是基数优化之前的序数优化。

序数优化侧重于影响目标的战略变化，说明了序数优化的基本概念，OO的两个基本原则是：决定性的秩序比价值更基本。

目标软化消除了寻找最佳解决方案的计算负担，还可以满足于“很有可能足够好”，而不是要求“肯定是最好的”，最后通过软化优化目标，给定的问题更容易解决。

在这项工作中，赛马条件(HR)与序数优化一起使用，以缩小选择最佳时间表的搜索空间，HR可以被描述为让搜索空间中的所有Schedules同时相互竞争，类似于N匹马参加比赛。

在分析过程中，某些计划可能在特定时间点领先，而相同的计划可能在另一个时刻滞后，时间表的位置由完成给定任务所需的估计时间确定。

这就像所有马匹的比赛同时停止一样，对于序数优化的子集选择，所有调度同时停止，并分析每个调度在停止时间的性能。

研究人员用数学形式化所提出的方法：拟议工作中使用的基本符号，假设他们将搜索空间作为一组候选调度(U)，其中θ是一个单独的调度，使得(θ∈U)。

而使用HR_ne从可用候选调度(U)中选择的前g调度，这个被称为使用抢占方法的子集G的“足够好”调度。

g表示子集G的大小，类似的基数和HR_e选择另一个子集S，称为“选定子集”。

子集S的选择标准直接影响找到最优调度的概率，而S内真正好的调度被称为k(≤g)，使得u>>g>>s>>k。

简单描述就是，k作为子集S中同时也是子集G的成员的调度数，而P通过增加G和S的大小可以使这种对齐概率更加准确。

根据这些提出的方法，在提供实时云计算场景的云计算环境上进行模拟，最终给出了定制模拟设置中使用的数据中心、虚拟机和云的配置详细信息并由有关数据中心的一般信息组成。

最简单的例子就是数据中心的数量、虚拟机的数量、云的数量等，算法给出了有关创建应用所提出方法的测试台的详细描述。

最开始创建5个不同的数据中心，然后创建25个具有不同配置的随机虚拟机，最后创建了两百五十个不同的云。

之后使用时间共享调度器将虚拟机调度到数据中心，使用空间共享调度器将云调度到虚拟机，设计了30个候选调度。

赛马条件(HR)与序数优化一起使用，以缩小选择最佳时间表的搜索空间，而时间表的位置由完成给定任务所需的估计时间确定。

再使用赛马，却没有从可用候选时间表(U)中排除的情况下选择的前g时间表，也被称为使用抢占方法的子集G的“足够好”时间表。

淘汰赛马选择另一个子集S，称为“选定子集”，随后使用序数优化来选择最有希望的时间表。

算法也导出一个数学方程，可用于预测未来出现的云的可能最小完工时间，并根据从上文提到的算法，可以获得的最佳时间表进行调度。

通过序数优化，选择10个最佳时间表，而每个时间表都有不同的配置，每个最佳计划应用四种不同类型的负载。

应用了250、300、350和400个云的四种不同工作负载，记录它们对应的Makespan，最后绘制与这些云和完工时间相对应的图表，然后应用线性回归。

计算该图的斜率和截距，最后得出方程：在尽可能短的完工时间内按照这些最佳调度安排未来云的数学方程。

面向对象的子集选择规则

序数优化使用选择规则来选择子集G&S，但在选择适当的选择规则之前，必须解决一些问题：通过使用基数评估对所有顶级设计进行排序并逐对或全局比较它们来选择S组。

还有通过迭代带有消除或不带有消除的初始设计，将初始计算预算分配给设计。

研究人员又在序数优化中，使用了适当的方法，当使用粗略模型对每个赛程的表现进行初始估计以选择前s个赛程时，将使用赛马条件。

当所提出的模型比较所有候选计划的平均值时，使用无消除的HR(HR_ne)，这也影响了子集G的选择。

有序性能曲线

没有消除的HR(HR_ne)用于选择子集G，该方法使用抢占方法比较所有候选调度的平均值，由于选择完工时间小于OPC平均值的进度表，最终将其称为顶级最佳进度表。

验收时间表是通过赛马方法和全球比较来选择的，即HR_e在该机制中，每一轮比较的最佳排程接收一个完工时间值，然后根据完工时间值将该冠军排程与其他排程进行比较。

每轮的获胜者将保留在接下来的每一轮比较中，而其他赛程表则通过丢弃它们而被淘汰，最后得到一个按降序排序的调度列表。

结论

云服务提供商的平台拥有来自各种云用户的异构基础设施，通过虚拟化在这些有限数量的资源上调度大量的云，以使每个云用户获得最小的延迟。

这项工作提出了一种基于序数优化建模技术的低开销调度方案，候选时间表的测试平台旨在应用和测试所提出的方法。

这包括创建各种数据中心、小云和虚拟机以及小云和虚拟机的调度策略，以便可以设置真实的云环境来调度任务并分析结果。

将不同的工作负载映射到应用序数优化建模技术后获得的最佳计划，以生成所需的完工时间，将线性回归技术应用于这些调度。

这也可以预测小云的未来调度，以获得给定的一组可用最佳调度的最小可能完工时间，在将来所提出的技术可以通过其他参数进一步实现。

相关标签：