Energy-Aware Real-Time Scheduling: DVFS, Sleep States and Deadlines

Battery-powered sensors, drones, wearables and thermally constrained edge boxes all face the same tension: the processor has to meet its deadlines, but every unnecessary cycle and every unnecessarily high voltage costs energy and heat. Energy-aware real-time scheduling tries to use the least energy that still meets every deadline. It works with two main levers: dynamic voltage and frequency scaling (DVFS), which slows the processor down, and dynamic power management (DPM), which puts it into sleep states between jobs.

This article explains the power model behind both levers, the classic static and dynamic slowdown algorithms (including Pillai and Shin’s cycle-conserving EDF), the race-to-idle debate, and the practical traps that make textbook savings disappear on real hardware.

The power model: why slowing down saves energy

A CMOS processor’s power has two main parts:

• Dynamic (switching) power: P_dyn = α · C · V² · f, where α is the activity factor, C the switched capacitance, V the supply voltage and f the clock frequency.
• Static (leakage) power: P_static ≈ V · I_leak. It is drawn whenever the circuit is powered, whether or not it is switching. Leakage rises with temperature and has become a large share of the total in modern process nodes.

The maximum stable frequency depends on voltage, so frequency and voltage are scaled together in discrete operating performance points (OPPs). The key quantity is energy per cycle: E_cycle = α · C · V². A job needs a roughly fixed number of cycles, so if you lower the voltage when you lower the frequency, the dynamic energy for the job falls quadratically with voltage. Lowering frequency without lowering voltage saves power but not energy. The job takes longer, and the dynamic energy per cycle stays the same.

Static power is what makes this complicated. Run a job more slowly and you pay leakage, plus the power of memory, interconnect and other components that don’t scale with the CPU clock, for longer. Below some critical speed, the extra static energy outweighs the dynamic savings, and the energy per job starts to rise again. Below the critical speed it is better to run faster and then sleep.

Static slowdown: choosing one speed offline

The simplest approach is to compute, at design time, the lowest constant speed at which the task set is still schedulable when every job takes its worst-case execution time (WCET). Write the normalized speed as s = f / f_max. If WCETs are measured at f_max, execution time scales roughly as C_i / s for CPU-bound code.

Under EDF

For implicit-deadline periodic tasks under EDF, the task set is schedulable at speed s if Σ C_i / T_i ≤ s. The optimal constant speed is simply the utilization U, rounded up to the next available OPP. Yao, Demers and Shenker’s 1995 work on job-level speed scheduling gives the theoretical foundation for optimal offline speed assignment in more general settings.

Under fixed priorities

Under rate-monotonic or deadline-monotonic priorities, the utilization bound is too pessimistic to use for speed selection. Use exact time-demand analysis instead. The minimum constant speed is:

s_min = max_i  min_{t ∈ S_i}  ( Σ_{j ≤ i} ⌈t / T_j⌉ · C_j ) / t

Here S_i is the set of scheduling points for task i: multiples of higher-priority periods up to D_i. Equivalently, you can scale all WCETs by 1/s for each candidate OPP and run ordinary response-time analysis, then keep the slowest OPP that passes. For a refresher on why EDF can run at full utilization while fixed priorities often can’t, see Rate Monotonic vs Earliest Deadline First.

A worked example

Suppose the processor offers OPPs at 50%, 75% and 100% of f_max. Under EDF the required speed is 0.60, so 75% is the lowest feasible OPP: scaled utilization is 0.60 / 0.75 = 0.80 ≤ 1. Under rate-monotonic priorities, check each OPP with response-time analysis on the scaled WCETs (2.67, 4 and 13.33 ms at 75%). Here 75% also passes. You can repeat the check quickly with the schedulability calculator by entering scaled execution times.

Dynamic slowdown and cycle-conserving EDF

Static slowdown assumes every job hits its WCET, but most jobs finish well before that. The difference is dynamic slack, and reclaiming it is where much of the practical energy saving comes from.

Pillai and Shin’s 2001 paper, “Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems,” introduced several such algorithms. The best known is cycle-conserving EDF (ccEDF). The idea is that once a job completes, its actual cycle count is known. Until that task’s next release, the scheduler can count the task’s utilization using the actual value instead of the worst case. At the next release the worst case is assumed again, so safety is preserved.

// Cycle-conserving EDF (after Pillai & Shin, 2001)
// U[i]: current utilization estimate for task i
// OPPs: available normalized speeds s_1 < s_2 < ... < s_m = 1.0

on_release(task i):
    U[i] = WCET[i] / T[i]          // assume worst case again
    select_speed()

on_completion(task i, cycles_used):
    U[i] = cycles_used / T[i]      // actual demand of this job
    select_speed()

select_speed():
    U_total = sum(U)
    s = smallest OPP with s >= U_total
    set_cpu_speed(s)               // includes voltage change

The same paper describes a cycle-conserving variant for rate-monotonic scheduling, and a look-ahead EDF that defers as much work as possible past upcoming deadlines so it can run even slower now. Later work extended these ideas with slack-stealing, inter-task slack distribution, and statistical approaches that use execution-time distributions instead of WCET alone.

Race-to-idle and dynamic power management

The alternative to slowing down is race-to-idle: run at full speed, finish the work early, and put the processor (or the whole SoC) into a deep sleep state. Which approach wins depends on the platform:

