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

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

软实时分布式系统中的时间期限分配

在分布环境下 ,任务在多个不同的站点上有处理要求。一个分布式任务需要划分成几个子任务 ,每个子任务在指定的站点上执行。在实时系统中 ,当要完成一个分布式任务时 ,应用系统的设计者经常要把总体时间细化。本文提出如何自动把总体时间期限转换为子任务的时间期限的方法。

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

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

A novel resource co-allocation model with constraints to budget and deadline in computational grid

To address the issue of resource co-allocation with constraints to budget and deadline in grid environments, a novel co-allocation model based on virtual resource agent was proposed. The model optimized resources deployment and price scheme through a three-side co-allocation mechanism, and applied queuing system to model the work of grid resources for providing quantitative deadline guarantees for grid applications. The validity and solutions of the model were presented theoretically. Extensive simulations were conducted to examine the effectiveness and the performance of the model by comparing with other co-allocation policies in terms of deadline violation rate, resource benefit and resource utilization. Experimental results show that compared with the three typical co-allocation policies, the proposed model can reduce the deadline violation rate to about 3.5% for the grid applications with constraints to budget and deadline. Also, the system benefits can be increased by about 30% compared with the those widely-used co-allocation policies.