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

An important theoretical result found by Baruah et al. [BKM + 92] is that there is an
upper bound on the competitive factor of any on-line algorithm. This is stated by the
following theorem.

Theorem 9.1 (Baruah et al.) In systems where the loading factor is greater than 2
( ρ> 2 ) and tasks' values are proportional to their computation times, no online
algorithm can guarantee a competitive factor greater than 0 . 25 .

The proof of this theorem is done by using an adversary argument, in which the on-
line scheduling algorithm is identified as a player and the clairvoyant scheduler as the
adversary. In order to propose worst-case conditions, the adversary dynamically gen-
erates the sequence of tasks depending on the player decisions, to minimize the ratio
Γ A / Γ ∗ . At the end of the game, the adversary shows its schedule and the two cumula-
tive values are computed. Since the player tries to do his best in worst-case conditions,
the ratio of the cumulative values gives the upper bound of the competitive factor for
any online algorithm.

TASK GENERATION STRATEGY

To create an overload condition and force the hand of the player, the adversary creates
two types of tasks: major tasks, of length C i , and associated tasks, of length
arbitrarily small. These tasks are generated according to the following strategy (see
Figure 9.9):

All tasks have zero laxity; that is, the relative deadline of each task is exactly
equal to its computation time.
After releasing a major task J i , the adversary releases the next major task J i +1
at time before the deadline of J i ; that is, r i +1 = d i − .

For each major task J i , the adversary may also create a sequence of associated
tasks, in the interval [ r i , d i ], such that each subsequent associated task is released
at the deadline of the previous one in the sequence (see Figure 9.9). Note that the
resulting load is ρ =2. Moreover, any algorithm that schedules any one of the
associated tasks cannot schedule J i within its deadline.
If the player chooses to abandon J i in favor of an associated task, the adversary
stops the sequence of associated tasks.
If the player chooses to schedule a major task J i , the sequence of tasks terminates
with the release of J i +1 .
Since the overload must have a finite duration, the sequence continues until the
release of J m , where m is a positive finite integer.