APERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 58

3.2.2 GUARANTEE

To guarantee that a set of tasks can be feasibly scheduled by the EDD algorithm, we
need to show that, in the worst case, all tasks can complete before their deadlines. This
means that we have to show that for each task, the worst-case finishing time f i

is less

than or equal to its deadline d i :

∀ i =1 ,...,n f i ≤ d i .

If tasks have hard timing requirements, such a schedulability analysis must be done
before actual tasks' execution. Without loss of generality, we can assume that tasks
J 1 ,J 2 ,...,J n are listed by increasing deadlines, so that J 1 is the task with the earliest
deadline. In this case, the worst-case finishing time of task J i can be easily computed

as

i

f i = C k .

k =1

Therefore, if the task set consists of n tasks, the guarantee test can be performed by
verifying the following n conditions:

i

∀ i =1 ,...,n C k ≤ d i . (3.1)

k =1

3.3 HORN'S ALGORITHM

If tasks are not synchronous but can have arbitrary arrival times (that is, tasks can
be activated dynamically during execution), then preemption becomes an important
factor. In general, a scheduling problem in which preemption is allowed is always
easier than its non-preemptive counterpart. In a non-preemptive scheduling algorithm,
the scheduler must ensure that a newly arriving task will never need to interrupt a
currently executing task in order to meet its own deadline. This guarantee requires a
considerable amount of searching. If preemption is allowed, however, this searching is
unnecessary, since a task can be interrupted if a more important task arrives [WR91].

In 1974, Horn found an elegant solution to the problem of scheduling a set of n in-
dependent tasks on a uniprocessor system, when tasks may have dynamic arrivals and
preemption is allowed (1

| preem | L max ).

The algorithm, called Earliest Deadline First (EDF), can be expressed by the follow-
ing theorem [Hor74]: