Rate Monotonic Scheduling

Rate-monotonic scheduling (German about, advise monotonic scheduling 'in short, RMS ) is a priority scheduling method for interruptible, periodic jobs and is often in real-time systems used. The priorities are statically determined based on the period duration of a job: the shorter the period duration of a job, the higher its priority.

Aperiodic jobs can be run using a fictitious periodic job that runs them when needed or takes no action otherwise. This technique is also known as the server principle.

Can be planned

A number of jobs can be guaranteed to be scheduled using Rate Monotonic Scheduling under the following conditions:

• Sufficient condition according to Liu and Layland : If the workload isless than or equal to a workload limit, the number of jobs can be planned. The limit onlydepends onthe numberof jobs: ${\displaystyle u}$ ${\displaystyle n}$

${\displaystyle u=\sum \limits _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n\cdot \left({\sqrt[{n}]{2}}-1\right)}$

${\displaystyle C_{i}}$: Execution times

${\displaystyle T_{i}}$: Period lengths

${\displaystyle n}$: Number of jobs

As the number of jobs ( ) increases, the limit approaches the value ln 2 ≈ 0.693. So if the calculated utilization is below 69.3%, all jobs can be safely scheduled. If the actual workload is greater than , however, a schedule can still exist under RMS with which no job violates its deadline. ${\displaystyle n\to \infty }$ ${\displaystyle u}$ ${\displaystyle n\cdot \left({\sqrt[{n}]{2}}-1\right)}$

• Harmonic periods . If the period durations are multiples of each other (harmonic), the jobs can be scheduled, if . So RMS is optimal under this condition. ${\displaystyle u\leq 1}$

See also

• Deadline Monotonic Scheduling
• Earliest Deadline First

literature

• Liu, Jane WS: Real-time systems. Prentice Hall, Upper Saddle River, NJ, 2000