允许违反局部时间约束的科学工作流调度策略

A scheduling policy of scientific workflows allowing the violation of local time constraints

提高科学工作流在云环境中的执行效率、降低执行费用受到广泛关注。用户期望的局部QoS约束与工作流的总体执行效率之间往往存在矛盾。针对该现象,在前期的研究基础上提出一种允许违反局部时间约束的科学工作流调度策略。通过对已聚簇的工作流任务集使用任务后向优先合并的方法,可实现任务间空闲时间片的合理利用,进而优化科学工作流的执行时间;另外,为充分利用任务的松弛时间,提高工作流的整体执行效率,允许部分任务的调度违反局部最晚完成时间的约束。实验结果表明,该策略能提前科学工作流的最早完成时间,提高处理机的利用率,并最终降低工作流的执行费用。

Improving the execution efficiency as well as reducing the execution cost of the scientific workflows in cloud is important. Focused on the conflict between user-desired local QoS constraints and the overall execution efficiency of the workflow, we propose a scheduling policy of scientific workflows allowing the violation of local time constraints. Based on backward merging of task clusters, free time spans between workflow task executions can be exploited, and the whole execution time of the workflow can be optimized. Furthermore, in order to make full use of the slack time during task execution and improve the overall efficiency of the workflow, some workflow tasks are permitted to violate the local constraint of the latest finish time. Experimental results show that the policy can bring forward the earliest finish time of the workflow and improve the utilization ratio of processors, and eventually lower the execution cost of the workflow.