Energy-Efficient Task Scheduling Based On Interval Partitioning In Embedded Real-Time System

With the restriction of volume and the using environment, it is difficult to charge for embedded devices, in some situation, the life cycle of embedded devices is the same with the supporting time of battery. Energy management has became one of the major goals in embedded systems research. Over the past decade, the research community has made signif-icant progress in the area of low-power system design. On the industry side, the Advanced Configuration and Power Interface (ACPI) standard has moved power management to the operating system level by providing system calls for predictive shutdown of system compo-nents. Many applications running on power-limited systems (such as embedded controllers) are subject to timing constraints. As a result, the real-time and energy-aware operation is a highly desirable and sometimes critical feature of an embedded system.Merging the small slacks into bigger one to enlarge the average length of system slacks is a very useful method to solve the problem of system energy. An interval partition based method is proposed to get a larger average length of system slacks. The partitioned interval is called CI since it has a Crenel-like shape. To merge all of the small slacks in a CI, no more than one deadline in CI for every task. Task instances can only be executed in the two side of CI, and the slack is located in the middle of CI. The task instance in CI arc classified into two types, the mandatory instance and the optional instance. In CI, the mandatory instance must be executed in the front side of CI and must complete its workload in CI, some workload of optional instance can be delayed to execute in the following CI, and the optional instance needs to execute in the end side of CI. Since there is at most one long slack in a CI, it can help the energy management algorithms to reduce system energy consumption.DPM (Dynamic Power Management) can transform the idle slack into lower power mode to get the energy saving. In different device models, two dynamic priority scheduling algorithms which use EDF are proposed to manage the system energy consumption. Target-ing at a single device model where all the tasks access the same and only device, scheduling algorithm namely CI-EDF is proposed to schedule the task instances in each Crenel-Interval to guarantee the schedulability (the upper utilization bound of the task set is1) of the task set. CI-EDF give the detail calculation methods to calculate the workload which should be completed in current CI for every task instance and the start time point that the optional task instances can be executed. CI-EDF has a time complexity of O(n2)(n is the number of the tasks in the system), and thus is quite efficient as an on-line scheme. Next, targeting at a more general multiple devices model where a task may access multiple devices and a device may also be accessed by multiple tasks, we propose another scheduling algorithm namely CI-EDFm, which has a time-complexity of O(nm)(m is the number of the devices in the system). In CI-EDFm, Device Crenel-Intervals (DCIs) for each device are calculated based on the properties of the tasks which need to access the device. Considering that a task instance may need to access multiple devices and thus be located in multiple DCIs, a weight-ing factor based strategy is designed to help determine whether the task instance should be delayed or not, with the objective of minimizing the energy consumption. To further reduce the energy consumption, DVFS is integrated into CI-EDF and CI-EDFm. Moreover, con-sidering that the task actual execution time is usually less than its worst case execution time (WCET), some reversions of CI-EDF and CI-EDFm are made to reclaim the dynamic slacks to get more energy saving.The transistor feature sizes of modern processors become more and more small, Smaller transistors have a lower threshold voltage and, because sub-threshold leakage grows exponentially, more current is lost into the transistor substrate. Processors with smaller transistors can run at higher frequencies with lower supply voltages. The net effect is a reduction in the dynamic range of power consumption that DVFS can utilise and an increase in static power consumption, the proportion of static power in processor power is increasing. Then, CI-Based algorithm CI-RM is applied to static priority scheduling to reduce the leakage power consumption of system. In CI-RM, every task has a threshold argument, which is calculated by the task period and the utilization of task set. CI-RM adopts a simple rule to delay task instance, in a Crenel-Interval, if the overlapping length between task instance and Crenel-Interval is bigger than the task’s threshold argument, this task instance needs to complete its overall workload in current Crenel-Interval, otherwise, this task instance must be delayed. A detail proof has been given to guarantee the schedulability of the task set. We also give the utilization range of the task set which can use CI-RM to schedule. CI-RM has a complexity of O(n). The experiments show that compared with other algorithms, more task set can scheduled by CI-RM, the average length of slacks which produced by CI-RM is two times than other algorithms, and CI-RM can get a better energy saving performance(12%at most).