云计算中一种带任务重复机制的任务划分策略---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除------本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除------本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---摘要：提出了一种带任务重复的任务划分策略算法D-ITPS（ImprovedtaskpartitioningStrategywithduplication），该算法首先将DAG图中的一些满足归并条件的任务进行归并，然后将所有的任务按照划分策略划分为一个个包，将包按照Max-Min策略整体调度到处理器上执行，在完成---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---基本的映射后，检测每个染色体是否可以通过任务重复来减少通信时间，若可以则在处理器的空闲时间隙重复任务以减少总调度长度。关键词：云计算;复杂DAG图;调度算法;任务重复;调度长度：TP30：ADOI：10.3969/j.issn.1003-6970.2019.12.002本文著录格式：张银娟.云计算中一种带任务重复机制的任务划分策略[J].软件，2019，40（12）：0612ATaskPartitioningStrategyWithTaskRepetitionMechanisminCloudComputingEnvironmentsZHANGYin-juan（GuanglingCollegeofYangzhouUniversity，YangZhou，激angsu，225000）【Abstract】：WepresentedanimprovedtaskpartitioningstrategywithduplicationD-ITPS，thealgorithmfirstlymergetasksinDAGwhichmeetmergingconditions，thenallofthetasksaredividedintosmallpackages，whicharescheduledtoprocessorsaccordingtoMax-Minalgorithm.Afterthecompletionofbasicmapping，detectingwhethereachchromosomecanreducecommunicationtimebyduplicatingtasks，ifpossible，duplicatethistaskintheidlegapofprocessortoreducethetotalschedulelength.【Keywords】：Cloudcomputing;ComplexDAG;Taskscheduling;Taskduplication;Makespan0引言云計算[1-3]环境下工作流的调度研究是一个NP完全问题，针对此问题提出许多算法，至今也有一些基于元启发式的算法用来解决NP问题，如：粒子群算法（PSO）[4]、禁忌搜索（TS）[5]，模拟退火（SA）[6]，遗传算法（GA）[7]等。相较之下，GA被认为是优化领域的一种好的方法且通过运用进化的原则在多项---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---式时间内从大量搜索空间和并行搜索中获得高质量的解决方案。它提供一些方法来估算有效参数。本文主要借助于遗传算法来求得调度的最优解，现有的一些基于遗传算法（GA）的算法，如文献[8-10]提出了应用于工作流调度的算法，但是它们均没有考虑到云计算中异构组件的特点，且并不适合云系统这样的异构分布式计算系统。基于GA的算法，有的通过随机选择来选择初始种群，有的在工作流的同一阶段用优化方法将任务排序，比如最先完成的任务，最小依赖的任务，最大依赖的任务，其中一些用具有至多两个输出节点的简单图来表示。文献[11]中考虑到云环境下异构的特性，但是该论文提出的算法中使用的是简单DAG图，而云环境下的工作流任务间的关系复杂，转换为DAG图后任务间的分层不明显，且每个任务的大小和其前后继任务都各不相同，显然简单的DAG图不能适用于云环境中。文献[12]提出了异构启发式算法（HSGA），它考虑到了异构环境下任务的复杂程度，采用复杂的DAG图对任务进行描述和调度，但是其交叉率和变异率均固定，易造成“早熟”的现象。通过以上对国内外研究现状的综述，可以看出针对云计算环境下的调度问题，目前学术界提出的方法策略非常多[13-14]，大多数从优化调度长度来考虑，也有从节能和负载平衡方面来考虑的。大部分学者将云计算环境中的工作流转化成简单的DAG图来考虑，从云计算任务复杂的程度来看，简单DAG图显然是不适用于云环境中的。本文通过对云环境下工作流进行处理，将其转化为复杂的DAG图并对其进行调度，同时考虑负载和计算资源性能的基础上，尽可能减少调度长度。1D-ITPS算法1.1D-ITPS的简单抽象模型图1给出了本文提出算法的简单抽象模型。图1任务抽象模型Fig.1Taskabstractmodel---本文来源于网络，仅供...