Recently, researchers have started building task-based schedulers, i.e., schedulers that consider the work of the system to consist of tasks with certain deadlines. The goal of a task-based scheduler is to use speeds just high enough to meet these deadlines with reasonable probability.
Yao et al. [23] described how to compute an optimal schedule when task CPU requirements and deadlines are known. Hong et al. [6] later showed how to compute such schedules more quickly using various heuristics. However, systems do not generally have definite knowledge of task CPU requirements, so these approaches are unrealistic.
Flautner et al. [4] built a task-based voltage
scheduler for Linux. This scheduler requires no modification of
applications--it infers all information about the system's tasks via
heuristics. It infers that an interactive task begins when a user
interface event arrives, and uses a complex work-tracking heuristic to
decide when such a task completes. It infers that a periodic task
begins when a periodic event occurs; it considers an event periodic if
the lengths of intervals between the last 
events have a small
variance. To determine the speed for a task, it essentially computes
the average of the speeds that would have completed past similar tasks
on time. In later work [3], they refined their
period detector (but not their task completion detector) to use a
simpler heuristic and they extended their interactive
performance-setting algorithm with two other policy layers: one for
application-specific policies and one for a per-task interval-based
policy.
Pillai et al. [19] built a task-based scheduler for real-time embedded systems that runs on Linux. This scheduler assumes complete knowledge of the deadlines and worst-case CPU requirements of all tasks in the system, and assumes these tasks are periodic. The scheduler uses different algorithms, some of which make provisions for tasks completing before their deadlines. One such algorithm slows down the CPU when a task creates slack in the schedule by completing early. Another algorithm anticipates that tasks will likely complete early and therefore starts tasks as slowly as possible and only uses higher speeds when these become necessary to guarantee on-time completion.