云环境下基于预算分配的科学工作流调度研究

云环境下的科学工作流部署不同于传统的独立任务调度,需同步考虑调度代价与时间问题。为此,提出基于预算分配的科学工作流调度方法,将工作流任务与虚拟机资源间的映射求解分为预算分配和资源提供与调度2个阶段。为优化预算使用,设计基于快优先的预算分配算法(FFTD)和基于慢优先的预算分配算法,实现预算在各任务间的子分配。基于任务最早完成时间的降序排列进行任务选择,在虚拟机可重用的情况下根据单个任务的子预算进行资源分配,保证工作流任务的顺利调度。引入5种常规类型的科学工作流进行实验,测试算法在不同类型工作流结构和不同预算约束下的性能,结果表明,FFTD算法在72%、88%、84%的实验场景中相比BDT-AI算法具有更高的虚拟机资源利用率、预算约束满足率以及更短的调度时间,综合性能更优。     

一种多重约束下确保成功率的云工作流调度方法

为提高多重约束下的调度成功率,提出一种满足期限和预算双重约束的云工作流调度算法。将可行工作流调度方案求解分解为工作流结构分层、预算分配、期限分配、任务选择和实例选择。工作流结构分层将所有工作流任务划分层次形成包任务,以提高并行执行程度;预算分配对整体预算在层次间进行分割;期限分配将全局期限在不同层次间分割;任务选择基于任务最早开始时间确定优先级,得到任务调度次序;实例选择根据时间和代价均衡因子,获取任务执行最佳实例。仿真结果证明,该算法在调度成功率、同步优化工作流执行时间与执行代价上相较对比算法更好。     

基于局部关键路径与截止期限分配的云工作流调度算法

为了解决云计算中截止期限约束下的工作流调度代价优化问题,提出一种基于局部关键路径和截止期限分配的工作流任务调度算法。为了满足期限约束,并最小化执行代价,算法将工作流任务的调度过程划分为两个阶段:期限分配阶段和调度资源选择阶段。期限分配阶段定义工作流的局部关键路径,并以递归的方式在局部关键路径上的任务间进行子期限分配;调度资源选择阶段在满足任务子期限的同时,为每个任务选择执行代价最低的资源进行任务调度,以实现调度代价优化。分析算法的时间复杂度,并通过一个算例对算法的实现思路进行了详细阐述。通过科学工作流结构的仿真实验,证明了算法不仅可以满足截止期限约束,而且可以降低工作流任务的执行代价。     

DAG分割模型下的云工作流调度策略

为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无循环图（DAG）分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标,算法将调度求解过程划分为三个阶段进行：工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图;分割结构调整阶段以降低执行跨度为目标,在不同分割间对任务进行重分配;资源分配阶段旨在选择代价最高效的任务与资源映射关系,确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明。PBWS算法仅以较小的执行跨度为开销,极大降低了工作流执行代价,实现了调度效率与调度代价的同步优化,其综合性能是优于同类型算法的。     

QoS约束云环境下的工作流能效调度算法

云环境可以为大规模工作流的执行提供高效、可靠的运行环境,但工作流执行时带来的高能耗不仅会增加云资源提供方的经济成本,还会影响云系统的可靠性,并对环境产生不利影响。为了在满足用户截止时间QoS需求的同时降低云环境中工作流调度的执行能耗,提出一种工作流能效调度算法QCWES。该算法将工作流的能效调度方案求解划分为3个阶段:截止时间重分配、任务调度选择排序以及基于DVFS的最佳资源选择。截止时间重分配阶段旨在将用户定义的全局工作流截止时间在各个任务间进行重分配,任务调度选择排序阶段旨在通过自顶向下的任务分级方式得到任务调度序列;基于DVFS的最佳资源选择阶段旨在为每个任务选择带有合适电压/频率等级的最优目标资源,在满足任务的子截止时间的前提下使总体能耗达到最小。通过随机工作流和基于高斯消元法的现实工作流结构,对算法的性能进行仿真实验分析。结果表明,所提算法可以在满足截止时间约束下降低工作流的执行能耗,实现用户方的QoS需求与资源方的能耗间的均衡。     

一种云工作流任务调度能效优化算法

工作流任务执行时带来的高能耗不仅会增加云资源提供方的经济成本,而且会降低云系统的可靠性。为了满足截止时间的同时,降低工作流执行能耗,提出一种工作流能效调度算法CWEES。算法将能效优化调度划分为三个阶段：初始任务映射、处理器资源合并和任务松驰。初始任务映射旨在通过任务自底向上分级排序得到任务调度初始序列,处理器资源合并旨在通过重用松驰时间合并相对低效率的处理器,降低资源使用数量,任务松驰旨在为每个任务重新选择带有合适电压/频率等级的最优目标资源,在不违背任务顺序和截止时间约束前提下降低工作流执行总能耗。通过随机工作任务模型对算法的性能进行了仿真实验分析。结果表明,CWEES算法不仅资源利用率更高,而且可以在满足截止时间约束下降低工作流执行能耗,实现执行效率与能耗的均衡。     

