DYNAMIC PRIORITY SERVERS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 166

Proof. For any aperiodic load, all the schedules produced by the DPE algorithm have
a unique corresponding EDF schedule σ , built according to the definition given above.
Moreover, the task set in σ is periodic with a processor utilization U = U p + U s .

Hence, σ is feasible if and only if U p + U s ≤ 1. Now we show that σ is feasible if

and only if σ

is feasible.

Observe that in each schedule σ the completion time of a periodic instance is always
less than or equal to the completion time of the corresponding instance in the schedule
σ . Hence, if σ is feasible, then also σ is feasible; that is, the periodic task set is
schedulable with the DPE algorithm. Vice versa, observing that σ is a particular
schedule produced by the DPE algorithm when there are enough aperiodic requests, if
σ is feasible, then σ will also be feasible; hence, the theorem holds.

6.2.2 RECLAIMING SPARE TIME

In hard real-time systems, the guarantee test of critical tasks is done by performing a
worst-case schedulability analysis; that is, assuming the maximum execution time for
all task instances. However, when such a peak load is not reached because the actual
execution times are less than the worst-case values, it is not always obvious how to
reclaim the spare time efficiently.

Using a DPE server, the spare time unused by periodic tasks can be easily reclaimed
for servicing aperiodic requests. Whenever a periodic task completes, it is sufficient to
add its spare time to the corresponding aperiodic capacity. An example of reclaiming
mechanism is shown in Figure 6.3.

As it can be seen from the capacity plot, at the completion time of the first two periodic
instances, the corresponding aperiodic capacities ( C S 1

and C 1 S 2

) are incremented by
an amount equal to the spare time saved. Thanks to this reclaiming mechanism, the
first aperiodic request can receive immediate service for all the seven units of time
required, completing at time t =11. Without reclaiming, the request would complete
at time t =12.

Note that reclaiming the spare time of periodic tasks as aperiodic capacities does not
affect the schedulability of the system. In fact, any spare time is already “allocated”
to a priority level corresponding to its deadline when the task set has been guaranteed.
Hence, the spare time can be used safely if requested with the same deadline.