Real-time task scheduling algorithms for maximum utilization of secondary batteries in portable devices

The spread of portable devices emphasizes the importance of low power energy techniques. The authors present dynamic real time scheduling algorithms which maximize utilized time of the secondary battery while preserving a deadline of real time tasks with frequency control. Firstly, we show that the decrease in secondary battery consumption is minimum when executing a program with as low a CPU frequency as possible. Secondly, we present a real time scheduling algorithm with arbitrary frequency control, and its correctness and computational complexity. For each task, the computational complexity of the algorithm is O(n) in general, where n is the number of tasks waiting execution; and that is O(1) in the amortized analysis when each task arrives in the order of its deadline. Thirdly, we address a scheduling problem with discrete frequency control. A decision problem corresponding to the scheduling problem is shown to be NP-complete when a frequency can be changed only at a task switching. Then, when the frequency can be changed at an arbitrary time, we describe an optimal scheduling algorithm which maximizes the utilized time of the secondary battery. The computational complexity of the algorithm has the same order as an algorithm in the case of arbitrary frequency