Efficient Algorithms for Jitterless Real-Time Tasks to DVS Schedules

In this paper, we focus on periodic task scheduling on a variable voltage processor with d discrete voltage/speed levels. We propose an intra-task DVS algorithm which constructs a minimum energy schedule for k tasks in O(d+k log k) time. We also give an inter-task DVS algorithm for constructing a schedule of n jobs in O(d+n log n) time where each task is composed of a sequence of jobs. Previous approaches for solving DVS problems have to generate a canonical schedule in advance and change the speed/voltage in O(dn log n) or O(n³) time. However, the length of a canonical schedule depends on the LCM of those of task periods and is of exponential length in general. In this paper, the tasks with arbitrary periods are transformed into harmonic periods so that the relative start time, finish time and preemption time of each task can be derived easily. These task features benefit greatly the predictability of schedules and the control on power-awareness.