Research On Energy-Efficient Scheduling Algorithm Of Distributed Real-Time Systems

Today, real-time systems especially distributed real-time systems in safety-critical domain are ubiquitous and have wide application perspective. Real-time systems have the extremely strict demand on timeliness and the reliability. To avoid the catastrophic consequences of missing deadlines, it is essential that real-time task meet deadlines even in presence of faults. Moreover, processor performance has improved at the expense of drastically increasing power consumption in recent years. Energy consumption has become a critical constraint in real-time system design. How to guarantee task deadlines while staying within energy constraints has already become the issue which is urgently awaited to be solved in the research field of real-time system. The real-time scheduling policies can safeguard timeliness and the reliability in real-time system. Energy-efficient real-time scheduling which is an combination of DVS mechanism and real-time scheduling algorithm, exploring its latent energy conservation on system level, has become the most effective strategy in real-time system energy consumption optimization design.In view of distributed real-time system design demand, we take the energy-efficient design as the main starting point, separately conducts the research in the schedulability verification, real-time task scheduling, fault tolerant scheduling in distributed hard real-time systems. We proposed a series of correlations methods and strategy. Furthermore, we complete the energy-efficient scheduling for distributed real-time systems by the time.Schedulability verification of real-time systems is an essential way to determine whether a given task set is schedulable. Due to massive complex characteristics of distributed real-time systems, it's indispensable to use the more rigorous formalized method to guarantee task deadlines. To support the research on the energy-efficient scheduling algorithm for real-time tasks, an extended time Petri net model, FRTPN (Frequency Related Time Petri Net) is proposed. FRTPN introduces the frequency space and frequency-related firing interval of the transition, which support modeling distributed real-time systems and integrating the schedulability verification into the energy optimizations. We define FRTPN with the inhibitor arcs for fault recovery. Moreover, formal semantics of FRTPN is presented and methods for energy evaluation and a reachability analysis method which is based on state space enumeration approach are given. The feasibility of the proposed approach is proven by the fault tolerance scheduling in real-time systems with checkpoint scheme.Dynamic voltage scaling (DVS) is an effective technique for reducing processor energy consumption, and can be effectively applied into the real-time systems for energy-efficient real-time scheduling. Most existing scheduling can not describe system comprehensively to model characteristic in the distributed real-time systems. Consequently, they can not be applied to the complicated design cases. Taking the effect of frequency scaling to energy saving and slack time waste in system into account, we propose an energy/time gradient-based DVS scaling algorithm with formal verification using FRTPN as specification models. In addition, we present a heuristic task allocation algorithm to reduce processor energy consumption. By exploring state space transformation rule, we enhance the efficiency of the algorithm.Fault-tolerance is typically achieved through component redundancy and replicated execution of tasks. In real-time systems, it is necessary to ensure that task re-execution does not jeopardize the timely completion of tasks. Energy analysis related to scheduling and timeliness of real-time systems has been extensively investigated. However, there is no previous attempt in energy analysis of primary/backup fault-tolerance mechanism. In this dissertation, we investigate an integrated approach that provides fault tolerance and DVS mechanism in real-time systems. Firstly, we propose a primary/backup fault-tolerance static DVS scheduling algorithm, setting processor frequency off-line. Being based on this work, a dynamic DVS scheduling algorithm adopts a reclaiming scheme to collects the slack time and residue time budget and redistribute them to other tasks. And then, we develop a heuristic algorithm, which delays the release time of the backup task as much as possible, thereby making it more likely for the primary with more time to execute and decrease energy. At last, experimental results demonstrate that the proposed method can reduce energy consumption of fault tolerant real-time system.In summary, the contributions and innovations of this dissertation include:(1) An extended time Petri net model, FRTPN (Frequency Related Time Petri Net) is proposed, which supports modeling distributed real-time systems and integrating the schedulability verification into the energy optimizations.(2) A energy/time gradient-based DVS scaling algorithm (ETGBS) is proposed, which put more attention on frequency scaling influencing to energy and task execute time. And a task allocation algorithm (UBTA) is proposed, which can decrease processor frequency switching energy consumption.(3) For the first time, design of energy-aware scheduling algorithms, and a deadline allocation algorithm in primary/backup fault-tolerant real-time systems takes DVS mechanism into account. It can guarantee timeliness and reliability while bringing more substantial energy saving.