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

Before concluding the discussion on the competitive analysis, it is worth pointing
out that all the above bounds are derived under very restrictive assumptions, such
as all tasks have zero laxity, the overload can have an arbitrary (but finite) duration,
and task's execution time can be arbitrarily small. In most real-world applications,
however, tasks characteristics are much less restrictive; therefore, the 0.25 bound has
only a theoretical validity, and more work is needed to derive other bounds based
on more realistic assumptions on the actual load conditions. An analysis of online
scheduling algorithms under different types of adversaries has been presented by Karp
[Kar92].

9.2.4 TYPICAL SCHEDULING SCHEMES

With respect to the strategy used to predict and handle overloads, most of the schedul-
ing algorithms proposed in the literature can be divided into three main classes, illus-
trated in Figure 9.11:

Best effort . This class includes those algorithms with no prediction for overload
conditions. At its arrival, a new task is always accepted into the ready queue, so
the system performance can only be controlled through a proper priority assign-
ment that takes task values into account.

With acceptance test . This class includes those algorithms with admission con-
trol, performing a guarantee test at every job activation. Whenever a new task
enters the system, a guarantee routine verifies the schedulability of the task set
based on worst-case assumptions. If the task set is found schedulable, the new
task is accepted in the system; otherwise, it is rejected.

Robust . This class includes those algorithms that separate timing constraints
and importance by considering two different policies: one for task acceptance
and one for task rejection. Typically, whenever a new task enters the system, an
acceptance test verifies the schedulability of the new task set based on worst-case
assumptions. If the task set is found schedulable, the new task is accepted in
the ready queue; otherwise, one or more tasks are rejected based on a different
policy, aimed at maximizing the cumulative value of the feasible tasks.

In addition, an algorithm is said to be competitive if it has a competitive factor greater
than zero.