Research For Algorithm Of Scheduling Multi-DAGs With Deadline On Cloud Computing

With the rapid development of cloud computing technology,more and more large-scale scientific computing application workflows make use of cloud computing resources to calculate.What's more,most of these applications can be expressed as DAG(Directed Acyclic Graph).The problem of scheduling multiple DAGs sharing resources with deadline has attracted widely attention of researchers.In this article,we design a framework for DAG scheduling on cloud computing.We propose MTMD(Maximize Throughput of Multi-DAG with Deadline)scheduling algorithm for maximizing throughput of multi-DAGs and CFS(Cost Fairness Scheduling)scheduling algorithm for the fair cost-optimization.The main research results and innovation on this dissertation are listed as follows:(1)We design a framework for DAG scheduling on cloud computing.The framework consists of resource capacity estimator,resource acquisition module,scheduling model and execution manager.Users make definitions of the workflow,resource and deadline,and submit applications to the workflow management system,then the workflow management system realize the access to the executive resource,meanwhile the scheduling and execution of the task.(2)As for the multi-DAGs scheduling problem with deadline,we proposed a MTMD algorithm which can schedule DAGs according to the urgency degree of the DAGs,the algorithm can also testify the DAGs that could not be scheduled in time,and abandon the DAGs with minimum level of execution when necessary,so as to improve the efficiency and throughout of the scheduling.To measure the performance of the scheduling algorithm of multi-DAG with deadline,this paper also conducted a comparative experiment to this algorithm with the algorithm of EDF,LLF and MDRS.According to the results and the analysis of the experiment,the scheduling performance of the MTMD algorithm is better than other three algorithms,no matter the degree of constraint term is emergent or loose.(3)Base on the MTMD,we also proposed a fair optimization algorithm for the calculation cost of the multi-DAG,taking the ratio of the calculation cost for unit load to the urgency degree of its constraint as the measurement standard of its equity.We take the standard deviation of the inequities of multi-DAGs as the inequity index of DAGs.The experiment compared the CFS algorithm with the MTMD algorithm,and the result showed that the CFS algorithm can reduce the inequity of the cost effectively and can reduce the whole executive cost of DAGs.