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

4.4 EARLIEST DEADLINE FIRST

The Earliest Deadline First (EDF) algorithm is a dynamic scheduling rule that selects
tasks according to their absolute deadlines. Specifically, tasks with earlier deadlines
will be executed at higher priorities. Since the absolute deadline of a periodic task
depends on the current j th instance as

d i,j =Φ i +( j − 1) T i + D i ,

EDF is a dynamic priority assignment. Moreover, it is typically executed in preemp-
tive mode, thus the currently executing task is preempted whenever another periodic
instance with earlier deadline becomes active.

Note that EDF does not make any specific assumption on the periodicity of the tasks;
hence, it can be used for scheduling periodic as well as aperiodic tasks. For the same
reason, the optimality of EDF, proved in Chapter 3 for aperiodic tasks, also holds for
periodic tasks.

4.4.1 SCHEDULABILITY ANALYSIS

Under the assumptions A1, A2, A3, and A4, the schedulability of a periodic task set
handled by EDF can be verified through the processor utilization factor. In this case,
however, the least upper bound is one; therefore, tasks may utilize the processor up
to 100% and still be schedulable. In particular, the following theorem holds [LL73,
SBS95]:

Theorem 4.2 A set of periodic tasks is schedulable with EDF if and only if

n

C i
T i ≤

1 .

i =1

Proof. Only if . We show that a task set cannot be scheduled if U> 1. In fact, by
defining T = T 1 T 2 ...T n , the total demand of computation time requested by all tasks
in T can be calculated as

n

T
T i

C i = UT.

i =1

If U> 1, that is, if the total demand UT exceeds the available processor time T , there
is clearly no feasible schedule for the task set.