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.

The significance of RMS lies in its optimality and the existence of a simple schedulability test. It is proven to be an optimal static-priority scheduling policy. This means that if a set of tasks can be scheduled by any static-priority algorithm, it can also be scheduled by RMS. The schedulability of a task set under RMS can be determined using a utilization bound test. For a set of ‘n’ tasks, the total processor utilization ‘U’ is the sum of the execution time [latex]C_i[/latex] divided by the period [latex]T_i[/latex] for each task ‘i’: [latex]U = \sum_{i=1}^{n} \frac{C_i}{T_i}[/latex]. Liu and Layland proved that if this total utilization is less than or equal to a specific bound, [latex]U \le n(2^{1/n}-1)[/latex], then the task set is guaranteed to be schedulable (i.e., no deadlines will be missed). As ‘n’ approaches infinity, this bound converges to [latex]\ln(2) \approx 0.693[/latex]. This provides a sufficient, but not necessary, condition for schedulability. A more precise but complex test, called exact analysis or response time analysis, can also be used.

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)

Verwandte Erfindungen, Innovationen und technische Prinzipien

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

> Login <