Table of Contents
Rate-monotonic scheduling algorithm (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority.
Some of the scheduling strategies, like round-robin or time-sharing presented a means of scheduling but did not give any information on whether the deadlines would actually be met.
Rate Monotonic Scheduling Algorithm:
Rate Monotonic analysis addresses how to determine whether a group of tasks, whose individual CPU utilization is known, will meet their deadlines. This approach assumes a priority preemption scheduling algorithm. The approach also assumes independent tasks. (no communication or synchronization). It can be stated as follows –
Given a set of periodic tasks and preemptive priority scheduling, then
assigning priorities such that the tasks with shorter periods have higher
priorities (rate-monotonic), yields an optimal scheduling algorithm.
In this discussion, each task discussed has the following properties:
- Each task is a periodic task which has a period P, which is the frequency with which it executes.
- An execution time E, which is the CPU time required during the period.
- A utilization U, which is the ratio E/P.
A task is schedulable if all its deadlines are met (i.e., the task completes its execution before its period elapses.) A group of tasks is considered to be schedulable if each task can meet its deadlines.
Rate monotonic analysis (RMA) is a mathematical solution to the scheduling problem for periodic tasks with known cost. The assumption with the RMA approach is that the total utilization must always be less than or equal to 100%.
In Simple terms:
The rate-monotonic scheduling algorithm schedules periodic processes using a static priority policy with preemption. Here each periodic process is assigned a priority based on its period. Shorter period has higher priority and longer period processes have lower priority.
If a lower-priority process is running and a higher-priority process becomes available to run, it will preempt the lower-priority process. The logic behind this policy is to assign a higher priority to tasks that require the CPU more often.
Period: Processes always occur at regular intervals of time which is called period.
Deadline: The time by which operation of the process must complete.
Execution time: Time required to execute the process i.e. CPU time.
The RMS algorithm generally assumes that the Period of a task is it’s deadline. In other words, a task must finish execution before the next period starts.
The theory underlying RMS is known as rate-monotonic analysis (RMA). This theory, as summarized below, uses a relatively simple model of the system.
- All processes run periodically on a single CPU.
- Context switching time is ignored.
- There are no data dependencies between processes.
- The execution time for a process is constant.
- All deadlines are at the ends of their periods.
- The highest-priority ready process is always selected for execution.
Example:
Rate-Monotonic Scheduling
| Process | Execution time(E) | Period (P) |
|---|---|---|
| P1 | 1 | 4 |
| P2 | 2 | 6 |
| P3 | 3 | 12 |
Here, P1 has the shortest period and P3 has the longest period. Applying the principles of RMA, we give P1 the highest priority, P2 the middle priority, and P3 the lowest priority.
P1->P2->P3
P1 will execute once every 4 time units. The time units may be milli seconds or microseconds or even seconds. And it will execute for 1 time unit
P2 will execute once every 6 time units and it will execute for a total of 2 time units.
P3 will execute once every 12 time units and it will execute for a total of 3 time units.
To understand all the interactions between the periods, we need to construct a timeline equal in length to the least-common multiple of the process periods, which is 12 in this case. The complete schedule for the least-common multiple of the periods is called the unrolled schedule. or the hyper-period.
hyper period = LCM of the periods of P1, P2 and P3 = LCM(4,6,12) = 12
It means, in 12 time units, P1 will execute 3 times, P2 will execute 2 times and P3 will execute 1 time.
Time unit 1 (0-1):
Since P1 has the highest priority, P1 executes first. The execution time for P1 is 1 time unit.
Time unit 2 and 3 (1-2-3):
The execution time pf P1 was 1 time unit and it has finished it’s execution. Therefore the next process can execute now. The next in the priority list is P2. The execution time of P2 is 2 time units.
Time Unit 4 (3-4):
P1 and P2 have finished their executions and now P3 can execute. But there is something interesting that happens here. P3 will not execute for 3 time units. It will execute for only 1 time unit. We will soon see why.
Time Unit 5 (4-5):
Normally, we think P3 should have continued it’s execution. However, the period(4) for P1 has passed and it is now time for P1 to execute again. P1 should execute once every 4 time units. P1 could have started after p3 completed execution. But according to RMA, P1 has higher priority. Therefore, P1 pre-empts (or interrupts) the execution of P3.
This time slot is now alotted to P1.
Time Unit 6 (5-6):
After P1 finishes execution, there is no other high-prio task pending execution. P2 has a higher priority than P3 but the period for P2 has not expired. P2 must execute once every 6 time units. It has already done that in the time units 2-3.
P3’s execution is pending. It requires 3 time units but could execute for only one time unit. Thus P3 executes now.
Time Unit 7 and 8 (6-7-8):
6 time units have elapsed and it is now time for P2 to execute. Since P2 has more priority than P3, P2 will pre-empt P3 and execute.
Time Unit 9 (8-9):
8 time units are over and it is once again time for P1 to execute. Since P1 has the highest priority, P1 will get executed, irrespective of the completion status of the other processes.
Time Unit 10 (9-10):
Remember from time unit 6, P3 still has work pending for one time unit. P1 and P2 have higher priorities than P3 but their executions are not pending. Thus this time slot can be allocated to P3.
CPU Utilization
At this point, we have reached the end of the schedule. We have used 10 time slots out of the available 12 time slots from the hyper period. During this empty time slots, the CPU remains idle.
We can also calculate the CPU utilization from this. The CPU is utilized for 10 slots out of 12. Thus
CPU Utilization = 10/12 = 83.33%
The same can be calculated with the following formula:
Therefore,
U = (1/4) + (2/6) + (3/12)
U = 83.33%
Rate Monotonic Scheduling Condition
A task is schedulable if all its deadlines are met (i.e., the task completes its execution before its period elapses.) A group of tasks is considered to be schedulable if each task can meet its deadlines.
Rate monotonic analysis (RMA) is a mathematical solution to the scheduling problem for periodic tasks with known cost. The assumption with the RMA approach is that the total utilization must always be less than or equal to 100%.
Vivek is a Senior Embedded Innovation Specialist. He has been working on Embedded Systems for the past 10 years. He loves to share his knowledge and train those who are interested. Nerdyelectronics.com was started out of this interest.
