Research On Task Scheduling Strategy Based On Complex DAG Graph In Cloud Environments

Cloud computing is an emerging resource use and procurement delivery system, it appears in the form of a fun and promotes the development of science and commercial applications. Similar to water and electricity, cloud computing provides a real-time, flexible and scalable services to users through on-demand consumption. Cloud computing is designed to allow a completely virtualized way to access large amounts of computing power. Cloud computing aims to provide a practical calculations by integrating resources and providing a single system view. Cloud computing represents a model in which a kind of computing infrastructure can act as a "cloud", companies or individuals can access these applications anywhere in the world.How to assign application tasks submitted by the user to respective processors quickly and effectively, in order to obtain the shortest response time and most effective results, this problem makes task scheduling in cloud computing environments a hot issue in academia. Many classic and new algorithms are applied to the cloud scheduling, these algorithms have made some adjustments and improvements to adapt to heterogeneous, dynamic and scalability of the cloud computing. Cloud computing scheduling in academia today is more and more, also more and more complex. Today many scientific applications, such as bioinformatics, chemistry, astronomy, etc., these applications contain a large number of tasks; there is a complex relationship between mission. These applications require a lot of computation and communication overhead, which in cloud computing system we cannot use a simple diagram to express.This article mainly study task scheduling in cloud computing environment. In this thesis, we mainly use genetic algorithms to assist to complete the task scheduling in cloud computing environments. This thesis focused on representing complex tasks by sophisticated DAG, and scheduling tasks to cloud computing platform for processing.The main contents and innovations are as follows:1、We proposed an adaptive workflow scheduling algorithm IAHA. It’s an improved adaptive algorithm based on HSGA algorithm, after tasks are submitted by users, we turn them into DAG, calculating and sorting tasks in DAG considering the complexity of the DAG topology and precedence constraints. For each chromosome pre-optimized to reduce the number of iterations and faster access to the most optimal solution, then according to the case of population change adaptive crossover and mutation rate to control and guide the algorithm to obtain the optimal solution.2、An improved adaptive heterogeneous algorithm with duplication D-IAHA is proposed. The idle gap in processors is used to repeat tasks which have the largest degree or lasted finish time to achieve the reduction of communication time between tasks which are assigned to different processors, so that the subtasks started ahead of time, the entire scheduled time schedule shortened. At the same time elimination of redundant tasks is taken into account, after dispatching check whether there are redundant repetitive tasks, if any, remove, so as not to increase the computational load of the processor.3、We presented an improved task partitioning strategy with duplication D-ITPS, the algorithm firstly merge tasks in DAG which meet merging conditions, then all of the tasks are divided into small packages, which are scheduled to processors according to Max-Min algorithm. After the completion of basic mapping, detecting whether each chromosome can reduce communication time by duplicating tasks, if possible, duplicate this task in the idle gap of processor to reduce the total schedule length.4、CloudSim is used in simulation experiments, and three algorithms proposed in this paper are compared with other these types of algorithms by experiment to verify the feasibility and effectiveness of three algorithms in this paper.