Research On Optimal Scientific Workflow Scheduling Algorithm With Deadline Constraint In Cloud Environment

Iaa S(infrastructure-as-a-Service)cloud computing platform shows great potential in building a flexible,efficient and low-cost operating environment for scientific applications such as scientific workflow.In addition,the “pay-as-you-go” billing mode of cloud service allows users to access "unlimited" resources,which greatly reduces the threshold of high-performance scientific computing.Although the Iaa S provides many advantages for the implementation of scientific workflow,the efficient implementation of scientific workflow in cloud environment still confronts the problem that resource supply and task scheduling are difficult to coordinate.Aiming at the requirements and problems in the real world,this paper proposes two optimization strategies for workflow scheduling with deadline constraints,which can achieve the user's requirements and minimize the execution cost.Based on the traditional heuristic algorithm,this paper proposes a deadline constrained scientific workflow scheduling algorithm DCWS(Deadline-Constrained Workflow Scheduling).The algorithm combines three steps to optimize the execution cost.Firstly,when DCWS calculates the priority of workflow tasks,it takes into account the communication overhead between tasks and the possible negative impact of putting a large number of parallel tasks together,so as to avoid the problem of a large number of parallel tasks gathered together.Secondly,the DCWS algorithm improves the resource utilization through the mechanism of task backfill and deadline constraint violation penalty in the actual scheduling,and accelerates the follow-up tasks in the case of the delay of the previous tasks to ensure that the overall deadline is met.Thirdly,the DCWS algorithm reduces the execution time of the workflow through the instance type upgrade strategy without increasing the execution cost of the workflow.At the same time,the instance degradation strategy is introduced to reduce the execution cost while meeting the deadline constraints of the workflow.The experimental results show that DCWS algorithm can generate a lower-cost scheduling scheme than the existing scheduling algorithm under the condition of meeting the deadline constraints of workflow.On the basis of DCWS algorithm,this paper proposes a deadline constrained scientific workflow cost optimization algorithm based on spot instances.Spot instance is introduced by cloud resource providers to attract users to use cloud and improve resource utilization.Compared with on-demand instances,spot instances have a great advantage in cost-saving,which can help users run large-scale computing tasks at a low cost.However,spot instances may be recycled by cloud providers at any time,and the execution time is uncertain,which has a negative impact on the execution of scientific workflow.Therefore,this paper proposes a segmented optimization strategy,which uses different bidding rules for different segments.In particular,the algorithm divides the set of tasks deployed on the same instance according to the billing interval.Then the critical path tasks are assigned to the on-demand instances.And spot instance is introduced to execute fine-grained tasks and low-utilization segments.When dealing with spot instance,the algorithm introduces a tricky-auction method.By putting forward an extreme bid to get an free instance hour.The experimental results show that the segmentation optimization strategy based on spot instances can further optimize the execution cost under the condition of meeting the deadline constraints of workflow.