Rate Monotonic (RM) Scheduling Algorithm

Rate-Monotonic (RM) is a well-known real-time scheduling algorithm used in real-time operating systems (RTOS) to schedule tasks with fixed or periodic deadlines. RM is a priority-based scheduling algorithm, where each task is assigned a priority based on its period: shorter periods result in higher priorities. The RM scheduling algorithm operates under the following principles:

The Rate Monotonic scheduling algorithm is a simple rule that assigns priorities to different tasks according to their time period. That is, a task with the smallest time period will have the highest priority, and a task with the longest time period will have the lowest priority for execution. As the time period of a task does not change, neither does its priority change over time. Therefore, Rate Monotonic is a fixed priority algorithm. The priorities are decided before the start of execution and they do not change over time.

Rate Monotonic (RM) Scheduling Algorithm Introduction

Rate monotonic scheduling algorithm works on the principle of preemption. Preemption occurs on a given processor when a higher priority task blocks a lower priority task from execution. This blocking occurs due to the priority level of different tasks in a given task set. Rate monotonic is a preemptive algorithm, which means if a task with a shorter period comes during execution, it will gain higher priority and can block or preempt currently running tasks. In RM, priorities are assigned according to the time period. The priority of a task is inversely proportional to its timer period. The task with the lowest time period has the highest priority, and the task with the highest period will have the lowest priority. A given task is scheduled under the rate monotonic scheduling algorithm if it satisfies the following equation:

where n is the number of tasks in a task set.

Example of RATE MONOTONIC (RM) SCHEDULING ALGORITHM

For example, we have a task set that consists of three tasks as follows

Table 1. Task set

U= 0.5/3 +1/4 +2/6 = 0.167+ 0.25 + 0.333 = 0.75

As processor utilization is less than 1 or 100% so task set is schedulable and it also satisfies the above equation of rate monotonic scheduling algorithm.

Figure 1. RM scheduling of Task set in table 1.

A task set given in table 1 it RM scheduling is given in figure 1. The explanation of above is as follows

1. According to RM scheduling algorithm task with shorter period has higher priority so T1 has high priority, T2 has intermediate priority and T3 has lowest priority. At t=0 all the tasks are released. Now T1 has highest priority so it executes first till t=0.5.
2. At t=0.5 task T2 has higher priority than T3 so it executes first for one-time units till t=1.5. After its completion only one task is remained in the system that is T3, so it starts its execution and executes till t=3.
3. At t=3 T1 releases, as it has higher priority than T3 so it preempts or blocks T3 and starts it execution till t=3.5. After that the remaining part of T3 executes.
4. At t=4 T2 releases and completes it execution as there is no task running in the system at this time.
5. At t=6 both T1 and T3 are released at the same time but T1 has higher priority due to shorter period so it preempts T3 and executes till t=6.5, after that T3 starts running and executes till t=8.
6. At t=8 T2 with higher priority than T3 releases so it preempts T3 and starts its execution.
7. At t=9 T1 is released again and it preempts T3 and executes first and at t=9.5 T3 executes its remaining part. Similarly, the execution goes on.

Rate Monotonic Features and Limitations

Rate-Monotonic Scheduling has certain key characteristics and limitations:

Priority Inversion: RM can suffer from priority inversion issues, where lower-priority tasks holding shared resources can block higher-priority tasks, leading to missed deadlines. This issue can be mitigated by using techniques like priority inheritance or priority ceiling protocols.

Utilization Bound: There is an upper bound on the total CPU utilization for RM to guarantee that all tasks meet their deadlines. This bound is approximately 69%, meaning that the sum of the CPU requirements of all tasks should be less than or equal to 69% of the total CPU capacity.

Feasibility Test: To determine whether a set of tasks can be scheduled using RM, you can use the RM feasibility test, which calculates the worst-case CPU utilization of the tasks and compares it to the utilization bound.

In summary, the Rate-Monotonic scheduling algorithm is a straightforward and efficient scheduling scheme for real-time systems, especially when task periods are known and predictable. However, it may not be suitable for more complex systems with dynamic priorities or where priority inversion can be a problem. In such cases, other scheduling algorithms like Earliest Deadline First (EDF) or Priority Inheritance Protocol may be more appropriate.

You may also like to read:

• EARLIEST DEADLINE FIRST (EDF) SCHEDULING ALGORITHM
• LEAST LAXITY FIRST (LLF) SCHEDULING ALGORITHM