Sensors 2012, 12 11338
a static, optimal, and polynomial-time scheduling algorithm for aperiodic tasks [7]. Pillai and Shin first
proposed a DVS algorithm based on schedulability tests [8], which selected a fixed supply voltage to
meet all the deadlines of a task set under the Earliest Deadline First (EDF) or Rate Monotonic (RM)
scheduling model, and then they presented two dynamic DVS algorithms. The first one is the
Cycle-Conserving RT-DVS algorithm, which uses the information of the Actual Execution Time
(AET) of the completed tasks under EDF scheduling, and the remaining time information of the
running tasks under RM scheduling, to select the lowest feasible operating frequency. The second one
is the Look-Ahead RT-DVS algorithm, which defers the execution of tasks as late as possible to make
the energy consumption as little as possible. Zhu presented a novel approach combining feedback
control with DVS schemes (Feedback-DVS) for hard real-time systems with dynamic workloads under
EDF scheduling [9]. In Feedback-DVS, each task is divided into two portions. In the first portion,
Feedback-DVS exploits frequency scaling when tasks execute with the average execution time in order
to minimize the energy consumption of tasks. In the second portion, Feedback-DVS meets hard
real-time requirements even in the worst execution time case. Chen and Thiele explored
energy-efficient real-time task scheduling in leakage-aware DVS systems for homogeneous
multiprocessor platforms [10]. They showed the critical speed might not be good enough to be viewed
as the lowest speed of execution, and load balancing might not be good from the energy-saving point
of view. Aiming at periodic tasksets, they developed a new algorithm (i.e., the RSLTF algorithm) to
perform processor and task assignment, which was more effective in energy savings. Although static
DVS algorithms have few runtime overheads, there is almost no purely static DVS energy-saving
algorithm for hard real-time systems. Static DVS algorithms take pessimistic views about the
execution time of tasks in order to guarantee the hard real-time requirements of tasks, which will lead
to pessimistic energy-saving results. In fact, the AET of tasks is usually less than the WCET of
tasks [11,12], so there is more slack time to use in runtime to lower the voltage of a processor further.
Most of the existing research uses dynamic DVS algorithms [9,10], or combines static DVS and
dynamic DVS algorithms [6–8,13,14].
Energy-saving problem has also been widely researched in soft real-time systems where there are
usually the requirements of DMR. Kargahi and Movaghar presented a method for reducing the long
run power consumption of a soft real-time system using DVS [15]. They modeled the system by using
a continuous-time Markov process model and gave a predefined upper bound on the fraction of lost
jobs. Aiming at the voltage assignment with probability (VAP) of soft real-time embedded systems
with uncertain execution times and discrete voltage DVS processors, Qiu et al. used Probabilistic
Data-Flow Graph to model tasks and proposed two optimal algorithms [16], VAP_S for uniprocessors
and VAP_M for multiprocessors to minimize the expected value of total energy consumption while
meeting timing constraints with guaranteed confidence probabilities. Rusu et al. evaluated several
DVS algorithms for systems with unpredictable workloads [17]. They found the stochastic DVS
scheme based on the collected statistical information about the workload probability distribution was
simple and effective to obtain the DVS scheduling and better explore power-performance tradeoffs.
Kluge et al. presented the autocorrelation clustering (ACC) method to optimize the energy consumption
of periodic soft real-time applications [18]. By learning the workload of single iterations within a
higher period, ACC predicts future workloads to adjust clock frequency and scheduling parameters,
which is completely application-independent. Yuan and Nahrstedt presented an energy-efficient