Rate-Monotonic-Scheduling (RMS) ist ein statisches Prioritätsverfahren für periodische Echtzeit-Aufgaben. Die Grundidee ist simpel: Je kürzer die Periode einer Aufgabe ist (je schneller sie wiederholt wird), desto höher bekommt sie die Priorität. Das Verfahren wurde 1973 von Chung Laung Liu und James Layland bewiesen und ist bis heute ein Standard in der Echtzeit-Ablaufplanung.
Die Prioritätsregel
Jede periodische Aufgabe hat eine Periode T (wie oft sie startet) und eine Worst-Case-Ausführungszeit C (wie lange sie pro Zyklus maximal braucht). RMS vergibt die Prioritäten nach der Rate, also der Wiederholfrequenz: Eine Aufgabe mit Periode 10 ms bekommt eine höhere Priorität als eine mit Periode 50 ms. Die Zuordnung geschieht einmalig zur Entwurfszeit und bleibt dann unverändert.
Der Liu-Layland-Bound
Liu und Layland bewiesen eine Schedulability-Bedingung: Eine Menge aus n periodischen Aufgaben ist unter RMS garantiert planbar, wenn die Summe der Auslastungen n·(2^(1/n) − 1) nicht überschreitet. Für sehr viele Aufgaben nähert sich diese Grenze dem Wert ln 2 ≈ 69,3 % an. Liegt die Gesamtauslastung darüber, kann man nicht mehr pauschal garantieren, dass alle Fristen eingehalten werden.
Stärken und Grenzen
RMS ist optimal unter allen statischen Prioritätsverfahren für präemptive Einprozessor-Systeme mit impliziten Deadlines und leicht implementierbar. Nachteile sind das Starvation-Risiko für Aufgaben mit langer Periode, die Anfälligkeit für Prioritätsinversion und die Tatsache, dass aperiodische Ereignisse schlecht abgedeckt werden. Im direkten Vergleich verbraucht das dynamische EDF-Verfahren die Prozessorzeit im theoretischen Fall vollständiger, ist aber schwerer vorhersagbar, wenn das System überlastet ist.
Verwandte Grundlagen: Scheduler, Preemption, Zeitscheibe, Prozess-Scheduling.