Page 122 - DCAP608_REAL TIME SYSTEMS

Unit 12: Priority-driven Scheduling of Periodic Tasks

12.2.1 Rate Monotonic and Deadline Monotonic Algorithms Notes

The rate monotonic algorithm assigns priorities to tasks based on their periods. The shorter the
period the higher the priority is. The rate of (job releases) of a task is the inverse of its period so
the higher the rate, the higher its priority. Each job is placed at the head of the priority queue and
is executed as soon as the job is released. When the relative deadline of every task is proportional
to its period, the RM and DM algorithms are identical. When the relative deadlines are arbitrary,
the DM algorithm performs better in the sense that it can sometimes produce a feasible schedule
when the RM fails. The RM algorithm always fails when the DM algorithm fails. As the priorities
of the tasks with short relative deadlines are too low, these tasks cannot meet their deadlines.

Did u know? RMA has been proved to be the optimal static priority real-time task scheduling
algorithms.

12.2.2 Some Well Known Dynamic Algorithms

The EDF assigns priorities to individual jobs in the tasks according to their absolute deadlines;
it is a dynamic-priority algorithm. Figure given below shows the EDF schedule of the two tasks
T and T .
1 2

Notes The basic principle of EDF is algorithm is very intuitive and easy to understand.
The scheduling test for EDF is also simple.
Here,

J is taken as First Job and J is taken as Second Job.
1 2
Figure 12.1: EDF Schedule of the Two Tasks T and T
1 2

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

 At time 0, the first jobs J , 1 and J2, 1 of both tasks are ready.
1
 The absolute deadline of J1, 1 is 2 and that of J2,1 is 5 so J1, 1 is higher priority.
 At time 2, J1, 2 is released and its deadline is 4, earlier than J2, 1.
 Hence J2, 1 is placed ahead of J2, 1 it preempts J2,1 and executes.

LOVELY PROFESSIONAL UNIVERSITY 117