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

Task Task1 Task2 Task3

Computation 1 2 5

Period 3 4 12

Skip Parameter 4 3 ∞

U p 1.25

skip skip

τ

1

0 3 6 9 12 15 18 21 24 27

skip skip

τ

2

0 4 8 12 16 20 24

τ

3

0 12 24

Figure 9.25 A schedulable set of firm periodic tasks.

SKIPS AND BANDWIDTH SAVING

If skips are permitted in the periodic task set, the spare time saved by rejecting the blue
instances can be reallocated for other purposes. For example, for scheduling slightly
overloaded systems or for advancing the execution of soft aperiodic requests.

Unfortunately, the spare time has a “granular” distribution and cannot be reclaimed at
any time. Nevertheless, it can be shown that skipping blue instances still produces a
bandwidth saving in the periodic schedule. Caccamo and Buttazzo [CB97] identified
the amount of bandwidth saved by skips using a simple parameter, the equivalent
utilization factor U skip
p

, which can be defined as

i g skip

(0 ,L )

U skip
p

i

=max
L≥ 0

(9.25)

L

where g skip
i

(0 ,L ) is given in Equation (9.22).

Using this definition, the schedulability of a deeply-red skippable task set can be also
verified using the following theorem ([CB97]):

Theorem 9.6 A set Γ of deeply-red skippable periodic tasks is schedulable by EDF if
U skip
p

≤ 1 .