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

关键词: 云计算, 科学工作流, 预算分配, 工作流调度, 资源调度

Abstract: The scientific workflow deployment in the cloud environment is different from the traditional independent task scheduling,and the scheduling time and cost should be considered simultaneously.To address the problem,a scientific workflow scheduling method based on budget allocation is proposed.The mapping between workflow tasks and virtual machine resources is divided into two stages:budget allocation,and resource provision and scheduling.In order to optimize budget usage,a budget allocation algorithm based on fast-priority,called FFTD,and budget allocation algorithm based on slow-priority,called SFTD,are designed to achieve sub-allocation of budget among tasks.The task selection is performed based on the descending order of the earliest completion time of the task,and the resources are allocated according to the sub-budget of the single task when the virtual machine is reusable,thereby ensuring smooth scheduling of the workflow task.Five kinds of conventional types of scientific workflows are introduced to test the performance of the algorithm under different types of workflow structures and different budget constraints.The results show that the FFTD algorithm has shorter scheduling time and higher virtual machine resource utilization and satisfaction rate of budget constraints than the BDT-AI algorithm in 72%,88%and 84% experimental scenarios,and the overall performance is better.

Key words: cloud computing, scientific workflow, budget allocation, workflow scheduling, resource scheduling

中图分类号: 

• TP393