沙特国王大学学报：云计算环境下的工作流资源调配与优化调度策略分享

沙特国王大学学报云计算环境Raza Abbas Haidri1，Chittaranjan Padmanabh Katti2，Prem Chandra Saxena3印度新德里贾瓦哈拉尔·尼赫鲁大学阿提奇莱因福奥文章历史记录：2017年5月12日收到2017年10月12日修订2017年10月27日接受2017年11月3日在线发布保留字：云计算资源调配工作流调度获取延迟服务质量（QoS）A B S T R A C T在云模式中，资源按需提供，并在租用的时间间隔内按使用付费通常，云用户使用这些资源来执行他们的应用程序。这些应用程序可以是一批独立的或工作流任务。现有的研究主要集中在优化各种服务质量（QoS）参数。本文针对工作流任务/应用程序提出了一种具有成本效益的截止期感知（CEDA）调度策略，以在满足工作流中截止期和优先级约束的同时，优化任务/应用程序的总执行时间和经济成本。CEDA选择具有最高向上排名的任务，并考虑虚拟机（VM）的获取延迟将所选任务分派到最便宜的VM实例。通过在标准科学工作流程（如Montage、CyberShake、LIGO和SIPHT）上与ICPCP和ICPPD 2进行比较，对所提出的策略进行了性能评估。实验结果表明，CEDA优于所有考虑的算法几乎所有的参数下的研究。©2017作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在计算基础设施即服务中，云资源提供者提供具有用户执行其应用所需的不同价格和容量的服务（Broberg等人， 2008年）。用户可以访问这些服务以执行他们的应用程序，例如“按需付费”的工作流，*通讯作者。电 子 邮 件 地 址 ： razaabbas. gmail.com （ R.A.Haidri ） 、 cpkatti@yahoo.com（C.P. Katti）、premchand_saxena@yahoo.com（P.C.Saxena）。1他在同一所大学获得了技术硕士学位。他在Aligarh穆斯林大学完成了MCA学位。他的研究兴趣是云计算领域。2他获得了硕士学位。密苏里大学哥伦比亚分校应用数学专业，1976年毕业于美国，1981年获得印度理工学院博士学位。他在国际知名期刊上发表了30多篇论文。他的研究领域包括并行计算和数值分析。3他获得了印度新德里德里大学的博士学位。他主修运筹学、通信和数据挖掘。他在国际知名期刊上发表了多沙特国王大学负责同行审查（Deelman等人，2009; Haidri等人， 2014年）。用户往往希望在一定的截止时间内以最小的代价完成他们的应用程序服务水平协议（SLA）是对现实世界的一种模仿，可以被视为服务提供商和用户之间的相互合同，通常旨在实现QoS（Hiles，1993）。有许多论文解决传统分布式系统（如网格）中的资源分配和调度问题调度问题，特别是在工作流等复杂应用中，由于资源和应用的异构性、时间约束、截止期约束等问题，调度问题变得困难。当大多数商业云提供商根据用户使用的时间间隔数向用户收费时，工作流在分布式系统中用于广泛的科学应用（Deelman等人，2009年）。通常，工作流应用被建模为有向无环图（DAG），其中每个节点表示任务，并且节点之间的有向弧示出任务之间的依赖性。几个网格项目，如ASKALON、Pegasus和GrADS，已经设计了可以在网格上执行的工作流（Wieczorek等人，2005;Deelman等人，2005; Berman等人，2005年）。然而，公用事业网格模型和当前商业云之间存在三个主要差异。首先是云的按需资源配置特性，它决定了https://doi.org/10.1016/j.jksuci.2017.10.0091319-1578/©2017作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comR.A. Haidri等人/沙特国王大学学报667用户所需的资源，而在公用电网，资源是有限的，并提前知道。因此，云用户幻想可以访问无限的资源，从而可以根据工作流程，截止日期和预算的需求增加或减少所获得的资源。第二个区别在于云和公用事业网格中的服务提供者的带宽。在云中，带宽大致是均匀的，而在公用事业网格中是异构的。第三，也是最重要的区别是云的特点是按使用付费的定价模式。用户必须为他们实际消费的东西付费。例如，假设用户使用6个单位的计算资源，租期为5个单位，则他/她必须支付两个租期。所提出的算法遵循与Google、Amazon和Cloud-Sigma（Amazon，2016;Google，2016; CloudSigma，2016）类似的定价模型。由于用户需要为已使用实例的持续时间付费，即使他/她只使用了其中的一部分，因此该算法必须最大限度地利用它最近，一些研究人员已经开始考虑云计算在执行科学工作流程中的优势（Hoffa等人，2008;Deelman，2010）。各种商业云，如亚马逊提供虚拟化的资源，使用户能够部署他们的服务和应用程序。这种服务供应模型被称为基础设施即服务（IaaS）（Deelman，2010）。然而，用户可以获得的资源数量和等待时间仍然是一个主要问题（Deelman，2010）。 几个网格项目，如VGrADS、Pegasus和ASKALON，也支持在云上执行工作流（Ramakrishnan等人，2009; Ostermann等人，2009年a、b）。尽管有很多好处，但云计算仍然面临着许多需要解决的挑战首先，在租用和释放时，VM需要时间来正确初始化（获取延迟）和关闭（终止延迟）。因此，获取资源所需的时间越长，总处理时间就越长，因此，关闭所需的时间也就越长（Mao和Humphrey，2012年）。因此，工作流程总成本将增加。因此，这些延误降低了整体绩效，影响了工作流程成本，并导致资源供应不足和错过最后期限。因此，云提供商需要考虑VM获取延迟。在所提出的工作中，假设每个VM具有平均捕获延迟。终止延迟不被考虑，因为它对最后期限约束没有影响。最后，由于云环境提供了99.9%的可用性（CloudHarmony，2016），因此我们不考虑任何VM故障。此外，假设用户指定的最后期限是可实现的。因此，主要关注的是在云中提供具有成本效益的可行时间表。工作流的调度是分配适当的资源分配给每个工作流任务，以满足QoS约束。任务调度是一个NP完全问题（Gary和Johnson，1979），在文献中已经发现了用于异构和同构分布式系统（例如网格）的几种启发式算法（Topcuoglu等人，2002年; Bajaj和Agrawal，2004年; Daoud和Kharma，2008年）。这些都是适合社区网格调度方法，因为他们试图减少工作流程的完工时间。为了在满足工作流中的截止期和优先级约束的前提下，优化工作流的总执行时间和经济成本，提出了一种基于成本有效截止期感知（CEDA）的工作流CEDA选择具有最高向上排名的任务，并考虑虚拟机（VM）的获取延迟将所选任务分派到最便宜的VM实例这些延误在启动时间长的情况下会产生影响，导致资源供应不足和错过最后期限。因此，需要考虑云的虚拟机获取延迟提供商已将拟定策略与已确立的最新技术水平方法（即ICPCP和ICPCPD 2）在标准科学工作流程（如蒙太奇、CyberShake、LIGO和SIPHT）上进行了比较，以评价其在文献中的位置。因此，本文其余部分的结构如下。第2节简要介绍了所做的相关工作。第3节中已经解释了问题的表述，包括应用模型和云资源模型。在第4节中给出了所提出的算法CEDA，并附有算法模板和示例。第5节介绍了模拟研究，讨论了实验中的各种观察结果和计算复杂性。第6节介绍了对所考虑的策略进行逐例比较的统计检验。最后，本文结束了第7节的工作得出的结论和未来的工作。2. 相关工作调度主要有四类，如列表调度、聚类调度、基于搜索的调度和基于复制的调度。在网格、集群等分布式计算领域中，已有许多关于工作流调度的研究工作。一些作品考虑了云环境中的相同问题（Yu等人，2005; Sakellariou等人，2007;Abrishami等人，2012年）。然而，在QoS约束下已经给出了与成本感知工作流调度相关的挑战的详细回顾（Smanchat 和Viriyapant，2015; Alkhanak 等人， 2015年）。由Liu提出的这些变体的目标是分别在严格的截止日期和固定的预算下优化执行成本和执行时间。该算法只考虑执行时间、计算代价和数据传输时间。不考虑VM采集延迟。Lee等人提出了另一种算法然而，该算法没有考虑VM获取延迟和工作流的任务依赖性比滕库尔等al. 提出了在云中存在各种静态和动态算法（Malawski等人，2015年）。他们的目标是优化的执行工作流的数量，同时试图满足其他QoS，如预算和截止日期。他们考虑了不同的延迟，如从IaaS云租赁VM时发生的VM获取和终止此外，它们还解决了VM性能变化的问题然而，他们只承认单一类型的VM，忽略了IaaS云的异构性。A al. 按需将工作流调度到Amazon EC2的spot实例上（Ostermann和Prodan，2012）。该算法在调度任务时综合考虑了spot实例的然而，它忽略了数据的传输时间，但考虑了VM延迟。Mao et.等人提出了一种用于云中工作流调度的动态策略（Mao和Humphrey，2011）。它们提供最便宜的时间表，在指定的截止日期之前完成工作流的执行。他们考虑不同价格、获取延迟和性能差异的各种类型的虚拟机然而，它们忽略了任务之间的数据传输时间，这对数据密集型工作流有重大影响。Abrishami et.al. 提出了IaaS云部分关键路径（IC-PCP）和具有最后期限分布的IaaS云部分关键路径（ICPPD 2）算法（Abrishami等人，2013年）。ICPCP将所有任务安排在668R.A. Haidri等人/沙特国王大学学报2×FG1/4fg;z到最便宜的VM实例的部分关键路径，该VM实例可以在工作流截止日期之前执行它们IC-PCPD 2算法计算所有工作流任务的子截止日期但是，它没有考虑必须在云环境中处理的VM实例获取延迟Poola等人提出了一种鲁棒的并行算法来处理云环境中的故障和性能变化，该算法优化了执行时间和成本（Poola等人， 2014年）。Byun等人提出的分区平衡时间调度（PBTS）算法 试图在每个时间间隔找到所需计算资源的最小量，以便在用户指定的完成时间内完成工作流的执行（Byun等人，2011年）。但是，它们忽略了计算资源的异构性，只考虑一种类型的VM。有一些元启发式的工作流调度方法。元启发式算法，如遗传算法（GA），粒子群优化（PSO）的工作流调度在云中也存在于文献中。Verma et.等人提出了一种遗传算法，该算法试图基于工作流的优先级在云上调度工作流，以便在满足工作流的最后期限的同时最小化执行成本（Verma和Kaushal，2014）。然而，该算法忽略了VM获取延迟。Chen提出了另一种基于遗传算法的调度算法。它试图优化执行成本和执行时间（Chen和Zhang，2009）。在没有找到可行解的情况下，它试图最小化总时间而不是总费用。Higashino等人提出的基于粒子群优化的启发式算法，尝试在网格上调度作业。它只试图最小化制作跨度（Higashino等人，2016年）。潘迪等等人介绍了另一种基于PSO的算法，其中他们试图平衡云中资源上的负载以及最小化工作流的总执行成本（Pandey等人，2010年）。提出了另一种基于PSO的算法，该算法试图在满足工作流截止日期的同时最小化工作流执行成本（Rodriguez和Buyya，2014）。用于数据密集型应用的多目标方法由Szabo开发（Szabo等人，2014年）。他们试图最小化任务之间的数据传输时间。此外，在Zhu等人的工作中，作者关注云的重要特征但没有考虑诸如VM的获取延迟和性能变化的问题（Zhu等人，2016年）。Xilong提出了一种节能的VM调度器，它试图占用额外的CPU份额（Xilong和Peng，2015）。它们采用共享回收策略，优先调度短期I/O密集型任务，避免I/O操作带来的性能下降。另外，网格和集群环境下的工作流调度研究主要集中在工作流的调度阶段，尽量减少工作流的执行时间。这是因为网格和集群提供了唯一的静态计算资源池。然而，除了执行时间之外，经济成本是云中的另一个参数。这意味着交付时间有效的解决方案将需要探索各种成本/时间的调度策略的替代品。如前所述，工作流调度方法在文献中已经建立的优化执行时间和经济成本排除了云的一个或多个主要属性，例如VM的异质性、获取延迟、性能变化、应用任务之间的依赖性约束、截止线和任务间通信要求，这导致了研究和开发新方法的进一步范围（Malawski等人，2015; Mao和Humphrey，2011; Poola等人，2014; Lee和Zomaya，2010）。所提出的工作是一个认真的尝试，开发一个具有成本效益的截止日期意识（CEDA）调度模型，以产生一个具有成本效益的时间表在可接受的水平处理工作流，同时满足用户考 虑 到 几 乎 所 有 上 述 特 性 ， 指 定 的 截 止 日 期 。 此外， IC-PCP（Abrishami等人， 2013）找到部分关键路径（PCP），从而将PCP中的所有任务调度到虚拟机的最便宜的可应用实例，该实例可以在工作流的截止期限内找到它们。在工作流中的剩余PCP上重复相同的过程，直到所有任务都被调度。IC-PCPD 2算法计算所有工作流任务的子截止时间，而不是找到部分关键路径，并将每个任务分配给最便宜的VM实例。而在所提出的工作中，CEDA选择具有最高向上排名的任务，并考虑虚拟机（VM）的获取延迟，将所选择的任务逐个调度到最便宜的VM实例。这使得调度程序能够正确估计任务的最早开始和完成时间，从而保证工作流的最后期限。CEDA还利用已租用的VM实例的剩余时间，通过根据向上的排名逐个分配任务，不产生额外的成本。由于PCP中的所有任务都分配给同一个VM实例，因此数据传输成本为零，但CEDA会尝试占用已租用的VM实例的未充分利用的时间间隔，而不会创建新的VM实例，直到我们没有未充分利用的时间间隔。因此，在传输成本和未充分利用的时间间隔的利用之间存在折衷。由于所提出的策略中所采用的策略，在满足工作流截止日期的同时，预计执行的总价格将始终优于ICPCP和ICPCPD 2。3. 调度系统模型在本节中，CEDA已经被提出，并简要描述了应用模型，云资源模型和云中工作流执行的问题定义如下。3.1. 应用模型一个工作流应用程序是由一个有向无环图G（T，E），其中T是一组任务t1，t2，. 可以在任何可用的虚拟机上执行。E T T是任务之间的有向弧或边的集合，以表示依赖性。每个依赖关系表示优先约束，该优先约束指示任务tj只能在任务ti已经完成之后才能开始其执行。t i的所有直接前趋者的集合f t j2 T：e j; i2 E g被称为前趋ig，t i的所有直接后继者的集合f t j2 T：e i;j2 E g被称为后继ig。没有任何前置任务的任务称为入口任务，即前置任务，没有任何后继任务的任务称为出口任务即成功。两个虚拟任务tentry和texit被添加到工作流的开始和结束。这些虚拟任务称为伪入口任务和伪出口任务。这些任务连接到实际的入口和出口任务，执行时间和通信时间为零。任务的大小和分配的权重到边缘ei; j为计算是所代表尺寸分别为i; j和i;j。存在用户指定的截止日期(D)对于每个科学工作流程（W）。截止日期定义为执行工作流所需的时间限制。3.2. 云资源模型IaaS提供商从虚拟机 集 合 中提供虚拟机（VM）实例VM 1; VM2;. ;VMm虚拟机到客户端。每个VM具有不同的配置，如内存大小、CPU类型和单位时间成本。虚拟机的配置决定其成本，即与较慢的虚拟机相比，较快的虚拟机成本更高。类型为'z'的VMth表示为VMz，vkz表示kVM的实例。PCRVMz和CostRVMz表示处理能力，R.A. Haidri等人/沙特国王大学学报669ð Þ我中国（假设计算之间的平均带宽为公司简介tp2pred vip我Pið5Þ浮点运算每秒（FLOPS）和VM z的价格。VM z上的任务t i的预期完成时间ECTti; VM z通过使用等式（1）计算。（一）.尺寸范围我这不会导致启动新VM实例所需的额外价格开销和VM获取时间。表1给出了工作中使用的符号XST时间ti：它是任务ti可以开始执行ECT_0 ti;VMjð1Þ因为所有的前任都已经被安排好了。它是在PC VMj然而，如果任务t和任务t在不同的当量（五）、ij8>0;如果ti2t条目对于VM类型，例如VM z和VM v，数据传输时间为TTT ei; j。是>最大值XSTtMETtTTe- --资源几乎等于所有存储和计算资源服务提供商提供的服务被认为是在同一物理环境中，像亚马逊地区。在这个假设下，TTei;j是计算的。如果Ti未被分配G：EST ti; vk; z;如果ti被分配给vk; z由Eq。 （二）、 当ti和tj都被分配给同一个在VM的实例中，TTei; ji变为零。其中，METti是ti的所有执行时间中VM集中可用的VM类型。它被计算为TtteeIjw eIjBð2ÞMETtiMINVMz2VMsetfECTti;VMz6XFT t it it：ti的预期完成时间在等式中给出。（七）、此外，假设服务提供商提供存储，年龄和计算服务，如弹性块存储（EBS）和亚马逊弹性计算云（EC2）（Juve）XFT tXST tiMETti;如果ti未赋值EFT= ti; vkz;如果ti被分配给vkzð7Þ的情况。例如， 2009年）。EC2用于运行工作流的任务，EBS可以连接到计算服务，提供suf-为输入/输出文件提供足够的空间据推测，任何一个...可以从VM集启动虚拟机实例，即没有限制租用VM实例的数量。还有，云计算遵循按使用付费模型，这意味着即使用户只使用了一小部分时间，也要对整个持续时间进行收费。因此，在所提出的模型中，每个租用的VM实例按分钟时间间隔收费。此外，所提出的模型忽略了虚拟机之间的数据传输成本，因为大多数真实云（如Amazon）中的数据传输成本是免费的此外，服务提供商申请使用此模型中不考虑存储服务，因为它们CriticalParent关键父项ti：任务ti的关键父项是ti，其具有在ti的最新数据到达时间。它在Eq中给出。（八）、关键部件的尺寸和尺寸MTW：工作流的最小执行时间在等式中给出（9）如下MTW¼MAXti2CPfXFTtig9r utk：任务按其向上排名值排序。它是从任务t k到t出口的关键路径的长度。它的递归定义如下影响调度算法。如果ti2t退出，ð10Þ如果iBUSINMAXtsucctfruBUSINTTT eisBUSING，则为，3.2.1. 问题定义在这项工作中的问题是映射的任务集T的工作-流到从VM集s2其中，wi是ti的平均计算时间，其由等式1给出（十一）、>u iÞ ¼670R.A. Haidri等人/沙特国王大学学报S2.以这种方式，执行总价（TPE）和总支出-Xm EC T细胞R.A. Haidri等人/沙特国王大学学报671工作流的操作时间（TET）最小化，同时满足最后期限和保留工作中672R.A. Haidri等人/沙特国王大学学报的优先约束-关于我们z1/z2MR.A. Haidri等人/沙特国王大学学报673ð11Þ674R.A. Haidri等人/沙特国王大学学报流 此外，假设用户指定的最后期限是可实现，因为所生成的调度受截止日期的限制R.A. Haidri等人/沙特国王大学学报675将工作流任务与上述任务映射的问题上述目标显示在Eqs中。（3）和（4）。676R.A. Haidri等人/沙特国王大学学报jVMXPoolj，ATkz-STkz，LFT ti：任务ti的最迟完成时间是ti可以R.A. Haidri等人/沙特国王大学学报677完成其计算，使所有工作流任务在工作流的截止日期之前执行。它是由678R.A. Haidri等人/沙特国王大学学报当量（12）如下LFT不退出（D;如果ti2 t退出R.A. Haidri等人/沙特国王大学学报679最小化TPE¼k¼ 1的情况。李680R.A. Haidri等人/沙特国王大学学报2个虚拟机池的成本为100VMz100V Mzð3ÞR.A. Haidri等人/沙特国王大学学报681iMIN测试如 果LFTts-METts-Tes ，则执行此操作;否则，ð12Þ682R.A. Haidri等人/沙特国王大学学报符合TET6 D;其中TET¼MAXti2WTET ¼MAX ti2W TET其中，ATk; z; STk; z是可用时间，VM池中vkz的开始时间，LI是租用间隔。4. 工作流调度算法该算法为工作流中的任务生成最便宜的调度，使得工作流在最短时间内被执行。指定的截止日期。此外，CEDA更喜欢选择现有的-STk; z：它是可以计算的VM实例vk; z由等式（十三）、STk; z¼ASTQti= AQD; if vk; zR VM Pool^ ti是分配给vk; z的第一个ATk; z：这是VM实例vk; z可用于exe的时间R.A. Haidri等人/沙特国王大学学报683cution。它在Eq中给出。（十四）、其中ti是分配给vk; z的最近任务RTk; z：它是VM实例vk; z的剩余时间，可以是计算如下RTkz¼，ATi;z-STi;z，×LI-ΔTiz-STizΔ15Ωing其计费周期的剩余时间足够的VM实例;LI;在最后完成时间之前执行任务684R.A. Haidri等人/沙特国王大学学报李（1个字母iið Þ我我表1使用Notations。象征意义T一组任务n T中的任务数ti工作流中的第i个大小ti任务ti中的指令数D工作流程ET中任务间通信的有向边集eij从任务ti到tjw eij从任务ti到tj的从VM z上执行的任务ti到VMv上执行的任务tj的b平均带宽VM集：VM 1;VM 2;：.. . ; VM n g由云服务提供商提供的所有类型的VM 的集合m VM集合中的VM类型数量VMzVMoftypezvk; z类型的VM的第k个实例计算类型z的第k个实例的容量，以FLOPS成本VMzVMz的货币成本succ ti任务ti的一组直接后继者predpredict i任务ti的测试输入伪输入任务texit伪退出任务CP关键路径AQD VM采集延迟LI租赁间隔ruUpperrankSTk; z vk; z的开始时间ATk; z vk; z的可用时间RTk; z vk; z的剩余时间ftig分配给vkz的任务集VM池6-VMzfvk; z; VMz; STk; z; ATk; z; RTk; z;f tigg实例的元组ECTti; VMz VMz上任务titi的平均处理时间MET ti任务的最小执行时间tiXST ti任务 ti的预期开始时间任务ti的预期完成时间EST ti; VMz任务ti在VMzEFT ti; VM z VMz上任务tiAST ti任务的实际开始时间ti任务ti的实际完成时间t iMTW工作流的最小执行时间TET工作流的总执行时间TPE工作流程执行总价EST_ti;v_k; z_i：它是任务ti可以在VM实例v_k; z上开始其执行的最早开始时间。它在Eq中给出（十六）、G，并计算MTW和LFT（步骤4-5）。在此基础上，计算出保证精度的向上秩EST t v（MAX½MAXtp2predvifXFTt pttpepg;AQD];ifvk;zRVMPoolG的dence约束，并将每个任务放入任务列表（步骤i;k; zMAX½MAXtpredvfXFTtpTTepi g;ATkz];否则6-7）。CEDA进入while循环（步骤7），并保持在此循环p 2阿吉什;ð16Þ直到任务列表中的所有任务都被设置为已分配（步骤8）。现在，CEDA从任务列表中挑选第一个任务（t），如果t不是我我EFT ti;vk; zt：它是任务ti可以完成其任务的最早完成时间。在VM实例vk; z上执行。它在Eq中给出（17）.EFTULTi;vk; zESTULTi; vk; zESTULTi; VM zESTULT i ; vk ; zESTULTi ;VMzESTULT iPricequiti;vk; z：在VM上执行任务ti伪任务，如果vk; z不在VM池中，则它启动vk; z并将其添加到VM池（步骤16之后，CEDA将ti赋值给vk; z，将ti设置为赋值，updates VM Pool;XST虚拟机池;XFT虚拟机池; AST虚拟机池;AFT虚拟机池; STkz; ATkz;RTkz实例vk; z.其定义如下;;;Pricequiti;vk; z;如果EFTt>LFT tlEFTti;vk;z-ESTti;vk;zm×CostVMzð18Þ并从任务列表中移除ti（步骤19-23）。在分配了所有任务之后，CEDA计算TET和TPE（步骤25）。AST_t_i_t：它是任务t_i的实际开始时间，其在等式中给出（十九）ASTANTTANTAFT ti：它是任务ti的实际完成时间，在等式中给出。（20）.AFTUti XFTUti 204.1. 算法（CEDA）算法1给出了CEDA的伪码。经过一些初始化（步骤14.1.1. 关键路径算法2显示了findcriticalPath过程的伪代码dure. 该算法接收G，n，e，XFT作为输入并返回G.首先，它将CP赋值为null，将texit赋值为ti。之后，它进入while循环，使用等式找到ti的关键父tp。（8），将tp添加到CP并将t tp添加到ti（步骤3-6）。此过程将重复进行，直到ti变为texit。4.1.2. Cheetron VM算法算法3显示了findCheapestInstanceprocedure.该算法接收任务ti作为输入并调度R.A. Haidri等人/沙特国王大学学报685ð Þ ð Þ ð Þ ð Þ2ðÞ将其分配给最便宜的VM实例vk; z，其中vk; z可以是新实例或现有实例。首先，它检查VM池（步骤2）。如果虚拟机池是算法2：findCriticalPath（G）空，则算法3计算ESTkti;vk; xk;在属于VM集的所有VM上执行EFT策略i; vk; x和PriceValue策略i; vk;x（步骤3-7）。之后，它找到具有最小价格的VM实例vk; index并返回vk; index（步骤8）。让我们考虑一种情况，具有相同价格值的VM实例的集合。在这种情况下，算法选择具有最低EFT的VM实例。如果虚拟机池是不空的，然后算法3计算每个现有实例的ESTti; v k; z;EFTti; v k; z和Priceti; v k; z输入：G，n，e，XFT输出量：CP1. CP¼/; ti¼ t出口2. 而我！1/4吨出口管开始以及类型VMz的新实例（步骤12-17）。在此之后，算法3找到具有最小EFT的VM实例v索引;z（步骤18）。如果v index; z是一个现有的实例，并且v index ; z的剩余时间足够大以容纳t i，则它返回v index;z（步骤20-25）。否则，算法3计算ESTATENTi; v k;p;EFTATENTi; v k; p和PriceATENTi; v k; p 为一新例如的键入VMpR VM Pool（步骤27在该计算之后，算法3选择并返回具有最小价格的VM实例vkiindex（步骤33-35）。算法1.输入：DAG（V，E）由n个任务“m”VM类型的1 × m阶成本矩阵n × m阶ECT矩阵n × nVM采集延迟AQD，租用时间间隔LI输出量：TET、TPE开始1. add tentry; texit和它们对应的依赖关系到G2. 使用公式计算G中每个任务的XST，MET，XFT（5）─（7）分别3. 将T入口，t出口设置为指定4. CP = findCriticalPath（G）5. 使用等式计算MTW。（9）和LFT为每个任务使用方程。（十二）6. 使用等式计算向上秩ru。（10）对于所有任务，通过从t出口7. 按ru的降序对Task_List中的任务进行8. 当Task_List中存在未计划的任务时，9.从Task_List中选择第一个任务ti10.如果没有入口和出口，11.将AST ti、AFT ti设置为零12.从Task_List中删除任务ti13.返回第714.End If15.vk; index<$findCheapestInstanceList16.如果k =k;索引RVM池17.从云中启动VMindex类型的新实例vk; index，VMPool¼VM Pool[vk; index18.End If19.更新VM池（_P）20.将任务ti分配给机器vk; index，将任务ti设置为已分配21.通过使用等式更新XST t i; XFT t i; AST t i和AFT t i。分别为5、7、19、2022.使用等式更新STk; index; ATk; index; RTk; index。（十三至十五）23.从“任务列表”列表中删除任务ti24. End While25. 使用公式计算TET和TPE。（3和4）端3.使用等式计算ti的临界母体 tp（八）4.CP¼ CP[tp5.ti¼ tp6. End While端算法3. findChepestInstance（t）输入：任务输出量：指数开始1. VM型¼/2. 如果虚拟机池容量超过1/23.对于每台机器VMx VM集，执行4.计算近似的最早开始时间ESTti;vk; x，使用等式（十六）5.计算近似的最早完成时间EFT_ti;vk; x_t，公式如下：（十七）6.使用等式1计算VMx上的任务ti的Pricequartiti; vk; x（十八）7.端8.半val;index]←MIN价格9.typeVM← vk; index10.返回值类型VMH11. 其他12.对于每台计算机VMz2 VM池，13.对于q1/ 4到jVMzj 114.计算近似的最早开始时间ESTti;vq; z，公式如下：（十六）15.计算近似的最早完成时间EFT ti;vq; z，公式如下：（十七）16.使用等式1计算VMx上的任务ti的Priceprice ti; vq; z（十八）17.端18.½val;index]←MINEFT19.临时价格i;VMz价格i; v索引;z价格20.如果索引！四季21.If½fEST ti; vindex; zt/ ATindex; zg&&[EFT索引i;v索引;z-ESTFT索引i; v索引;z- RT索引;zg]22.typeVM ←vindex; z23.返回类型VM24.End If25.End If26.端27.对于每台计算机VMp2 VM集和VMpR VM池（接下页）