A dynamic task scheduling algorithm for battery powered DVS systems

Battery lifetime enhancement is a critical design parameter for mobile computing devices. Maximizing battery lifetime is a particularly difficult problem due to the non-linearity of the battery behavior and its dependence on the characteristics of the discharge profile. In this paper we address the problem of dynamic task scheduling with voltage scaling in a battery-powered DVS system. The objective is to maximize the residual charge and the battery voltage after the execution of tasks. We present here a two phase algorithm: in the first phase (off-line) a battery-aware algorithm schedules the tasks in a hyper-period assuming WCET. In the second phase (on-line), the algorithm reassigns the voltage levels based on the additional slack generated due to the AET being less than the WCET. Simulation with 10,000 random examples shows that the proposed algorithm does significantly better than the competitive low power real time scheduling algorithm. We extend this procedure to handle scheduling on multi-processor environments.