Product Design, Manufacturing & Innovation Resources
Heim » Rate-Monotonic Scheduling (RMS)

Rate-Monotonic Scheduling (RMS)

1973
  • C. L. Liu
  • James Layland
Computerarbeitsplatz in einem Kontrollraum zur Analyse der ratenmonotonen Terminplanung für Echtzeitsysteme.

(Abbildung dient nur zur Veranschaulichung)

Rate-Monotonic Scheduling (RMS) ist ein statischer Prioritätsplanungsalgorithmus für periodische Aufgaben in Echtzeitsystemen. Er weist Aufgaben Prioritäten basierend auf ihrer Häufigkeit zu: Je kürzer die Periode einer Aufgabe (und damit ihre Rate), desto höher ihre Priorität. RMS ist ein optimaler statischer Prioritätsplanungsalgorithmus; das heißt, wenn ein beliebiger statischer Prioritätsplanungsalgorithmus eine Aufgabenmenge planen kann, kann dies auch RMS. Die Planbarkeit lässt sich mithilfe eines Auslastungstests überprüfen.

Rate-Monotonic Scheduling (RMS) ist ein Eckpfeiler der Echtzeitsystemtheorie und wurde 1973 in einer wegweisenden Arbeit von Liu und Layland eingeführt. Es bietet eine einfache, aber leistungsstarke Methode zur Planung einer Menge unabhängiger, unterbrechbarer, periodischer Aufgaben auf einem einzelnen Prozessor. Das Kernprinzip besteht darin, jeder Aufgabe eine feste Priorität zuzuweisen, die umgekehrt proportional zu ihrer Periode ist. Eine Aufgabe, die alle 10 ms ausgeführt werden muss, hat eine höhere Priorität als eine Aufgabe, die alle 100 ms ausgeführt wird.

Die Bedeutung von RMS liegt in seiner Optimalität und der Existenz eines einfachen Planbarkeitstests. Es ist erwiesen, dass es sich um eine optimale statische Prioritätsplanungsstrategie handelt. Das bedeutet: Wenn eine Menge von Aufgaben mit einem beliebigen statischen Prioritätsalgorithmus geplant werden kann, kann sie auch mit RMS geplant werden. Die Planbarkeit einer Aufgabenmenge unter RMS kann mithilfe eines Auslastungsgrenztests bestimmt werden. Für eine Menge von n Aufgaben ist die gesamte Prozessorauslastung U die Summe der Ausführungszeit Ci geteilt durch die Periode Ti für jede Aufgabe i: U = ∑i=1n Ci/Ti. Liu und Layland bewiesen, dass die Aufgabenmenge garantiert planbar ist (d. h., es werden keine Fristen verpasst), wenn die Gesamtauslastung kleiner oder gleich einer bestimmten Schranke ist: U ≤ n(2^{1/n}-1). Für n → ∞ konvergiert diese Schranke gegen ln(2) ≈ 0,693. Dies ist eine hinreichende, aber nicht notwendige Bedingung für Planbarkeit. Alternativ kann ein präziserer, aber komplexerer Test, die sogenannte exakte Analyse oder Antwortzeitanalyse, verwendet werden.

UNESCO Nomenclature: 1203
- Computerwissenschaften

Typ

Software/Algorithmus

Störung

Inkremental

Verwendung

Weitverbreitete Verwendung

Vorläufer

  • Warteschlangentheorie
  • Operationsforschung
  • frühe Arbeiten zu Computer-Scheduling-Algorithmen
  • Entwicklung von Time-Sharing-Betriebssystemen

Anwendungen

  • Satellitensteuerungssysteme
  • Anwendungen zur Fahrzeugsteuerung
  • Avionik- und Flugsteuerungssysteme
  • Industrieautomation und Robotik
  • Echtzeit-Signalverarbeitung

Patente:

NA

Potenzielle Innovationsideen

Aufgrund des hohen Datenverkehrs durch Web-Scraping-Bots, der derzeit mehr als 40.000 Anfragen pro Tag umfasst, ist dieser Inhalt ausschließlich Community-Mitgliedern vorbehalten.
> Anmelden < oder > Registrieren < (100% kostenlos) Zugriff darauf sowie auf alle anderen eingeschränkten Inhalte und Tools.

Verwandt mit: Rate-Monotonic Scheduling, RMS, Echtzeitsysteme, Scheduling-Algorithmus, statische Priorität, periodische Aufgaben, Planbarkeitsanalyse, Auslastungsgrenze, Liu und Layland, optimales Scheduling.

Historischer Kontext

Rate-Monotonic Scheduling (RMS)

1970
1970
1970
1973
1980
1980
1980
1970
1970
1970
1970-01-01
1975-06-01
1980
1980
1980

(wenn das Datum unbekannt oder nicht relevant ist, z. B. „Strömungsmechanik“, wird eine gerundete Schätzung seines bemerkenswerten Auftretens bereitgestellt)

Bilder in voller Größe und Downloads sind nur für registrierte Mitglieder 100% kostenlos verfügbar.

> Login <