Dynamic voltage scaling for multitasking real-time systems with uncertain execution time

Dynamic voltage and frequency scaling can save energy for real-time systems. Frequencies are generally assumed proportional to voltages. Previous studies consider the probabilistic distributions of tasks' execution time to assist dynamic voltage scaling in task scheduling. These studies use probability information for intratask voltage scheduling but do not sufficiently explore the opportunities for intertask scheduling to save more energy. This paper presents a new approach to combine intra- and intertask voltage scheduling for better energy savings in hard real-time systems with uncertain task execution time. Our approach takes three steps: 1) We calculate statistically the optimal voltage schedules for multiple concurrent tasks, using earliest deadline first scheduling for an ideal processor that can change the frequency continuously; 2) we then adapt the solution to a processor with a limited range of discrete frequencies, using a polynomial-time heuristic algorithm; and 3) finally, we improve our solution, considering the time and energy overheads of frequency switching for schedulability and energy reduction. Our simulation shows that the new approach can save more energy than existing solutions while meeting hard deadlines.