Page 77 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes 5. Release times and deadlines of jobs are ……………… with the precedence constraints of
the jobs.
6. Effective Release time of a job without ……………… is equal to its given release time.

7.3 Optimality of the EDF and LST Algorithm

Priorities can be assigned to jobs according to their deadlines. The earlier the deadline, the
higher the priority is. Such scheduling algorithm is called the Earliest-Deadline-First (EDF)
algorithms. When Preemption is allowed and jobs do not contend for resources, the EDF algorithm
can produces a feasible schedule of a set J of jobs with arbitrary release times and deadlines on
a processor if and only if J has feasible schedules. Any feasible schedule of J can be systematically
transformed into an EDF schedule.

Example: Suppose that in a schedule, parts of J and J are scheduled in the intervals I1 and
i k
I2. The deadline d of J is later than the deadline d of J , but I is earlier than I . There are two
i i k k 1 2
cases; first the release time of J may be later than the end of I so J cannot be scheduled in I as
k 1 k 1
the two jobs are already scheduled on the EDF basis in these intervals.
In the second case the release time r of J is before the end of I ; we assume that r is no later than
k k 1 k
the beginning of I . We swap J and J , if the interval I is shorter than I , we move the portion of
1 i k 1 2
J that fits in I forward to I and move the entire portion of J scheduled in I backward to I and
k 1 1 i 1 2
place it after J (Figure b). We can do a similar swap if the interval I is longer than I ; we move
k 1 2
the entire portion of J scheduled in I to I and place it before J and move the portion of J that fits
k 2 1 i i
in I . The result of this swap is that these two jobs are now scheduled on the EDF basis. This
2
transformation is repeated for every pair of jobs that are not scheduled on the EDF basis according
the given non-EDF schedule until no such pair exists. The schedule may still not be an EDF
schedule if some interval is left idle while there are jobs ready for execution but are scheduled
in a later interval. This idle time can be eliminated by moving one or more of these jobs forward
into the idle interval and leave the interval where the jobs were scheduled idle. This process is
repeated if necessary until the processor never idles when there are jobs ready for execution.
Thus every feasible schedule can be transformed into a preemptive EDF schedule.

Figure 7.3: Example 1 for Optimality of the EDF and LST Algorithm

Source: ansari.szabist-isb.edu.pk/RTS/RTS0508.ppt

72 LOVELY PROFESSIONAL UNIVERSITY