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

O ( kn ). If the value of k is constant (and small, compared to the task set size), then
the complexity becomes linearly proportional to the number of tasks.

A disadvantage of the heuristic scheduling approach is that it is not optimal. This

means that, if there is a feasible schedule, the Spring algorithm may not find it.

3.5 SCHEDULING WITH PRECEDENCE

CONSTRAINTS

The problem of finding an optimal schedule for a set of tasks with precedence re-
lations is in general NP -hard. However, optimal algorithms that solve the problem
in polynomial time can be found under particular assumptions on the tasks. In this
section we present two algorithms that minimize the maximum lateness by assuming
synchronous activations and preemptive scheduling, respectively.

3.5.1 LATEST DEADLINE FIRST

( 1 | PREC,SYNC | L MAX )

In 1973, Lawler [Law73] presented an optimal algorithm that minimizes the maximum
lateness of a set of tasks with precedence relations and simultaneous arrival times. The
algorithm is called Latest Deadline First (LDF) and can be executed in polynomial
time with respect to the number of tasks in the set.

Given a set of n tasks and a directed acyclic graph (DAG) describing their prece-

dence relations, LDF builds the scheduling queue from tail to head: among the tasks
without successors or whose successors have been all selected, LDF selects the task
with the latest deadline to be scheduled last. This procedure is repeated until all tasks
in the set are selected. At run time, tasks are extracted from the head of the queue,
so that the first task inserted in the queue will be executed last, whereas the last task
inserted in the queue will be executed first.

J

The correctness of this rule is proved as follows: Let J be the complete set of tasks

to be scheduled, let Γ be the subset of tasks without successors, and let J l be the

task in Γ with the latest deadline d l .If σ is any schedule that does not follow the EDL
rule, then the last scheduled task, say J k , will not be the one with the latest deadline;
thus d k ≤

⊆J

d l . Since J l is scheduled before J k , let us partition Γ into four subsets, so