Research Of Scheduling Algorithms In Distributed Systems

Distributed system is an important form for high performance parallel computing. However, before using distributed systems for high performance parallel computing, some difficulties must be solved. The difficulties include parallel algorithm design, task partition, communication coordination and synchronizations, task scheduling, etc. Amongst these various difficulties, task scheduling is the most important issue. If task scheduling cannot be solved effectively, distributed system parallel computing will degrade system efficiency dramatically, even lower performance below that of single computer system.This dissertation systematically overviewed the latest developments of task scheduling algorithms based on task duplication and genetic algorithms. A model of scheduling algorithms is constructed by simultaneously using DAG and Gantt. To overcome the limitations of existing algorithms, this dissertation proposed some optimized and improved algorithmsThe major contributions of this dissertation are:1. This dissertation analyzed the factors that affect task scheduling. Under appropriate hypothesis premise, this dissertation constructed the model of task scheduling algorithms. A series of parameters have been put forward to accurately describe the transformation of task status before and after scheduling. These works built the foundation of the new proposed algorithms.2. This dissertation analyzed the limitations of the existing task duplication based heuristic algorithms, and then proposed two scheduling algorithms for homogeneous system and heterogeneous system respectively. To fully utilize the processor capacity and to improve the scheduling performance, this dissertation defined the maximum idle time slot of processor. In the homogeneous algorithm, this dissertation dynamically determined the critical tasks and overcame the limitations of the existing greedy strategy based algorithms. Furthermore, this dissertation employed both linear merging strategy and nonlinear merging strategy to reduce the number of processors and hence reduce the occupation of processor resources.3. To overcome the limitations of the existing algorithms with fixed genetic operator parameters, this dissertation proposed a self-adaptive genetic scheduling (SAGS) algorithm. Using variational trend of key characteristics of population, SAGS algorithm constructed flexible fitness function, cross probability function and mutative probability function. SAGS algorithm can adaptively adjust fitness, cross probability and mutative probability during evolution process. SAGS employed different genetic operator parameters in different stages and hence significantly improved the situation of premature convergence and convergence stagnation in traditional genetic algorithms.4. This dissertation proposed two knowledge-based genetic scheduling algorithms, KGS and CPGS. To overcome the limitations of the existing algorithms when constructing initial population, Under KGS algorithm, this dissertation employed critical path knowledge and main sequence knowledge in constructing initial population, thus obtained initial population with improved quality. Moreover, this algorithm provided the genetic algorithm with an improved starting point and gained better scheduling performance. Under CPGS algorithm, this dissertation made a simpler and clearer chromosome code scheme, which is easier for genetic operators. Meanwhile, this algorithm optimized the decode algorithm which makes it stronger in adaptability and hence achieved better chromosomes decoding and improved its scheduling performance.5. This dissertation proposed multi-population and level set based genetic scheduling (MPLS) algorithm. To maintain the diversity of population, this algorithm employed evolutional methodology of multi populations and hence overcame the limitations of the traditional algorithms. Different from the sole-population evolution, the multi-population evolution partitioned the initial population into umpty sub-populations. Each sub-population evolved independently according to certain schema. In proper situation, the sub-populations would exchange information among themselves, to maintain the population diversity. In addition, this algorithm introduced level set choice strategy and designed multi-player choice strategy, hence obtained higher convergence speed.