Deadline Constrained Scheduling Optimization Algorithm for Workflow in Clouds Using Spot Instance

Abstract

In recent years,due the advantages of on-demand resource provisioning and pay-as-you-go billing model,it is increa-singly popular to execute large-scale workflow applications in cloud environments.Cloud service providers offer resources with different capabilities at different prices.In order to improve resource utilization,many cloud service providers provide transient resources at a much lower price than normal resources.Spot instance provided by Amazon EC2 can greatly reduce the execution cost of workflow.One of the main problems of workflow scheduling in cloud is to find a cheaper scheduling method on the premise of meeting the deadline.To solve this problem,a deadline constrained scheduling optimization algorithm for workflow in clouds using spot instance(Spot-ProLis) is proposed.The algorithm takes into account the case that the data transmission time of the same virtual machine is zero,and uses the method of probabilistic upward rank to order tasks.In the resource allocation stage,spot instances are added as candidate resources,which effectively reduces the execution cost.Experiment results show that compared with the classical ProLis algorithm,Spot-ProLis has significant advantages in reducing the execution cost.

Keywords

• cloud|workflow scheduling|spot instance|deadline|cost|optimization