Editing Rate-monotonic scheduling (section)

== Upper bounds on utilization ==

=== Least upper bound ===
{{harvtxt|Liu|Layland|1973}} proved that for a set of {{mvar|n}} periodic tasks with unique periods, a feasible schedule that will always meet deadlines exists if the [[Central processing unit|CPU]] utilization is below a specific bound (depending on the number of tasks). The schedulability test for RMS is:

:<math>U = \sum_{i=1}^{n} {U_i} = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n({2}^{1/n} - 1)</math>

where {{mvar|U}} is the utilization factor, {{mvar|C<sub>i</sub>}} is the computation time for process {{mvar|i}}, {{mvar|T<sub>i</sub>}} is the release period (with deadline one period later) for process {{mvar|i}}, and {{mvar|n}} is the number of processes to be scheduled. For example, {{mvar|U&nbsp;≤&nbsp;0.8284}} for two processes. When the number of processes tends towards [[infinity]], this expression will tend towards:

:<math>\lim_{n \rightarrow \infty} n(\sqrt[n]{2} - 1) = \ln 2 \approx 0.693147\ldots</math>

Therefore, a rough estimate when <math>{n} \geq {10}</math> is that RMS can meet all of the deadlines if total CPU utilization, {{mvar|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 {{mvar|n}} or in cases where {{mvar|U}} is close to this estimate, the calculated utilization bound should be used.

In practice, for the <math>{i^{th}}</math> process, <math>{C_i}</math> should represent the worst-case (i.e. longest) computation time and <math>{T_i}</math> should represent the worst-case deadline (i.e. shortest period) in which all processing must occur.

=== Relationship to queueing theory ===
In [[queueing theory]], {{mvar|T<sub>i</sub>}} is called the '''interarrival time''', and {{mvar|C<sub>i</sub>}} is called the ''' service time'''.  These two parameters are often specified as rates:
:<math>\lambda_i = { 1 \over T_i } </math> is the '''arrival rate''', and
:<math>\mu_i = { 1 \over C_i } </math> is the '''service rate'''.

The utilization for each task, denoted {{mvar|&rho;<sub>i</sub>}}, is then:
:<math> \rho_i = { \lambda_i \over \mu_i } = { C_i \over T_i } = U_i</math>
as above.

=== Upper bound for harmonic task sets ===

Liu and Layland noted that this bound may be relaxed to the maximum possible value of 1.0, if for tasks <math>{T_m}</math>, <math>{T_i}</math> where <math>{T_m} {>} {T_i}</math> and <math>i = 1...m-1</math>, <math>{T_m}</math> is an integer multiple of <math>{T_i}</math>, which is to say that all tasks have a period that is not just a multiple of the shortest period, <math>{T_1}</math>, but instead that any task's period is a multiple of all shorter periods.  This is known as an [[Harmonic Task Set|harmonic task set]].  An example of this would be:  <math>[{T_1},{T_2},{T_3},{T_4}] = [1, 3, 6, 12]</math>.  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.

=== Generalization to harmonic chains ===

Kuo and Mok<ref>{{cite book|author=T.-W. Kuo |author2=A.K. Mok |title=&#91;1991&#93; Proceedings Twelfth Real-Time Systems Symposium |chapter=Load adjustment in adaptive real-time systems |year=1991|pages=160–170|doi=10.1109/REAL.1991.160369|isbn=0-8186-2450-7|s2cid=31127772}}</ref> showed that for a task set made up of {{mvar|K}} harmonic task subsets (known as ''harmonic chains''), the least upper bound test becomes:
:<math>U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq K({2}^{1/K} - 1)</math>
In the instance where for each task, its period is an exact multiple of every other task that has a shorter period, the task set can be thought of as being composed of {{mvar|n}} harmonic task subsets of size 1 and therefore <math>{K}{=}{n}</math>, which makes this generalization equivalent to Liu and Layland's least upper bound.  When <math>{K}{=}{1}</math>, the upper bound becomes 1.0, representing full utilization.

=== Stochastic bounds ===

It has been shown that a randomly generated periodic task system will usually meet all deadlines when the utilization is 88% or less,<ref>{{citation|first1=J.|last1=Lehoczky|first2=L.|last2=Sha|first3=Y.|last3=Ding|contribution=The rate monotonic scheduling algorithm: exact characterization and average case behavior|title=IEEE Real-Time Systems Symposium|pages=166–171|year=1989|doi=10.1109/REAL.1989.63567|isbn=978-0-8186-2004-1|s2cid=206524469}}.</ref> 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.

=== Hyperbolic bound ===
The hyperbolic bound<ref>{{citation|author1=Enrico Bini |author2=Giorgio C. Buttazzo |author3=Giuseppe M. Buttazzo |title=Rate Monotonic Analysis: the Hyperbolic Bound|journal=IEEE Transactions on Computers|year=2003|volume=52|issue=7|pages=933–942|doi=10.1109/TC.2003.1214341|hdl=11382/200358|hdl-access=free}}</ref> is a tighter sufficient condition for schedulability than the one presented by Liu and Layland:
:<math>\prod_{i=1}^n (U_i +1) \leq 2</math>,
where {{mvar|U<sub>i</sub>}} is the CPU utilization for each task.  It is the tightest upper bound that can be found using only the individual task utilization factors.