Transition-Aware Dynamic Voltage Scaling for Jitter-Controlled Real-Time Scheduling: A Tree-Structured Approach

Dynamic voltage scaling (DVS) is a key technique for embedded real-time systems to reduce energy consumption by lowering the supply voltage and operating frequency. Most existing DVS algorithms have to generate the canonical schedules or estimate the lengths of slack time in advance for generating the voltage scaling decisions. Therefore, these methods execute either on the length (least-common-multiple) of schedules which is exponential length in general or spend much overhead for estimating available slack which is hard to predict accurately. In this paper, we study the periodic dynamic real-time tasks, whose periods are transformed in a jitter-controlled manner, and assuming their jobs could be completed early. Our approach constructs a tree structure corresponding to a schedule and maintains the tree at each early-completion point. Our approach consisting off-line and on-line algorithm also handles the transition times and takes O(nk) and O(k+pmax/pmin) time respectively, where n, k and pmax/pmin denotes the number of jobs, task and degree, respectively.