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

1

RED
RHD
D_OVER

0.95

0.9

0.85

0.8

0.75

0.7

0.4 0.6 0.8 1 1.2 1.4 1.6

Average load

Figure 9.15 Performance of D over against RED and RHD.

Note that in underload conditions D over and RED exhibit optimal behavior ( HV R =
1), whereas RHD is not able to achieve the total cumulative value, since it does not take
deadlines into account. However, for high load conditions ( ρ> 1 . 5), RHD performs
even better than RED and D over .

In particular, for random task sets, D over is less effective than RED and RHD for two
reasons: first, it does not have a reclaiming mechanism for recovering rejected tasks in
the case of early completions; second, the threshold value used in the rejection policy
is set to reach the best competitive factor in a worst-case scenario. But this means
that for random sequences D over may reject tasks that could increase the cumulative

value, if executed.

In conclusion, we can say that in overload conditions no online algorithm can achieve
optimal performance in terms of cumulative value. Competitive algorithms are de-
signed to guarantee a minimum performance in any load condition, but they cannot
guarantee the best performance for all possible scenarios. For random task sets, robust
scheduling schemes appear to be more appropriate.