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:
-
- : Execution times
- : Period lengths
- : 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.
- 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.
See also
literature
- Liu, Jane WS: Real-time systems. Prentice Hall, Upper Saddle River, NJ, 2000