DESIGN PROCESS OF REAL-TIME OPERATING SYSTEMS (RTOS) - Software Design for Six-Sigma: A Roadmap for Excellence - page 71

TABLE 3.5 Static Scheduling Design Options and Comparison

Purpose Advantages Disadvantages Efficiency Implementation

Round
Robin

Allows
multiple
tasks to
execute on
a unipro-
cessor
system

Ease of
implemen-
tation and
adequate
for simple
systems
where all
tasks are
equal

Does not
give
preference
to more
critical
tasks

Can be
efficient if
the correct
time
quantum
is selected

Easy to
implement

Rate
Mono-
tonic
(RM)

Assigns
fixed
priorities
to tasks

Easy to
implement
and simple
concept;
faster
tasks have
higher
priority

Even with
low
utilization,
∼ 70%,
tasks can
miss
deadlines

Is the most
efficient
static
scheduling
algorithm

More
complicated
than
round-robin
but less than
dynamic
scheduling

3.4.5 Dynamic Scheduling

An alternative to static scheduling is dynamic scheduling. Dynamic scheduling is
when the priorities of tasks can change during run time. The reasons for dynamic
schedule varies; it could be that a task may miss its deadline or that a task may need a
resource that another, lower priority task currently has. When using static scheduling
and the CPU is highly used (greater than 70%), there is a high likelihood that a task
may miss its deadline. However, dynamic scheduling allows the CPU to reach much
higher utilization, but it comes at a price—dynamic scheduling is complex.
A common dynamic scheduling technique is called priority inversion. This type
of scheduling is used in an interrupt-driven system that has priorities assigned to
each of the periodic tasks. However, if a lower priority task has a resource that is
needed by a higher priority task, the lower priority task is allowed to complete its
execution until it releases the resource, even if the higher priority task is scheduled
to run. The reasoning behind this type of scheduling technique is that it makes the
resource available for the high-priority task as soon as possible. If the control switched
out from the lower priority task while it was still holding the resource, the higher
priority task would be blocked anyway, thus increasing its overall time to execute. In
summary, priority inversion has its benefits because it frees up resources quickly for
the high-priority task so that it can have access to the resource and execute its code.
But it can be difficult to determine when priority inversion may occur, and therefore,
worst-case execution time can be difficult to calculate. The overall efficiency of the
system is better than static scheduling algorithms, but it can be difficult to implement
and not all systems would benefit from this type of algorithm.