Research On The Task Fault-tolerant Scheduling Optimization Algorithms For The Distributed Real-Time System

With the growing popularity of computer application,the distributed real-time system is more and more widely used.The real time system must be able to deliver correct results in a timely manner even in the presence of faults.The timeliness and reliability have already become the issue which is urgently awaited to be solved in the research field of the real-time system.The real-time fault-tolerant scheduling algorithm is an effective method to safeguard the timeliness and the reliability in real-time system.The effective task fault-tolerant scheduling algorithm plays a very important role in enhancing the system performance and assuring the schedulability and the reliability in the real-time system.The distributed real-time system must make sure the task executed correctly in the single machine and completed timely even in the presence of transient faults,and also make sure the task completed correctly and timely even in the presence of permanent faults.A lot of research on the fault-tolerant scheduling algorithm in the real-time system has been conducted,but there do exist some problems that have not been resolved.So this thesis has conducted a comprehensive analysis on the task fault-tolerant scheduling algorithm in the real-time system,and studies the optimization of the task fault-tolerant scheduling algorithms deeply on the single machine and the task fault-tolerant scheduling algorithms of the distributed real-time system in the presence of faults.The contribution of this thesis can be summarized as follows:Firstly,the local optimization checkpoint interval algorithm is proposed based on the rollback recovery fault-tolerant model,by which the number of the faults can be determined by the task worst case response time and the interval between two consecutive faults.The algorithm can minimize the task worst case response time and can overcome the defects that some fault-tolerant model can only tolerant one fault and that the checkpoint intervals of some fault-tolerant algorithms are based on the optimization interval under the single fault assumption or are based on the optimization interval under the assumption of a certain number of faults.The checkpoint global optimization algorithm is proposed to optimize the checkpoint intervals of all the tasks,by which to further reduce the task response time when many tasks executing concurrently and promote the real-time system fault-tolerant resilience and the schedulability.Secondly,the task worst case response time formula under the fault-tolerant priority mixed strategy is deduced based on the local optimization checkpoint interval.Then the fault-tolerant priority search algorithm under the priority mixed strategy based on the local optimization checkpoint interval is proposed according to the schedulability analysis.The algorithm can make the task that affected by the fault preempt the slack time of other tasks to further reduce the task response time.Thirdly,the task worst case response time formula based on the global optimization checkpoint interval and the fault-tolerant priority mixed strategy is deduced.The optimization model that can minimize the task worst case response time by the checkpoint interval global optimization and the fault-tolerant priority search is designed.The algorithm that can globally optimize the checkpoint and search the fault-tolerant priority is proposed to solve the optimization model based on the Mixed PSO.Finally,the reliability computing method that can consider both the node fault and the link fault is proposed,the method is based on the general scheduling mode.The 0-1 integer programming model that can descript the general scheduling problem is established.The reliability aware multi-duplication task general scheduling algorithm is proposed based on the evolutionary mechanism of the genetic algorithm.The algorithm can resolve the 0-1 integer programming model by search the task duplication scheduling node and the time that the task can start to execute.The algorithm can minimize the task scheduling Makespan while satisfying the task reliability requirements.The proposed optimization and scheduling algorithms have been thoroughly evaluated with extensive simulation experiments.The checkpoint interval local optimization can reduce the task worst case response time,the checkpoint global optimization can further reduce the worst case response time of the task set.The fault-tolerant priority mixed strategy can further reduce the task worst case response time.The fault-tolerant priority mixed strategy based on the global optimization checkpoint interval can further reduce the task worst case response time than that based on the local optimization checkpoint interval in most cases.The fault-tolerant scheduling algorithm that adopts the general scheduling mode can further reduce the worst case response time than that adopts the strict scheduling mode.