In computer science, rate-monotonic scheduling (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. 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 (processes do not share resources, e.g. a hardware resource, a queue, or any kind of semaphore blocking or non-blocking (busy-waits)) Deterministic deadlines are exactly equal to periods Static priorities (the task with the highest static priority that is runnable immediately preempts all other tasks) Static priorities assigned according to the rate monotonic conventions (tasks with shorter periods/deadlines are given higher priorities) Context switch times and other thread operations are free and have no impact on the model 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.
Optimality The rate-monotonic priority assignment is optimal under the given assumptions, 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.
Upper bounds on utilization
Least upper bound 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). The schedulability test for RMS is:
U = ∑ i = 1 n U i = ∑ i = 1 n C i T i ≤ n ( 2 1 / n − 1 ) {\displaystyle U=\sum _{i=1}^{n}{U_{i}}=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({2}^{1/n}-1)}
where U is the utilization factor, Ci is the computation time for process i, Ti is the release period (with deadline one period later) for process i, and n is the number of processes to be scheduled. For example, U ≤ 0.8284 for two processes. When the number of processes tends towards infinity, this expression will tend towards:
lim n → ∞ n ( 2 n − 1 ) = ln 2 ≈ 0.693147 … {\displaystyle \lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots }
Therefore, a rough estimate when n ≥ 10 {\displaystyle {n}\geq {10}} is that RMS can meet all of the deadlines if total CPU utilization, U, is less than 70%. The other 30% of the CPU can be dedicated to lower-priority, non-real-time tasks. For smaller values of n or in cases where U is close to this estimate, the calculated utilization bound should be used. In practice, for the i t h {\displaystyle {i^{th}}} process, C i {\displaystyle {C_{i}}} should represent the worst-case (i.e. longest) computation time and T i {\displaystyle {T_{i}}} should represent the worst-case deadline (i.e. shortest period) in which all processing must occur.
Relationship to queueing theory In queueing theory, Ti is called the interarrival time, and Ci is called the service time. These two parameters are often specified as rates:
λ i = 1 T i {\displaystyle \lambda _{i}={1 \over T_{i}}} is the arrival rate, and
μ i = 1 C i {\displaystyle \mu _{i}={1 \over C_{i}}} is the service rate. The utilization for each task, denoted ρi, is then:
… excerpt ends here. Continue reading the full article.
