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

Nominal load = 3

1

0.9 RED

GED
EDF

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Average unused computation time ratio (beta)

Figure 9.14 Performance of various EDF scheduling schemes: best-effort (EDF), guar-
anteed (GED) and robust (RED).

For small values of β , that is, when tasks execute for almost their maximum com-
putation time, the guaranteed (GED) and robust (RED) versions are able to obtain a
significant improvement compared to the plain EDF scheme. Increasing the unused
computation time, however, the actual load falls down and the plain EDF performs
better and better, reaching the optimality in underload conditions. Note that as the
system becomes underloaded ( β 0 . 7) GED becomes less effective than EDF. This

is due to the fact that GED performs a worst-case analysis, thus rejecting tasks that
still have some chance to execute within their deadline. This phenomenon does not
appear on RED, because the reclaiming mechanism implemented in the robust scheme
is able to recover the rejected tasks whenever possible.

In the second experiment, D over is compared against two robust algorithms: RED
(Robust Earliest Deadline) and RHD (Robust High Density). In RHD, the task with the
highest value density ( v i /C i ) is scheduled first, regardless of its deadline. Performance
results are shown in Figure 9.15.