Research On The Fault-Tolerant Scheduling Algorithms For Hard-Real-Time Systems

In the fault-tolerant hard-real-time systems, all tasks must be completed before or at the deadlines even in the presence of failures. Otherwise, it will cause catastrophic results. As a result, the hard-real-time systems are widely applied in critical circumstances, such as aviation, military defense. The fault-tolerant scheduling algorithm for hard-real-time systems is to construct the task scheduling orders through software method and then theoretically prove the real-time and reliability. So, it is an important research branch of real-time system. There are various types of hard-real-time systems and new application requirements emerge one after another. The chanllenges pose for the original hard-real-time fault tolerance theory. So, it is quite necessary to expland the exsiting fault-tolerant hard-real-time shcheduling algorithms to meet the new demands.The primary/backup, PB for short, technique is an important fault-tolerance in distributed hard-real-time systes, in which the primary copy and backup copy of the same task should be assigned to different processors. Fault-tolerant rate-monotonic first-fit, referred to as FTRMFF, is a classic algorithm used in distributed real-time systems with rate-monotic scheduling, referred to as RMS, and PB technique as foundation. FTRMFF assigns each task to the first processor, in which RMS-scheduable and reliability are satisfied simultaneously, according to non-decreasing rate-monotonic prority order. The processor allocation by first-fit mode is hard to fully exploit the loading capacity of tasks. To overcome the drawback, first, the definations of slack factor and compact factor are given to indicate the processor idlenss and task compatibility respectively. Then, a heuristic algorithm, called fault-tolerant rate-monotonic compact-factor-driven, is proposed to assign the tasks following the principle of maximal compact factor first, which can make single processor holds more tasks and improve the performance of schedulablility.According to the trigger time, there are two typies of backup copy:active backup copy and passive backup copy. The former starts to be active stimulatively with its primary copy, while the latter doesn't be activated until its primary copy fails. So, the passive backup copy has shorter exection window which is the duration from being active to the deadline. In FTRMFF, the prority of backup copy inherits that of its corresponding primary copy, which is against the full usage of CPU slack, In view of the situation, the fault-tolerant hard-real-time scheduling algorithm based on improving the priority of passive backup copy is propsed. On the basis of strict analysis of worst case response time, the algorithm steals the slack time to implement the fault-tolerance of the tasks with low priorty, which can make passive backup copy meets its deadline. Also, the priority-improving factor searching algorithm is propsed according to the strategy. It is verified that the strategy of improving priority is useful to impove the schedulability and CPU utility by simulations.Essentilally, the strategy of improving priority is propsed to consider the urgent degree of passive backup copy. Simular situation occurs after the processor hardware error and the different instances of the same tasks have different urgent degree. Specifically, when a hardware failure occurs, the task instance in current period is usually more urgent than the subsequent ones. As we know, in RMS algorithm, all instances of the same task have unified prority. So, it is hard to steal the slack to urgent instance by priority adjustment method. A novel strategy of delay in non-urgent period, referred to as DNUP, is propsed. DNUP strategy can postpone the execution of non-urgent instance as late as possible and reserve the slack time for the instance with low priority, thus it has more chance to complete its execution in urgent period. Moreover, the computation of the worst case reponse time in urgent period and maximal delay time in non-urgent period is given accurately. In the uniprocessor real-time system, low-power fault-tolerant scheduling algorithm should consider the DVS technique will increase the transient fault probability. The slack time are completely used to decrease the working voltage not only occupies the reservation for alternative but also increases the energy consumption. Through quantitative analysis on the relationship between voltage/frequency and fault occurring, aimed to minimize the expect energy consumption, the definition of optimal frequency is given firstly. Then, according to the energy-saving efficiency under optimal frequency, each task is assigned an energy priority and a heuristic power-aware fault-tolerant scheduling algorithm is propsed. The algorithm preferentially allocates the slack to the tasks with high energy prority to lower their working frequency to the optimal frequency levels.DVS technique poses more complex effects on distributed real-time systems than that in uniprocessor systems. DVS technique will longer the exection time and this maybe cause the type of backup copy changed from active to passive. The increased redundance will add both hardware and energy overhead.First, analysis on the interplay between fault-tolerance and energy-saving as well as their quantitative needs on processor slack resource is given. Then, the traditional fault-tolerant completion time test (FTCTT) is expanded to power-aware fault-tolerant completion time test (PAFTCTT). Based on PAFTCTT, a voltage slowdown factor calculation is proposed. These slowdown factors not only guarantee that all hard tasks can be scheduled within their deadlines despite of any single permanent fault, but also effectively reduce energy consumption.