A Multi DAG Scheduling Strategy Based On Backfill In Cloud Computing

Cloud computing is a new business model that integrates traditional technologies such as virtualization,large-scale storage,distributed computing,and parallel computing.Task scheduling based on Directed Acyclic Graph(DAG)is one of the key technologies in cloud computing.According to the needs of users and tasks,it adopts appropriate scheduling strategies to allocate a large number of different tasks to the appropriate processor resources for processing to achieve the goal of minimizing task completion time and total time cost.In this paper,the DAG scheduling problem of cloud computing and worldwide literature of related technologies are classified from the perspectives of technical strategy,scheduling target,and scheduling environment.The research status of single DAG resource scheduling and multi DAG resource scheduling algorithms in cloud computing are explored,and the advantages and disadvantages of various scheduling algorithms are analyzed and summarized.For the static task scheduling problem of a single DAG,the HEFT algorithm and the IHEFT algorithm can provide satisfied performance generally,but they can have better results under certain circumstances.The k-HEFT is proposed in this paper as an improved HEFT algorithm.For the same scheduling problem,when k takes different values,the algorithm can present different scheduling results.Therefore,under the premise of appropriately increasing time cost,by comparing the scheduling results when k is taken different values,k-HEFT generally has better scheduling results compare to HEFT.Experimental results show that k-HEFT algorithm can effectively shorten the Makespan of DAG scheduling and optimize resource utilization.For multi DAG scheduling problem,this paper proposes a scheduling method based on backfill strategy.In the case of multiple DAG arrival at different times,during the scheduling process,the late arrived DAG occupies the idle period left by the previously arrived and scheduled DAG.Therefore,idle period on the resources is reduced to shorten the completion time of the scheduling,and utilization of resources can be optimized.