Rate Monotonic (R.M) and Deadline Monotonic (D.M) Algorithm | Real Time System

Download our Android App from Google Play Store and start reading Reference Notes Offline.

Rate Monotonic (R.M) algorithm and Deadline Monotonic (D.M) Algorithm, Real Time System Notes | Sixth Semester, BSc.CSIT | Tribhuvan University (TU)

Rate Monotonic Algorithm (R.M)
Rate Monotonic algorithm is a fixed priority algorithm which assigns priorities to task, based on their periods: the shorter the period, higher the rate and hence higher the priority.
Consider T1=(4,1), T2=(5,2) and T3=(20,5)

• Priority of T1 is the highest because it’s period is the shortest.
• Each job in this task is placed at the head of the priority queue and is executed as soon as the job is released.
• T2 has the next priority. The execution of 1st job in T2 is delayed until the 1st job in T1 completes and 4th job in T2 is preempted at time 16 when the 5th job in T1 is released.
• Jobs in T3 execute only when there is no job in the higher priority task ready for execution.

Theorem:
A system of simply periodic, independent, preemptable tasks whose relative deadlines are equal to or larger than their periods is schedulable on one processor according to Rate Monotonic algorithm if and only if its total utilization is equal to or less than 1.

Proof:
Suppose the tasks are in phase and processor never idles before the tasks Ti misses a deadline for the first time at t.
T is an integer multiple of pi because tasks are simply periodic, t is also an integer multiple of the period pk of every higher priority task Tk for k=1,2,…… i-1. Hence the total time required to complete all the jobs with deadlines before and at t is equal to $\sum_{k=1}^{i}(\frac{e_{k}t}{p_k})$ which is equal to t times the total utilization $U_i= \sum_{k=1}^{i}U_k$ of the highest priority tasks. That Ti misses a deadline at t means that this demand for time exceeds t. i.e; Ui>1.

Deadline Monotonic Algorithm (DM)
It is a fixed priority algorithm which assigns priorities to tasks according to their relative deadlines: the shorter the deadline, the higher the priority.
Consider T1=(50, 50, 25, 100), T2=(0, 62.5, 10, 20), T3=(0, 125, 25, 50)

• T2 has the highest priority because the relative deadline 20 is the shortest among the tasks.
• T1 with relative deadline of 100 has the lowest priority.
• When relative deadline of every task is proportional to it’s period, the Rate Monotonic and Deadline Monotonic algorithms are identical.
• When the relative deadline are arbitrary, the Deadline Monotonic algorithm performs better in the sense that it can sometimes produce a feasible schedule when the Rate Monotonic algorithm fails, while the Rate Monotonic algorithm always fails when the Deadline Monotonic fails.

Algorithm:
A system T of independent, preemptable periodic tasks that are in phase and have relative deadlines equal to or less than their respective periods can be feasibly scheduled on one processor according to Deadline Monotonic algorithm whenever it can be feasibly scheduled according to any fixed-priority algorithm.

Proof:
This theorem is true because we can transform a feasible fixed priority schedule that is not a Deadline Monotonic schedule into one that is.

Suppose that a system has a feasible fixed priority schedule. i.e not a Deadline Monotonic in order of increasing relative deadline. When we find 2 tasks Ti and Ti+1 which are such that Di is less than Di+1 but T1 has lower priority than Ti+1 according to this schedule. We switch the priorities of the two tasks and modify the schedule accordingly. After the switch, the priorities of the two tasks are assigned on the Deadline Monotonic basic relative to one another. By repeating this schedule we can transform the given schedule into Deadline Monotonic schedule.

(Visited 669 times, 6 visits today)

Posted By : | Comment RSS | Category : Sixth Semester
Tag :
Community | Toolbar | Android App | Founder/Developer : Hari Prasad Chaudhary | CSIT Portal Manager : Digvijay Chaudhary