Rate Monotonic Scheduling

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Rate Monotonic Scheduling (deutsch etwa ‚ratenmonotone Einplanung‘; kurz: RMS) ist ein Prioritätsscheduling-Verfahren für unterbrechbare, periodische Jobs und wird häufig in Echtzeitsystemen eingesetzt. Die Prioritäten werden statisch anhand Periodendauer eines Jobs festgelegt: je kürzer die Periodendauer eines Jobs, desto höher ist seine Priorität.

Aperiodische Jobs können mithilfe eines fiktiven periodischen Jobs ausgeführt werden, der diese bei Bedarf ausführt oder andernfalls keine Aktion durchführt. Dieses Technik wird auch als Serverprinzip bezeichnet wird.

Einplanbarkeit[Bearbeiten]

Unter folgenden Bedingungen ist eine Menge von Jobs mittels Rate Monotonic Scheduling garantiert einplanbar:

  • Hinreichende Bedingung nach Liu und Layland: Ist die Auslastung u kleiner oder gleich einer Auslastungsschranke, ist die Job-Menge einplanbar. Die Schranke ist dabei nur von der Anzahl n der Jobs abhängig:
u = \sum\limits_{i=1}^{n}{\frac{C_i}{T_i}} \le n \cdot \left(\sqrt[n]{2} -1\right)
C_i: Ausführungszeiten
T_i: Periodenlängen
n: Anzahl der Jobs
Mit zunehmender Anzahl von Jobs (n \to \infty) nähert sich die Schranke dem Wert ln 2 ≈ 0,693. Wenn also die berechnete Auslastung u unter 69,3 % liegt, sind alle Jobs sicher einplanbar. Wenn die tatsächliche Auslastung größer als n \cdot \left(\sqrt[n]{2} -1\right) ist, kann aber trotzdem ein Ablaufplan unter RMS existieren, mit dem kein Job seine Deadline verletzt.
  • Harmonische Periodendauern. Wenn die Periodendauern Vielfache voneinander sind (harmonisch), sind die Jobs einplanbar, falls u \le 1. Unter dieser Bedingung ist RMS also optimal.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

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