Rate-monotonic scheduling
In computer science, rate-monotonic scheduling is a priority assignment algorithm used in real-time operating systems 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.
These operating systems are generally preemptive and have deterministic guarantees with regard to response times. Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a particular application.
Introduction
A simple version of rate-monotonic analysis assumes that threads have the following properties:- No resource sharing
- Deterministic deadlines are exactly equal to periods
- Static priorities
- Static priorities assigned according to the rate monotonic conventions
- Context switch times and other thread operations are free and have no impact on the model
proved that for a set of periodic tasks with unique periods, a feasible schedule that will always meet deadlines exists if the CPU utilization is below a specific bound. The schedulability test for RMS is:
where is the computation time, is the release period, and is the number of processes to be scheduled. For example, for two processes. When the number of processes tends towards infinity, this expression will tend towards:
Therefore, a rough estimate is that RMS can meet all of the deadlines if CPU utilization is less than 69.32%. The other 30.7% of the CPU can be dedicated to lower-priority non real-time tasks. It is known that a randomly generated periodic task system will meet all deadlines when the utilization is 85% or less, however this fact depends on knowing the exact task statistics which cannot be guaranteed for all task sets.
The hyperbolic bound is a tighter sufficient condition for schedulability than the one presented by Liu and Layland:
where is the CPU utilization for each task.
The rate-monotonic priority assignment is optimal, meaning that if any static-priority scheduling algorithm can meet all the deadlines, then the rate-monotonic algorithm can too. The deadline-monotonic scheduling algorithm is also optimal with equal periods and deadlines, in fact in this case the algorithms are identical; in addition, deadline monotonic scheduling is optimal when deadlines are less than periods. For the task model in which deadlines can be greater than periods, Audsley's algorithm endowed with an exact schedulability test for this model finds an optimal priority assignment.
Avoiding priority inversion
In many practical applications, resources are shared and the unmodified RMS will be subject to priority inversion and deadlock hazards. In practice, this is solved by disabling preemption or by priority inheritance. Alternative methods are to use lock free algorithms or avoid the sharing of a mutex/semaphore across threads with different priorities. This is so that resource conflicts cannot result in the first place.Disabling of preemption
- The
OS_ENTER_CRITICALandOS_EXIT_CRITICALprimitives that lock CPU interrupts in a real-time kernel, e.g. MicroC/OS-II - The
splxfamily of primitives which nest the locking of device interrupts,Priority inheritance
- The basic priority inheritance protocol promotes the priority of the task that holds the resource to the priority of the task that requests that resource at the time the request is made. Upon release of the resource, the original priority level before the promotion is restored. This method does not prevent deadlocks and suffers from chained blocking. That is, if a high priority task accesses multiple shared resources in sequence, it may have to wait on a lower priority task for each of the resources. The to the Linux kernel includes an implementation of this formula.
- The priority ceiling protocol enhances the basic priority inheritance protocol by assigning a ceiling priority to each semaphore, which is the priority of the highest job that will ever access that semaphore. A job cannot preempt a lower priority critical section if its priority is lower than the ceiling priority for that section. This method prevents deadlocks and bounds the blocking time to at most the length of one lower priority critical section. This method can be suboptimal, in that it can cause unnecessary blocking. The priority ceiling protocol is available in the VxWorks real-time kernel. It is also known as Highest Locker's Priority Protocol.
| pessimistic | optimistic | |
| immediate | OS_ENTER_CRITICAL / OS_EXIT_CRITICAL | splx, highest locker |
| lazy | priority ceiling protocol, basic priority inheritance protocol |
In practice there is no mathematical difference between the lazy and immediate algorithms, and the immediate algorithms are more efficient to implement, and so they are the ones used by most practical systems.
An example of usage of basic priority inheritance is related to the "Mars Pathfinder reset bug" which was fixed on Mars by changing the creation flags for the semaphore so as to enable the priority inheritance.
Example
| Process | Execution Time | Period |
| P1 | 1 | 8 |
| P2 | 2 | 5 |
| P3 | 2 | 10 |
The utilization will be:
The sufficient condition for processes, under which we can conclude that the system is schedulable is:
Since so the system is may or may not be schedulable
we need to go for TDA analysis for each task to see if the system is schedulable or not.
For Harmonics task set we can use Ei/Pi < 1 formula