满足实时云任务需求的主动响应式工作流调度模型

为了改善云平台中多工作流调度时的执行代价和资源利用率,提出一种满足实时云任务需求的主动响应式工作流调度算法.该算法可以分别针对新工作流的到达、任务完成后的虚拟机资源提供、紧迫任务到达等做出主动的实时响应调度策略,从而充分利用虚拟机资源的空闲时槽和更大化的任务并行程度,以混合形式调度来自不同工作流的任务.在确保截止期限约束的同时,有效满足实时云任务的调度需求.大量实时工作流的仿真测试表明,与另外几种同类型算法相比,该算法不仅可以降低任务执行代价,而且可以得到更高的资源利用率,实现算法预期效果.     

信任约束下的网格工作流任务调度算法*

提出了信任约束下的网格工作流任务调度算法。该算法结合直接经验和推荐经验计算资源的信任度,根据任务在候选资源上的执行时间确定关键任务,然后选择满足执行时间和信任综合函数的资源。实验结果表明。该算法不仅缩短了工作流的完成时间,而且提高了调度的成功率。     

OSG环境中可靠性增强的工作流自适应调度

针对实际的网格环境-Open Science Grid (OSG),提出了一个多阶段网格工作流调度机制,主要包括站点发现、站点初始评估以及站点动态评估和选择.通过基于时间序列的性能预测值评估各资源站点的初始性能,提出了一个基于网格资源站点自适应评分机制的选择算法.为了提高工作流执行的可靠性并尽可能缩短执行时间,设计了一个增量式的任务副本策略,并采用各资源站点任务排队等待时间的经验累积分布函数图来优化任务副本的设置参数.在实际网格环境OSG中,基于网格工作流系统Swift完成的大量实验结果表明,所提出的算法和策略能够有效减小工作流调度长度和作业拒绝率,同时在OSG中能够成功完成的Swift工作流规模也明显增大.     

基于边缘云环境的工作流调度与卸载决策算法

边缘云环境中,为改善任务执行效率和移动客户端能效,以最小化执行时长和降低移动端能耗为目标,提出一种工作流调度与卸载决策算法PCTSO.依据工作流任务的结构层次,设计基于优先级的待调度任务选择机制;设计基于连续任务选择的卸载机制,验证连续依赖型任务的整体卸载可以更有效利用边缘云服务器资源,提升任务执行并行度.利用随机工作流结构和Montage科学工作流进行仿真实验,其结果表明,该算法在满足能量约束的同时,可以进一步提升多工作流的调度效率,降低执行时长.     

一种双匹配动态调度算法

提出了适于异构环境独立任务调度的双匹配动态调度算法（BM算法）．BM算法将任务与处理机实现双匹配，使大部分任务在执行时间最短而且完成时间最早的处理机上执行．对于无法实现双匹配的任务，采用最早完成时间最小者优先的策略进行调度．BM算法可以同时满足负载均衡和高吞吐率两个目标．BM算法与通常用作评测基准的Min-min算法的比较结果表明，BM算法的运行时间远少于Min-min算法，其调度跨度比Min-min算法减少约9％．     

基于可靠性的云工作流调度策略

经过对已有云工作流调度算法中可靠性问题进行分析研究,针对一些算法在任务调度过程中只考虑提高整个工作流的可靠性而牺牲了时间或增加花费的问题,结合云计算的特点,提出一种基于可靠性的工作流调度策略。该策略结合了工作流中任务的可靠性,充分考虑任务的优先顺序并结合复制的思想,在减少传输过程失败率的同时降低传输时间,使整个工作流在降低完成时间的同时,提高整体可靠性。通过实验和分析表明,通过该策略云工作流在不同任务数和通信运算比(CCR)的可靠性比异态最早结束时间算法(HEFT)算法及其改进算法——SHEFTEX都有所提升,完成时间比HEFT算法有所减少。     

基于可靠性的云工作流调度策略

经过对已有云工作流调度算法中可靠性问题进行分析研究,针对一些算法在任务调度过程中只考虑提高整个工作流的可靠性而牺牲了时间或增加花费的问题,结合云计算的特点,提出一种基于可靠性的工作流调度策略。该策略结合了工作流中任务的可靠性,充分考虑任务的优先顺序并结合复制的思想,在减少传输过程失败率的同时降低传输时间,使整个工作流在降低完成时间的同时,提高整体可靠性。通过实验和分析表明,通过该策略云工作流在不同任务数和通信运算比（CCR）的可靠性比异态最早结束时间算法（HEFT）算法及其改进算法--SHEFTEX都有所提升,完成时间比HEFT算法有所减少。     

