Page 78 - DCAP608_REAL TIME SYSTEMS

Unit 7: Commonly used Algorithm to Real-time Scheduling

Notes
!
Caution When the goal of scheduling is to meet deadline, there is no advantage to completing
any job sooner than necessary.

We may want to postpone the execution of hard real-time jobs for some reason. So we can use
another latest release time (LRT) algorithm. This algorithm treats release times as deadlines and
deadlines as release times and schedules the jobs backwards, starting from the latest deadline of
all jobs, in priority-driven manner, to the current time. The priorities are based on the release
times of jobs; the later the release time, the higher the priority. As it may leave the processor idle
when there are jobs ready for execution, the LT algorithms is not a priority-driven algorithm.
Consider the figure below:

 IN the precedence graph, the number next of the job name is the executing time of the job.
 Its feasible interval is given by the range of time next to its execution time.

Figure 7.4: Example 2 for Optimality of the EDF and LST Algorithm

Source: ansari.szabist-isb.edu.pk/RTS/RTS0508.ppt
 The latest deadline among all jobs is 8. Hence time starts at 8 and goes backwards to 0.
 At time 8, J2 is ready and is scheduled. At time 7, J3 is also ready to be scheduled, but
because J2 has a later release time, it has a higher priority.

 J2 is scheduled from 7 to 6. When J2 completes at time 6, J1 is ready.
 However as J3 has a higher priority and is, there from, scheduled from 6 to 4.
Finally J1 is scheduled from 4 to 1. The result is a feasible schedule.

7.4 Non-optimality of the EDF and LST Algorithm

It is natural to ask whether EDF and the LST algorithms remain optimal if preemption is not
allowed or there is more than one processor.

LOVELY PROFESSIONAL UNIVERSITY 73