Energy-efficient scheduling algorithms for real -time systems

Over the past several years, many embedded real-time systems have emerged with energy conservation requirements. Most of these systems comprise battery-operated microprocessors and I/O devices. The increasingly complex software and faster hardware used by these systems introduce more energy consumption, but battery technology is not keeping up. Therefore, aggressive energy conservation techniques are needed to extend their lifetimes. Traditionally, the research community has focused on processor-based power management techniques, with many articles published on processor energy conservation. On the other hand, research of power conservation for I/O devices as well as the overall system has received little attention. In this dissertation, we first analyze the problem of online energy aware I/O scheduling for embedded real-time systems. We introduce the concept of device slack to represent the length of time that a device can be put in the low power state without causing any job to miss its deadline. Based on the concept of device slack, we propose two online energy-aware I/O device scheduling algorithms based on the preemptive periodic task model: Energy-Efficient Device Scheduling (EEDS) and Energy-Efficient Device Scheduling with Non-preemptible Resources (EEDS_NR). The EEDS algorithm keeps track of device slack for devices and performs device power state transitions to save energy, without jeopardizing temporal correctness. Although EEDS can achieve excellent energy conservation, it can only support fully preemptive system. The EEDS_NR algorithm generalize EEDS to support non-preemptive shared critical regions. Next, the trade-off between I/O-based energy conservation and processor-based energy conservation is studied. Dynamic Voltage Scaling (DVS)-based scheduling algorithms can effectively reduce the processor energy consumption at the cost of increased execution time, which in turn increases the I/O device standby energy consumption. On the other hand, I/O-based Dynamic Power Management (DPM) techniques save device energy by aggressively reducing the time that devices are active, which requires the highest processor speed. Therefore, DVS alone or DPM alone may not achieve the same level of energy conservation that a scheduling algorithm considering both can achieve. To this end, we introduce and evaluate the System-wide Energy-Aware EDF (SYS_EDF) algorithm, which integrates device scheduling and processor voltage scaling to reduce the overall system energy consumption. In summary, this dissertation discusses the design, the theoretical correctness, and the evaluation of a set of energy-efficient scheduling algorithms for real-time systems