智能水滴算法优化云计算工作流调度

埃及信息学杂志19（2018）33全文云计算环境下工作流调度的扩展智能水滴算法Shaymaa Elsherbinya，Eman Eldaydamonya，Mohammed Alrahmawyb，Alaa Eldin Reyadca埃及曼苏拉大学计算机和信息学院信息技术系b埃及曼苏拉大学计算机与信息学院计算机科学系c埃及曼苏拉大学计算机和信息学院信息系统系阿提奇莱因福奥文章历史记录：2016年9月19日收到2017年5月17日修订2017年7月2日接受2017年7月11日在线提供保留字：云计算调度算法资源管理智能水滴工作流调度基于自然的算法A B S T R A C T云计算作为一种高性能计算环境正在兴起，它具有大规模、异构的自治系统集合和灵活的计算架构。许多资源管理方法可以提高整个云计算系统的效率。云计算资源管理的关键部分是资源调度。云虚拟机上任务的优化调度是一个NP难问题，已有许多算法来解决。这些调度器之间的差异是由于调度器的调度策略本文的重点是在云计算中的工作流调度，这是最近得到了很多关注，因为工作流已经出现作为一个范例来表示复杂的计算问题。我们提出了一种新的算法，扩展了基于自然的智能水滴（IWD）算法，优化了云上工作流的调度。该算法的实现和嵌入在工作流仿真工具包中，并在不同的模拟云环境中进行测试，不同的成本模型。我们的算法表现出显着的增强了经典的工作流调度算法。 将该算法与MIN-MIN、MAX-MIN、Round Robin、FCFS、MCT、PSO和C-PSO等算法进行了比较，结果表明，该算法在性能和成本上都有明显的提高。©2018制作和主办由Elsevier B.V.代表开罗计算机和信息学院大学这是一篇CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍云计算正在成为一个热门话题，在学术界和工业界都获得了很多关注，因为它使数据和服务能够远程存储，但可以从任何地方访问。每天，许多公司和组织都将其数据和应用程序转移到云，因为云具有灵活和动态的基础架构，除了可以快速配置和发布的可配置软件服务之外，还提供了QoS保证的计算环境，并且管理工作量最小。*通讯作者。电子邮件地址：mrahmawy@gmail.com（M. Alrahmawy）。开罗大学计算机和信息系负责同行审查。因此，如何提高系统的性能，减少可能导致性能下降或不安全使用的障碍，成为众多研究者关注的焦点。因此，云计算的活跃研究领域包括安全性、调度、隐私和策略、云存储、云性能、部署、能源管理等。任务调度是影响云计算环境性能的重要问题。调度是将任务映射到可用资源的过程，任务的特点和要求。高效的调度是云计算的基本要求，因为它可以优化云资源的使用，以提供高质量的高效服务。随着越来越多的用户开始使用云来部署复杂的应用程序和存储远程数据，迫切需要有强大的调度算法，可以将任务分配给数据中心。本文重点研究了云计算环境下的工作流建模问题云中的工作流调度问题是一般问题的一个特例，http://dx.doi.org/10.1016/j.eij.2017.07.0011110-8665/©2018制作和主办由Elsevier B. V.代表开罗大学计算机和信息学院这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表埃及信息学杂志杂志主页：www.sciencedirect.com34S. Elsherbiny等人/Egyptian Informatics Journal 19（2018）33云中的任务调度，其中一些可并行任务之间存在一些优先执行依赖关系;因此，工作流调度除了其自身的依赖关系特性外，还具有任务调度问题的所有特性和特征。现有的异构计算环境下的工作流调度算法有很多，这些算法根据不同的应用需求进行适当的折衷，或者采用多种调度算法的组合然而，这些算法很难直接应用到云环境中，因为云环境不同于传统的异构环境和网格环境，提供了超大规模的资源池，而这些资源池的使用又受到云提供商提供的复杂处理成本方案的限制。这增加了云调度器要满足的额外目标;该目标是优化租用云资源的资源利用率，以最小化执行工作流的处理成本[1]。在本文中，我们提出了一个云工作流调度算法的基础上的元启发式IWD算法，以满足所需的目标，最小化的最大完工时间和成本的执行工作流在云上为了评估所提出的调度器，我们使用workflowSim仿真环境中使用所提出的算法执行一组常见的工作流在不同的模拟数据中心与不同的配置和成本模型。本文的其余部分组织如下：在第二节中，介绍了云计算中工作流调度的背景和概念。在第3节中，基本的智能水滴（IWD）算法进行了概述。在第4节中，介绍了一些相关的工作。在第5节中，我们提出了我们提出的工作流调度算法，并解释了它的不同阶段;然后，在第6节中，我们给出了一个简单详细的案例研究，以解释所提出的算法的操作。然后，在第7节中给出了一组性能和成本评估实验，并将所提出的算法与其他算法进行了比较，使用了不同的并行处理器配置和成本模型。最后在第8节中给出了结论和未来的工作。2. 云计算工作流是一种有吸引力的范例，可以帮助科学家协调复杂的多步骤模拟和分析。工作流通常用于分布式计算环境，例如网格和云，因为它们在建模广泛应用方面的强大能力，包括科学计算、多处理器系统[2]、多层Web[3]和大数据处理应用[4]。随着云技术的发展，云环境下的工作流调度问题已经成为一个重要的研究课题。一个工作流的图形表示使用有向无环图（DAG），以反映工作流的任务之间的相互依赖性，其中的节点表示要执行的计算任务上的可用资源和有向边表示任务之间的数据流或控制流的依赖性通常，任务在特定资源上的执行时间与该资源的速度成反比;因此，将各个工作流任务优化映射除了广泛的工作流执行时间要求之外，由于大量数据的处理，工作流应用程序通常涉及存在于任务之间的依赖性云计算的出现引入了公用事业型市场模型，其中可以按需以按使用付费的方式获得具有不同容量时尚. 一般来说，工作流调度器的两个最重要的目标成本不仅涉及处理单个任务所产生的计算成本，还涉及数据传输成本，其中必须在计算和存储站点之间传输潜在的大量数据。将服务的各种任务映射到一组资源的问题被归类为NP难问题[5]。使用已知算法来寻找NP难问题的解决方案是不切实际的，这意味着难以构建以合理的计算速度工作的最佳调度器一般来说，NP难问题可以通过枚举法、启发式法或近似法来解决然而，使用枚举方法构建最佳工作流调度器需要首先构建所有可能的调度器并逐个比较它们以选择最佳的一个，这对于云工作流调度是不可行的，因为由于要处理的大量工作流而存在穷尽数量的可能因此，基于算法构建的查询器可能是找到合理快速的合理好查询器的次优方法。为此，我们提出了一个调度器，扩展了元启发式IWD算法，调度任务连接到彼此的工作流，我们评估此调度器使用WorkflowSim模拟器，这已被选择，因为它提供了一个框架，考虑到异构系统的开销和故障，它支持广泛使用的工作流优化技术，如任务集群。3. 智能水滴算法近年来，IWD已被用于许多领域，以解决优化和复杂的科学问题，如旅行销售员问题（TSP[6]），车间作业调度[7]，Steiner树问题[8]，代码覆盖[9]，图着色[10]，优化路由协议[11]，多维背包问题（MKP）[12]，车辆路由问题[13]，空中机器人路径规划[14]，使用修改的Otsu准则的自动多层三层支撑IWD算法首先由Shah-Hosseini，H. 在2007年[6]。IWD算法的灵感来自于湖泊、河流和海洋中自然水滴的流动，水流通过最佳路径到达其最终目的地，通常是湖泊或海洋。在它们到达目的地的过程中，水滴与周围的环境（河床）发生反应并影响它。河床可以被水滴改变，它们可以影响水滴的方向。重力迫使水滴向目的地移动。如果没有障碍物或障碍物，水滴的移动会沿着直线到达目的地。但实际上，在真实的场景中，有不同类型的障碍，如曲折，岩石和转弯。 在原有的IWD算法中，自然水滴具有两个属性：水滴的速度和土壤的量水滴的土壤收集和移动受到其路径中大量土壤的负面影响，而它们沿着土壤较少的路径移动得更快，并且可以获得更高的速度并从该路径侵蚀更多的土壤。水滴的速度使它们能够将土壤从一个地方转移到另一个地方。更多的土壤可以从河床收集和转移的更快的水滴，其中水滴的速度受到路径属性的影响。在IWD算法中，水滴从源移动到以有限长度的时间步长计算目的地水滴的速度与其所经过的路径的土壤的倒数成此外，水滴的土壤增加S. Elsherbiny等人/Egyptian Informatics Journal 19（2018）3335因为它们从路径上收集了一些泥土;这种增加与它们的行进时间成反比，其中行进时间持续时间取决于水流的速度和行进的距离。在决定选择通过的路径时，路径中的土壤量是一个主要考虑因素;水滴总是喜欢更容易的路径，即土壤较少的路径。IWD算法构造最佳路径的概率解，其中迭代地更新算法的参数以便收敛到高质量解。最佳逼近算法用于寻找最佳解的近似解。[18]的作者确定了IWD算法重要性的三个原因：（I）它比其他技术更快地收敛到解决方案，（II）它使用平均值收敛到高质量的解决方案，（III）它对动态环境非常灵活，并且很容易合并弹出威胁。4. 相关工作在云计算环境下，人们对工作流应用程序在分布式资源上的调度进行了广泛的研究在这些研究中，已经使用了几种算法进行调度，这些算法应用不同的调度策略和参数。其中，有各种工作流调度算法。例如，[19]的作者提出了一种使用蚁群优化（ACO）的调度器，以满足所有用户指定的QoS约束，该调度器使用一组算法和工作流实验来计算信息素值。在[20]中提出的调度算法中，作者使用粒子群优化（PSO）来调度云资源上的工作流;该算法同时考虑了计算成本和数据传输成本。免疫粒子群优化算法（IPSO）在文献[21]中得到了应用，它是一种网格任务调度模型在文献[22]中，提出了一种多工作流的多QoS约束调度策略作者在[23]中提出了另一种基于PSO的算法，该算法同时考虑数据传输成本和计算成本来调度云服务之间的应用;他们对一组工作流应用进行了实验，其中他们根据云价格模型改变数据通信成本和计算成本该方案表现出了很好的性能，它实现了更多的成本节约和更好的性能，在最大完工时间和成本优化。SHEFT工作流调度算法在[24]中给出。初步实验表明，该算法不仅在优化工作流执行时间方面优于几种典型的工作流调度算法，而且能够在工作流执行过程中实现资源的弹性伸缩。作者[25日]提出一市场导向的等级制通过以上分析，我们可以得出结论：工作流调度已经有了很多研究工作，但是在满足弹性和异构云环境下的QoS等方面还需要进一步的研究。5. 建议的工作流调度程序本文提出了一种新的基于IWD的云调度算法（IWDC），用于优化云计算环境中不同工作流任务执行的调度。我们已经开发了一个实现所提出的算法，并将其嵌入到WorkflowSim模拟器中，成为其主要的调度算法。在本节中，我们将展示如何扩展IWD以在云环境中调度工作流所提出的算法分为三个阶段，参见图1，其中前两个阶段与所提出的修改的IWD算法相同[9]，第三个阶段表示使IWDC算法能够在云环境中调度以下小节详细介绍了这种新算法的各个阶段。5.1. 准备和参数初始化阶段该算法的第一步是初始化所有的静态参数，这些参数包括每个边缘的土壤和每个水滴的速度（IWD）。包括指定静态值的算法参数的定义如表1所示。5.2. 道路建设阶段在此阶段，根据等式（1）中定义的适应度函数计算图形每条边上的初始土壤。土壤;最大值aω子图jω条件图j ω;1其中土壤（i，j）是指从节点i到节点j的有向边上的土壤量。条件（j）标识节点j是否如果它有一个或多个子节点，则它被分配一个值1;否则，它被分配0。方法子图（j）对该特定节点（j）之下的节点的数量进行计数。max（）方法用于确保soil（i，j）= 1;如果子图(j)条件（j）== 0。最后，a，b具有常数值a = 2，b= 1。在初始化参数之后，只要一些路径还没有被穿过，就重复下面解释的步骤（A-D）以更新土壤值。步骤A：选择下一个访问节点：对于WD，根据计算出的概率在调度操作列表中选择下一个要访问的节点（设计了条件概率计算方案，进一步提高解空间的多样性调度，它考虑并优化了任务到概率i j土壤微生物vcSoil i k k0 2本地云数据中心中的服务分配和任务到虚拟机分配。Cat SwarmOptimization（CSO）被[26]的作者用于云中的工作流调度。算法-哪里;Rk（c） &中文rithm旨在减少能源浪费，其政策是更新猫的位置。该算法被证明是更有效的比粒子群算法，因为它收敛到最优解，在较少的迭代次数。在[27]中，提出了一种资源感知的混合算法来调度云中的批处理作业和工作流，其中任务首先被分配给云资源组;然后对每个组应用经典调度来调度其分配的任务。– 土壤（i，j）：指两个节点– Rk步骤B：计算WD的D土壤：局部土壤更新负责控制寻路的收敛速度，因此，为了充分适应和控制收敛速度，WD携带的土壤通过以下公式进行定界：36S. Elsherbiny等人/Egyptian Informatics Journal 19（2018）33ðÞ算法：IWDC工作流调度开始//阶段1：准备和静态参数设置（第5-1节）设置初始参数：av、bv、cv、as、bs、cs、P等。设置每个水滴的初始速度：Vel_WD（i，j）//第二阶段：WDWHILE工作流图不为空DO//发现生成的WD计算工作流程图方程（1）中剩余每2个节点之间的边缘上的土壤重复，直到发现从接收器到源的完整WD路径设置为最顶层节点作为当前访问的节点计算所有可能的边概率公式（2）使用计算的概率选择下一个要访问的计算WD携带的土壤到选择下一个节点方程（3）计算WD行进到访问节点的时间等式（4）计算WD的速度;公式（5）选定节点方程边缘的局部土壤更新（6）如果选定的访问节点是叶节点，则删除叶节点如果叶节点的父节点的所有子节点都已删除（或不存在），则删除叶节点结束IF结束IF将发现的WD路径添加到最佳发现路径列表重新初始化动态WD参数END WHILE在最佳发现路径列表中搜索最佳路径PIWD_best//阶段3：任务分配阶段（第5-3节）WHILE发现的最佳路径列表不为空从最佳WD路径列表中获取最佳分配路径PIWD_bestWHILE（Pbest有更多未调度的任务）如果tpath在路径PIWD_best的根处，则在PIWD_best中获得下一个最顶层的未调度任务tnext在虚拟机列表中搜索所选最快的可用虚拟机VM如果选择了虚拟机 存在为选定的VM分配路径其他在虚拟机列表中搜索将空闲的虚拟机，并将其设置为选定的虚拟机。为选定的虚拟机分配路径END IF其他将t路径分配给路径PIWD_best END IF中为其父任务分配的同一虚拟机对于同一级别的t路径获取此级别中最左侧的未调度任务t级别在虚拟机列表中搜索所选最快的可用虚拟机VM如果所选虚拟机存在将t级别分配给选定的其他在虚拟机列表中搜索将空闲的虚拟机，并将其设置为选定的虚拟机为选定的虚拟机分配级别END IF结束时结束时端Fig. 1. IWDC工作流调度算法。作为D土壤学i;j;wdv/bbs/csω时间轴i;jð3Þ提出了一种有界局部土壤更新，以充分利用引导信息，控制寻路的收敛速度而bs和cs是表1中声明的正参数，时间轴i：子图i-子图i=速度轴其中（子图（i）步骤C：WD的更新速度的计算：在从节点i移动到节点j之后，WD的速度受到节点i和节点j之间存在的土壤量的影响。因此，可以使用等式（5）中的公式来计算WD的速度的变化并对其进行限制。Dvelocity i;j;wdvvelocity wdvvelocity av= bv cvωsoilocity i; j; wdvvelocityS. Elsherbiny等人/Egyptian Informatics Journal 19（2018）3337表1IWD参数的定义。符号定义N就业人数M虚拟机概率（i，j）WD从节点i移动到节点j的概率时间（i，j）WD从节点i移动到节点j所花费的时间D土壤（i，j，wd）WD在节点i和节点j之间的路径上收集的土壤节点jVel（i，j，wd）WD从节点i到节点j时的速度av，bv，cv WD速度更新参数这些参数被指定为如下任意选择的常数值[6]，av = bv = cv = 0.1as，bs，cs WD土壤更新参数as = bs = cs = 0.1局部土壤更新参数该参数被指定为任意选择的常数，如下q= 0.1Vel_WD初始速度值设置为Vel_WD = 100父/叶节点叶节点图二. 父/叶节点。哪里– soil（i，j）是在WD穿过节点i和j之间的路径之前该路径上的土壤量。– av、bv、cv是如前所述的用户定义的正参数。– vel（WD）是的先前速度的的WD。步骤D：局部土壤更新：由于WD携带一定量的土壤，因此沿着从节点i到节点j的路径的土壤减少。因此，使用以下等式计算从i到j的路径上的更新的土壤量Soil（i，j）土壤i;jω 1-qω d土壤i;j ω-qωD土壤i;j;wdqω 6哪里– q是一个常数。– D土壤（i，j，wd）是WD从节点i移动到节点j时从路径中移除的土壤。在IWD算法中，提出了更新全局土壤以保留所获得结果的良好在更新当前节点的算法的值之后，对沿着所选路径的所有后继节点依次重复相同的过程（步骤A-D），直到其到达叶节点。当它到达叶节点后，该节点被删除，其父节点也被检查。如果某个节点的所有叶子都被删除了，那么它也会被删除，如图2所示，以防止再次访问它。5.3. 任务分配阶段该阶段代表对原始IWD算法的扩展，它在完成第二阶段之后开始，在第二阶段中遍历整个工作流并且发现所有IWD路径在该阶段中，为了将工作流任务分配给云VM，调度器在最佳发现的IWD路径的引导下按顺序逐层分配工作流任务。如算法中所示，调度器从最佳发现路径PIWD_best的根到其叶逐一遍历最佳发现路径PIWD_best上的所有任务t路径对于PIWD_best的根（即第一级）处的任务，算法搜索所选择的最快空闲机器VM，并选择它以将其分配给该任务;如果不存在空闲VM，则算法找到下一个空闲的VM，并选择它来执行该任务。在下一个级别中，默认情况下，同一路径中的所有派生任务都将分配给在其根目录中为任务选择的同一个VM最快的免费VM在最佳路径的每个级别，在该级别将任务t路径分配给PIWD_best之后，算法将其级别上属于其他连接路径的所有任务t级别分配为图三. 案例研究工作流程。从左到右，其中对于每个任务t级别，下一个快速空闲VM被分配给它;否则，如果没有可用的空闲VM，则调度发现下一个空闲VM并将其分配给该任务。这很重要，因为它确保了任务之间的优先关系的尊重在完成上述步骤后，工作流中的某些任务可能仍未调度，例如：如果工作流具有多个未连接的路径，则一旦整个PIWD_best被完全遍历，则在同一工作流中包含未调度任务的下一个最佳IWD路径上重复相同的步骤。6. 应用云工作流调度器的案例研究在这一节中，我们提出了一个案例研究，如何将我们提出的算法应用于一个示例工作流。我们研究了它的详细执行场景，并分析了它的行为。该案例研究扩展了[28]中的案例研究，它具有由9个任务组成的工作流，这些任务表示为编号为0到8的DAG中的节点，如图所示。3.第三章。在图中，每个节点表示计算任务，并且对应节点之间的每个有向边表示任务之间的数据或控制依赖性。顺序很重要，因为工作流应用程序尊重优先关系。在图上应用我们的算法步骤经历以下阶段：部署和准备阶段：在该阶段中，分配所有静态参数并为每个节点计算子图值;某个节点的该值指示连接到该节点的所有子节点和孙节点的数量，其中使用深度优先遍历算法遍历子图即，在示例工作流中，节点（0）的子图值= 8，节点（2）的子图值=6，节点（4）的子图值= 3，并且节点（3，5，6，7，8）的子图值为零。等式（1）中所需的决策条件Condition（(1) 检查并标记每个节点。因此，只有节点（0，2，4）被标记为值1，因为它们具有非零子图值，而所有其他节点（3，5，6，7，8）被标记为值0。路径构造阶段：在该阶段中，算法从根开始处理，即从节点（0）开始，并遍历树以应用等式（1）。（1）在这个例子中，水滴在01234567838S. Elsherbiny等人/Egyptian Informatics Journal 19（2018）33节点（0）有两条路径要通过;要么到节点（1），要么到节点（2）。然后，我们计算沿两条路径的土壤，如方程所示。（一）.沿两条路径的土壤值计算如下：土壤含水量0;2升/升最大值2ω6升/升1ω1升/升;1升/升13土壤含水量0;1升/升最大值2ω0升 1ω0升;1升/升1接下来，我们使用等式（2）计算两条路径中的每一条的概率，以便找出下一条要访问的路径，如下所示：磷0;1 ‰土壤0;1 ‰= 1‰土壤0;1 ‰土壤0;2 ‰土壤1= 14磷0;2磷1/4土壤0;2磷1/4=磷1/4土壤0;1磷1/4土壤0;2磷1/413= 14具有较高概率的路径被选择为首先被访问因此，节点（2）被选择为在节点（1）之前首先被访问然后，为了计算节点（0）到节点（2）之间的土壤量变化，我们首先计算从节点（0）到节点（2）的时间(0)如等式（2）中所指示的，通过WD到节点（2）。其中，如表1中所假设的，初始速度为100。时间间隔0;200 ½最大值f8-600; 1g= 100½ 2= 100½ 0： 02秒根据IWDC算法，当WD沿着所选路径行进时，WD携带一些土壤，该量可以根据等式（1）计算。（3）如下：D土壤0;2011=101 1ω 0：0201 0： 98这导致WD速度和沿着所选路径的剩余WD速度和剩余土壤量的新值可以根据方程计算如下：（5）和（6）分别如下：D速度0;2100 1= 1 1ω13 100： 07更新土壤0;20：9ω 13- 0： 1ω 0： 98< $11： 6土壤含水量0： 98在到达节点（2）之后，WD具有可用于选择下一个节点的三个节点：节点（3）、节点（4）、节点（5），为了决定访问它们中的哪个节点，IWDC算法重新计算它们中的每个节点处的土壤量;然后它使用计算的土壤量来计算访问它们中的每个的概率，如前所述，如下所土壤微生物2;土壤类2; 4ω 1 <$7;土壤微生物2; 60%1P2 O32;4 O3/4土壤2;4 O3=f土壤2;4 O3/4土壤2;4 O3/4土壤2; 4O3/4土壤 7= 920： 77P2O3 2; 3P2O3/Soil2;3 P2O3=fSoil2;4 P2O3/Soil2;3 P2O3/Soil2;6P2O3 g1/ 4= 107101101 1/ 4= 9/4 0： 11P2O32;6O3/Soil2;6O3=fSoil2;4O3/Soil2;3O3/Soil2; 6O3/g1/ 4= 107101101 1/ 4= 9/4 0： 11从这些值中可以清楚地看出，节点（4）是下一个要访问的选定节点，因为它在三个节点中具有最大的概率。与先前从节点（0）到节点（2）的路径一样，计算节点（2）之间WD行进的IWDC参数。(2)和节点（4），计算/更新的值为：时间表2;4小时24小时6-3小时=100： 07< $0： 03D土壤2;4土1= 1土 1ω 0：03土 1 ω 0： 97D速度2;400：07 1=1 1ω700： 195更新土壤2;400：9ω 7- 0： 1ω 0： 97< $6： 2土壤含水量<$0： 98< $0： 97< $1： 95在节点（4），我们只有三个子节点：节点（6），节点（7）和节点（8），因为它们都是没有子节点的叶节点，从节点4到它们的路径上的土壤量不会改变，而三个节点得到相同的概率值去每个节点。土壤4;601土壤4;701土壤4;801P10 4;600P104;700P104;8000： 33因此，随机选择这些叶节点中的一个作为下一个要访问的节点。这里，我们假设节点（6）被随机选择为下一个节点，并且从节点4到6的路径的更新参数计算如下：时间表4;6秒13-0秒=100： 195< $0： 03D土壤4;611= 101101ω 0：05 ω 1 0： 97D速度表4;601100： 195 1=1 1ω 100：695更新土壤表4;601 0： 9ω 1- 0： 1ω 0： 97< $0：803土壤表wd 1： 95 0： 97< $2： 92从以上步骤，由IWDC算法发现的最佳路径P IWD_best是： 两个？ 四个？第六章接下来，在第二次迭代中重复上述相同的计算，其中IWDC在清除预先访问的路径之后再次从节点（0）重新启动。这导致第二最佳路径，即：0？ 两个？ 四个？第七章 然后，再次重复该过程，直到发现工作流图中的所有路径，这导致以下顺序的最佳路径： 两个？ 四个？八，零？ 两个？三，零？ 两个？ 5、最后0？1.一、任务分配阶段：在该阶段中，对表2所示的具有不同速度的4个虚拟机进行逐级分配，其中调度器将位于最佳发现路径PIWD_best的根节点（0）处的任务分配给最快空闲的虚拟机;然后，由于在节点（0）的级别没有其它任务，调度器进入下一级别，在该下一级别，调度器首先搜索属于PIWD_best的该级别的任务，该任务是节点（2）处的任务，并将其分配给分配给其父节点（节点（0））处的任务的同一VM。之后，它检查在该级别是否还有未分配的任务，并将其从左到右分配给下一个免费的VM由于只有节点（1）处的任务未被分配，调度器将其分配给第二快的VM。然后，在下一个级别中重复相同的过程。因此，我们注意到，选择作为最快VM的VM 3来执行所有任务tpath（0，2，4，6），其位于PIWD_best上。在执行每项在这些任务中，调度器将位于相同级别上但属于其他路径的任务一级一级地分配给空闲VM，并考虑它们之间的依赖性。 在该工作流中，参见表3，由于节点1位于与节点（2）相同的级别，因此它被分配给下一个快速空闲VM，即在这种情况下的VM2。由于这一层上没有更多的节点，调度程序转到下一层，在那里它找到节点3和5上的任务，因为它们都依赖于在节点（2）的任务上，它们必须被调度以供执行表2案例研究中使用的虚拟机速度VMVM0VM1VM2VM3速度（MIPS）500625750875S. Elsherbiny等人/Egyptian Informatics Journal 19（2018）3339表3计划工作流任务的计时属性。任务深度执行分配开始完成ID水平时间VM时间时间016.4VM306.4229.03VM36.415.431213.73VM26.420.13437.66VM315.4323.09647.66VM323.0930.753315.68VM115.4331.115316.6VM015.4332.03749.87VM223.0932.96847.66VM330.7538.41在节点（2）在15.43完成之后。因此，调度器按照从左到右的顺序将它们分配给此时最快空闲的虚拟机，分别为VM1和VM0，因为VM3和VM2此时分别忙于执行节点4和1处的任务。此后，调度器检查最后一级中未分配的任务，即按顺序检查节点7、8处的任务。由于这两个任务都依赖于节点4上的任务，因此它们都等待节点4完成在23.09的时刻执行。此时，只有VM 2是空闲的;因此，节点7处的任务被分配给它;然后，节点8处的任务被分配给第一个最快的空闲VM，该VM是在30.75完成沿着最佳路径的最后一个任务（即，节点6处的任务）的执行之后变得可用于分配的VM 3。最后，该算法按顺序检查下一个最佳路径;如果它们存在，则检查它们上是否有任何尚未分配的任务，其中在排除最佳路径之后重复最佳路径的场景分配的任务。在该工作流中，在完成最佳路径的处理之后，没有其他任务保持未签名;因此，算法终止。对于所研究的工作流，如表3所示，最大完工时间（最后一个任务完成执行的时间）等于38.41，这是节点8处的任务完成执行的时刻。该值与其他一些常见算法FCFS、MCT、RR、MIN-MIN和MAX-MIN的最大完工时间值进行了比较，见表4。很明显，我们的算法优于所有算法。7. 实验和结果CloudSim工具包是一个基于Java的离散事件云仿真工具包。它是一个著名的云计算基础设施和服务建模和仿真框架，它可以模拟大规模云计算环境。然而，CloudSim只支持执行单个作业的工作负载，缺乏对科学工作流调度的支持。因此，为了评估所提出的工作流调度算法，WorkflowSim仿真工具已被使用。WorkflowSim运行在 CloudSim 之 上， 作 为一 个 扩展 层来 处 理云 之 上的 工作 流 。WorkflowSim 增 加 了 支 持 科 学 工 作 流 模 拟 所 需 的 功 能 。WorkflowSim不仅支持调度机制的评估，而且还可以分析各种任务调度/执行开销和故障。因此，我们在WorkflowSim 1.1中实现了我们的IWDC算法，并针对一组众所周知的调度进行算法（稍后详细解释）。我们在一个运行在PC上的系统上运行我们的实验，该PC具有Intel（R）Core（TM）i3- 3217 U CPU@1.80 GHz，4.00 GB的RAM，并运行Windows 64位操作系统。我们将我们的实验分为两组;第一组的实验是使用建议的非现实环境的配置进行模拟的，该环境提供了建议的非现实配置和建议的云数据中心的成本模型，而第二组中的实验是使用现实环境进行模拟的，该环境遵循商业Amazon EC2云的精确配置。7.1. 使用建议的非现实云环境进行评估在下文中，我们提出了一个非现实的云环境，使用Work-flowSim预先分配的模拟参数，以表示云数据中心，工作流应该在其中执行。然后，我们解释了我们在实验中使用的不同工作流程，最后，我们介绍了拟议实验的场景并解释了所获得的结果。模拟器被分配表5中所示的一组参数，其中VM的数量根据实验而变化。此外，VM的带宽值和速度在使用同构配置的情况下对于所有VM是固定的，或者在使用异构配置的情况下在所示的范围内变化。7.1.1. 使用通用工作流程进行为了评估所提出的调度程序，我们生成了五个不同大小的通用工作流，并在每个工作流上应用所提出的IWDC调度算法然后，我们比较了结果与其他著名的算法，最小-最小，最大-最小，轮循，FCFS和MCT，在相同的工作流上得到的结果对于每个工作流，我们在CloudSim中使用每个实验中指示的不同数量/配置的虚拟机7.1.1.1. 通用工作流实验I。 在这些实验中，我们将我们提出的算法应用于所示的通用工作流在图4中。此工作流有20个任务，其中每个任务具有相同的长度（T = 10 MI）。我们在3台同构虚拟机（MIPS =1000，BW = 1000）上进行了实验。然后，我们在三个异构虚拟机（MIPS BW =（500，666.66，833.33））上重复相同的实验。运行这些算法所获得的结果示于图1和图2中。5和6.我们可以看到，所提出的IWDC算法得分最小的完工时间，而FCFS得分最差的完工时间在两种配置。此外，我们可以看到，MIN-MIN，MAX-MIN，MCT得分接近表5模拟参数。参数值数据中心数量VM数量3、5、10、20PE数（CPU）1带宽均匀：1000，异质：[0表4与其他常见算法的评估所提出的算法。算法FCFSMCTMIN-MINRRMAX-MINIWDC完工时间110.7039.5040.7746.2741.0638.4140S. Elsherbiny等人/Egyptian Informatics Journal 19（2018）33≤≤见图4。 通用工作流I的结构。2001000- a-通用工作流程II见图7。 通用工作流程II。- b-任务列表图五.在3个同构虚拟机上调度通用工作流I（20个任务）的Makespan值。285.363002001000见图6。在3个异构VM上调度通用工作流I（20个任务）的Makespan值。相同的完工时间，这是预期的，因为所有这些算法的7.1.1.2. 通用工作流实验2。在这些实验中，我们将我们提出的算法应用于图1所示的自定义生成的工作流。早上7 与上一节中的工作流不同，此工作流有25个任务，其中每个任务具有不同的长度;任务的长度如图所示。 7 b. 实验在WorkflowSim中进行，使用两种主要配置：5个同构VM（MIPS = 1000，BW = 1000）和5个异构VM（MIPS≤ 1000，BW≤ 1000）。运行结果-使用这两种配置进行这些实验的结果示于图1A和1B中。分别为8和9。从图中可以看出，在同构配置下，IWDC调度算法的最大完工时间等于RR，MIN-MIN和MCT，低于FCFS，MAX-MIN;而在异构配置下，IWDC调度算法的最大完工时间小于其他算法。7.1.1.3. 通用工作流实验III。在这组实验中，我们将我们提出的算法应用于具有50个任务的更大的自定义生成工作流，见图10。所有的实验都是在WorkflowSim中进行的，超过5个，10个，然后20个虚拟机。该工作流的实验首先假设所有任务都被分配了相同的长度T = 15，见图11;然后，在为任务分配随机的不相等长度（T）后重复相同的实验15），参见图12。从结果来看，所提出的IWDC调度器具有比所有其它算法低的Makespan，其中它明显好于FCFS和RR，但比其它三种算法稍好7.1.1.4. 通用工作流实验IV. 在这些实验中，我们将我们提出的算法应用于一个更大的生成工作流，该工作流具有100个任务，如图13所示。我们根据以下四种配置将实验分为四组：– 所有任务都具有相同的长度（T = 10），并且所有VM都是同构的（MIPS = 1000，BW = 1000）– 所有任务的长度都不相等（T15），所有虚拟机都是同构的（MIPS = 1000，BW = 1000）– 所有任务都具有相同的长度（T = 10），并且所有VM都是异构的（MIPS≤1000，BW ≤ 1000）– 所有任务有非等长度（T≤ 15），和vm被异构（MIPS≤ 1000，BW≤ 1000）150.21110.2190.21141.31126.3完工时间完工时间节点长度162023503100426056206670754084209750107801175012324135901429015489163541767918579194652042021564223502345024390S. Elsherbiny等人/Egyptian Informatics Journal 19（2018）334110000500006004002000vm=5vm=10vm=20见图8。在5个同构VM上调度通用工作流II（25个任务）的Makespan值。10000见图11。在5、10、20个异构VM上调度通用工作流III（50个等长任务）的Makespan值。15000500001000050000vm=5vm=10vm=20见图9。在5个异构VM上调度通用工作流II（25个任务）的Makespan值。见图10。 通用工作流程III.四组实验中的每一组都在具有（5，10，20）个VM的运行这四组实验所获得的结果示于图1A和1B中。分别为14-17。我们可以看到，在四组实验中，我们提出的IWDC调度器得分最低的完工时间与所有其他算法相比。收集本节中列出的所有实验的结果并总结在表6中，其中最低值以红色显示。从表中可以清楚地看出，在测试的情况下，我们提出的算法击败了所有其他算法，因为它在所有实验中提供了最低的完工时间值见图12。在5、10、20个异构V