Rate-monotonic scheduling

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.

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:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({2}^{1/n}-1)}$

where C_i is the computation time, T_i is the release period (with deadline one period later), 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:

${\displaystyle \lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots }$

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,[3] however this fact depends on knowing the exact task statistics (periods, deadlines) which cannot be guaranteed for all task sets.

The hyperbolic bound[4] is a tighter sufficient condition for schedulability than the one presented by Liu and Layland:

${\displaystyle \prod _{i=1}^{n}(U_{i}+1)\leq 2}$,

where U_i 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.[5] 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.[6]

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.

The utilization will be: ${\displaystyle {\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725}$.

The sufficient condition for ${\displaystyle 3\,}$ processes, under which we can conclude that the system is schedulable is:

$${\displaystyle U=3(2^{\frac {1}{3}}-1)=0.77976>0.693\ldots (0.693{\text{ is utilization bound for RMS for }}n=\infty \ldots )}$$

.

Since ${\displaystyle 0.77976>0.725\ldots }$ the system is schedulable.

For Harmonics task set we can use Ei/Pi <= 1 formula.

• Deos, a time and space partitioned real-time operating system containing a working Rate Monotonic Scheduler.
• Deadline-monotonic scheduling
• Dynamic priority scheduling
• Earliest deadline first scheduling
• RTEMS, an open source real-time operating system containing a working Rate Monotonic Scheduler.
• Scheduling (computing)

• Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, New York, NY: Springer.
• Alan Burns and Andy Wellings (2009), Real-Time Systems and Programming Languages (4th ed.), Addison-Wesley, ISBN 978-0-321-41745-9
• Liu, Jane W.S. (2000), Real-time systems, Upper Saddle River, NJ: Prentice Hall, Chapter 6.
• Joseph, M.; Pandya, P. (1986), "Finding response times in real-time systems", BCS Computer Journal, 29 (5): 390–395, doi:10.1093/comjnl/29.5.390.
• Sha, Lui; Goodenough, John B. (April 1990), "Real-Time Scheduling Theory and Ada", IEEE Computer, 23 (4): 53–62, doi:10.1109/2.55469

• Mars Pathfinder Bug from Research @ Microsoft
• What really happened on Mars Rover Pathfinder by Mike Jones from The Risks Digest, Vol. 19, Issue 49
• The actual reason for the Mars Pathfinder Bug, but those who actually dealt with it, rather than someone whose company and therefore stock value depended upon the description of the problem, or someone who heard someone talking about the problem.