In computer science, rate-monotonic scheduling (RMS)[1] is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class.
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.
A simple version of rate-monotonic analysis assumes that threads have the following properties: It is a mathematical model that contains a calculated simulation of periods in a closed system, where round-robin and time-sharing schedulers fail to meet the scheduling needs otherwise.
Rate monotonic scheduling looks at a run modeling of all threads in the system and determines how much time is needed to meet the guarantees for the set of threads in question.
[3] 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.
[4] Liu & Layland (1973) proved that for a set of n periodic tasks with unique periods, a feasible schedule that will always meet deadlines exists if the CPU utilization is below a specific bound (depending on the number of tasks).
For smaller values of n or in cases where U is close to this estimate, the calculated utilization bound should be used.
should represent the worst-case deadline (i.e. shortest period) in which all processing must occur.
Liu and Layland noted that this bound may be relaxed to the maximum possible value of 1.0, if for tasks
It is acknowledged by Liu and Layland that it is not always feasible to have a harmonic task set and that in practice other mitigation measures, such as buffering for tasks with soft-time deadlines or using a dynamic priority assignment approach may be used instead to allow for a higher bound.
, which makes this generalization equivalent to Liu and Layland's least upper bound.
It has been shown that a randomly generated periodic task system will usually meet all deadlines when the utilization is 88% or less,[6] however this fact depends on knowing the exact task statistics (periods, deadlines) which cannot be guaranteed for all task sets, and in some cases the authors found that the utilization reached the least upper bound presented by Liu and Layland.
The hyperbolic bound[7] is a tighter sufficient condition for schedulability than the one presented by Liu and Layland: where Ui is the CPU utilization for each task.
It is the tightest upper bound that can be found using only the individual task utilization factors.
In many practical applications, resources are shared and the unmodified RMS will be subject to priority inversion and deadlock hazards.
Alternative methods are to use lock-free algorithms or avoid the sharing of a mutex/semaphore across threads with different priorities.
Second is the inheritance optimistic (boost a minimum amount) or pessimistic (boost by more than the minimum amount): In practice there is no mathematical difference (in terms of the Liu-Layland system utilization bound) 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.
[citation needed] An example of usage of basic priority inheritance is related to the "Mars Pathfinder reset bug" [13][14] which was fixed on Mars by changing the creation flags for the semaphore so as to enable the priority inheritance.
All interrupt service routines (ISRs), whether they have a hard real-time deadline or not should be included in RMS analysis to determine schedulability in cases where ISRs have priorities above all scheduler-controlled tasks.
However, an ISR with a period/deadline longer than any non-ISR process period with a critical deadline results in a violation of RMS and prevents the use of the calculated bounds for determining schedulability of a task set.
Imposing this shorter period results in prioritization that conforms to RMS, but also results in a higher utilization factor for the ISR and therefore for the total utilization factor, which may still be below the allowable bound and therefore schedulability can be proven.
of 1 millisecond, then the ISR would have a higher priority, but a lower rate, which violates RMS.
When determining schedulability, a margin of CPU utilization due to ISR activity should be subtracted from the least upper bound.
, and because being below the Least Upper Bound is a sufficient condition, the system is guaranteed to be schedulable.
processes, under which we can conclude that the task set is schedulable, remains: The total utilization will be: Since
, the system is determined not to be guaranteed to be schedulable by the Liu and Layland bound.
Using the tighter Hyperbolic bound as follows: it is found that the task set is schedulable.
processes, under which we can conclude that the task set is schedulable, remains: The total utilization will be: Since
, the system is determined not to be guaranteed to be schedulable by the Liu and Layland bound.