Editing Rate-monotonic scheduling (section)

=== 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.