## 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 T_{1}=(4,1), T_{2}=(5,2) and T_{3}=(20,5)

- Priority of T
_{1}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.
- T
_{2}has the next priority. The execution of 1^{st}job in T2 is delayed until the 1^{st}job in T_{1}completes and 4^{th}job in T_{2}is preempted at time 16 when the 5^{th}job in T_{1}is released. - Jobs in T
_{3}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 T_{i} misses a deadline for the first time at t.

T is an integer multiple of p_{i} because tasks are simply periodic, t is also an integer multiple of the period p_{k} of every higher priority task T_{k} 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 which is equal to t times the total utilization of the highest priority tasks. That T_{i} misses a deadline at t means that this demand for time exceeds t. i.e; U_{i}>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 T_{1}=(50, 50, 25, 100), T_{2}=(0, 62.5, 10, 20), T_{3}=(0, 125, 25, 50)

- T
_{2}has the highest priority because the relative deadline 20 is the shortest among the tasks. - T
_{1}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 T_{i} and T_{i+1} which are such that D_{i} is less than D_{i+1} but T_{1} has lower priority than T_{i+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.