PERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 117

An interesting property of EDF during permanent overloads is that it automatically
performs a period rescaling, so tasks start behaving as they were executing at a lower
rate. This property has been proved by Cervin in his PhD dissertation [Cer03] and it
is formally stated in the following theorem.

Theorem 4.7 (Cervin) Assume a set of n periodic tasks, where each task is described
by a fixed period T i , a fixed execution time C i , a relative deadline D i , and a release
offset Φ i .If U> 1 and tasks are scheduled by EDF, then, in stationarity, the average
period T i of each task τ i is given by T i = T i U .

Note that under fixed priority scheduling, a permanent overload condition causes a
complete blocking of the lower priority tasks.

As discussed later in the topic, another major advantage of dynamic scheduling with
respect to fixed priority scheduling is a better responsiveness in handling aperiodic
tasks. This property comes from the higher processor utilization bound of EDF. In fact,
the lower schedulability bound of RM limits the maximum utilization ( U s = C s /T s )
that can be assigned to a server for guaranteeing the feasibility of the periodic task set.
As a consequence, the spare processor utilization that cannot be assigned to the server
is wasted as a background execution. This problem does not occur under EDF, where,
if U p is the processor utilization of the periodic tasks, the full remaining fraction 1 − U p

can always be allocated to the server for aperiodic execution.

Exercises

4.1 Verify the schedulability and construct the schedule according to the RM algo-

rithm for the following set of periodic tasks:

C i T i

τ 1 2 6

τ 2 2 8

τ 3 2 12