基于TOPSIS的云环境下高效并发工作流调度算法的研究及性能比较

沙特国王大学学报基于TOPSIS的云环境下高效并发工作流调度算法K. 卡良查克拉瓦蒂湖Shyamalaa，V.Vaidehiba计算机科学与工程学院，VIT Chennai，印度b印度泰米尔纳德邦特蕾莎修女女子阿提奇莱因福奥文章历史记录：2019年12月11日收到2020年2月21日修订2020年2月26日接受在线预订2020年保留字：TOPSIS服务质量截止日期调度并发工作流A B S T R A C T调度是一种决策机制，它通过确定活动在可用资源集上的执行顺序来实现多个活动之间的资源共享。在分布式系统中，调度在不同时间提交的多个工作流是一个巨大的挑战。特别是，具有时间约束的并发工作流调度使得问题在云中变得更加复杂，这是由于云的动态性，例如弹性、非同质资源类型、各种定价方案和虚拟化。为了提高最终用户的满意度和系统性能，需要一个管理良好的截止期工作流调度。同时，云计算中固有的不确定性增加了调度问题的难度。因此，如何在提高系统性能的同时，优化多个调度准则是一个很大的挑战。针对上述问题，提出了一种基于多准则决策（MCDM）方法的异构分布式环境下并发工作流调度方法，提出了逼近理想解的排序法（TOPSIS）.使用执行时间、成本和通信时间的加权和根据工作流任务需求，在现有资源中找出最优资源。该方法最小化了工作流的最大完工时间和执行代价，提高了不确定环境下的资源效率。与基于最后期限约束和资源利用率的最早完成时间-最大有效约简（EFT-MER）算法、基于云的工作流调度算法（CWSA）和异构最早完成时间（HEFT）算法进行了性能比较。我们的实验结果表明，建议的T-CCWSA优于当前国家的最先进的算法与标准实现最后期限约束，最小化执行成本和资源效率。©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍复杂的科学应用，如生物信息学、地球科学、天文学和灾害建模，可 以 自 然 地 以 工 作 流 的 形 式 表 示 （ Arabnejad 等 人 ， 2019 年 ;Partheeban和Kavitha，2018年）。工作流表示的好处之一是工作流可以是可重用的、可再现的，甚至可以通过其他工作流进行跟踪（Guo等人，2018; Iyenghar和Pulvermueller，2018）。与此同时，*通讯作者。电子邮件地址：kalyan. gmail.com（K.K. Chakravarthi）。沙特国王大学负责同行审查如果工作流执行的完成时间超过某个指定时间，可能发生的灾难将变得无用。这些基于工作流的应用程序对于在实时工作流任务中处理大量 数 据 以 及 期 望 的 计 算 资 源 的 成 本 降 低 是 高 度 要 求 和 挑 战 的（Ghafouri等人， 2018年）。工作流调度是将工作流任务映射到计算资源的过程。工作流任务之间的关系是多重的，相互依赖的，由于复杂的操作。因此，父子关系和数据/控制依赖关系之间的相互关系由有向无环图（DAG）表示。每个工作流任务具有与其他工作流相关联的各种执行时间、优先级和时间限制（Emmanuel等人，2018年; Zhou等人，2018年）。高效的工作流调度对于实现用户服务质量（QoS）要求是必不可少的，例如，最小化执行时间，同时最大化系统性能，例如，资源的使用https://doi.org/10.1016/j.jksuci.2020.02.0061319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com2360K.K. Chakravarthi等人/沙特国王大学学报此外，为了达到良好的效率，不同的工作流应用程序需要不同的调度策略在分布式系统。大多数文献研究了同构计算系统，而一些研究集中在异构系统，每个不同的QoS约束。现有的方法倾向于面向过程和/或面向数据而不是面向资源，并且它们缺乏有效的任务到资源映射策略（Aziz等人， 2015年）。此外，在传统调度中，像任务通信时间和计算时间这样的参数被认为是确定性的（Khorsand等人，2016;Wang等人，2018年; Zhou等人，2018; Su等人，2015年）。事实上，在现实世界中，调度问题中涉及的各种因素在本质上往往是不精确或不确定的（Zavadskas和Podvezko，2016; Pan和Deng，2018; Jiang和Hu，2018;Sun和Deng，2019）。特别是，在调度问题中到目前为止，研究人员已经对建模和处理不确定信息的问题引起了相当大的关注（Yager，2018; He和Jiang，2018; Kang等人，2019年; Yang等人，2018; Deng，2018; Zavadskas例如， 2017年）。随着具有不同配置的云资源的大量扩散，选择最佳资源来满足和实现业务策略并满足用户的QoS要求是具有挑战性的，目标通常相互矛盾（ Cusumano ， 2010; Assunção 等 人 ， 2010; Jatoth 等 人 ， 2017;Martino 等 人， 2016; Hajji和 Mezni，2017; Capuano 等 人， 2018;Capuano等人，2017; Carrasco等人，2015年）。应考虑多种不相容的定性和定量标准，寻找最合适的资源。如何在满足用户不同QoS需求的同时优化工作流调度具有重要意义。因此，云资源的选择可以被认为是MCDM问题（Abdel-Basset例如，2018年）。MCDM的目标是在存在多个不利决策标准的情况下，从其他备选方案中确定最佳备选方案。在调度问题中，MCDM最近，MCDM方法为几个现实世界的问题提供了解决方案。MCDM是一个运筹学的子学科，它明确地从潜在的备选方案中识别出最佳备选方案（Chen等人，2008; Yue，2011）通过分析几个可能是具体或模糊的属性或标准。从过去的几十年来，MCDM技术已经建立在主观偏好顺序中，以识别、分类和选择替代方案（Behzadian等人， 2012年）。MCDM已广泛用于许多领域（Abdel-Basset等人，2018年;Abdel-Basset等人，2019），在各种MCDM研究中，TOPSIS（TOPSIS）方法（Hwang和Yoon，1981）已成功应用于不同领域（Shidpour等人，2013;Chang等人，2018年）。最初，TOPSIS是由Hwang和Yoon（Hwang和Yoon，1981）开发的，以找到最佳方案，确定为与正理想解（PIS）距离最短，与负理想解（NIS）距离最长的方案（Olson，2004; Kao，2010; Wang和Luo，2010; Lotfi等人，2013; Sarraf等人， 2013年）。TOPSIS方法比其他MCDM模型更此外，TOPSIS中的准则和备选方案的数量不受限制。TOPSIS方法对现实世界的决策问题有很大的影响，并且适用于各种应用（Mir urcu，2012; Mir等人，2016年）。尽管如此，云计算研究人员对MCDM的使用关注较少。我们的建议使用TOPSIS解决这些问题的资源选择过程中，并优化工作流调度在云中。本文件提出了一种基于QoS参数的云资源排序多准则决策模型。提出了一种新的动态工作流调度算法T-CCWSA。用T-CCWSA实现了TOPSIS算法，以获得最优的解决方案来执行工作流调度。其余的工作安排如下。第2节提供了一个精确的研究文献工作流调度和突出的主要工作和建议。第3节给出了问题形成的概述。第4节讨论了TOPSIS的一般化机制，第5节将详细描述工作流调度问题的建议解决方案。第六部分给出了对所达到结果的评估报告及其比较图表。在本文的最后，在第7节中，工作流调度的未来工作的可能范围提出了建议。2. 相关工作近年来，异构分布式环境下的工作流调度问题受到了广泛的关注，各种研究提出了许多工作流调度方法，以获得接近最优的解决方案。工作流调度可以分为单工作流调度和多工作流调度。单工作流调度方法可以粗略地分为QoS约束调度和尽力而为调度（Yu等人，2008年）。最佳努力调度（Arabnejad和Barbosa，2014; Daoud和Kharma，2008; Zhou等人，2016）旨在最小化调度长度，同时忽略各种用户的QoS约束。QoS约束调度（Abrishami等人，2012;Arabnejad和Barbosa，2014; Azad和Navimipour，2017; Wu等人，2016;Zheng和Sakellariou，2013）试图在QoS约束下提高调度性能，例如在预算约束下最小化时间或在截止期限约束下最小化成本。多工作流调度可以分为离线调度和在线调度。离线调度不处理在生成调度后到达的工作流。在文献中，已经提出了许多离线调度算法。Zhao和Sakellariou（Zhao and Sakellariou，2006）提出了两种基于公平的策略：完成时间公平策略和当前时间公平策略。在这两种策略中，公平性都是基于“减速”原则，它是单独调度一个工作流时的期望执行时间与所有工作流一起调度时的期望执行时间之比.这两个策略之间的区别在于，当前时间公平策略确定所有工作流的减速值，而完成时间公平策略仅估计选定工作流的减速值。然而，这两种算法只涉及离线调度时，所有的工作流是事先已知的。Xu et al.（2017）提出了一种扩展槽回填（ESB）算法，用于在截止日期约束下进行多工作流调度。该算法的目标是最小化空闲时隙的数量和最大化资源利用率。它使用基于优先级顺序的顺序策略来调度所有工作流。对于每个工作流，基于资源利用或相对紧急程度计算优先级。反过来，每个新任务都会尝试回填最早的时间槽。如果最早的时隙不足以回填，则将其延长。总体而言，ESB算法更好地利用小时隙，不能满足新的任务回填的要求相比，现有的方法。在线计划允许用户随时提交工作流。提出了几种在线工作流调度算法。完成时间公平算法已被田等人修改。（2012）在Zhao和Sakellariou（2006）中描述，并提出了一个●●●K.K. Chakravarthi等人/沙特国王大学学报2361JJJ. Σ瓦尔瓦尔KK.Σj;kKK我我JJk;j我KJJJ工作流程><一nJJK一一12.ΣN.Σ>。 --jj;kp jj我不知道no动态E-公平调度算法对于每个新到达的工作流，E-公平算法使用减速值并决定下一个应该调度哪个工作流。禹和史（2008）提出了RANK HYBD算法，该算法解决了工作-顶点ti表示工作流wi中的第j个任务。此外，E i<$T i×T i表示任务之间的有向边。如果存在一个优先条件，则存在形式为ti;ti的边ei2E不同用户在不同时间提交的流。 该算法在任务t， 和t i，其中t i 这是一个直接的预测，k j k调度最低级别的工作流，以最大限度地减少工作流等待-任务Ti的后继者，并且任务Ti是任务Ti的直接后继者。时间。但这种做法并没有达到很高的公平性。为了j j k前D。ti表示由所有ti的立即数组成的任务集对于先前到达的工作流中的未调度任务，将不调度先前工作流中的剩余任务在Arabnejad和Barbosa（2012）中提出的公平动态工作流调度（FDWS）算法解决了RANK HYBD（Yu和Shi，2008）中发生的不公平性以及在线工作流管理（OWM）中发生的任务选择的延迟（Hsu等人，2011年）的报告。OWM和RANK HYBD算法被提出来最小化所有工作流的平均完成时间。另一方面，FDWS算法旨在减少每个工作流的等待和执行时间。FDWS算法在平均最大完工时间、成功率（%）和调度长度比（SLR）方面优于RANK HYBD和OWM算法。Arabnejad等人（2014年）调查了并发工作流的离线和在线查询，并提出了max-min和min-min的修改版本（Maheswaran等人，1999）算法。作者将FDWS算法与OWM、RANK HYBD、修改的max-min和min-min算法进行了比较，发现FDWS算法的性能优于OWM算法，FDWS表现最好。上述在线调度算法前辈们，成功的我 表示任务集，包括所有Ti 对于某个工作流w i2W，约束质量可以建模为QoS i 1/4coni;coni，其中coni和coni表示用户指定的约束，例如截止日期或预算以及用户指定的截止日期或预算的约束值云平台提供无限数量的虚拟机，各种配置（Zhu等人，2016年; Calheiros和Buyya，2014年）。设VT1/4 fvt1;vt2;vt3. 表示云中可用的m种类型的虚拟机。参数rvmvtu 代表类型为vtu的第k个VM。虚拟机的价格表示为pricevmvtu是单位时间间隔的成本。它不值得-从而可以在任何时间点获取和终止虚拟机。此外，虚拟机按单位时间间隔收费，任何部分使用单位时间都将收费在整个时期。在多工作流调度中，符号ET是表示所述任务在VM上的执行时间tivmvtu。另外，这些符号JK仅解决工作流之间资源共享的公平性最小化完工时间但在现收现付模式下，ij;k而EFTi表示最早开始时间和最早结束时间任务ti在VMvmvtu上的时间。任务ti使用资源和服务，只为他们使用的东西付费因此，jkj从用户的角度来看，时间和成本是最重要的两个因素可以在VMvmvtu上开始执行 被称为最早的开始tant因素Arabnejad和Barbosa概述的在线战略时间和计算如下。（2014）承认成本和时间，但旨在尽量减少每8>ESTi¼Ti;ifpre d.tti空我我我ð1Þ阿拉伯内贾德和Barbosa（2015）和阿拉伯内贾德和巴博萨（2017）提出了多工作流截止日期-预算调度jmaxESTpMETpMTTp j>：ti2predtt;否则（MWDBS）算法的最后期限和预算约束下的并发工作流。MWDBS算法具有更高的精度-p其中MTT是J表示最小数据通信时间，cess速率比其他算法，特别是对于高度并发的情况下，即那些具有较低的到达间隔。然而，这种方法在不一致的模型下确实有缺点，因为它基于向上的排名来选择每个任务（Topcuoglu等人，2002年）（排名u）优先级，不考虑执行成本。因此，在用户的最后期限和预算限制之间没有实现可接受的折衷与目前的调度策略相比，在完整的调度-前趋任务ti到当前任务ti和METi表示任务ti在VMvmvtu上的最小执行时间 在云中的所有VM类型中具有最小执行时间的2个VT，并计算为见面之后我就minETi2vmvtusVT规则是在工作流到达时产生的，所提出的方法在工作流到达时为每个工作流任务连续地产生新的调度。显然，预计完成时间，EFTi可以被计算为改变其实际执行时间以减轻云不确定性对调度性能的影响这项工作也吸引了ij;k ¼ESTj;k METj;kð3Þ注意一种基于MCDS的TOPSIS方法工作流任务映射采用TOPSIS算法，该算法综合考虑多个实质性因素，将。TOPSIS算法的参与支持多个优化调度性能的目标函数在任意的工作流调度中，任务ti的最迟完成时间LFTi是任务完成其计算之前的时间，使得工作流wi的完成时间小于用户指定的截止日期 它被定义为>8di;如果为100 c。tt i空3. 问题公式化LFT i <$：ti2succtiPJW¼ fw1;w2;w3. . ;wng.工作流wi2W可以建模为ð4Þ关于我们G i;QoS i;T i，其中G i;QoS i，和T i表示工作流结构、服务质量约束和到达时间。 工作流w i的工作由于工作流中的优先级约束，任务不能执行，直到它收集了所有的数据，从它的直接前代，我们有以下的约束。被描述为有向非循环图（DAG）Gi1/2Ti;Ei1/2，其中i我我我我是。ti;ti;. . . 是顶点的集合，并且N表示计数FTp;k PURPOSEDTp;j 6STj;k8ep;j2Ei5ESTj;kp;jj;kEFTJ例如，如果后续工作流中的任务等级小于O2362K.K. Chakravarthi等人/沙特国王大学学报K（）ET最小化TEC价格· pK如果你是一个人，½] ←ωti2019年j;kKK我¼J我其中，FTi表示任务ti在VM v m v t u上的完成时间 DTi表1p;k pkp;j决策矩阵。表示任务ti和ti之间的数据传输时间。工作流P J调度环境中，工作流wi的完成时间FTi是最大的，ET DT C将其所有任务的完成时间定义为FTi¼maxnFTio6成本C用于在VMvmvtu上执行任务t i 被计算为ij;kj;k四分之一价格vmvtuωJK我j;kNtð7Þv ij¼ wjω Dij 其中i={1，2，3，.. . 、p}，j={1，2，3，.. . ，q}和wj价格E。vmvtu是虚拟机的成本vmvtu 每隔表示第j个目标的权重值。þt是时间间隔的单位。为了保证工作流的截止期，wi中的所有工作流任务必须在截止期di之前完成执行。因此，这带来了另一个限制FTi6di;8wi2W8在（5）和（8）中受到上述约束的情况下，优化的主要目标是最小化完成工作流集合W的总执行成本（TEC），其可以被计算为VMjuKk¼1其中，jVMj表示获取的VM的数量，并且pk表示K具有积极影响的标准和与对解决方案具有消极影响的标准的值相关联的消极理想解决方案S-由下式给出：S=V=1;V=2;V=3;. . . ;VqgS-1/4fV-1;V-2;V-3;. . . ;V-qg在这种情况下，ET、DT和C被视为具有积极影响的标准，必须最小化步骤e计算分离测量值。每个备选方案与正理想解S-和负理想解S-的分离计算为：vuX3。ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiΣffiffi2ffiffi租用VM的时间单位数vmvtu。资源利用率也是云服务的一个重要指标副供应商评估云平台的性能Sω¼tj¼0 Vij-Vj因此，我们还将重点放在最大限度地提高虚拟机的平均资源利用率上，这可以定义为vuX3。ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiΣffiffi2ffiffiVMjVMjS0¼tj¼0Vij-V-jMaximizeXwtk=Xatk10其中Sω和S0表示到正理想的最短距离k¼1k¼1解S_∞与负理想解其中wtk和atk表示VM 工作时间和活动时间(idle时间+工作时间）。4. TOPSIS法本节介绍TOPSIS法的基本概念。TOPSIS算法在算法1中给出，步骤如下。S-分别为备选项，j表示标准的数量。步骤f计算相对于S的理想解的相对接近度（RC），并定义为，RCS0S0Sω步骤g根据偏好对RCi进行步骤a构成大小为p x q的决策矩阵（D），其中p分别表示备选方案的数量和q表示准则的数量。备选方案由虚拟机（VM）表示，并且标准由如表1所示的目标函数表示。步骤b通过与每个标准进行比较将维度属性转换为非维度属性。表1中的决策矩阵使用等式1归一化。（一）算法1：TOPSIS法输入：任务、ET、DT和C输出：排名计算资源设置标准为ET、DT和C计算决策矩阵D½ET]←SizeofTask=MipsOfVMD½DT]←FileSizeOfTask=BandwidthOfVMDMXijp2IJ1/1ð11ÞD C处理单位成本执行时间任务时间标准化决策矩阵计算加权归一化决策矩阵计算S和S-其中i={1，2，3，.. . ，p}，j={1，2，3，.. . ，q}，并且Xij表示第i备选项以及矩阵D中的第j个步骤c对于每个标准，根据标准在调度过程中的相关性给出权重值。通过将归一化D中的每个元素（Dij）与对应于每个准则的权重值相乘来生成加权归一化决策矩阵。一组福利属性，即，多越好S-←负属性的集合，即， 越少越好确定测量值与S-和S-的分离，替代计算相对接近度（RC）对虚拟机进行CX步骤d正理想解S以价值为导向，VM1ET11DT12C13VM2ET21DT22C33VM3ET31DT32C33––––––––VMpETp1DTp2Cp3K.K. Chakravarthi等人/沙特国王大学学报2363JKKJSs;k我KKJJJJ我我Sj、j、J12KJJti2predtiLJ12KJET t1≤t 2K6ETt3然后将这两个任务合并为一个新的任务t12. - 是的Σj kk工作流，任务合并算法将流水线任务合并到LJ步骤d：更新precedenting、successors、Finish time和resort5. TOPSIS启发的成本有效的并发工作流合并任务而ti之间的通信时间调度算法工作流调度是一个NP完全问题任务ti和ti为零。序列任务合并步骤如下所步骤a：对于任务ti，如果它只有一个后继者ti，并且ti只有问题，并在可接受的j k k内找到最佳时间表一个父t1然后用任务t1替换t1和t2时间不可行。 本文提出了一种T-CCWSA算法，j j k朱克它允许资源供应和调度决策满足每个工作流步骤b：设置ti朱克作为孩子的父母成本该算法通常维护一个资源池，该资源池根据准备好执行的当前任务要求进行缩放其主要目标是有效利用这些资源，作为一种成本控制机制，而不影响工作流程的最后期限。图 1描述了序列任务合并过程。先进的-顺序任务合并的阶段有两个：1.所有合并的任务都是顺序任务，不影响任务的优先级规则。2.降低了任务的货币成本，因为我们不需要传输数据集。场景1用图1中的示例来说明。在传统的调度中，当一个新的工作流到达时，任务T1只有一个前驱任务T1如图1所示，工作流任务包括立即映射到虚拟k j机械.与其他方法不同的是，所提出的方法将等待任务添加到taskPool中，并且仅将就绪任务映射到VM。T-CCWSA算法由五个阶段组成：任务合并，工作流预处理，WQ任务处理器，任务调度，任务监视器。任务测试i已调度到VMvmvtu 对于完成时间即，ST is ET is= 40 s。此外，数据通信时间假定为DTi 1/415s。根据场景1，我们合并两个任务tj和ti。它有助于避免任务之间的通信时间i和ti在不同的资源上运行时，5.1. 任务合成为了减少算法的运行时开销，工作流被预处理以合并流水线任务（图1A和1B）。1、2、把一个任务。它有助于节省数据传输时间到下一个流水线阶段，也加速了动态的生成运行时间开销。场景2：一个场景，重点是最小化多个前置任务的任务让我们假设任务t是 包含多个前驱任务，和Pred ti我不知道你在说什么;tig.让maxETsub ti，作为ti的前一个中的最大完成时间，表示为maxE Tsub b.timax. -是的E T. 我不知道。如果两个人的结束时间一个任务。直观地说，任务合并可以防止数据通信时间延迟工作流任务的启动时间。在这里我们举例说明合并任务并不超过的最大完成时间maxETsub，则可以将任务合并在一起。多个前置任务合并实现步骤概述如下.如何合并任务的前置任务以最小化任务的启动时间。步骤答：为一任务我不是d组tifti;ti;.. . ;tig.找到出来所有前任任务场景1：一个场景，专注于最小化任务让我们假设两个任务： 和ti是序列任务，ti是步骤b：按照任务完成时间的升序排列任务步骤c：选择两个完成时间最短的任务。如果ti的继承者。 由于任务t i无法开始执行直到它从任务ti接收到数据集，.iii.伊古里任务t i应满足条件ST i PST i 你好。对根据新的完成时间的任务kk;rj;sj;ss;k步骤e：重复步骤b到d，直到前驱组为空图 2描述了合并前置任务的过程。前置任务合并的优点有两个：a.它不影响后继者的执行时间b。可以降低任务的执行成本。场景2用图1中的示例说明。 二、假设任务T i具有三个前驱任务T i、T i和T i 如图2所示。它K12 3Fig. 1. 序列任务合并的过程。假设所有任务都映射到相同的VM实例类型VMvmvtu 每个任务的执行时间分别为20 m、30 m和60m图二. 前置任务合并的过程。JK不调度/供应计划。 当用户提交新J2364K.K. Chakravarthi等人/沙特国王大学学报31不J1JJJ2分别任务t i 不能启动它的执行，直到任务tifin-5.4. 任务调度器K3因为任务ti具有最长的执行时间，所以它的执行是：我然而，如果我们改变ti之间的关系而ti作为任务tj尝试以最小的代价执行任务tj如图2所示，t的总执行时间为 和我小于50米且不大于60米。因此，如果t i 和ti任务被合并，这有助于减少使用的虚拟机数量在其最后完成时间LFTi之前。首先，对所有空闲虚拟机集合，调用TOPSIS算法，得到能够完成任务在LFTi之前的具有最小成本和任务的任务ti将被分配。2j j防止ti和ti之间的数据传输时间，如果空闲虚拟机不可用，则对所有虚拟机调用TOPSIS算法。1 2在不同的资源上，也减少了运行时间开销。5.2. 工作流预处理当用户向调度程序提交新的工作流wi时，工作流预处理器合并管道任务并确定每个任务的最早开始时间ESTi和最晚完成时间LFTi在云中的VM类型以找到VM类型，使得其以最小成本满足任务的最晚完成时间。将获取一个新的VM来执行任务。算法4：任务调度J J在工作流WI中，然后将所有任务分类为就绪任务和等待任务。没有任何前 置 任 务 的 任 务 被 称 为 就 绪 任 务 并 被 添 加 到 就 绪 任 务 池（readyTaskPool），否则，任务被称为等待任务并被添加到任务池（taskPool）。工作流预处理器算法在算法2中给出。算法2：工作流预处理器5.5. 任务监测器任务监视器不断地收集任务状态信息，并且如果任何任务完成其执行，则它重新计算ESTi，后续任务的LFT i。对于每个后继者，它获取所有前后继者的任务信息，如果所有前后继任务监控算法在算法5中给出。算法5：任务监视器5.3. WQ任务处理程序WQ任务处理器将等待的任务移动到就绪任务池。将任务从taskPool移动到readyTask的策略池在算法3中呈现对于taskPool中的每个任务，其ESTi等于当前时间，当前时间和任务的前驱已经完成它们的执行，从任务中移除池并添加到readyTaskPool。在此之后，所有任务都准备就绪-按最新开始时间的升序排序算法3：WQ任务处理器6. 绩效评价本节介绍了T-CCWSA与最近发布的基于云的工作流调度算法（CWSA）（Rendy和Maier，2017）的比较，最早完成时间-最大有效减 少 （ EFT-MER ） （ Lee 等 人 ， 2015 ） 和 异 质 最 早 完 成 时 间（HEFT）（Topcuoglu等人，2002年，符合我们的目标和条件。这些算法在下面简要解释。基于云的工作流调度算法（CWSA）是为在线调度而设计的。当新的工作流到达时，计算资源按其计算速度降序排序。该算法将工作流任务插入到资源的空闲槽中，以最小化执行成本。如果12K.K. Chakravarthi等人/沙特国王大学学报2365遇遇我一不可行时，采用最小完成时间法来调度任务。最早完成时间-此外，最大有效减少（MER）通过合并具有较少工作负载的资源以填充其他资源上的空闲时隙来细化基本执行计划。HEFT算法根据每个工作流任务到出口任务的最大长度给每个工作流任务分配一个向上的排序。随后，它选择具有最高向上排名的任务，并将其分配给最短完成时间的资源。为了评估算法的性能影响，我们考虑1.总成本如等式所示。（9）2.资源利用率如等式中所示。（10）和3 .第三章。计划成功率（PSR）由等式表示（12），并在Zheng和Sakellariou（2013）以及Zheng和Sakellariou（2012）中定义。PSR提供了在给定实验中获得的有效时间表的百分比。成功满足最后期限6.2. 实验设置云服务提供商提供具有不同配置的各种类型的VM。EC2云产品的VM配置（Anwar和Deng，2018）如表2所示。假设对于每种类型的VM，以每秒浮点运算（FLOPS）为单位的处理能力可从提供商获得或可被估计（Schad等人，2010年）。根据虚拟机的处理能力，得到了工作流任务在各种类型的虚拟机中的估计执行时间。每个虚拟机的CPU性能变化是根据Schad等人（2010）提供的结果建模的。此外，根据正态分布，每个虚拟机的性能最多会降低24%。其平均值为12%，标准差为10%。类似地，同一数据中心中的数据传输时间最多增加19%（Schad等人，2010年，基于正态分布。其平均值为9.5%，标准差为5%。平均带宽是根据Amazon的Elastic Block Store设置的PSR¼100×模拟运行ð12Þ（Amazon Elastic Block Store）即，20兆每秒。 VM计费时间设置为10分钟间隔，估计采集延迟设置为1分钟，类似于Meena等人。（ 2015年）。到评价的性能度量，的截止期限因素6.1.实验工作流程T-CCWSA的性能用在不同科学领域中使用的不同工作流程来评估：LIGO、表观基因组学、Cyber-Shake和Montage。这些工作流具有不同的结构属性，例如管道、聚合、分布和重新分布，以及不同的组成，如图3所示。天文学应用程序Mon- tage将一系列图像拼接在一起，创造出个性化的天空马赛克。蒙太奇任务要求高考虑BaseDeadline。我们引入了一个类似于Abrishami等人的截止日期因子D。（2013），基于此，我们改变了工作流的截止时间。我们将d从0.3变化到1.5，步长为0.3.为此，所有工作流任务都在运行工作流W i的最快资源和最短时间上执行是得到了Wi是第i个工作流执行时间的下限。最后期限是根据公式中规定的规则确定的。（十三）、高强度I/O和低处理能力CPU。LIGO的工作-Flow的目标是探测引力波。此工作流需要Dw¼TiWiω113大内存与高CPU。表观基因组学被用于生物技术，其中，Ti是工作流到达时间，Wi是最短时间formatics自动化基因组测序操作。而且遇到这些任务需要具有有限I/O调节的高功率计算处理器。Cybershake最适合使用合成地震图模拟地震灾害这些工作流任务需要大量的内存和高CPU. 为了便于评估调度算法，Bharathi等人。（2008）开发了一套类似混凝土的各种尺寸的合成工作流程并且d是如下定义的截止期限因子。对于最后期限因子d以0.3的视差变化表2VM实例规范。科学工作流程合成工作流的特点是XML格式的DAG，可在工作流生成器中使用。为了评估所提出的算法在性能方面的结果，实验被仔细地设计并针对具有不同数量的任务的上述指定的工作流进行：小任务（约25个任务）、平均任务（约100个任务）和大任务（约1000个任务）。图三. 工作流结构在特征方面有所不同。遇到类型的VMECU内存（GiB）费用（美元/小时）m3.medium13.750.067c3.xlarge43.750.21m3.xlarge4150.266c3.2xlarge8150.42m3.2xlarge16300.5322366K.K. Chakravarthi等人/沙特国王大学学报6.3. 工作流截止日期图4显示了所提出的T-CCWSA以及现有算法- CWSA、EFT-MER和HEFT的工作流截止时间的性能影响为了评估算法在不同工作流截止日期上的性能，BaseDeadline从0逐渐增加到1.5，增量为0.3。从图4a中可以看出，当最后期限因子增加时，四种算法的成本略有下降。这是因为延长工作流的截止期限可以使工作流在截止期限内有更多的空闲时间来完成工作流的执行。因此，可以将更多的并行任务分配给同一虚拟机执行，从而使用更少的VM。此外，配置和价格较低的虚拟机还可以满足工作流的最后期限，这进一步降低了整体成本。图4a中的实验结果表明，T-CCWSA的成本平均分别比CWSA、EFT-MER和HEFT以下事实可以归因于所提出的T-CCWSA的优越性。首先，T-CCWSA算法仅在虚拟机准备就绪时才将任务调度到接下来合并流水线任务降低了任务的执行成本，因为我们不需要传输数据集。图图4 b显示，随着BaseDeadline的增加，T-CCWSA、CWSA、EFT-MER 和 HEFT 算 法 的 利 用 率 有 上 升 趋 势 。 这 是 因 为 当BaseDeadline增加时，工作流的截止日期更长，这有助于在同一资源上连续执行更多并行任务，从而减少空闲时隙。此外，建议的T-CCWSA的平均资源利用率分别比CWSA，EFT-MER和HEFT高4.8%，11.8%和22%。T-CCWSA在分配给虚拟机以供其执行的就绪任务中;因此，可以尽可能地减少资源上的空闲时隙。但是在其他比较算法中，所有的工作流任务都被立即映射到虚拟机，这限制了此类算法基于运行时间信息来调度任务。6.4. 工作流计数为了评价这四种算法在工作流计数环境下的性能，我们在固定死线基数的情况下，以500为增量逐渐增加工作流计数，从500增加到2500。T-CCWSA、CWSA、EFT-MER和HEFT的实验结果如图所示。五、从图5a可以看出，总执行成本随着工作流的计数线性增加。原因很明显，因为更多的工作流涉及更多的虚拟机，工作时间更长，导致成本更高。此外，实验结果表明，T-CCWSA的总成本平均比CWSA，EFT-MER和HEFT分别低5.26%，6.57%和20.52%。从图5b中，我们可以观察到，无论工作流计数如何变化，算法T-CCWSA 、 CWSA 、 EFT-MER 和 HEFT 的 资 源 利 用 率 都 稳 定 在79.40%、74.65%、67.60%和57.40%。实验结果表明，T-CCWSA算法在提高云资源的资源利用率方面具有明显的优势。6.5. 规划成功率图图6a示出了在截止期限因子的不同组合下针对CYBERSHAKE获得的结果。当最后期限因素为见图4。 工作流截止日期的性能影响。图五. 工作流计数的性能影响。K.K. Chakravarthi等人/沙特国王大学学报2367见图6。 规划成功率。相对较小，T-CCWSA算法的平均规划成功率（PSR）相对较高。当最后期限因素的增加，T-CCWSA算法的PSR与CWSA算法一致。与其他算法相比，HEFT算法的PSR更小。图图6（b-d）显示了针对EPIGEN 0 MICS、LIGO和蒙太奇应用获得的PSR。从图6通过增加最后期限因子，可获得更多松弛时间来执行工作流，从而导致T-CCWSA的PSR值增加。T-CCWSA算法性能更好的原因是，它只在虚拟机准备就绪时才将任务调度到虚拟机。因此，它降低了工作流任务的计划长度。因此，它会在定义的截止日期内创建一个成本较低的计划。6.6. 讨论上述结果表明，该算法具有优于基线算法CWSA，EFT-MER和HEFT的性能这种性能优越性背后的直觉如下：T-CCWSA算法仅在虚拟机准备就绪时才将任务调度到虚拟机通过合并流水线任务降低了数据传输成本T-CCWSA通过实施MCDM、TOPSIS方法作为决策者，T-CCWSA的性能得到了提高。 TOPSIS方法综合考虑任务的执行时间、执行成本和数据传输时间三个指标，从可用资源中寻找理想资源。7. 结论现有的并发工作流调度算法大多集中在离线调度上，很少涉及在线调度。针对云计算平台中动态并发工作流在自定义截止期限约束下的 调 度 问 题 ， 提 出 了 一 种 T-CCWSA （ TOPSIS inspired Cost-Efficient Concurrent Work- flow Scheduling Algorithm）算法。建议的T-CCWSA使成本，系统的资源利用率之间的良好的权衡。对于模拟，使用Cloud