HANDLING OVERLOAD CONDITIONS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 293

9.2 HANDLING APERIODIC OVERLOADS

In this section we consider event-driven systems where tasks arrive dynamically at
unknown time instants. Each task consists of a single job, which is characterized by
a fixed (known) computation time C i and a relative deadline D i . As a consequence,
the overload in these systems can only be caused by the excessive number of tasks and
can be detected at task activation times.

9.2.1 PERFORMANCE METRICS

When tasks are activated dynamically and an overload occurs, there are no algorithms
that can guarantee a feasible schedule of the task set. Since one or more tasks will miss
their deadlines, it is preferable that late tasks be the less important ones in order to
achieve graceful degradation. Hence, in overload conditions, distinguishing between
time constraints and importance is crucial for the system. In general, the importance
of a task is not related to its deadline or its period; thus, a task with a long deadline
could be much more important than another one with an earlier deadline. For example,
in a chemical process, monitoring the temperature every ten seconds is certainly more
important than updating the clock picture on the user console every second. This
means that, during a transient overload, is better to skip one or more clock updates
rather than miss the deadline of a temperature reading, since this could have a major
impact on the controlled environment.

In order to specify importance, an additional parameter is usually associated with each
task, its value , that can be used by the system to make scheduling decisions.

The value associated with a task reflects its importance with respect to the other tasks
in the set. The specific assignment depends on the particular application. For instance,
there are situations in which the value is set equal to the task computation time; in
other cases, it is an arbitrary integer number in a given range; in other applications, it
is set equal to the ratio of an arbitrary number (which reflects the importance of the
task) and the task computation time; this ratio is referred to as the value density .

In a real-time system, however, the actual value of a task also depends on the time at
which the task is completed; hence, the task importance can be better described by
an utility function. For example, a non-real-time task, which has no time constraints,
has a low constant value since it always contributes to the system value whenever it
completes its execution. On the contrary, a hard task contributes to a value only if it
completes within its deadline, and since a deadline miss would jeopardize the behav-
ior of the whole system, the value after its deadline can be considered minus infinity