Research On Grid Resource Scheduling Algorithm And Simulation Technology For Grid Computing

Grid is a set of emerging technologies built on Internet, its emergence sets off the third technology wave following the traditional Internet and World Wide Web (WEB). Grid is an environment that integrates calculation and resources, which can absorb all kinds of computing resources all over the world to achieve the various resources sharing thoroughly. Resources scheduling is an important element of the grid research, aiming at achieving the optional scheduling of the tasks submitted by users and improving the overall throughput of the grid system. Because the resources in Grid are heterogeneous inherently, dynamic and self-ruling, it makes the resource scheduling in Grid more complicated. Grid resource scheduling problem is proved to be an NP complete problem, and genetic algorithms are proved to be sharpen tools to solve NP-complete problem. Therefore, this paper made deep research on the theory of grid computing, made a full analysis and comparison of the basic idea and the advantages and disadvantages of the existing grid resource scheduling algorithm. On this basis, this paper selected the genetic algorithm as the basis for improvement and proposed a grid resource scheduling algorithm based on QoS Guided GA.This paper made lot of theoretical research to established good foundation for the future work. This paper summarized the basic concepts, features and architecture of grid computing; introduced the characteristics, processes, organizational models, the scheduling execution flow, evaluation criteria, and several common grid resource scheduling algorithms in detail; described the emergence and development of genetic algorithm, its basic principle and implementation process in detail; made comprehensive analysis and comparison of the technical features, advantages and disadvantages, and the limitations and trends of several prevalent grid simulation technology.According to some shortcomings of the simple genetic algorithm (SGA)in grid scheduling, this paper drawed on quality of service(QoS) mechanism of economic models, proposed a series of improvements, the main content of the article includes 5 aspects as below:First, the traditional grid scheduling algorithm based on SGA, only has a simple scheduling object that is improving the overall throughput for the grid system, ignoring the factors of grid quality of service, can not guarantee the grid user's requirements for the quality of service. This paper aiming at ensuring the throughput of the grid system and grid quality of service, introduced the deadline and budget two QoS indicators of the economic model into the genetic algorithm, and proposed a grid resource scheduling algorithm based on QoS Guided GA.Secondly, in the previous study of grid scheduling algorithms the relationship between sub-tasks mostly were assumed that they were independent, had no dependent relationships, to simplify the study, with no consideration of the priority among sub-tasks. This paper considered three aspects of the task requirements including the task requirements of resources, the time, and cost constraints, gave the computing formula for task QoS priority, in order to determine the priorities between different subtasks.Thirdly, this paper improved the original fitness function in order to select the individuals with smallest time span and high quality of service. It improved the original search method with single object that is minimizing the time span, greatly increased user satisfaction degree with quality of service.Fourthly, the simple genetic operation of SGA has been improved in this paper. Select operation integrated"Roulette"with the best individual saving strategy; the implementation of the crossover operation can be judged with calculating the Hamming distance between two individuals; mutation operation introduced the competition mechanism before and after the mutation. With these improvements, it can solve the "premature" convergence and "cheating" problem of SGA.Finally, this paper designed all components of the grid resource scheduling algorithm based on QoS Guided GA in detail. It selected full-featured, widely used grid simulator GridSim to doing simulated experiment, programmed the improved algorithm, compared with the traditional SGA and Min-Min algorithm through many experiments. Finally, the advantages of the improved algorithm's performance were verified.