BASIC CONCEPTS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 37

In static real-time systems, where the task set is fixed and known a priori, all task
activations can be precalculated off line, and the entire schedule can be stored in a
table that contains all guaranteed tasks arranged in the proper order. Then, at runtime,
a dispatcher simply removes the next task from the table and puts it in the running
state. The main advantage of the static approach is that the runtime overhead does
not depend on the complexity of the scheduling algorithm. This allows very sophis-
ticated algorithms to be used to solve complex problems or find optimal scheduling
sequences. On the other hand, however, the resulting system is quite inflexible to
environmental changes; thus, predictability strongly relies on the observance of the
hypotheses made on the environment.

In dynamic real-time systems (typically consisting of firm tasks), tasks can be created
at runtime; hence the guarantee must be done online every time a new task is created.
A scheme of the guarantee mechanism typically adopted in dynamic real-time systems
is illustrated in Figure 2.14.

If Γ is the current task set that has been previously guaranteed, a newly arrived task
τ new is accepted into the system if and only if the task set Γ =Γ

∪{ τ new } is found

schedulable. If Γ

is not schedulable, then task τ new is rejected to preserve the feasi-

bility of the current task set.

It is worth noting that since the guarantee mechanism is based on worst-case assump-
tions a task could unnecessarily be rejected. This means that the guarantee of firm
tasks is achieved at the cost of a lower efficiency. On the other hand, the benefit of
having a guarantee mechanism is that potential overload situations can be detected in
advance to avoid negative effects on the system. One of the most dangerous phenom-
ena caused by a transient overload is called domino effect . It refers to the situation
in which the arrival of a new task causes all previously guaranteed tasks to miss their
deadlines. Let us consider for example the situation depicted in Figure 2.15, where
five jobs are scheduled based on their absolute deadlines.

scheduling

activation

YES termination

acceptance

READY RUNNING

test

preemption

NO

signal
free resource

wait on
busy resource

WAITING

Figure 2.14 Scheme of the guarantee mechanism used in dynamic real-time systems.