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

TABLE 3.6 Dynamic Scheduling Design Options and Comparison

Purpose Advantages Disadvantages Efficiency Implementation

Priority
Inver-
sion

Frees up a
resource that
is held by a
low-priority
task so that a
high-priority
task can run

Frees up
resources
quickly

The WCET
can be
difficult to
calculate

Can be more
efficient
than static
scheduling
algorithms

Difficult

Earliest
Deadline
First
(EDF)

Gives highest
priority to
the task that
must finish
first

Allows for
higher
CPU uti-
lization
(up to
100%)

If overuti-
lized, it is
difficult to
predict
which
tasks will
meet their
deadline

Can be very
efficient

Difficult

Another type of dynamic scheduling algorithm is called the earliest deadline first
(EDF) algorithm. This algorithm allows for very high utilization of the CPU, up to
100%. To ensure tasks finish by their deadline, the scheduler places all tasks in a
queue and keeps track of their deadlines. The task with the closest deadline is given
highest priority for execution. This means that the tasks priorities can change based on
their deadline time. However, this type of scheduling is not practical for systems that
require tasks to execute at regular time intervals. If a current sensor must be read every
100

µ

s, or as close as possible to it, this type of algorithm does not guarantee that the
task will execute at a certain designated time. It instead guarantees that the task will
finish before its deadline; consistency is not important. This type of scheduling, is
not used very often because of the complexity involved in its implementation. Most
commercial RTOS do not support this type of scheduling and the cost associated
with developing this in-house does not make it a popular choice. However, if the
system becomes overused and purchasing new hardware is not an option, the EDF
algorithm may be a good choice. Table 3.6 shows dynamic scheduling design options
and comparison.

3.5 INTERTASK COMMUNICATION AND RESOURCE SHARING

In a multitasking system running on a single processor, tasks usually need to commu-
nicate with each other. Data produced in one task may be consumed by another task
or one task may be responsible for calculating a value that is then required for another
tasks calculations. Protecting this data and preserving its integrity is extremely impor-
tant because without valid data, the system will behave unpredictable and fail. One of
the most basic principles for data integrity is task reentrancy. Tasks containing global