基于动态资源选择策略的微服务工作流调度算法

为解决现有云中工作流调度算法在面对大量微服务任务组成的工作流时出现整体调度成本偏高的问题,提出一种基于动态资源选择策略(dynamic resource selection strategy, DRSS)的微服务工作流调度算法——DRSS调度算法。利用任务在工作流中的位置确定任务的子截止期以及调度优先级,采用动态资源选择策略对任务进行调度,获得任务执行的最优资源,在此基础上更新任务状态以及虚拟机实例的资源向量。实验结果表明,该算法在调度成功率与成本方面上较同类算法更优。     

一种基于引力搜索机制的云工作流调度算法

为了同步优化云环境中工作流调度长度和代价,提出一种基于引力搜索算法的工作流任务调度算法。算法以异构最早完成时间机制生成引力搜索的部分初始代理,并结合随机生成方式,得到初始种群;利用引力搜索的进化机制,通过代理适应度的评估,得到最终在调度时间和调度代价上综合性能最优的任务映射方案。利用一个算例对算法的有效性进行了论证与评估,并以四种实际科学工作流模型对算法进行了大规模仿真实验。结果表明,该算法不仅可以得到最小的调度代价,且调度时间在所有算法中也是较小的,其综合性能是最优的。     

云中截止时间动态分配的工作流调度成本优化算法

现如今,如何在满足截止时间约束的前提下降低工作流的执行成本,是云中工作流调度的主要问题之一。三步列表调度算法可以有效解决这一问题。但该算法在截止时间分配阶段只能形成静态的子截止时间。为方便用户部署工作流任务,云服务商为用户提供了的三种实例类型,其中竞价实例具有非常大的价格优势。为解决上述问题,提出了截止时间动态分配的工作流调度成本优化算法(S-DTDA)。该算法利用粒子群算法对截止时间进行动态分配,弥补了三步列表调度算法的缺陷。在虚拟机选择阶段,该算法在候选资源中增加了竞价实例,大大降低了执行成本。实验结果表明,相较于其他经典算法,该算法在实验成功率和执行成本上具有明显优势。综上所述,S-DTDA算法可以有效解决工作流调度中截止时间约束的成本优化问题。     

基于OGSA网格的分层式网格任务调度器设计

文章根据网格任务调度的需求、网格任务调度的特点,在充分分析一般网格任务调度的过程等的基础上,另外考虑到了网格计算环境的一些特点,比如虚拟化、分层次及自治的本质特征,以及在工作流任务协同需求下网格任务的资源依赖、粗粒度、重复执行等特性的前提下,改进设计了一种网格工作流任务主从式分层调度模型,并给出了调度策略和调度算法实现。该调度器模型在实际的网格工作流任务协同系统中得到了较好的应用效果。     

一种云计算环境下的工作流双向调度方法

为降低云计算中工作流调度的时间和成本,提出了一种双向调度算法,以实现后向Backward和前向Forward的双向调度。首先,Backward算法按照每个任务的最迟开始时间进行后向调度;此基础上,为降低虚拟机调度费用,Forward算法尽可能地提前调度每个任务,且在前向调度过程中充分考虑到工作流deadline、最大cost及传输时间的限制,从而实现对虚拟机的动态调度。由实验可知,本算法比BDA算法以及ICPCP算法更节约虚拟机调度成本,提高了调度的灵活性。     

基于均衡适应度的云工作流调度算法

针对工作流任务调度优化问题,提出一种云工作流任务调度遗传算法。为了寻找工作流执行时间与执行代价的同步最优解,建立了遗传调度模型。在个体编码方面,采用了一种二维排列编码方法,可以更好地展现工作流任务间的执行次序;综合考虑任务执行代价与最早完成时间两个因素,设计了一种均衡适应度函数;为了丰富种群个体多样性,引入三种遗传交叉操作和两种遗传变异操作,以产生新的个体,增加了最优解的求解概率。通过数值仿真实验,在多个性能指标上对算法进行分析。结果表明,该调度算法能更好地平衡执行代价与调度效率,性能优于同类算法。     

云环境下基于任务分类和LPM优化模型的调度算法

针对用户任务预算不足或期望完成时间较短,云服务方无法保障任务全部完成,提出基于任务分类和线性规划优化模型调度策略,使任务完成数最大化,同时考虑任务重要性。算法根据任务长短及重要性进行分类,然后建立任务计算资源关系矩阵及3个相关约束条件,以任务完成数最大化为目标函数,搭建线性规划模型,并给出算法实现。模拟实验表明,在同样的用户任务预算和期望完成时间条件下,该算法任务完成数最大值明显高于经典算法。