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

9.4 HANDLING PERMANENT OVERLOADS

This section presents some methodologies for handling permanent overload conditions
occurring in periodic task systems when the total processor utilization exceeds one.
Basically, there are three methods to reduce the load:

Job skipping. This method reduces the total load by properly skipping (i.e.,
aborting) some job execution in the periodic tasks, in such a way that a minimum
number of jobs per task is guaranteed to execute within their timing constraints.

Period adaptation. According to this approach, the load is reduced by enlarging
task periods to suitable values, so that the total workload can be kept below a
desired threshold.

Service adaptation. According to this method, the load is reduced by decreasing
the computational requirements of the tasks, trading predictability with quality of
service.

9.4.1 JOB SKIPPING

The computational load of a set of periodic tasks can be reduced by properly skipping
a few jobs in the task set, in such a way that the remaining jobs can be scheduled within
their deadlines. This approach is suitable for real-time applications characterized by
soft or firm deadlines, such as those typically found in multimedia systems, where
skipping a video frame once in a while is better than processing it with a long delay.
Even in certain control applications, the sporadic skip of some job can be tolerated
when the controlled systems is characterized by a high inertia.

To understand how job skipping can make an overloaded system schedulable, consider
the following example, consisting of two tasks, with computation times C 1 =2and
C 2 =8and periods T 1 =4and T 2 =12. Since the processor utilization factor is
U p =14 / 12 > 1, the system is under a permanent overload, and the tasks cannot be
scheduled within their deadlines. Nevertheless, Figure 9.24 shows that skipping a job
every three in task τ 1 the overload can be resolved and all the remaining jobs can be
scheduled within their deadlines.

In order to control the overall system load, it is important to derive the relation between
the number of skips (i.e., the number of aborted jobs per task) and the total computa-
tional demand. In 1995, Koren and Shasha [KS95] proposed a new task model (known
as the firm periodic model) suited to be handled by this technique.