Research On Several Problems Of Scheduling Multiple Dags Sharing Resources

In recent years, along with the development of the technologies forheterogeneous distributed computing, such as Grid and Clouds workflow systems,the problem of scheduling concurrent multiple DAGs sharing resources inheterogeneous distributed computing systems recently has attracted widely attentionof researchers. At present, the research about scheduling concurrent multiple DAGin heterogeneous distributed systems have been making progress, however, there aremany problems need to be given a further research and to be resolved.This dissertation focus on some problems of scheduling for multiple DAGssharing resources in heterogeneous distributed system to spread research, whichinclude scheduling for multiple DAGs with multiple priorities, the throughputmaximization of concurrent multiple DAGs with deadline-constraints, costoptimization and fairness of cost optimization. The solution to these problems wouldbe beneficial to improving resource usage, reasonably dealing with the schedulingrelationship among the multiple DAG applications, and effectively reducing costs ofmultiple DAG applications in some heterogeneous distributed computing systems,such as Grid and Clouds workflow systems. Therefore, these research results willhave both theoretical and applicable value.The main research results and innovation on this dissertation are listed asfollows:(1) To the problem of scheduling multiple DAG applications with multiplepriorities submitted at different times, a new scheduling system model for DAGswith multiple priorities, an improved method to famous Fairness algorithm and aBackfill algorithm are proposed. And then, based on the above new model and twoalgorithms, a hybrid strategy MMHS is also proposed, which not only can solve thefairness of scheduling multiple DAGs with the same priority level submitted atdifferent times, but also can ensure that the execution of the DAGs with higherpriorities cannot be influenced by the DAGs with lower priorities. The relatedexperimental results show that the MMHS can reasonably schedule multiple DAGswith multiple priorities and improve utilization rate of resources better. In addition,the experimental results about scheduling two-DAGs show a significant “TrailEnding” phenomenon, which is valuable for academic study and application.(2) To the problems of the throughput maximization of DAG in schedulingconcurrent multiple DAGs with deadline constraints sharing resources, we proposethe notion of “oversaturation” situation first, which may be caused by rigidconstraints from deadline of each DAG, and propose two methods of the “relative strictness” and “laxity”, which are used to measure the urgency degree of a DAG’sdeadline. Then, we propose a scheduling algorithm called MDRS based on relativestrictness and propose another alternative algorithm called LLF-Sim-MDRSbased onthe mechanism of combining the LLF (Least-Laxity-First) with the MDRS. The twoalgorithms can schedule multiple DAGs with deadline constraints in terms ofdifferent methods of measuring deadline urgency degree and deal with the possible“oversaturation” situation. Once the “oversaturation” is detected, the two algorithmstry to drop some DAG as less as possible while maximizing overall throughput ofDAGs through the method of combining Stack with Backtracking. The relatedexperiments show that both the MDRS and LLF-Sim-MDRScan effectively improve therelated performances, whereas the MDRS is optimal.(3) To solve the problem of cost optimization for multiple DAGs on the basis ofmaximizing overall throughput of DAGs, we propose an algorithm called PDTCbased on the MDRS and the probe of the total cost decreasing. If there is any sparetime left for any DAGs after maximizing overall throughput of DAGs by the MDRS,then the PDTC attempts to reduce total cost of the multiple DAGs while meetingtheir deadlines. Last, experiments demonstrate that, in contrast with MDRS, thePDTC can effectively reduce the total cost of concurrent multiple DAGs.(4) To the problem of the fairness in the cost optimization for multiple DAGson the basis of maximizing overall throughput of DAGs, the possible greatunfairness resulting from the “Matthew Effect” in the cost optimization is alsoanalyzed and discussed. And then, the related methods used in evaluating thefairness about the cost optimization and an algorithm called CDVRS, which is basedon the method of maximizing cost decrease on variance of the relative strictness, areproposed. The related experiments demonstrate that, in contrast with MDRS andPDTC, not only can the CDVRS effectively reduce the total cost of multiple DAGsto be scheduled, but also can improve the metric about the fairness of costoptimization.