Researches On Task Scheduling Algorithm In Distributed Heterogeneous Environment

Distributed system are becoming more and more widely used with it's excellent computing power.Computing nodes in distributed systems are usually performance of heterogeneous.In order to make full use of the computing resources in distributed systems,improve the satisfaction of users' access to computing resources and ensure the fairness of computing resource scheduling,it is necessary to carry out the research of task scheduling in distributed heterogeneous environment.The problem of scheduling is studied.More and more researchers pay attention to task scheduling problem in distributed heterogeneous system environment.The research of task scheduling in distributed heterogeneous system environment has become one of the hot topics in high performance computing.This paper focuses on the distributed heterogeneous enviro nment of independent tasks and dependent tasks,using fog computing as the application scenarios,and assigns and schedules tasks to the computing resources through specific scheduling strategy.A reasonable task scheduling algorithm can shorten the makespan of task set,improve the performance of the distributed heterogeneous system,reduce the average waiting time of scheduled task set,and all of the algorithms in the paper have good stability.The main work and innovation of this paper are as follows:(1)Firstly,the process of association rules classification mining is improved to reduce quantities of candidate sets and frequent sets generated in the classification process,and an improved association rules mining algorithm I-Apriori algorithm is proposed in the paper.Based on I-Apriori algorithm,a fog computing task scheduling model and TSFC task scheduling algorithm are proposed.TSFC algorithm combines the association rules generated by I-Apriori algorithm with the minimum completion time of task.TSFC algorithm is used to schedule tasks to corresponding fog computing nodes.TSFC algorithm is experimented and evaluated by real task scheduling environment in Windows operation system and SimGrid simulation platform in Linux operation system.TSFC algorithm is superior to other similar algorithms in task scheduling makespan and average waiting time,and has a certain ability of self-study of task scheduling.(2)Aiming at the inconsistency of task ready time in online task scheduling,a weighted earliest completion time algorithm for independent task online scheduling is proposed in the paper.The algorithm takes task ready time,task transmission communication time,task scheduling time and task completion time as the parameters of task ranking,and choose the processor with the least earliest completion time or the least number of weighted links to schedule task.Socket programming interface is adopted to realize task configuration,processor configuration,task distribution,task scheduling and return task scheduling information in Java program.The advantages of wEFT algorithm and similar algorithms in task scheduling manespan and average waiting time are compared are proved by experiments.(3)A dependent task scheduling model and task scheduling algorithm IHEFT(Improvement Heterogeneous Earliest Finish Time)algorithm based on global priority are proposed in this paper.The IHEFT algorithm mainly optimizes two aspects,which are task sorting and task scheduling.The variance of task scheduling cost on every processor node and the average communication overhead as the basis of task ordering.In the stage of task scehduling,task duplication of some task nodes in DAG with some conditions can make full use of heterogeneous computing resources and shorten the completion time of task set.Experiment results show that the IHEFT algorithm performs more performance than the HEFT algorithm and the CPOP algorithm in terms of the task scheduling makespan,the average waiting time and the average value of Slack.(4)A multiple DAGs task scheduling model and MDTS(Multiple DAGs Task Scheduling)algorithm based on distributed heterogeneous computing environment are proposed in the paper.The MDTS algorithm combines an entry task node and an exit task node to merge multiple DAG task graphs into a single DAG task graph,then transforms the multiple DAG task scheduling problem into a single DAG task scheduling problem.In the process of single DAG task scheduling,the variance of task scheduling cost and the average communication overhead are calculated on the basis of each task node,IHEFT algorithm is used to schedule the sorted dependent tasks.Experiment results show that the MDTS algorithm performs better performance than the Sequential and the Interleave algorithm in terms of the task scheduling makespan,the average waiting time and the average value of Slack.