Study Of Task Scheduling Technique In The Fault-Tolerant Real-Time Distributed System

Task scheduling in Real-time Distributed Computer Systems (RTDCS) is an issue mat is full of challenge, also a hot research subject nowadays. Because task scheduling problem is a typical NP problem and a critical aspect which directly impacts the system performance, to study task scheduling scheme in RTDCS is of great significance. With the support of the key national preresearch project for the 10th five-year plan, this paper has deeply studied scheduling theory and engineering practice of RTDCS, aimed at large amount of existing real-time relevant period multitasks (RTRPMT) and tasks to be fault-tolerant (TFT).Firstly, the paper studies the theory of task scheduling scheme in RTDCS according to the architecture model and property of RTDCS , proposes principles and method for partitioning tasks, gives the proof of task schedulability and an evaluation system for schedule algorithm.Based on summarized and analyzed the existing problems of the solution for scheduling RTRPMT and TFT, the author constructs a new heuristic function which adequately takes predecessor and successor relation among tasks into account, targeting that the direct successor of current running task is to be given the earliest time to be run. Theoretical proof and simulation suggests that this constructive function has stronger heuristic power, and has better effectiveness for scheduling DAGA task-replication based heuristic static scheduling algorithm is also proposed (namely Processor Pre-allocation Algorithm for DAG tasks, PPA), utilizing the aforementioned heuristic function aimed at RTRPMT. It is demonstrated that PPA is capable of getting shortest scheduling time for the tasks as a whole to be scheduled, and able to reduce the number of processors used while meeting the real-tune requirement Theoretical analysis and simulation is also made, experimental data and comparison table with other algorithms are also presented. Because of no limitation to task granularity, PPA is especially suitable for scheduling fine granularity tasks (also suitable for coarse and medium tasks of course), consequently helpful theoretically and practically for studying task schedule algorithm for RTDCS.According to the principle of fault-tolerant scheduling, combined with characteristics of TFT in RTDCS, the paper puts forward the scheduling model of TFT, corresponding implementation mechanism and the dynamic fault-tolerant scheduling algorithm (namely FTPB) and analyzes its complexity, with experimental data and contrast table compared with other analogic algorithm.Both theoretical proof and practice show that FTPB can efficiently utilize CPU resource and increase the task acceptance ratio without adding extra resource to the system. So FTPB has better fault-tolerant capability and at the same time guarantees the real-time demand of task. Not only is FTPB applicable for periodic tasks, but also for non-periodic tasks.Lastly, the paper proposes the architecture of a fault-tolerant RTDCS, the fault-tolerant design skeleton of the whole system, and the implementation technique of fault-tolerance of a high performance fault-tolerant server, with the presentation of the task scheduling structure figure, schedule mechanism, implementation scheme and a corresponding demonstration system, all of which will be used in the project.