Dissertation > Excellent graduate degree dissertation topics show

Research on Energy-Efficient Scheduling Algorithm of Distributed Real-Time Systems

Author: ChenAi
Tutor: ZhouXueHai
School: University of Science and Technology of China
Course: Computer System Architecture
Keywords: distributed real-time systems energy-efficient design real-time scheduling fault-tolerant real-time scheduling formal schedulability verification frequency related time Petri net (FRTPN)
CLC: TP316.4
Type: PhD thesis
Year: 2007
Downloads: 532
Quote: 4
Read: Download Dissertation


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.

Related Dissertations

  1. Research and Implementation of Support Layer Prototype of Internet of Things (IoT) Service Platform,TN929.5
  2. Embedded real-time operating system ARTs-OS 's EDF scheduling improvements,TP316.2
  3. Fault-tolerant real-time systems based on energy-efficient scheduling algorithm,TP316.2
  4. The Research of EDZL Real-time Scheduling Algorithm for Multiprocessor Systems,TP316.2
  5. Research on Real-time Scheduling for Static Segment in FlexRay Systems Based on Hybrid Genetic Algorithm,U463.6
  6. Research on Real-Time Scheduling Algorithm for Time-Triggered CAN Systematic Matrix with Fault-tolerant Model,TP273
  7. The Modeling Optimization and the Algorithm of IO Jitter and Latency in the Hard Real-time Task Scheduling,TP316.2
  8. Codesign of Control and Scheduling for Networked Control Systems,TP273
  9. Study on Modeling and Scheduling Optimization of FMS for Systemic Workflow,TH165
  10. The Research and Optimization of Real-time Technology in Embedded Linux Based on One-shot Clock,TP316.81
  11. Industrial Ethernet nodes of development and communication protocols,TP273
  12. Interactive Scheduling Mechanism for Virtual Experiments Based on Multi-domain Modeling,TP391.9
  13. Consider distributing information attributes Scheduling,TP30
  14. Researching Scheduling Algorithm of Embedded Linux Operating System,TP316.81
  15. Based on the the ARM9 embedded real-time linux system platform to build,TP368.12
  16. Study on the Method for Optimal Load Dispatch of Thermal Power Units Under the AGC Mode,TM621
  17. A Real-time Scheduling Model for Demand Responsive Campus Bus System,F572
  18. Research on Timing Analysis of Distributed Real-time Systems,TP316.2
  19. Research and Design of Scheduling Algorithm Based on RT-Linux,TP316.2
  20. Research on Methods of Real-time Scheduling in Urban Rail Transit,U239.5
  21. Research and Improvement in Task Schedule of the Enbedded Real-Time Operating System,TP316.2

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer software > Operating system > Distributed operating systems, parallel -type operating system
© 2012 www.DissertationTopic.Net  Mobile