Next: Multimedia-Data Transmission
Up: Process Management
Previous: Requirements
The following paragraphs cover only periodic tasks, which request the processors at
constant intervals. Two algorithms dominate the scheduler implementations in multimedia-capable
operating systems:
- Earliest Deadline First (EDF).
-
EDF is an optimal dynamic algorithm.
Any beginning of a new period of a task triggers a reordering of the complete schedule,
according to the deadlines of the scheduled tasks.
- Rate-Monotonic Scheduling
-
Rate-monotonic scheduling is an optimal static, priority-driven
algorithm. During the set-up phase, each task is assigned a static priority
according to its requested processing rate: the shorter a task's period, the higher
is its priority. Afterwards, each task is processed with this priority, and no
rearrangement of the priorities is necessary as long as no new task appears.
Both algorithms can be extended by dividing each task into a mandatory part, which secures an acceptable
result, and an optional part, which refines the work.
Tasks are primarily scheduled with respect to the mandatory parts, while the optional parts are
only processed during underload periods. This arrangement allows scaling of continuous media.
Comparing EDF to rate-monotonic scheduling, context switches are less probable using EDF.
In addition, EDF can schedule tasks successfully at
processor-utilisation rates up to 100 percent, whereas rate monotonic's processor utilisation is upwardly
bounded by 69 percent before a failure occurs in
worst-case scenarios.
On the other hand, rate monotonic incurs less overhead for continuous-media data streams:
the rate-monotonic algorithm uses the periodicity of continuous media to compute a static schedule
during setup while EDF must determine the task to run for every incoming event.
tspeuker@cip.informatik.uni-erlangen.de