• When static and platform power are high relative to dynamic power, race-to-idle often wins, because shortening active time cuts the large constant cost.
• When the voltage range is wide, leakage is modest and deep sleep states are expensive to enter and leave, DVFS tends to win.
• Many real systems combine both. They run at or slightly above the critical speed, then sleep.

The break-even time

A sleep state saves energy only if the idle interval is long enough to pay back the energy spent entering and leaving it. A common formulation of the break-even time is:

T_BE = max( t_tr ,  (E_tr − P_sleep · t_tr) / (P_idle − P_sleep) )

Here t_tr and E_tr are the total transition time and energy, P_idle is the power when idle but awake, and P_sleep is the sleep-state power. Idle intervals shorter than T_BE should not use that state. Real-time schedulers can do better than reactive idle governors because they know future release times. Procrastination scheduling (Jejurikar and Gupta) deliberately delays job execution, within what deadlines allow, to merge short idle gaps into fewer, longer ones that are worth sleeping through.

Comparing the main techniques

Practical traps on real hardware

Execution time does not scale linearly

Memory-bound code waits on DRAM, whose latency in nanoseconds doesn’t change with the CPU clock. Dividing the WCET at f_max by s is therefore usually conservative. But on SoCs where bus, cache or memory-controller clocks scale with the CPU clock, the relationship can break down, so measure WCET at every OPP you intend to use. Our guide to WCET analysis methods covers how to do this credibly, and our WCET and timing analysis service can characterize per-OPP timing for you.

Transitions cost time and energy

A DVFS change can involve waiting for a voltage regulator to settle and a PLL to relock, which can stall the CPU. Bound this transition time and charge it to the job or the scheduler in your analysis. Algorithms that change speed at every scheduling event should be evaluated with realistic transition costs, not with the zero-overhead model common in early papers.

Frequency domains are shared

On multicore SoCs, cores in a cluster usually share a frequency and voltage domain. The cluster must run at the speed required by its busiest core. That makes load balancing an energy question: partitioned scheduling that spreads utilization evenly across cores in a domain lets the whole cluster run slower. Heterogeneous designs with big and little cores add another dimension. See Multicore real-time scheduling for partitioning heuristics.

Thermal throttling overrides your schedule

If the platform’s thermal management can lower frequency below the speed your analysis assumed, the guarantees no longer hold. Either analyze at a frequency the platform can sustain under worst-case thermal conditions, or treat throttling as a mode change with its own degraded task set.

Linux, reservations and contracts

On Linux, the cpufreq subsystem and its schedutil governor select frequency based on scheduler utilization signals. For the SCHED_DEADLINE class, schedutil uses the reserved bandwidth as a floor when choosing a frequency, and recent kernels scale deadline runtime accounting for CPU frequency and capacity. Linux’s Energy Aware Scheduling (EAS) uses an energy model of the platform to place tasks on heterogeneous CPUs, though it is aimed mainly at fair-class tasks rather than hard real-time work. Our article on SCHED_DEADLINE and the Constant Bandwidth Server explains the reservation model. Our Real-Time Linux Tuning service covers pinning OPPs, controlling idle states and checking latency under power management.

Reservations raise a subtle question: is a budget measured in time or in cycles? If the CPU slows down, a time budget delivers less work. A cycle budget has to be stretched in time, which consumes more of the reservation period. Contract-based frameworks handle this by negotiating budgets that hold at a given power level. Energy and power-aware scheduling was part of the original FRESCOR project’s objectives, alongside its work on contract-based resource management. See Contract-based scheduling explained for the general model.

Frequently asked questions

Does lowering the clock frequency always save energy?

No. Lowering frequency alone reduces power but stretches execution, so dynamic energy per job stays about the same and static energy grows. Savings come from lowering voltage as well, and only above the platform’s critical speed.

Is cycle-conserving EDF safe for hard real-time tasks?

Under its assumptions (ideal EDF, implicit deadlines, execution time scaling with speed, bounded transition overhead), yes. It reclaims slack only after a job has completed and restores the worst-case estimate at the next release. Real platforms need transition overheads and non-linear scaling added to the analysis.

When should I prefer race-to-idle?

When static, memory and peripheral power make up a large part of the total, when the voltage range is narrow, or when the platform has deep sleep states with low wake-up cost. The answer is platform-specific, so measure energy per job at each OPP.

How do I model sleep-state wake-up latency in analysis?

Treat it as release jitter for jobs that may be released while the CPU sleeps, or as an extra blocking term. Either way, use a measured worst case, and restrict the idle governor to states whose latency you have analyzed.

Can DVFS be used with fixed-priority scheduling?

Yes. Static speed selection works with exact time-demand or response-time analysis at each OPP. Dynamic reclamation for fixed priorities exists too, such as cycle-conserving RM, though it is usually less aggressive than EDF-based methods.

References and further reading

1. P. Pillai, K. G. Shin, “Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems,” ACM Symposium on Operating Systems Principles (SOSP), 2001.
2. F. Yao, A. Demers, S. Shenker, “A Scheduling Model for Reduced CPU Energy,” IEEE Symposium on Foundations of Computer Science (FOCS), 1995.
3. R. Jejurikar, R. K. Gupta, work on procrastination scheduling and leakage-aware DVS, Design Automation Conference proceedings, mid-2000s.
4. Dynamic voltage scaling — Wikipedia
5. CPU Performance Scaling (cpufreq) — Linux kernel documentation
6. Energy Aware Scheduling — Linux kernel documentation
7. Deadline Task Scheduling — Linux kernel documentation